Skip Navigation


Bioinformatics Advance Access originally published online on October 18, 2005
Bioinformatics 2005 21(24):4338-4347; doi:10.1093/bioinformatics/bti713
This Article
Right arrow Full Text Freely available
Right arrow FREE Full Text (Print PDF) Freely available
Right arrowOA All Versions of this Article:
21/24/4338    most recent
bti713v1
Right arrow Comments: Submit a response
Right arrow Alert me when this article is cited
Right arrow Alert me when Comments are posted
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in ISI Web of Science
Right arrow Similar articles in PubMed
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrow Search for citing articles in:
ISI Web of Science (8)
Google Scholar
Right arrow Articles by Hordijk, W.
Right arrow Articles by Gascuel, O.
Right arrow Search for Related Content
PubMed
Right arrow PubMed Citation
Right arrow Articles by Hordijk, W.
Right arrow Articles by Gascuel, O.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author 2005. Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions{at}oxfordjournals.org
The online version of this article has been published under an open access model. Users are entitled to use, reproduce, disseminate, or display the open access version of this article for non-commercial purposes provided that: the original authorship is properly and fully attributed; the Journal and Oxford University Press are attributed as the original place of publication with the correct citation details given; if an article is subsequently reproduced or disseminated not in its entirety but only in part or as a derivative work this must be clearly indicated. For commercial re-use, please contact journals.permissions{at}oxfordjournals.org

Improving the efficiency of SPR moves in phylogenetic tree search methods based on maximum likelihood

Wim Hordijk and Olivier Gascuel *

Projet Méthodes et Algorithmes pour la Bioinformatique, LIRMM, UMR CNRS 5506, Université Montpellier 2 161 rue Ada, 34392 Montpellier, France

*To whom correspondence should be addressed.

Motivation: Maximum likelihood (ML) methods have become very popular for constructing phylogenetic trees from sequence data. However, despite noticeable recent progress, with large and difficult datasets (e.g. multiple genes with conflicting signals) current ML programs still require huge computing time and can become trapped in bad local optima of the likelihood function. When this occurs, the resulting trees may still show some of the defects (e.g. long branch attraction) of starting trees obtained using fast distance or parsimony programs.

Methods: Subtree pruning and regrafting (SPR) topological rearrangements are usually sufficient to intensively search the tree space. Here, we propose two new methods to make SPR moves more efficient. The first method uses a fast distance-based approach to detect the least promising candidate SPR moves, which are then simply discarded. The second method locally estimates the change in likelihood for any remaining potential SPRs, as opposed to globally evaluating the entire tree for each possible move. These two methods are implemented in a new algorithm with a sophisticated filtering strategy, which efficiently selects potential SPRs and concentrates most of the likelihood computation on the promising moves.

Results: Experiments with real datasets comprising 35–250 taxa show that, while indeed greatly reducing the amount of computation, our approach provides likelihood values at least as good as those of the best-known ML methods so far and is very robust to poor starting trees. Furthermore, combining our new SPR algorithm with local moves such as PHYML's nearest neighbor interchanges, the time needed to find good solutions can sometimes be reduced even more.

Availability: Executables of our SPR program and the used datasets are available for download at http://atgc.lirmm.fr/spr

Contact: gascuel{at}lirmm.fr; wim{at}santafe.edu

Received on July 25, 2005; revised on October 7, 2005; accepted on October 9, 2005

Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?


This article has been cited by other articles:


Home page
 Phil Trans R Soc BHome page
S. Q. Le, N. Lartillot, and O. Gascuel
Phylogenetic mixture models for proteins
Phil Trans R Soc B, December 27, 2008; 363(1512): 3965 - 3976.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
L. Si Quang, O. Gascuel, and N. Lartillot
Empirical profile mixture models for phylogenetic reconstruction
Bioinformatics, October 15, 2008; 24(20): 2317 - 2323.
[Abstract] [Full Text] [PDF]

Home page
 Syst BiolHome page
A. Stamatakis, P. Hoover, and J. Rougemont
A Rapid Bootstrap Algorithm for the RAxML Web Servers
Syst Biol, October 1, 2008; 57(5): 758 - 771.
[Abstract] [Full Text] [PDF]

Home page
 Mol Biol EvolHome page
S. Q. Le and O. Gascuel
An Improved General Amino Acid Replacement Matrix
Mol. Biol. Evol., July 1, 2008; 25(7): 1307 - 1320.
[Abstract] [Full Text] [PDF]

Home page
 Phil Trans R Soc BHome page
N. Lartillot and H. Philippe
Improvement of molecular phylogenetic inference and the phylogeny of Bilateria
Phil Trans R Soc B, April 27, 2008; 363(1496): 1463 - 1472.
[Abstract] [Full Text] [PDF]

Home page
 Syst BiolHome page
D. A. Morrison
Increasing the Efficiency of Searches for the Maximum Likelihood Tree in a Phylogenetic Analysis of up to 150 Nucleotide Sequences
Syst Biol, December 1, 2007; 56(6): 988 - 1010.
[Abstract] [Full Text] [PDF]

Home page
 Proc. Natl. Acad. Sci. USAHome page
D. E. Wildman, M. Uddin, J. C. Opazo, G. Liu, V. Lefort, S. Guindon, O. Gascuel, L. I. Grossman, R. Romero, and M. Goodman
Genomics, biogeography, and the diversification of placental mammals
PNAS, September 4, 2007; 104(36): 14395 - 14400.
[Abstract] [Full Text] [PDF]

Home page
 Mol Biol EvolHome page
D. Baurain, H. Brinkmann, and H. Philippe
Lack of Resolution in the Animal Phylogeny: Closely Spaced Cladogeneses or Undetected Systematic Errors?
Mol. Biol. Evol., January 1, 2007; 24(1): 6 - 9.
[Abstract] [Full Text] [PDF]

Home page
 BioinformaticsHome page
A. Stamatakis
RAxML-VI-HPC: maximum likelihood-based phylogenetic analyses with thousands of taxa and mixed models
Bioinformatics, November 1, 2006; 22(21): 2688 - 2690.
[Abstract] [Full Text] [PDF]


Disclaimer: Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.