TY - JOUR
T1 - An efficient algorithm for sorting by block-interchanges and its application to the evolution of vibrio species
AU - Lin, Ying Chih
AU - Lu, Chin Lung
AU - Chang, Hwan You
AU - Tang, Chuan Yi
PY - 2005
Y1 - 2005
N2 - 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.
AB - 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.
KW - Genome rearrangement
KW - Permutation group
KW - Sorting by block-interchanges
KW - Sorting by transpositions
KW - Vibrio genomes
UR - http://www.scopus.com/inward/record.url?scp=13444253942&partnerID=8YFLogxK
U2 - 10.1089/cmb.2005.12.102
DO - 10.1089/cmb.2005.12.102
M3 - 文章
C2 - 15725736
AN - SCOPUS:13444253942
SN - 1066-5277
VL - 12
SP - 102
EP - 112
JO - Journal of Computational Biology
JF - Journal of Computational Biology
IS - 1
ER -