標題: An efficient algorithm for sorting by block-interchanges and its application to the evolution of vibrio species
作者: Lin, YC
Lu, CL
Chang, HY
Tang, CY
生物科技學系
Department of Biological Science and Technology
關鍵字: genome rearrangement;sorting by block-interchanges;sorting by transpositions;permutation group;vibrio genomes
公開日期: 2005
摘要: In the study of genome rearrangement, the block-interchanges have been proposed recently as a new kind of global rearrangement events affecting a genome by swapping two nonintersecting segments of any length. The so-called block-interchange distance problem, which is equivalent to the sorting by block-interchange problem, is to find a minimum series of block-interchanges for transforming one chromosome into another. In this paper, we study this problem by considering the circular chromosomes and propose a O(deltan) time algorithm for solving it by making use of permutation groups in algebra, where n is the length of the circular chromosome and 3 is the minimum number of block-interchanges required for the transformation, which can be calculated in O(n) time in advance. Moreover, we obtain analogous results by extending our algorithm to linear chromosomes. Finally, we have implemented our algorithm and applied it to the circular genomic sequences of three human vibrio pathogens for predicting their evolutionary relationships. Consequently, our experimental results coincide with the previous ones obtained by others using a different comparative genomics approach, which implies that the block-interchange events seem to play a significant role in the evolution of vibrio species.
URI: http://hdl.handle.net/11536/25456
http://dx.doi.org/10.1089/cmb.2005.12.102
ISSN: 1066-5277
DOI: 10.1089/cmb.2005.12.102
期刊: JOURNAL OF COMPUTATIONAL BIOLOGY
Volume: 12
Issue: 1
起始頁: 102
結束頁: 112
Appears in Collections:Articles


Files in This Item:

  1. 000226864700007.pdf