PentaPlot: A software tool for the illustration of genome mosaicism

BMC Bioinformatics
Lutz Hamel1, Olga Zhaxybayeva2, J. Peter Gogarten2
1Department of Computer Science and Statistics, University of Rhode Island, Kingston, RI, 02881, USA
2Department of Molecular and Cell Biology University of Connecticut Storrs CT 06269-3125 USA

Tóm tắt

Abstract Background Dekapentagonal maps depict the phylogenetic relationships of five genomes in a visually appealing diagram and can be viewed as an alternative to a single evolutionary consensus tree. In particular, the generated maps focus attention on those gene families that significantly deviate from the consensus or plurality phylogeny. PentaPlot is a software tool that computes such dekapentagonal maps given an appropriate probability support matrix. Results The visualization with dekapentagonal maps critically depends on the optimal layout of unrooted tree topologies representing different evolutionary relationships among five organisms along the vertices of the dekapentagon. This is a difficult optimization problem given the large number of possible layouts. At its core our tool utilizes a genetic algorithm with demes and a local search strategy to search for the optimal layout. The hybrid genetic algorithm performs satisfactorily even in those cases where the chosen genomes are so divergent that little phylogenetic information has survived in the individual gene families. Conclusion PentaPlot is being made publicly available as an open source project at http://pentaplot.sourceforge.net.

Từ khóa


Tài liệu tham khảo

Darwin C: On the Origin of Species by Means of Natural Selection, or the Preservation of Favoured Races in the Struggle for Life. London: John Murray, Albemarle Street; 1859.

Lamarck J-B: Histoire naturelle des animaux sans vertebras. Paris 1815.

Gogarten JP, Murphey RD, Olendzenski L: Horizontal gene transfer: pitfalls and promises. Biol Bull 1999, 196: 359–361.

Li W-H: Molecular Evolution. Sunderland, MA: Sinauer Associates; 1997.

Doolittle WF: Phylogenetic classification and the universal tree. Science 1999, 284: 2124–9. 10.1126/science.284.5423.2124

Olendzenski L, Zhaxybayeva O, Gogarten JP: What's in a Tree? Does Horizontal Gene Transfer Determine Microbial Taxonomy? In Cellular Origin and Life in Extreme Habitats. Vol. 4: Symbiosis. Edited by: Seckbach J. Netherlands: Kluwer Academic Publishers; 2001.

Koonin EV, Makarova KS, Aravind L: Horizontal gene transfer in prokaryotes: quantification and classification. Annu Rev Microbiol 2001, 55: 709–42. 10.1146/annurev.micro.55.1.709

Hilario E, Gogarten JP: Horizontal transfer of ATPase genes – the tree of life becomes a net of life. Biosystems 1993, 31: 111–9. 10.1016/0303-2647(93)90038-E

Gogarten JP, Doolittle WF, Lawrence JG: Prokaryotic evolution in light of gene transfer. Mol Biol Evol 2002, 19: 2226–38.

Zhaxybayeva O, Hamel L, Raymond J, Gogarten JP: Visualization of Phylogenetic content of Five Genomes with Dekapentagonal Maps. Genome Biology 2004, 5: R20. 10.1186/gb-2004-5-3-r20

Zhaxybayeva O, Gogarten JP: An Improved Probability Mapping Approach to Assess Genome Mosaicism. BMC Genomics 2003, 4: 37. 10.1186/1471-2164-4-37

Zhaxybayeva O, Gogarten JP: Bootstrap, Bayesian probability and maximum likelihood mapping: Exploring new tools for comparative genome analyses. BMC Genomics 2002, 3: 4. 10.1186/1471-2164-3-4

Weisstein EW: Circular Permutations, In: Eric Weisstein's World of Mathematics.[http://mathworld.wolfram.com/CircularPermutation.html]

Holland JH: Adaptation in Natural and Artificial Systems. University of Michigan Press; 1975.

Wall M: GALIB: A C++ Library of Genetic Algorithm Components. Distributed through.1996. [http://lancet.mit.edu/ga/]

Knuth DE: The TeXbook. Reading, Mass.: Addison-Wesley; 1986.

Altschul SF, Madden TL, Schaffer AA, Zhang J, Zhang Z, Miller W, Lipman DJ: Gapped BLAST and PSI-BLAST: a new generation of protein database search programs. Nucleic Acids Res 1997, 25: 3389–402. 10.1093/nar/25.17.3389

Montague MG, Hutchison CA 3rd: Gene content phylogeny of herpesviruses. Proc Natl Acad Sci U S A 2000, 97: 5334–9. 10.1073/pnas.97.10.5334

Fitch WM: Homology a personal view on some of the problems. Trends Genet 2000, 16: 227–31. 10.1016/S0168-9525(00)02005-9

Gogarten JP: Which is the most conserved group of proteins? Homology-orthology, paralogy, xenology, and the fusion of independent lineages. J Mol Evol 1994, 39: 541–3. 10.1007/BF00173425

Goldberg DE: Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley; 1989.

Moscato P: An introduction to population approaches for optimization and hierarchical objective functions: The role of tabu search. Annals of Operations Research 1993, 41: 85–121.

Krasnogor N, Smith J: Emergence of Profitable Search Strategies Based on a Simple Inheritance Mechanism. Proceedings of the Genetic and Evolutionary Computation Conference 2001, 432–439.

Koza JR: Genetic programming: on the programming of computers by means of natural selection. Cambridge, Mass.: MIT Press; 1992.

Strimmer K, von Haeseler A: Likelihood-mapping: a simple method to visualize phylogenetic content of a sequence alignment. Proc Natl Acad Sci, USA 1997, 94: 6815–6819. 10.1073/pnas.94.13.6815

Raymond J, Zhaxybayeva O, Gogarten JP, Gerdes SY, Blankenship RE: Whole-genome analysis of photosynthetic prokaryotes. Science 2002, 298: 1616–20. 10.1126/science.1075558

Thông tin
Thông tin xuất bản

BMC Bioinformatics

Thông tin tác giả