MLGO: phylogeny reconstruction and ancestral inference from gene-order data

BMC Bioinformatics

Fei Hu¹  Yu Lin²  Jijun Tang¹ 

[1] Department of Computer Science and Engineering, University of South Carolina, Columbia 29208, SC, USA

[2] Department of Computer Science and Engineering, University of California, San Diego 92093 La Jolla, CA, USA

关键词: Maximum likelihood;    Genome rearrangement;    Ancestral inference;    Phylogeny reconstruction;   

Others  :  1085231
DOI  :  10.1186/s12859-014-0354-6

 received in 2014-07-16, accepted in 2014-10-16,  发布年份 2014

【 摘 要 】

Background

The rapid accumulation of whole-genome data has renewed interest in the study of using gene-order data for phylogenetic analyses and ancestral reconstruction. Current software and web servers typically do not support duplication and loss events along with rearrangements.

Results

MLGOMLGO (Maximum Likelihood for Gene-Order Analysis) is a web tool for the reconstruction of phylogeny and/or ancestral genomes from gene-order data. MLGOMLGO is based on likelihood computation and shows advantages over existing methods in terms of accuracy, scalability and flexibility.

Conclusions

To the best of our knowledge, it is the first web tool for analysis of large-scale genomic changes including not only rearrangements but also gene insertions, deletions and duplications. The web tool is available from http://www.geneorder.org/server.php webcite.

【 授权许可】

   
2014 Hu et al.; licensee BioMed Central Ltd.

【 图 表 】

Figure 1.

Figure 2.

Figure 3.

【 参考文献 】

