{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T20:46:14Z","timestamp":1762375574995},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2012,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:sec>\n            <jats:title>Background<\/jats:title>\n            <jats:p>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.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Results<\/jats:title>\n            <jats:p>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.<\/jats:p>\n          <\/jats:sec>\n          <jats:sec>\n            <jats:title>Conclusions<\/jats:title>\n            <jats:p>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.<\/jats:p>\n          <\/jats:sec>","DOI":"10.1186\/1748-7188-7-3","type":"journal-article","created":{"date-parts":[[2012,1,30]],"date-time":"2012-01-30T18:44:23Z","timestamp":1327949063000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":61,"title":["MRL and SuperFine+MRL: new supertree methods"],"prefix":"10.1186","volume":"7","author":[{"given":"Nam","family":"Nguyen","sequence":"first","affiliation":[]},{"given":"Siavash","family":"Mirarab","sequence":"additional","affiliation":[]},{"given":"Tandy","family":"Warnow","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,1,26]]},"reference":[{"key":"142_CR1","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/S0196-8858(82)80004-3","volume":"3","author":"LR Foulds","year":"1982","unstructured":"Foulds LR, Graham RL: The Steiner problem in phylogeny is NP-complete. Advances in Applied Mathematics. 1982, 3: 43-49.","journal-title":"Advances in Applied Mathematics"},{"issue":"4","key":"142_CR2","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1089\/cmb.1994.1.337","volume":"1","author":"L Wang","year":"1994","unstructured":"Wang L, Jiang T: On the complexity of multiple sequence alignment. J Comput Biol. 1994, 1 (4): 337-348.","journal-title":"J Comput Biol"},{"key":"142_CR3","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1109\/TCBB.2006.4","volume":"3","author":"S Roch","year":"2006","unstructured":"Roch S: A short proof that phylogenetic tree reconstruction by maximum likelihood is hard. IEEE Trans Comput Biol and Bioinformatics. 2006, 3: 92-94.","journal-title":"IEEE Trans Comput Biol and Bioinformatics"},{"key":"142_CR4","first-page":"343","volume-title":"Proceedings of the 2002 International Workshop on Algorithms in Bioinformatics (WABI'02), Rome, Lecture Notes in Computer Science (LNCS #2452)","author":"B Moret","year":"2002","unstructured":"Moret B, Roshan U, Warnow T: Sequence length requirements for phylogenetic methods. Proceedings of the 2002 International Workshop on Algorithms in Bioinformatics (WABI'02), Rome, Lecture Notes in Computer Science (LNCS #2452). 2002, 343-356. Springer Verlag"},{"issue":"5934","key":"142_CR5","doi-asserted-by":"publisher","first-page":"1561","DOI":"10.1126\/science.1171243","volume":"324","author":"K Liu","year":"2009","unstructured":"Liu K, Raghavan S, Nelesen S, Linder CR, Warnow T: Rapid and accurate large-scale coestimation of sequence alignments and phylogenetic trees. Science. 2009, 324 (5934): 1561-1564.","journal-title":"Science"},{"key":"142_CR6","volume-title":"PLoS Currents Tree of Life","author":"K Liu","year":"2010","unstructured":"Liu K, Linder CR, Warnow T: Multiple sequence alignment: a major challenge to large-scale phyloge-netics. PLoS Currents Tree of Life. 2010, http:\/\/knol.google.com\/k\/kevin-liu\/multiple-sequence-alignment-a-major\/ectabesw3uba\/9"},{"key":"142_CR7","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1093\/sysbio\/syr095","volume":"61","author":"K Liu","year":"2011","unstructured":"Liu K, Warnow T, Holder M, Nelesen S, Yu J, Stamatakis A, Linder C: SAT\u00e9-II: very fast and accurate simultaneous estimation of multiple sequence alignments and phylogenetic trees. Syst Biol. 2011, 61: 90-106.","journal-title":"Syst Biol"},{"key":"142_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4020-2330-9","volume-title":"Phylogenetic Supertrees combining information to reveal The Tree Of Life","author":"O Bininda-Emonds","year":"2004","unstructured":"Bininda-Emonds O: Phylogenetic Supertrees combining information to reveal The Tree Of Life. 2004, Computational Biology, Kluwer Academic, Dordrecht, the Netherlands"},{"key":"142_CR9","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1186\/1748-7188-5-18","volume":"5","author":"M Bansal","year":"2010","unstructured":"Bansal M, Burleigh J, Eulenstein O, Fern\u00e1ndez-Baca D: Robinson-Foulds Supertrees. Alg Mol Bio. 2010, 5: 18-","journal-title":"Alg Mol Bio"},{"key":"142_CR10","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/978-1-4020-2330-9_2","volume-title":"Phylogenetic Supertrees combining information to reveal The Tree Of Life","author":"B Baum","year":"2004","unstructured":"Baum B, Ragan MA: The MRP method. Phylogenetic Supertrees combining information to reveal The Tree Of Life. Edited by: Bininda-Emonds ORP. 2004, 17-34. Kluwer Academic, Dordrecht, the Netherlands"},{"key":"142_CR11","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/978-1-4020-2330-9_4","volume-title":"Phylogenetic Supertrees combining information to reveal The Tree Of Life","author":"J Burleigh","year":"2004","unstructured":"Burleigh J, Eulenstein O, Fern\u00e1ndez-Baca D, Sanderson M: MRF supertrees. Phylogenetic Supertrees combining information to reveal The Tree Of Life. Edited by: Bininda-Emonds O. 2004, 65-86. Kluwer Academic, Dordrecht, the Netherlands"},{"key":"142_CR12","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1109\/TCBB.2006.26","volume":"3","author":"D Chen","year":"2006","unstructured":"Chen D, Eulenstein O, Fern\u00e1ndez-Baca D, Sanderson M: Minimum-Flip Supertrees: complexity and algorithms. IEEE\/ACM Trans Comp Biol Bioinf. 2006, 3: 165-173.","journal-title":"IEEE\/ACM Trans Comp Biol Bioinf"},{"issue":"3","key":"142_CR13","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1080\/10635150701416682","volume":"56","author":"JA Cotton","year":"2007","unstructured":"Cotton JA, Wilkinson M: Majority-Rule Supertrees. Syst Biol. 2007, 56 (3): 445-452.","journal-title":"Syst Biol"},{"issue":"5","key":"142_CR14","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1080\/10635150701639754","volume":"56","author":"V Ranwez","year":"2007","unstructured":"Ranwez V, Berry V, Criscuolo A, Fabre P, Guillemot S, Scornavacca C, Douzery E: PhySIC: a veto supertree method with desirable properties. Syst Biol. 2007, 56 (5): 798-817.","journal-title":"Syst Biol"},{"issue":"2","key":"142_CR15","doi-asserted-by":"publisher","first-page":"243","DOI":"10.1080\/10635150802033014","volume":"57","author":"M Steel","year":"2008","unstructured":"Steel M, Rodrigo A: Maximum Likelihood Supertrees. Syst Biol. 2008, 57 (2): 243-250.","journal-title":"Syst Biol"},{"issue":"12","key":"142_CR16","doi-asserted-by":"publisher","first-page":"i115","DOI":"10.1093\/bioinformatics\/btq196","volume":"26","author":"V Ranwez","year":"2010","unstructured":"Ranwez V, Criscuolo A, Douzery EJ: SuperTriplets: a triplet-based supertree approach to phylogenomics. Bioinf. 2010, 26 (12): i115-i123.","journal-title":"Bioinf"},{"key":"142_CR17","volume-title":"An experimental study of Quartets MaxCut and other supertree methods","author":"M Swenson","year":"2011","unstructured":"Swenson M, Suri R, Linder C, Warnow T: An experimental study of Quartets MaxCut and other supertree methods. Alg Mol Bio. 2011, 6 (7): Special issue for selected papers from WABI 2010"},{"key":"142_CR18","doi-asserted-by":"publisher","first-page":"3","DOI":"10.2307\/1222480","volume":"41","author":"B Baum","year":"1992","unstructured":"Baum B: Combining trees as a way of combining data sets for phylogenetic inference, and the desirability of combining gene trees. Taxon. 1992, 41: 3-10.","journal-title":"Taxon"},{"key":"142_CR19","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/1055-7903(92)90035-F","volume":"1","author":"MA Ragan","year":"1992","unstructured":"Ragan MA: Phylogenetic inference based on matrix representation of trees. Mol Phylog Evol. 1992, 1: 53-58.","journal-title":"Mol Phylog Evol"},{"key":"142_CR20","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1186\/1748-7188-5-37","volume":"5","author":"A Kupczok","year":"2010","unstructured":"Kupczok A, Schmidt H, von Haeseler A: Accuracy of phylogeny reconstruction methods combining overlapping gene data sets. Alg Mol Bio. 2010, 5: 37-53.","journal-title":"Alg Mol Bio"},{"issue":"43-49","key":"142_CR21","first-page":"299","volume":"3","author":"LR Foulds","year":"1982","unstructured":"Foulds LR, Graham RL: The Steiner problem in phylogeny is NP-complete. Adv Appl Math. 1982, 3 (43-49): 299-","journal-title":"Adv Appl Math"},{"key":"142_CR22","volume-title":"PAUP*: Phylogenetic analysis using parsimony (* and other methods) Ver 4","author":"D Swofford","year":"2002","unstructured":"Swofford D: PAUP*: Phylogenetic analysis using parsimony (* and other methods) Ver 4. 2002, Sinauer Associates, Sunderland, Massachusetts"},{"key":"142_CR23","doi-asserted-by":"publisher","first-page":"774","DOI":"10.1111\/j.1096-0031.2008.00217.x","volume":"24","author":"P Goloboff","year":"2008","unstructured":"Goloboff P, Farris J, Nixon K: TNT, a free program for phylogenetic analysis. Cladistics. 2008, 24: 774-786.","journal-title":"Cladistics"},{"key":"142_CR24","volume-title":"Syst Biol","author":"M Swenson","year":"2011","unstructured":"Swenson M, Suri R, Linder C, Warnow T: SuperFine: fast and accurate supertree estimation. Syst Biol. 2011,http:\/\/sysbio.oxfordjournals.org\/content\/early\/2011\/09\/16\/sysbio.syr092.abstract,"},{"key":"142_CR25","volume-title":"27th Symposium on Applied Computing (ACM-SAC)","author":"D Neves","year":"2012","unstructured":"Neves D, Warnow T, Sobral J, Pingali K: Parallelizing SuperFine. 27th Symposium on Applied Computing (ACM-SAC). 2012"},{"key":"142_CR26","doi-asserted-by":"publisher","first-page":"2688","DOI":"10.1093\/bioinformatics\/btl446","volume":"22","author":"A Stamatakis","year":"2006","unstructured":"Stamatakis A: RAxML-NI-HPC: Maximum likelihood-based phylogenetic analyses with thousands of taxa and mixed models. Bioinf. 2006, 22: 2688-2690.","journal-title":"Bioinf"},{"issue":"3","key":"142_CR27","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1080\/10635150701431905","volume":"56","author":"PA Goloboff","year":"2007","unstructured":"Goloboff PA, Pol D: On divide-and-conquer strategies for parsimony analysis of large data sets: Rec-I-DCM3 versus TNT. Syst Biol. 2007, 56 (3): 485-495.http:\/\/sysbio.oxfordjournals.org\/content\/56\/3\/485.abstract","journal-title":"Syst Biol"},{"key":"142_CR28","volume-title":"A simulation study comparing supertree and combined analysis methods using SMIDGen","author":"M Swenson","year":"2010","unstructured":"Swenson M, Barban\u00e7on F, Linder C, Warnow T: A simulation study comparing supertree and combined analysis methods using SMIDGen. Alg Mol Bio. 2010, 5 (8): Special issue of selected papers from WABI 2009"},{"issue":"1367-4803 (Prin","key":"142_CR29","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1093\/bioinformatics\/bti191","volume":"21","author":"A Stamatakis","year":"2005","unstructured":"Stamatakis A, Ludwig T, Meier H: RAxML-III: a fast program for maximum likelihood-based inference of large phylogenetic trees. Bioinf. 2005, 21 (1367-4803 (Print)): 456-63.","journal-title":"Bioinf"},{"issue":"5","key":"142_CR30","doi-asserted-by":"publisher","first-page":"818","DOI":"10.1080\/10635150600999150","volume":"55","author":"M McMahon","year":"2006","unstructured":"McMahon M, Sanderson M: Phylogenetic supermatrix analysis of GenBank sequences from 2228 Papilionoid legumes. Syst Biol. 2006, 55 (5): 818-836.","journal-title":"Syst Biol"},{"key":"142_CR31","volume-title":"PhD thesis","author":"M Swenson","year":"2008","unstructured":"Swenson M: Phylogenetic Supertree Methods. PhD thesis. 2008, The University of Texas at Austin"},{"key":"142_CR32","first-page":"893","volume-title":"ACM\/SIAM Symposium on Discrete Algorithms (SODA'04)","author":"G Ganapathy","year":"2004","unstructured":"Ganapathy G, Ramachandran V, Warnow T: On contract-and-refine-transformations between phylogenetic trees. ACM\/SIAM Symposium on Discrete Algorithms (SODA'04). 2004, 893-902. SIAM Press"},{"key":"142_CR33","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1007\/BF02459467","volume":"59","author":"C Tuffley","year":"1997","unstructured":"Tuffley C, Steel M: Links between maximum likelihood and maximum parsimony under a simple model of site substitution. Bull Math Bio. 1997, 59: 581-607.","journal-title":"Bull Math Bio"},{"key":"142_CR34","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1126\/science.1206357","volume":"333","author":"MJ Sanderson","year":"2011","unstructured":"Sanderson MJ, McMahon MM, Steel MA: Terraces in phylogenetic tree space. Science. 2011, 333: 448-450.","journal-title":"Science"},{"key":"142_CR35","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1186\/1471-2148-6-93","volume":"6","author":"RMD Beck","year":"2006","unstructured":"Beck RMD, Bininda-Emonds ORP, Cardillo M, Liu FGR, Purvis A: A higher-level MRP supertree of placental mammals. BMC Evol Biol. 2006, 6: 93-","journal-title":"BMC Evol Biol"},{"key":"142_CR36","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1642\/0004-8038(2002)119[0088:SSCPEO]2.0.CO;2","volume":"119","author":"M Kennedy","year":"2002","unstructured":"Kennedy M, Page R: Seabird supertrees: combining partial estimates of procellariiform phylogeny. The Auk. 2002, 119: 88-108.","journal-title":"The Auk"},{"key":"142_CR37","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1017\/S0952836904005539","volume":"264","author":"M Cardillo","year":"2004","unstructured":"Cardillo M, Bininda-Emonds ORP, Boakes E, Purvis A: A species-level phylogenetic supertree of marsupials. J Zool. 2004, 264: 11-31.","journal-title":"J Zool"},{"key":"142_CR38","first-page":"277","volume":"9","author":"M Wojciechowski","year":"2000","unstructured":"Wojciechowski M, Sanderson M, Steele K, Liston A: Molecular phylogeny of the \"temperate herbaceous tribes\" of papilionoid legumes: a supertree approach. Adv Legume Syst. 2000, 9: 277-298.","journal-title":"Adv Legume Syst"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1748-7188-7-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T18:41:22Z","timestamp":1630521682000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/1748-7188-7-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1,26]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,12]]}},"alternative-id":["142"],"URL":"https:\/\/doi.org\/10.1186\/1748-7188-7-3","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1,26]]},"assertion":[{"value":"7 October 2011","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 January 2012","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 January 2012","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"3"}}