MBE Advance Access originally published online on May 26, 2004
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Mol. Biol. Evol. 21(8):1565-1571. 2004
DOI: 10.1093/molbev/msh176
© 2004 by the Society for Molecular Biology and Evolution. ISSN: 0737-4038
IQPNNI: Moving Fast Through Tree Space and Stopping in Time
* Heinrich-Heine Universität Düsseldorf, Germany
Forschungszentrum Jülich, Germany
E-mail: haeseler{at}cs.uni-duesseldorf.de.
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(n2) 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).
Key Words: sequence evolution • maximum likelihood • tree reconstruction • phylogenetics • quartet tree • nearest neighbor interchange • accuracy • rbcL • record value
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  J. Shi, J. B. Franklin, J. T. Yelinek, I. Ebersberger, G. Warren, and C. Y. He Centrin4 coordinates cell and nuclear division in T. brucei J. Cell Sci., September 15, 2008; 121(18): 3062 - 3070. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 T. H. Kloepper, C. N. Kienle, and D. Fasshauer SNAREing the Basis of Multicellularity: Consequences of Protein Family Expansion during Evolution Mol. Biol. Evol., September 1, 2008; 25(9): 2055 - 2068. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 R. Kamikawa, Y. Inagaki, and Y. Sako Direct phylogenetic evidence for lateral transfer of elongation factor-like gene PNAS, May 13, 2008; 105(19): 6965 - 6969. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 H. Khan and J. M. Archibald Lateral transfer of introns in the cryptophyte plastid genome Nucleic Acids Res., May 1, 2008; 36(9): 3043 - 3053. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
I. Ruiz-Trillo, A. J. Roger, G. Burger, M. W. Gray, and B. F. Lang A Phylogenomic Investigation into the Origin of Metazoa Mol. Biol. Evol., April 1, 2008; 25(4): 664 - 672. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 A. Fong and J. M. Archibald Evolutionary Dynamics of Light-Independent Protochlorophyllide Oxidoreductase Genes in the Secondary Plastids of Cryptophyte Algae Eukaryot. Cell, March 1, 2008; 7(3): 550 - 553. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 J. W. Leigh, E. Susko, M. Baumgartner, and A. J. Roger Testing Congruence in Phylogenomic Analysis Syst Biol, February 1, 2008; 57(1): 104 - 115. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
A. D. Kennedy, M. Otto, K. R. Braughton, A. R. Whitney, L. Chen, B. Mathema, J. R. Mediavilla, K. A. Byrne, L. D. Parkins, F. C. Tenover, et al. From the Cover: Epidemic community-associated methicillin-resistant Staphylococcus aureus: Recent clonal expansion and diversification PNAS, January 29, 2008; 105(4): 1327 - 1332. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
E. Bapteste, E. Susko, J. Leigh, I. Ruiz-Trillo, J. Bucknam, and W.F. Doolittle Alternative Methods for Concatenation of Core Genes Indicate a Lack of Resolution in Deep Nodes of the Prokaryotic Phylogeny Mol. Biol. Evol., January 1, 2008; 25(1): 83 - 91. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
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]
|
|
|
|
|
|
T. Schlegel, O. Mirus, A. von Haeseler, and E. Schleiff The Tetratricopeptide Repeats of Receptors Involved in Protein Translocation across Membranes Mol. Biol. Evol., December 1, 2007; 24(12): 2763 - 2774. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 S. Moslavac, K. Nicolaisen, O. Mirus, F. Al Dehni, R. Pernil, E. Flores, I. Maldener, and E. Schleiff A TolC-Like Protein Is Required for Heterocyst Development in Anabaena sp. Strain PCC 7120 J. Bacteriol., November 1, 2007; 189(21): 7887 - 7895. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
S. Whelan New Approaches to Phylogenetic Tree Search and Their Application to Large Numbers of Protein Alignments Syst Biol, October 1, 2007; 56(5): 727 - 740. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 T. H. Kloepper, C. N. Kienle, and D. Fasshauer An Elaborate Classification of SNARE Proteins Sheds Light on the Conservation of the Eukaryotic Endomembrane System Mol. Biol. Cell, September 1, 2007; 18(9): 3463 - 3471. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
W. White, S. Hills, R Gaddam, B. Holland, and D. Penny Treeness Triangles: Visualizing the Loss of Phylogenetic Signal Mol. Biol. Evol., September 1, 2007; 24(9): 2029 - 2039. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
H. Khan, N. Parks, C. Kozera, B. A. Curtis, B. J. Parsons, S. Bowman, and J. M. Archibald Plastid Genome Sequence of the Cryptophyte Alga Rhodomonas salina CCMP1319: Lateral Transfer of Putative DNA Replication Machinery and a Test of Chromist Plastid Phylogeny Mol. Biol. Evol., August 1, 2007; 24(8): 1832 - 1842. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
L. A. Hug and A. J. Roger The Impact of Fossils and Taxon Sampling on Ancient Molecular Dating Analyses Mol. Biol. Evol., August 1, 2007; 24(8): 1889 - 1897. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
T. M. Keane, T. J. Naughton, and J. O. McInerney MultiPhyl: a high-throughput phylogenomics webserver using distributed computing Nucleic Acids Res., July 13, 2007; 35(suppl_2): W33 - W37. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 R. Bredemeier, T. Schlegel, F. Ertel, A. Vojta, L. Borissenko, M. T. Bohnsack, M. Groll, A. von Haeseler, and E. Schleiff Functional and Phylogenetic Properties of the Pore-forming beta-Barrel Transporters of the Omp85 Family J. Biol. Chem., January 19, 2007; 282(3): 1882 - 1890. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
L. Voggu, S. Schlag, R. Biswas, R. Rosenstein, C. Rausch, and F. Gotz Microevolution of Cytochrome bd Oxidase in Staphylococci and Its Implication in Resistance to Respiratory Toxins Released by Pseudomonas. J. Bacteriol., December 1, 2006; 188(23): 8079 - 8086. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 C. L. Afonso, E. R. Tulman, G. Delhon, Z. Lu, G. J. Viljoen, D. B. Wallace, G. F. Kutish, and D. L. Rock Genome of crocodilepox virus. J. Virol., May 1, 2006; 80(10): 4978 - 4991. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 C. Guder, S. Pinho, T. G. Nacak, H. A. Schmidt, B. Hobmayer, C. Niehrs, and T. W. Holstein An ancient Wnt-Dickkopf antagonism in Hydra Development, March 1, 2006; 133(5): 901 - 911. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
I. Paulsen and A. von Haeseler INVHOGEN: a database of homologous invertebrate genes Nucleic Acids Res., January 1, 2006; 34(suppl_1): D349 - D353. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 W. Hordijk and O. Gascuel Improving the efficiency of SPR moves in phylogenetic tree search methods based on maximum likelihood Bioinformatics, December 15, 2005; 21(24): 4338 - 4347. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
C. Rausch, T. Weber, O. Kohlbacher, W. Wohlleben, and D. H. Huson Specificity prediction of adenylation domains in nonribosomal peptide synthetases (NRPS) using transductive support vector machines (TSVMs) Nucleic Acids Res., October 12, 2005; 33(18): 5799 - 5808. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
B. Q. Minh, L. S. Vinh, A. von Haeseler, and H. A. Schmidt pIQPNNI: parallel reconstruction of large maximum likelihood phylogenies Bioinformatics, October 1, 2005; 21(19): 3794 - 3796. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
R. Fleissner, D. Metzler, and A. von Haeseler Simultaneous Statistical Multiple Alignment and Phylogeny Reconstruction Syst Biol, August 1, 2005; 54(4): 548 - 561. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
S. Guindon, F. Lethiec, P. Duroux, and O. Gascuel PHYML Online--a web server for fast maximum likelihood-based phylogenetic inference Nucleic Acids Res., July 1, 2005; 33(suppl_2): W557 - W559. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
J. Sullivan, Z. Abdo, P. Joyce, and D. L. Swofford Evaluating the Performance of a Successive-Approximations Approach to Parameter Optimization in Maximum-Likelihood Phylogeny Estimation Mol. Biol. Evol., June 1, 2005; 22(6): 1386 - 1392. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
E. Seif, J. Leigh, Y. Liu, I. Roewer, L. Forget, and B. F. Lang Comparative mitochondrial genomics in zygomycetes: bacteria-like RNase P RNAs, mobile elements and a close source of the group I intron invasion in angiosperms Nucleic Acids Res., February 2, 2005; 33(2): 734 - 744. [Abstract] [Full Text] [PDF]
|
|