Analysis of circular genome rearrangement by fusions, fissions and block-interchanges
详细信息 查看全文
- 作者：Chin Lung Lu (1)
Yen Lin Huang (2)
Tsui Ching Wang (1)
Hsien-Tai Chiu (1) - 刊名：BMC Bioinformatics
- 出版年：2006
- 出版时间：December 2006
- 年：2006
- 卷：7
- 期：1
- 全文大小：613KB
- 参考文献：1. Hannenhalli S, Pevzner PA: Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. / J Assoc Comput Mach 1999, 46:1鈥?7.
2. Bader DA, Yan M, Moret BMW: A linear-time algorithm for computing inversion distance between signed permutations with an experimental study. / J Comput Biol 2001, 8:483鈥?91. CrossRef
3. Bafna V, Pevzner PA: Genome rearrangements and sorting by reversals. / SIAM J Comput 1996, 25:272鈥?89. CrossRef
4. Berman P, Hannenhalli S: Fast sorting by reversal. / Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching (CPM1996), Volume 1075 of Lecture Notes in Computer Science / (Edited by: Hirschberg DS, Myers E). Springer-Verlag 1996, 168鈥?85.
5. Berman P, Hannenhalli S, Karpinski M: 1.375-approximation algorithm for sorting by reversals. / Proceedings of the 10th Annual European Symposium on Algorithms (ESA2002), Volume 2461 of Lecture Notes in Computer Science / (Edited by: Mohring RH, Raman R). Springer-Verlag 2002, 200鈥?10.
6. Caprara A: Sorting by reversal is difficult. / Proceedings of the 1th Annual International Conference on Research in Computational Molecular Biology (RECOMB1997) ACM Press 1997, 75鈥?3.
7. Caprara A: Sorting permutations by reversals and Eulerian cycle decompositions. / SIAM J Discrete Math 1999, 12:91鈥?10. CrossRef
8. Christie DA: A 3/2-approximation algorithm for sorting by reversals. / In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA1998), ACM/SIAM 1998, 244鈥?52.
9. Kaplan H, Shamir R, Tarjan RE: Faster and simpler algorithm for sorting signed permutations by reversals. / SIAM J Comput 2000, 29:880鈥?92. CrossRef
10. Kececioglu JD, Sankoff D: Exact and approximation algorithms for the inversion distance between two permutations. / Proceedings of the 4th Annual Symposium on Combinatorial Pattern Matching (CPM1993), Volume 684 of Lecture Notes on Computer Science / (Edited by: Apostolico A, Crochemore M, Galil Z, Manber U). Springer-Verlag 1993, 87鈥?05.
11. Bafna V, Pevzner PA: Sorting by transpositions. / SIAM J Discrete Math 1998, 11:221鈥?40. CrossRef
12. Walter MEMT, Dias Z, Meidanis J: Reversal and transposition distance of linear chromosomes. / Proceedings of String Processing and Information Retrieval (SPIRE1998) IEEE Computer Society 1998, 96鈥?02.
13. Christie DA: Sorting by block-interchanges. / Inform Process Lett 1996, 60:165鈥?69. CrossRef
14. Lin YC, Lu CL, Chang HY, Tang CY: An efficient algorithm for sorting by block- interchanges and its application to the evolution of Vibrio species. / J Comput Biol 2005, 12:102鈥?12. CrossRef
15. Lu CL, Wang TC, Lin YC, Tang CY: ROBIN: a tool for genome rearrangement of block-interchanges. / Bioinformatics 2005, 21:2780鈥?782. CrossRef
16. Hannenhalli S: Polynomial algorithm for computing translocation distance between genomes. / Discrete Appl Math 1996, 71:137鈥?51. CrossRef
17. Kececioglu JD, Ravi R: Of mice and men: algorithms for evolutionary distances between genomes with translocation. / Proceedings of the 6th ACM-SIAM Symposium on Discrete Algorithms (SODA1995) ACM/SIAM, San Francisco 1995, 604鈥?13.
18. Hannenhalli S, Pevzner PA: Transforming men into mice (polynomial algorithm for genomic distance problem). / Proceedings of the 36th IEEE Symposium on Foundations of Computer Science (FOCS1995) IEEE Computer Society 1995, 581鈥?92.
19. Meidanis J, Bias Z: Genome rearrangements distance by fusion, fission, and transposition is easy. / Proceedings of the 8th International Symposium on String Processing and Information Retrieval (SPIRE2001) / (Edited by: Navarro G). IEEE Computer Society 2001, 250鈥?53.
20. Tillier ER, Collins RA: Genome rearrangement by replication-directed translocation. / Nat Genet 2000, 26:195鈥?97. CrossRef
21. Yancopoulos S, Attie O, Friedberg R: Efficient sorting of genomic permutations by translocation, inversion and block interchange. / Bioinformatics 2005, 21:3340鈥?346. CrossRef
22. FFBI: a tool of circular genome rearrangement by fusions, fissions and block-interchanges[http://genome.life.nctu.edu.tw/FFBI/]
23. The COG database[http://www.ncbi.nlm.nih.gov/COG/]
24. Dorsch M, Lane D, Stackebrandt E: Towards a phylogeny of the genus Vibrio based on 16S rRNA sequences. / Int J Syst Bacterial 1992, 42:58鈥?3. CrossRef
25. Kita-Tsukamoto K, Oyaizu H, Nanba K, Simidu U: Phylogenetic relationships of marine bacteria, mainly members of the family Vibrionaceae ,determined on the basis of 16S rRNA sequences. / Int J Syst Bacteriol 1993, 43:8鈥?9. CrossRef
26. Okada K, Iida T, Kita-Tsukamoto K, Honda T: Vibrios commonly possess two chromosomes. / J Bacteriol 2005, 187:752鈥?57. CrossRef
27. Thompson JD, Higgins DG, Gibson TJ: CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice. / Nucleic Acids Res 1994, 22:4673鈥?680. CrossRef
28. Felsenstein J: PHYLIP: phylogeny inference package (version 3.2). / Cladistics 1989, 5:164鈥?66.
29. Fraleigh JB: / A First Course in Abstract Algebra / 7 Edition Addison-Wesley 2003.
30. Meidanis J, Dias Z: An alternative algebraic formalism for genome rearrangements. / Comparative Genomics: Empirical and Analytical Approaches to Gene Order Dynamics, Map Alignment and Evolution of Gene Families / (Edited by: Sankoff D, Nadeau JH). Kluwer Academic Publisher 2000, 213鈥?23.
31. Cormen TH, Leiserson CE, Rivest RL, Stein C: / Introduction to Algorithms / 2 Edition The MIT Press 2001.
32. Gabow HN, Tarjan RE: A linear-time algorithm for a special case of disjoint set union. / J Comput Syst Sci 1985, 30:209鈥?21. CrossRef
33. Tatusov RL, Koonin EV, Lipman DJ: A genomic perspective on protein families. / Science 1997, 278:631鈥?37. CrossRef
34. Koonin EV: Orthologs, paralogs, and evolutionary genomics. / Annu Rev Genet 2005, 39:309鈥?38. CrossRef
35. GenePlot[http://www.ncbi.nlm.nih.gov/sutils/geneplot.cgi]
36. Garcia-Vallve S, Guzman E, Montero MA, Romeu A: HGT-DB: a database of putative horizontally transferred genes in prokaryotic complete genomes. [http://www.fut.es/~debb/HGT/] / Nucleic Acids Res 2003, 31:187鈥?89. CrossRef - 作者单位：Chin Lung Lu (1)
Yen Lin Huang (2)
Tsui Ching Wang (1)
Hsien-Tai Chiu (1)
1. Department of Biological Science and Technology, National Chiao Tung University, Hsinchu, 300, ROC, Taiwan
2. Department of Computer Science, National Tsing Hua University, Hsinchu, 300, ROC, Taiwan - ISSN：1471-2105
文摘
Background 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. Results 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 (n 2) 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. Conclusion FFBI is a useful tool for the bioinformatics analysis of circular and multiple genome rearrangement by fusions, fissions and block-interchanges.