Bioinformatics Vol. 17 no. 90001 2001
Pages S165-S173
© 2001 Oxford University Press
New approaches for reconstructing phylogenies from gene order data
1 Department of Computer Science, University
of New Mexico, Albuquerque, NM 87131, USA
2 Department of Computer Sciences,
University of Texas, Austin, TX 78712, USA
Received on February 5, 2001
; revised on April 2, 2001
; accepted on April 2, 2001
We report on new techniques we have developed for reconstructing phylogenies on whole genomes. Our mathematical techniques include new polynomial-time methods for bounding the inversion length of a candidate tree and new polynomial-time methods for estimating genomic distances which greatly improve the accuracy of neighbor-joining analyses. We demonstrate the power of these techniques through an extensive performance study based on simulating genome evolution under a wide range of model conditions. Combining these new tools with standard approaches (fast reconstruction with neighbor-joining, exploration of all possible refinements of strict consensus trees, etc.) has allowed us to analyze datasets that were previously considered computationally impractical. In particular, we have conducted a complete phylogenetic analysis of a subset of the Campanulaceae family, confirming various conjectures about the relationships among members of the subset and about the principal mechanism of evolution for their chloroplast genome. We give representative results of the extensive experimentation we conducted on both real and simulated datasets in order to validate and characterize our approaches. We find that our techniques provide very accurate reconstructions of the true tree topology even when the data are generated by processes that include a significant fraction of transpositions and when the data are close to saturation.
Contact: moret{at}cs.unm.eduor tandy{at}cs.utexas.edu
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  Y. Lin and B. M.E. Moret Estimating true evolutionary distances under the DCJ model Bioinformatics, July 1, 2008; 24(13): i114 - i122. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
T. Faraut, S. de Givry, P. Chabrier, T. Derrien, F. Galibert, C. Hitte, and T. Schiex A comparative genome approach to marker ordering Bioinformatics, January 15, 2007; 23(2): e50 - e56. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 L. Cui, N. Veeraraghavan, A. Richter, K. Wall, R. K. Jansen, J. Leebens-Mack, I. Makalowska, and C. W. dePamphilis ChloroplastDB: the Chloroplast Genome Database Nucleic Acids Res., January 1, 2006; 34(suppl_1): D692 - D696. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 J.-F. Pombert, C. Otis, C. Lemieux, and M. Turmel The Chloroplast Genome Sequence of the Green Alga Pseudendoclonium akinetum (Ulvophyceae) Reveals Unusual Structural Features and New Insights into the Branching Order of Chlorophyte Lineages Mol. Biol. Evol., September 1, 2005; 22(9): 1903 - 1918. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
E. Belda, A. Moya, and F. J. Silva Genome Rearrangement Distances and Gene Order Phylogeny in {gamma}-Proteobacteria Mol. Biol. Evol., June 1, 2005; 22(6): 1456 - 1467. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 V. B. Yap and L. Pachter Identification of Evolutionary Hotspots in the Rodent Genomes Genome Res., April 1, 2004; 14(4): 574 - 579. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 P. Pevzner and G. Tesler Human and mouse genomic sequences reveal extensive breakpoint reuse in mammalian evolution PNAS, June 24, 2003; 100(13): 7672 - 7677. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 A. Caprara The Reversal Median Problem INFORMS Journal on Computing, January 1, 2003; 15(1): 93 - 113. [Abstract] [PDF]
|
|
|
|
|
|
E. E. Schadt, J. S. Sinsheimer, and K. Lange Applications of Codon and Rate Variation Models in Molecular Phylogeny Mol. Biol. Evol., September 1, 2002; 19(9): 1550 - 1562. [Abstract] [Full Text] [PDF]
|
|