SORTING GENOMES BY TRANSLOCATIONS AND DELETIONS

Xingqin Qi*, Guojun Li, Shuguang Li, Ying Xu

Department of Applied Mathematics, Shandong University at Weihai, Weihai, 264213, China. qixingqin@163.com

Comput Syst Bioinformatics Conf. August, 2006. Vol. 5, p. 157-166. Full-Text PDF

*To whom correspondence should be addressed.

Given two signed multi-chromosomal genomes Π and Γ with the same gene set, the problem of sorting by translocations (SBT) is to find a shortest sequence of translocations transforming Π to Γ, where the length of the sequence is called the translocation distance between Π and Γ. In 1996, Hannenhalli gave the formula of the translocation distance for the first time, based on which an O(n