An efficient algorithm for sorting by block-interchanges and its application to the evolution of vibrio species

Ying Chih Lin, Chin Lung Lu*, Hwan You Chang, Chuan Yi Tang

*此作品的通信作者

研究成果: 期刊稿件文章同行評審

48 引文 斯高帕斯(Scopus)

摘要

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 script O sign(δn) time algorithm for solving it by making use of permutation groups in algebra, where n is the length of the circular chromosome and S is the minimum number of block-interchanges required for the transformation, which can be calculated in script O sign(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.

原文英語
頁(從 - 到)102-112
頁數11
期刊Journal of Computational Biology
12
發行號1
DOIs
出版狀態已出版 - 2005
對外發佈

指紋

深入研究「An efficient algorithm for sorting by block-interchanges and its application to the evolution of vibrio species」主題。共同形成了獨特的指紋。

引用此