DocumentCode :
3231151
Title :
A translocation, insertion and deletion distance formula for sorting genomes
Author :
Hao Fanchang ; Luan Junfeng ; Zhu Daming ; Feng Haodi
Author_Institution :
Sch. of Comput. Sci. & Technol., Shandong Univ., Jinan, China
fYear :
2009
fDate :
25-28 July 2009
Firstpage :
1843
Lastpage :
1846
Abstract :
Sorting genomes by translocation, insertion and deletions has already been researched for years such as in. However, the authors in 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, 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.
Keywords :
bioinformatics; genetics; genomics; molecular biophysics; deletion distance formula; gene insertion; gene translocation; genome sorting; polynomial time; Algorithm design and analysis; Bioinformatics; Biological cells; Computer science; Computer science education; Educational technology; Error correction; Genomics; Polynomials; Sorting; deletion; distance formula; insertion; sorting genomes; translocation;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Computer Science & Education, 2009. ICCSE '09. 4th International Conference on
Conference_Location :
Nanning
Print_ISBN :
978-1-4244-3520-3
Electronic_ISBN :
978-1-4244-3521-0
Type :
conf
DOI :
10.1109/ICCSE.2009.5228260
Filename :
5228260
Link To Document :
بازگشت