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.
sorting genomes translocation insertion deletion distance formula
HAO Fanchang LUAN Junfeng ZHU Daming FENG Haodi
School of Computer Science and Technology Shandong University, Jinan, P.R.China
国际会议
第四届国际计算机新科技与教育学术会议(2009 4th International Conference on Computer Science & Education)
南京
英文
1843-1846
2009-07-25（万方平台首次上网日期，不代表论文的发表时间）