{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T14:38:18Z","timestamp":1787063898752,"version":"build-2736575974"},"reference-count":37,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2021,5,7]],"date-time":"2021-05-07T00:00:00Z","timestamp":1620345600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1458652"],"award-info":[{"award-number":["1458652"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The estimation of phylogenetic trees for individual genes or multi-locus datasets is a basic part of considerable biological research. In order to enable large trees to be computed, Disjoint Tree Mergers (DTMs) have been developed; these methods operate by dividing the input sequence dataset into disjoint sets, constructing trees on each subset, and then combining the subset trees (using auxiliary information) into a tree on the full dataset. DTMs have been used to advantage for multi-locus species tree estimation, enabling highly accurate species trees at reduced computational effort, compared to leading species tree estimation methods. Here, we evaluate the feasibility of using DTMs to improve the scalability of maximum likelihood (ML) gene tree estimation to large numbers of input sequences. Our study shows distinct differences between the three selected ML codes\u2014RAxML-NG, IQ-TREE 2, and FastTree 2\u2014and shows that good DTM pipeline design can provide advantages over these ML codes on large datasets.<\/jats:p>","DOI":"10.3390\/a14050148","type":"journal-article","created":{"date-parts":[[2021,5,7]],"date-time":"2021-05-07T22:36:24Z","timestamp":1620426984000},"page":"148","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Disjoint Tree Mergers for Large-Scale Maximum Likelihood Tree Estimation"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8676-7565","authenticated-orcid":false,"given":"Minhyuk","family":"Park","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Illinois Urbana-Champaign, Urbana, IL 61801, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3550-2636","authenticated-orcid":false,"given":"Paul","family":"Zaharias","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Illinois Urbana-Champaign, Urbana, IL 61801, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7717-3514","authenticated-orcid":false,"given":"Tandy","family":"Warnow","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Illinois Urbana-Champaign, Urbana, IL 61801, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2021,5,7]]},"reference":[{"key":"ref_1","first-page":"57","article-title":"Some probabilistic and statistical problems in the analysis of DNA sequences","volume":"17","year":"1986","journal-title":"Lect. Math. Life Sci."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1109\/TCBB.2006.4","article-title":"A short proof that phylogenetic tree reconstruction by maximum likelihood is hard","volume":"3","author":"Roch","year":"2006","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1312","DOI":"10.1093\/bioinformatics\/btu033","article-title":"RAxML version 8: A tool for phylogenetic analysis and post-analysis","volume":"30","author":"Stamatakis","year":"2014","journal-title":"Bioinformatics"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"4453","DOI":"10.1093\/bioinformatics\/btz305","article-title":"RAxML-NG: A fast, scalable and user-friendly tool for maximum likelihood phylogenetic inference","volume":"35","author":"Kozlov","year":"2019","journal-title":"Bioinformatics"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"1530","DOI":"10.1093\/molbev\/msaa015","article-title":"IQ-TREE 2: New models and efficient methods for phylogenetic inference in the genomic era","volume":"37","author":"Minh","year":"2020","journal-title":"Mol. Biol. Evol."},{"key":"ref_6","unstructured":"Swofford, D.L. (2021, May 05). PAUP* (*Phylogenetic Analysis Using PAUP), Version 4a161. Available online: http:\/\/phylosolutions.com\/paup-test\/."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1093\/sysbio\/syq010","article-title":"New algorithms and methods to estimate maximum-likelihood phylogenies: Assessing the performance of PhyML 3.0","volume":"59","author":"Guindon","year":"2010","journal-title":"Syst. Biol."},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Price, M.N., Dehal, P.S., and Arkin, A.P. (2010). FastTree 2\u2014Approximately maximum-likelihood trees for large alignments. PLoS ONE, 5.","DOI":"10.1371\/journal.pone.0009490"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Liu, K., Linder, C.R., and Warnow, T. (2011). RAxML and FastTree: Comparing two methods for large-scale maximum likelihood phylogeny estimation. PLoS ONE, 6.","DOI":"10.1371\/journal.pone.0027731"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"486","DOI":"10.1093\/molbev\/msx302","article-title":"Evaluating fast maximum likelihood-based phylogenetic programs using empirical phylogenomic data sets","volume":"35","author":"Zhou","year":"2018","journal-title":"Mol. Biol. Evol."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1093\/molbev\/msu300","article-title":"IQ-TREE: A fast and effective stochastic algorithm for estimating maximum-likelihood phylogenies","volume":"32","author":"Nguyen","year":"2015","journal-title":"Mol. Biol. Evol."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1038\/d41586-021-00525-x","article-title":"Want to track pandemic variants faster? Fix the bioinformatics bottleneck","volume":"591","author":"Hodcroft","year":"2021","journal-title":"Nature"},{"key":"ref_13","first-page":"239","article-title":"Taxon sampling and the accuracy of phylogenetic analyses","volume":"46","author":"Heath","year":"2008","journal-title":"J. Syst. Evol."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"3292","DOI":"10.1093\/molbev\/msaa139","article-title":"ASTRAL-Pro: Quartet-based species-tree inference despite paralogy","volume":"37","author":"Zhang","year":"2020","journal-title":"Mol. Biol. Evol."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"33","DOI":"10.12688\/wellcomeopenres.14265.2","article-title":"Evaluation of phylogenetic reconstruction methods using bacterial whole genomes: A simulation based study","volume":"3","author":"Lees","year":"2018","journal-title":"Wellcome Open Res."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1093\/sysbio\/syaa058","article-title":"Phylogeny estimation given sequence length heterogeneity","volume":"70","author":"Smirnov","year":"2021","journal-title":"Syst. Biol."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"3279","DOI":"10.1093\/molbev\/msx261","article-title":"Fragmentary gene sequences negatively impact gene tree and species tree reconstruction","volume":"34","author":"Sayyari","year":"2017","journal-title":"Mol. Biol. Evol."},{"key":"ref_18","unstructured":"Zhang, Q.R., Rao, S., and Warnow, T.J. (2018, January 20\u201322). New Absolute Fast Converging Phylogeny Estimation Methods with Improved Scalability and Accuracy. Proceedings of the 18th International Workshop on Algorithms in Bioinformatics, WABI 2018, Helsinki, Finland."},{"key":"ref_19","unstructured":"Blanchette, M., and Ouangraoua, A. (2018). NJMerge: A Generic Technique for Scaling Phylogeny Estimation Methods and Its Application to Species Trees. Comparative Genomics. RECOMB-CG 2018. Lecture Notes in Computer Science, Springer."},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"i417","DOI":"10.1093\/bioinformatics\/btz344","article-title":"TreeMerge: A new method for improving the scalability of species tree estimation methods","volume":"35","author":"Molloy","year":"2019","journal-title":"Bioinformatics"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/s12864-020-6605-1","article-title":"Unblended disjoint tree merging using GTM improves species tree estimation","volume":"21","author":"Smirnov","year":"2020","journal-title":"BMC Genom."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"523","DOI":"10.1093\/sysbio\/46.3.523","article-title":"Gene trees in species trees","volume":"46","author":"Maddison","year":"1997","journal-title":"Syst. Biol."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"3250","DOI":"10.1093\/bioinformatics\/btr553","article-title":"FastSP: Linear time calculation of alignment accuracy","volume":"27","author":"Mirarab","year":"2011","journal-title":"Bioinformatics"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1109\/TCBB.2020.2990867","article-title":"Using Constrained-INC for large-scale gene tree and species tree estimation","volume":"18","author":"Le","year":"2020","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Molloy, E.K., and Warnow, T. (2019). Statistically consistent divide-and-conquer pipelines for phylogeny estimation using NJMerge. Algorithms Mol. Biol., 14.","DOI":"10.1186\/s13015-019-0151-x"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/0025-5564(81)90043-2","article-title":"Comparison of phylogenetic trees","volume":"53","author":"Robinson","year":"1981","journal-title":"Math. Biosci."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1093\/sysbio\/syr095","article-title":"SAT\u00e9-II: Very fast and accurate simultaneous estimation of multiple sequence alignments and phylogenetic trees","volume":"61","author":"Liu","year":"2012","journal-title":"Syst. Biol."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1089\/cmb.2014.0156","article-title":"PASTA: Ultra-large multiple sequence alignment for nucleotide and amino-acid sequences","volume":"22","author":"Mirarab","year":"2015","journal-title":"J. Comput. Biol."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Smirnov, V., and Warnow, T. (2020). MAGUS: Multiple Sequence Alignment using Graph Clustering. Bioinformatics.","DOI":"10.1093\/bioinformatics\/btaa992"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"1561","DOI":"10.1126\/science.1171243","article-title":"Rapid and accurate large-scale coestimation of sequence alignments and phylogenetic trees","volume":"324","author":"Liu","year":"2009","journal-title":"Science"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1093\/oxfordjournals.molbev.a003973","article-title":"Heterotachy, an important process of protein evolution","volume":"19","author":"Lopez","year":"2002","journal-title":"Mol. Biol. Evol."},{"key":"ref_32","unstructured":"Fletcher, W. (2021, May 05). INDELible v1.03 Control File Tutorial. Available online: http:\/\/abacus.gene.ucl.ac.uk\/software\/indelible\/tutorial\/nucleotide-branch.shtml."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"1879","DOI":"10.1093\/molbev\/msp098","article-title":"INDELible: A flexible simulator of biological sequence evolution","volume":"26","author":"Fletcher","year":"2009","journal-title":"Mol. Biol. Evol."},{"key":"ref_34","unstructured":"Guo, S. (2021, May 05). CIPRES Simulation Data. Available online: https:\/\/kim.bio.upenn.edu\/software\/csd.shtml."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"2798","DOI":"10.1093\/molbev\/msv150","article-title":"FastME 2.0: A comprehensive, accurate, and fast distance-based phylogeny inference program","volume":"32","author":"Lefort","year":"2015","journal-title":"Mol. Biol. Evol."},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"609","DOI":"10.1111\/1755-0998.13281","article-title":"ASAP: Assemble species by automatic partitioning","volume":"21","author":"Puillandre","year":"2021","journal-title":"Mol. Ecol. Resour."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/BF01731581","article-title":"A simple method for estimating evolutionary rates of base substitutions through comparative studies of nucleotide sequences","volume":"16","author":"Kimura","year":"1980","journal-title":"J. Mol. Evol."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/5\/148\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:58:05Z","timestamp":1760162285000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/5\/148"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,7]]},"references-count":37,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2021,5]]}},"alternative-id":["a14050148"],"URL":"https:\/\/doi.org\/10.3390\/a14050148","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5,7]]}}}