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
-
Epidemic community-associated methicillin-resistant Staphylococcus aureus: recent clonal expansion and diversification.Proc Natl Acad Sci U S A. 2008 Jan 29;105(4):1327-32. doi: 10.1073/pnas.0710217105. Epub 2008 Jan 23. Proc Natl Acad Sci U S A. 2008. PMID: 18216255 Free PMC article.
-
Microevolution of cytochrome bd oxidase in Staphylococci and its implication in resistance to respiratory toxins released by Pseudomonas.J Bacteriol. 2006 Dec;188(23):8079-86. doi: 10.1128/JB.00858-06. J Bacteriol. 2006. PMID: 17108291 Free PMC article.
-
Evolutionary dynamics of light-independent protochlorophyllide oxidoreductase genes in the secondary plastids of cryptophyte algae.Eukaryot Cell. 2008 Mar;7(3):550-3. doi: 10.1128/EC.00396-07. Epub 2008 Jan 4. Eukaryot Cell. 2008. PMID: 18178774 Free PMC article.
-
Dating first cases of COVID-19.PLoS Pathog. 2021 Jun 24;17(6):e1009620. doi: 10.1371/journal.ppat.1009620. eCollection 2021 Jun. PLoS Pathog. 2021. PMID: 34166465 Free PMC article.
-
Co-expression of VAL- and TMT-opsins uncovers ancient photosensory interneurons and motorneurons in the vertebrate brain.PLoS Biol. 2013;11(6):e1001585. doi: 10.1371/journal.pbio.1001585. Epub 2013 Jun 11. PLoS Biol. 2013. PMID: 23776409 Free PMC article.
MeSH terms
LinkOut - more resources
Full Text Sources
