PMCCPMCCPMCC

Search tips
Search criteria 

Advanced

 
Logo of amolbioBioMed CentralBiomed Central Web Sitesearchsubmit a manuscriptregisterthis articleAlgorithms for Molecular Biology : AMB
 
Algorithms Mol Biol. 2012; 7: 3.
Published online Jan 26, 2012. doi:  10.1186/1748-7188-7-3
PMCID: PMC3308190
MRL and SuperFine+MRL: new supertree methods
Nam Nguyen,1 Siavash Mirarab,1 and Tandy Warnowcorresponding author1
1Department of Computer Science, University of Texas at Austin, Austin, Texas, USA
corresponding authorCorresponding author.
Nam Nguyen: namphuon/at/cs.utexas.edu; Siavash Mirarab: smirarab/at/cs.utexas.edu; Tandy Warnow: tandy/at/cs.utexas.edu
Received October 7, 2011; Accepted January 26, 2012.
Abstract
Background
Supertree methods combine trees on subsets of the full taxon set together to produce a tree on the entire set of taxa. Of the many supertree methods, the most popular is MRP (Matrix Representation with Parsimony), a method that operates by first encoding the input set of source trees by a large matrix (the "MRP matrix") over {0,1, ?}, and then running maximum parsimony heuristics on the MRP matrix. Experimental studies evaluating MRP in comparison to other supertree methods have established that for large datasets, MRP generally produces trees of equal or greater accuracy than other methods, and can run on larger datasets. A recent development in supertree methods is SuperFine+MRP, a method that combines MRP with a divide-and-conquer approach, and produces more accurate trees in less time than MRP. In this paper we consider a new approach for supertree estimation, called MRL (Matrix Representation with Likelihood). MRL begins with the same MRP matrix, but then analyzes the MRP matrix using heuristics (such as RAxML) for 2-state Maximum Likelihood.
Results
We compared MRP and SuperFine+MRP with MRL and SuperFine+MRL on simulated and biological datasets. We examined the MRP and MRL scores of each method on a wide range of datasets, as well as the resulting topological accuracy of the trees. Our experimental results show that MRL, coupled with a very good ML heuristic such as RAxML, produced more accurate trees than MRP, and MRL scores were more strongly correlated with topological accuracy than MRP scores.
Conclusions
SuperFine+MRP, when based upon a good MP heuristic, such as TNT, produces among the best scores for both MRP and MRL, and is generally faster and more topologically accurate than other supertree methods we tested.
Keywords: MRP, MRL, supertrees, phylogenetics
Articles from Algorithms for Molecular Biology : AMB are provided here courtesy of
BioMed Central