• [1]Yancopoulos S, Attie O, Friedberg R: Efficient sorting of genomic permutations by translocation, inversion and block interchange. Bioinformatics 2005, 21(16):3340-3346.
• [2]Blanchette M, Bourque G, Sankoff D: Breakpoint phylogenies. Genome Inform 1997, 1997:25-34.
• [3]Moret B, Wang L, Warnow T, Wyman S: New approaches for reconstructing phylogenies from gene order data. Bioinformatics 2001, 17(suppl 1):165-173.
• [4]Bourque G, Pevzner P: Genome-scale evolution: reconstructing gene orders in the ancestral species. Genome Res 2002, 12(1):26-36.
• [5]Lin Y, Rajan V, Moret BME: TIBA: a tool for phylogeny inference from rearrangement data with bootstrap analysis. Bioinformatics 2012, 28(24):3324-3325.
• [6]Saitou N, Nei M: The neighbor-joining method: a new method for reconstructing phylogenetic trees. Mol Biol Evol 1987, 4(4):406-425.
• [7]Desper R, Gascuel O: Fast and accurate phylogeny reconstruction algorithms based on the minimum-evolution principle. J Comput Biol 2002, 9(5):687-705.
• [8]Lin Y, Moret BME: Estimating true evolutionary distances under the DCJ model. Bioinformatics 2008, 24(13):i114-i122.
• [9]Wang L-S, Jansen R, Moret BME, Raubeson L, Warnow T: Fast phylogenetic methods for the analysis of genome rearrangement data: an empirical study. In Pacific Symposium on Biocomputing. Pacific Symposium on Biocomputing (PSB). World Scientific, Singapore; 2001:524-535.
• [10]Hu F, Gao N, Zhang M, Tang J: Maximum likelihood phylogenetic reconstruction using gene order encodings. In Computational Intelligence in Bioinformatics and Computational Biology (CIBCB), 2011 IEEE Symposium On. IEEE, USA; 2011:1-6.
• [11]Lin Y, Hu F, Tang J, Moret BME: Maximum likelihood phylogenetic reconstruction from high-resolution whole-genome data and a tree of 68 eukaryotes. In Proc. 18th Pacific Symp. on Biocomputing, (PSB). World Scientific, Singapore; 2013:285-296.
• [12]Ma J, Zhang L, Suh BB, Raney BJ, Burhans RC, Kent WJ, Blanchette M, Haussler D, Miller W: Reconstructing contiguous regions of an ancestral genome. Genome Res 2006, 16(12):1557-1565.
• [13]Ma J, Ratan A, Raney BJ, Suh BB, Zhang L, Miller W, Haussler D: Dupcar: reconstructing contiguous ancestral regions with duplications. J Comput Biol 2008, 15(8):1007-1027.
• [14]Ma J: A probabilistic framework for inferring ancestral genomic orders. In Bioinformatics and Biomedicine (BIBM), 2010 IEEE International Conference On. IEEE, USA; 2010:179-184.
• [15]Gagnon Y, Blanchette M, El-Mabrouk N: A flexible ancestral genome reconstruction method based on gapped adjacencies. BMC Bioinformatics 2012, 13(Suppl 19):4.
• [16]Bergeron A, Blanchette M, Chateau A, Chauve C: Reconstructing ancestral gene orders using conserved intervals. In Proc. 4th Int’l Workshop Algs. in Bioinformatics (WABI’04). Springer, Germany; 2004:14-25.
• [17]Alekseyev MA, Pevzner PA: Breakpoint graphs and ancestral genome reconstructions. Genome Res 2009, 19(5):943-957.
• [18]Murat F, Xu J-H, Tannier E, Abrouk M, Guilhot N, Pont C, Messing J, Salse J: Ancestral grass karyotype reconstruction unravels new mechanisms of genome shuffling as a source of plant evolution. Genome Res 2010, 20(11):1545-1557.
• [19]Ouangraoua A, Tannier E, Chauve C: Reconstructing the architecture of the ancestral amniote genome. Bioinformatics 2011, 27(19):2664-2671.
• [20]Lin CH, Zhao H, Lowcay SH, Shahab A, Bourque G: webmgr: an online tool for the multiple genome rearrangement problem. Bioinformatics 2010, 26(3):408-410.
• [21]Hu F, Zhou J, Zhou L, Tang J: Probabilistic reconstruction of ancestral genomes with gene insertions and deletions. IEEE/ACM Trans Comput Biol Bioinformatics 2014, 11(4):667-672.
• [22]Sankoff D, Blanchette M: Probability models for genome rearrangement and linear invariants for phylogenetic inference. In Proc. 3rd Int’l Conf. Comput. Mol. Biol. (RECOMB’99). ACM, USA; 1999:302-309.
• [23]Stamatakis A: Raxml-vi-hpc: maximum likelihood-based phylogenetic analyses with thousands of taxa and mixed models. Bioinformatics 2006, 22(21):2688-2690.
• [24]Felsenstein J: Confidence limits on phylogenies: an approach using the bootstrap. Evol 1985, 39:783-791.
• [25]Lin Y, Rajan V, Moret BME: Bootstrapping phylogenies inferred from rearrangement data. In Proc. 11th Workshop Algs. in Bioinf. (WABI’11), Lecture Notes in Computer Science, Vol. 6833. Springer, Germany; 2011:175-187.
• [26]Yang Z, Kumar S, Nei M: A new method of inference of ancestral nucleotide and amino acid sequences. Genetics 1995, 141(4):1641-1650.
• [27][http://www.tsp.gatech.edu/concorde] webcite Applegate D, Bixby R, Chvatal V, Cook W: Concorde tsp solver2006. []
• [28]Clark AG, Eisen MB, Smith DR, Bergman CM, Oliver B, Markow TA, Kaufman TC, Kellis M, Gelbart W, Iyer VN, Pollard DA, Sackton TB, Larracuente AM, Singh ND, Abad JP, Abt DN, Adryan B, Aguade M, Akashi H, Anderson WW, Aquadro CF, Ardell DH, Arguello R, Artieri CG, Barbash DA, Barker D, Barsanti P, Batterham P, Batzoglou S, et al.: Evolution of genes and genomes on the drosophila phylogeny. Nature 2007, 450(7167):203-218.
• [29]López MD, Samuelsson T: eGOB: eukaryotic gene order browser. Bioinformatics 2011, 27(8):1150-1151.
• [30]Ponting CP: The functional repertoires of metazoan genomes. Nat Rev Genet 2008, 9(9):689-698.
• [31]Srivastava M, Begovic E, Chapman J, Putnam NH, Hellsten U, Kawashima T, Kuo A, Mitros T, Salamov A, Carpenter ML, Signorovitch AY, Moreno MA, Kamm K, Grimwood J, Schmutz J, Shapiro H, Grigoriev IV, Buss LW, Schierwater B, Dellaporta SL, Rokhsar DS: The trichoplax genome and the nature of placozoans. Nature 2008, 454(7207):955-960.
• [32]Simillion C, Janssens K, Sterck L, Van de Peer Y: i-adhore 2.0: an improved tool to detect degenerated genomic homology using genomic profiles. Bioinformatics 2008, 24(1):127-128.
• [33]Pham SK, Pevzner PA: Drimm-synteny: decomposing genomes into evolutionary conserved segments. Bioinformatics 2010, 26(20):2509-2516.
• [34]Rödelsperger C, Dieterich C: Cyntenator: progressive gene order alignment of 17 vertebrate genomes. PloS one 2010, 5(1):8861.