IQPNNI: moving fast through tree space and stopping in time
- PMID: 15163768
- DOI: 10.1093/molbev/msh176
IQPNNI: moving fast through tree space and stopping in time
Abstract
An efficient tree reconstruction method (IQPNNI) is introduced to reconstruct a phylogenetic tree based on DNA or amino acid sequence data. Our approach combines various fast algorithms to generate a list of potential candidate trees. The key ingredient is the definition of so-called important quartets (IQs), which allow the computation of an intermediate tree in O(n(2)) time for n sequences. The resulting tree is then further optimized by applying the nearest neighbor interchange (NNI) operation. Subsequently a random fraction of the sequences is deleted from the best tree found so far. The deleted sequences are then re-inserted in the smaller tree using the important quartet puzzling (IQP) algorithm. These steps are repeated several times and the best tree, with respect to the likelihood criterion, is considered as the inferred phylogenetic tree. Moreover, we suggest a rule which indicates when to stop the search. Simulations show that IQPNNI gives a slightly better accuracy than other programs tested. Moreover, we applied the approach to 218 small subunit rRNA sequences and 500 rbcL sequences. We found trees with higher likelihood compared to the results by others. A program to reconstruct DNA or amino acid based phylogenetic trees is available online (http://www.bi.uni-duesseldorf.de/software/iqpnni).
Similar articles
-
Increasing the efficiency of searches for the maximum likelihood tree in a phylogenetic analysis of up to 150 nucleotide sequences.Syst Biol. 2007 Dec;56(6):988-1010. doi: 10.1080/10635150701779808. Syst Biol. 2007. PMID: 18066931
-
On the quality of tree-based protein classification.Bioinformatics. 2005 May 1;21(9):1876-90. doi: 10.1093/bioinformatics/bti244. Epub 2005 Jan 12. Bioinformatics. 2005. PMID: 15647305
-
Representation in stochastic search for phylogenetic tree reconstruction.J Biomed Inform. 2006 Feb;39(1):43-50. doi: 10.1016/j.jbi.2005.11.001. Epub 2005 Nov 28. J Biomed Inform. 2006. PMID: 16359929
-
BOOL-AN: a method for comparative sequence analysis and phylogenetic reconstruction.Mol Phylogenet Evol. 2009 Sep;52(3):887-97. doi: 10.1016/j.ympev.2009.04.019. Epub 2009 May 5. Mol Phylogenet Evol. 2009. PMID: 19422923 Review.
-
[Algorithms for constructing phylogenetic trees of maximum topological similarity].Mol Gen Mikrobiol Virusol. 1988 Mar;(3):9-15. Mol Gen Mikrobiol Virusol. 1988. PMID: 3043212 Review. Russian.
Cited by
-
A Mek1-Mek2 heterodimer determines the strength and duration of the Erk signal.Nat Struct Mol Biol. 2009 Mar;16(3):294-303. doi: 10.1038/nsmb.1564. Epub 2009 Feb 15. Nat Struct Mol Biol. 2009. PMID: 19219045
-
Untangling the evolution of Rab G proteins: implications of a comprehensive genomic analysis.BMC Biol. 2012 Aug 8;10:71. doi: 10.1186/1741-7007-10-71. BMC Biol. 2012. PMID: 22873208 Free PMC article.
-
PHYML Online--a web server for fast maximum likelihood-based phylogenetic inference.Nucleic Acids Res. 2005 Jul 1;33(Web Server issue):W557-9. doi: 10.1093/nar/gki352. Nucleic Acids Res. 2005. PMID: 15980534 Free PMC article.
-
Evolution of rhodopsin ion pumps in haloarchaea.BMC Evol Biol. 2007 May 18;7:79. doi: 10.1186/1471-2148-7-79. BMC Evol Biol. 2007. PMID: 17511874 Free PMC article.
-
PALM: a paralleled and integrated framework for phylogenetic inference with automatic likelihood model selectors.PLoS One. 2009 Dec 7;4(12):e8116. doi: 10.1371/journal.pone.0008116. PLoS One. 2009. PMID: 19997614 Free PMC article.
MeSH terms
LinkOut - more resources
Full Text Sources
