A Translocation, Insertion and Deletion Distance Formula for Sorting Genomes

摘要

Sorting genomes by translocation, insertion and deletions has already been researched for years such as in [1, 2]. However, the authors in [1] did not consider the case that a gene in the target genome does not appear in the source genome. Translocation is a reciprocal operation in sorting genomes, and deletion and insertion are reciprocal to each other. In this paper, we first correct an error in the algorithm in [2], and then propose an algorithm to sort the genomes with different genes using translocation, insertion and deletion in polynomial time O(n3). We also analyze the distance between the original genome and sorted genome.