Lu Chin Lung, Huang Yen Lin, Wang Tsui Ching, Chiu Hsien-Tai
Department of Biological Science and Technology, National Chiao Tung University, Hsinchu 300, ROC, Taiwan.
BMC Bioinformatics. 2006 Jun 12;7:295. doi: 10.1186/1471-2105-7-295.
Analysis of genomes evolving via block-interchange events leads to a combinatorial problem of sorting by block-interchanges, which has been studied recently to evaluate the evolutionary relationship in distance between two biological species since block-interchange can be considered as a generalization of transposition. However, for genomes consisting of multiple chromosomes, their evolutionary history should also include events of chromosome fusions and fissions, where fusion merges two chromosomes into one and fission splits a chromosome into two.
In this paper, we study the problem of genome rearrangement between two genomes of circular and multiple chromosomes by considering fusion, fission and block-interchange events altogether. By use of permutation groups in algebra, we propose an O (n2) time algorithm to efficiently compute and obtain a minimum series of fusions, fissions and block-interchanges required to transform one circular multi-chromosomal genome into another, where n is the number of genes shared by the two studied genomes. In addition, we have implemented this algorithm as a web server, called FFBI, and have also applied it to analyzing by gene orders the whole genomes of three human Vibrio pathogens, each with multiple and circular chromosomes, to infer their evolutionary relationships. Consequently, our experimental results coincide well with our previous results obtained using the chromosome-by-chromosome comparisons by landmark orders between any two Vibrio chromosomal sequences as well as using the traditional comparative analysis of 16S rRNA sequences. ConclusionFFBI is a useful tool for the bioinformatics analysis of circular and multiple genome rearrangement by fusions, fissions and block-interchanges.
通过块交换事件进化的基因组分析会导致一个组合问题，即通过块交换进行排序，由于块交换可被视为转座的一种推广，该问题最近已被研究用于评估两个生物物种之间的进化距离。然而，对于由多条染色体组成的基因组，其进化历史还应包括染色体融合和裂变事件，其中融合将两条染色体合并为一条，裂变将一条染色体分裂为两条。
在本文中，我们通过综合考虑融合、裂变和块交换事件，研究了两个环状多染色体基因组之间的基因组重排问题。利用代数中的置换群，我们提出了一种O(n²)时间算法，以有效地计算并获得将一个环状多染色体基因组转化为另一个所需的最少融合、裂变和块交换序列，其中n是两个研究基因组共有的基因数量。此外，我们已将此算法实现为一个名为FFBI的网络服务器，并将其应用于通过基因顺序分析三种人类弧菌病原体的全基因组，每种病原体都有多个环状染色体，以推断它们的进化关系。因此，我们的实验结果与我们之前使用地标顺序对任意两个弧菌染色体序列进行逐染色体比较以及使用16S rRNA序列的传统比较分析所获得的结果非常吻合。结论FFBI是通过融合、裂变和块交换对环状和多基因组重排进行生物信息学分析的有用工具。
