Bioinformatics Vol. 19 Suppl. 1 2003
Pages i305-i312
© 2003 Oxford University Press
Scaling up accurate phylogenetic reconstruction from gene-order data
Department of Computer Science, University of New Mexico, Albuquerque, NM 87131, USA
Received on January 6, 2003
; accepted on February 20, 2003
Motivation: Phylogenetic reconstruction from gene-order data has attracted increasing attention from both biologists and computer scientists over the last few years. Methods used in reconstruction include distance-based methods (such as neighbor-joining), parsimony methods using sequence-based encodings, Bayesian approaches, and direct optimization. The latter, pioneered by Sankoff and extended by us with the software suite GRAPPA, is the most accurate approach, but cannot handle more than about 15 genomes of limited size (e.g. organelles).
Results: We report here on our successful efforts to scale up direct optimization through a two-step approach: the first step decomposes the dataset into smaller pieces and runs the direct optimization (GRAPPA) on the smaller pieces, while the second step builds a tree from the results obtained on the smaller pieces. We used the sophisticated disk-covering method (DCM) pioneered by Warnow and her group, suitably modified to take into account the computational limitations of GRAPPA. We find that DCM-GRAPPA scales gracefully to at least 1000 genomes of a few hundred genes each and retains surprisingly high accuracy throughout the range: in our experiments, the topological error rate rarely exceeded a few percent. Thus, reconstruction based on gene-order data can now be accomplished with high accuracy on datasets of significant size.
Availability: All of our software is available in source form under GPL at http://www.compbio.unm.edu
Contact: moret{at}cs.unm.edu
* To whom correspondence should be addressed.
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  M. A. Alekseyev and P. A. Pevzner Breakpoint graphs and ancestral genome reconstructions Genome Res., May 1, 2009; 19(5): 943 - 957. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 A. Esteban-Marcos, A. E. Darling, and M. A. Ragan Seevolution: visualizing chromosome evolution Bioinformatics, April 1, 2009; 25(7): 960 - 961. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
R. Fremez, T. Faraut, G. Fichant, J. Gouzy, and Y. Quentin Phylogenetic exploration of bacterial genomic rearrangements Bioinformatics, May 1, 2007; 23(9): 1172 - 1174. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 D. V. Lavrov and B. F. Lang Poriferan mtDNA and Animal Phylogeny Based on Mitochondrial Gene Arrangements Syst Biol, August 1, 2005; 54(4): 651 - 659. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
S. Pasek, A. Bergeron, J.-L. Risler, A. Louis, E. Ollivier, and M. Raffinot Identification of genomic features using microsyntenies of domains: Domain teams Genome Res., June 1, 2005; 15(6): 867 - 874. [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]
|
|
|
|
|
|
B. Larget, D. L. Simon, J. B. Kadane, and D. Sweet A Bayesian Analysis of Metazoan Mitochondrial Genome Arrangements Mol. Biol. Evol., March 1, 2005; 22(3): 486 - 495. [Abstract] [Full Text] [PDF]
|
|