{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T13:47:21Z","timestamp":1767275241368},"reference-count":44,"publisher":"Oxford University Press (OUP)","issue":"12","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":1576,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/3.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012,6,15]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Motivation: While phylogenetic analyses of datasets containing 1000\u20135000 sequences are challenging for existing methods, the estimation of substantially larger phylogenies poses a problem of much greater complexity and scale.<\/jats:p><jats:p>Methods: We present DACTAL, a method for phylogeny estimation that produces trees from unaligned sequence datasets without ever needing to estimate an alignment on the entire dataset. DACTAL combines iteration with a novel divide-and-conquer approach, so that each iteration begins with a tree produced in the prior iteration, decomposes the taxon set into overlapping subsets, estimates trees on each subset, and then combines the smaller trees into a tree on the full taxon set using a new supertree method. We prove that DACTAL is guaranteed to produce the true tree under certain conditions. We compare DACTAL to SAT\u00e9 and maximum likelihood trees on estimated alignments using simulated and real datasets with 1000\u201327 643 taxa.<\/jats:p><jats:p>Results: Our studies show that on average DACTAL yields more accurate trees than the two-phase methods we studied on very large datasets that are difficult to align, and has approximately the same accuracy on the easier datasets. The comparison to SAT\u00e9 shows that both have the same accuracy, but that DACTAL achieves this accuracy in a fraction of the time. Furthermore, DACTAL can analyze larger datasets than SAT\u00e9, including a dataset with almost 28 000 sequences.<\/jats:p><jats:p>Availability: DACTAL source code and results of dataset analyses are available at www.cs.utexas.edu\/users\/phylo\/software\/dactal.<\/jats:p><jats:p>Contact: \u00a0tandy@cs.utexas.edu<\/jats:p>","DOI":"10.1093\/bioinformatics\/bts218","type":"journal-article","created":{"date-parts":[[2012,6,11]],"date-time":"2012-06-11T14:09:18Z","timestamp":1339423758000},"page":"i274-i282","source":"Crossref","is-referenced-by-count":44,"title":["DACTAL: divide-and-conquer trees (almost) without alignments"],"prefix":"10.1093","volume":"28","author":[{"given":"Serita","family":"Nelesen","sequence":"first","affiliation":[{"name":"1 Dept. of Computer Science, Calvin College, Grand Rapids, MI 49546, 2Dept. of Computer Science, Rice University, Houston, TX 77005, 3Dept. of Pathology and Laboratory Medicine, The University of Pennsylvania, Philadelphia, PA 19104, 4Section of Integrative Biology and 5Dept. of Computer Science, The University of Texas at Austin, Austin, TX 78712, USA"}]},{"given":"Kevin","family":"Liu","sequence":"additional","affiliation":[{"name":"1 Dept. of Computer Science, Calvin College, Grand Rapids, MI 49546, 2Dept. of Computer Science, Rice University, Houston, TX 77005, 3Dept. of Pathology and Laboratory Medicine, The University of Pennsylvania, Philadelphia, PA 19104, 4Section of Integrative Biology and 5Dept. of Computer Science, The University of Texas at Austin, Austin, TX 78712, USA"}]},{"given":"Li-San","family":"Wang","sequence":"additional","affiliation":[{"name":"1 Dept. of Computer Science, Calvin College, Grand Rapids, MI 49546, 2Dept. of Computer Science, Rice University, Houston, TX 77005, 3Dept. of Pathology and Laboratory Medicine, The University of Pennsylvania, Philadelphia, PA 19104, 4Section of Integrative Biology and 5Dept. of Computer Science, The University of Texas at Austin, Austin, TX 78712, USA"}]},{"given":"C. Randal","family":"Linder","sequence":"additional","affiliation":[{"name":"1 Dept. of Computer Science, Calvin College, Grand Rapids, MI 49546, 2Dept. of Computer Science, Rice University, Houston, TX 77005, 3Dept. of Pathology and Laboratory Medicine, The University of Pennsylvania, Philadelphia, PA 19104, 4Section of Integrative Biology and 5Dept. of Computer Science, The University of Texas at Austin, Austin, TX 78712, USA"}]},{"given":"Tandy","family":"Warnow","sequence":"additional","affiliation":[{"name":"1 Dept. of Computer Science, Calvin College, Grand Rapids, MI 49546, 2Dept. of Computer Science, Rice University, Houston, TX 77005, 3Dept. of Pathology and Laboratory Medicine, The University of Pennsylvania, Philadelphia, PA 19104, 4Section of Integrative Biology and 5Dept. of Computer Science, The University of Texas at Austin, Austin, TX 78712, USA"}]}],"member":"286","published-online":{"date-parts":[[2012,6,9]]},"reference":[{"key":"2023012512394046800_B1","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","article-title":"A basic local alignment search tool","volume":"215","author":"Altschul","year":"1990","journal-title":"J. Mol. Biol."},{"key":"2023012512394046800_B2","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/PL00008277","article-title":"The performance of neighbor-joining methods of phylogenetic reconstruction","volume":"25","author":"Atteson","year":"1999","journal-title":"Algorithmica"},{"key":"2023012512394046800_B3","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1111\/j.2517-6161.1995.tb02031.x","article-title":"Controlling the false discovery rate: A practical and powerful approach to multiple testing","volume":"57","author":"Benjamini","year":"1995","journal-title":"J. Roy. Stat. Soc."},{"key":"2023012512394046800_B4","first-page":"273","article-title":"Two strikes against perfect phylogeny","volume-title":"ICALP 1992","author":"Bodlaender","year":"1992"},{"key":"2023012512394046800_B5","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1186\/1471-2105-3-1","article-title":"The comparative RNA web (CRW) site: an online database of comparative sequence and structure information for ribosomal, intron and other RNAs","volume":"3","author":"Cannone","year":"2002","journal-title":"BMC Bioinf."},{"key":"2023012512394046800_B6","first-page":"436","article-title":"Evolutionary trees can be learned in polynomial time in the two-state general Markov model","volume-title":"Proc. IEEE Symp. Foundations of Comput. Sci. FOCS98","author":"Cryan","year":"1998"},{"key":"2023012512394046800_B7","first-page":"261","article-title":"Recovering evolutionary trees through harmonic greedy triplets","volume-title":"Proc. 10th Ann. ACM\/SIAM Symp. Discr. Algs. (SODA99)","author":"Cs\u00fcr\u0151s","year":"1999"},{"key":"2023012512394046800_B8","first-page":"123","article-title":"Alignment-free phylogenetic reconstruction","volume-title":"Proc. RECOMB 2010","author":"Daskalakis","year":"2010"},{"key":"2023012512394046800_B9","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1186\/1471-2105-5-113","article-title":"MUSCLE: a multiple sequence alignment method with reduced time and space complexity","volume":"5","author":"Edgar","year":"2004","journal-title":"BMC Bioinf."},{"key":"2023012512394046800_B10","first-page":"217","article-title":"Local quartet splits of a binary tree infer all quartet splits via one dyadic inference rule","volume":"16","author":"Erd\u00f6s","year":"1997","journal-title":"Comput. Artif. Intell."},{"key":"2023012512394046800_B11","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1002\/(SICI)1098-2418(199903)14:2<153::AID-RSA3>3.0.CO;2-R","article-title":"A few logs suffice to build (almost) all trees (i)","volume":"14","author":"Erd\u00f6s","year":"1999","journal-title":"Random Struct. Algorith."},{"key":"2023012512394046800_B12","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/S0304-3975(99)00028-6","article-title":"A few logs suffice to build (almost) all trees (ii)","volume":"221","author":"Erd\u00f6s","year":"1999","journal-title":"Theor. Comput. Sci."},{"key":"2023012512394046800_B13","doi-asserted-by":"crossref","first-page":"548","DOI":"10.1080\/10635150590950371","article-title":"Simultaneous statistical multiple alignment and phylogeny reconstruction","volume":"54","author":"Fleissner","year":"2005","journal-title":"Syst. Biol."},{"key":"2023012512394046800_B14","first-page":"379","article-title":"Fast and reliable reconstruction of phylogenetic trees with short edges","volume-title":"Symp. Algorithms for Discrete Mathematics (SODA)","author":"Gronau","year":"2008"},{"key":"2023012512394046800_B15","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1093\/sysbio\/42.2.182","article-title":"An empirical test of bootstrapping as a method for assessing confidence in phylogenetic analysis","volume":"42","author":"Hillis","year":"1993","journal-title":"Syst. Biol."},{"key":"2023012512394046800_B16","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1080\/10635150701294741","article-title":"Is multiple-sequence alignment required for accurate inference of phylogeny?","volume":"56","author":"Hohl","year":"2007","journal-title":"Syst. Biol."},{"key":"2023012512394046800_B17","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1089\/106652799318337","article-title":"Disk-covering, a fast converging method for phylogenetic tree reconstruction","volume":"6","author":"Huson","year":"1999","journal-title":"J. Comput. Biol."},{"key":"2023012512394046800_B18","first-page":"118","article-title":"Solving large scale phylogenetic problems using DCM2","volume-title":"Proceedings of the Seventh International Conference on Intelligent Systems for Molecular Biology (ISMB)","author":"Huson","year":"1999"},{"key":"2023012512394046800_B19","doi-asserted-by":"crossref","first-page":"1924","DOI":"10.1137\/S0097539799361683","article-title":"A polynomial-time approximation scheme for inferring evolutionary trees from quartet topologies and its applications","volume":"30","author":"Jiang","year":"2001","journal-title":"SIAM J. Comput."},{"key":"2023012512394046800_B20","doi-asserted-by":"crossref","first-page":"372","DOI":"10.1093\/bioinformatics\/btl592","article-title":"PartTree: an algorithm to build an approximate tree from a large number of unaligned sequences","volume":"23","author":"Katoh","year":"2007","journal-title":"Bioinf."},{"key":"2023012512394046800_B21","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1093\/bib\/bbn013","article-title":"Recent developments in the MAFFT multiple sequence alignment program","volume":"9","author":"Katoh","year":"2008","journal-title":"Briefings in Bioinf."},{"key":"2023012512394046800_B22","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1016\/j.mbs.2005.11.003","article-title":"A signal-to-noise analysis of phylogeny estimation by neighbor-joining: insufficiency of polynomial length sequences","volume":"199","author":"Lacey","year":"2006","journal-title":"Math. Biosci."},{"key":"2023012512394046800_B23","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":"2023012512394046800_B24","article-title":"Multiple sequence alignment: a major challenge to large-scale phylogenetics","author":"Liu","year":"2010","journal-title":"PLoS Currents: Tree of Life."},{"key":"2023012512394046800_B25","doi-asserted-by":"crossref","first-page":"10557","DOI":"10.1073\/pnas.0409137102","article-title":"An algorithm for progressive multiple alignment of sequences with insertions","volume":"102","author":"Loytynoja","year":"2005","journal-title":"Proc. Natl Acad. Sci. USA."},{"key":"2023012512394046800_B26","first-page":"228","article-title":"Bayesian phylogenetic inference under a statistical indel model","volume-title":"Proc. Third International Workshop on Algorithms for Bioinformatics (WABI 2003)","author":"Lunter","year":"2003"},{"key":"2023012512394046800_B27","first-page":"343","article-title":"Sequence length requirements for phylogenetic methods","volume-title":"Proc. 2nd Int'l Workshop Algorithms in Bioinformatics (WABI'02)","author":"Moret","year":"2002"},{"key":"2023012512394046800_B28","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1093\/bioinformatics\/17.suppl_1.S190","article-title":"Designing fast converging phylogenetic methods","volume":"17","author":"Nakhleh","year":"2001","journal-title":"Bioinformatics"},{"key":"2023012512394046800_B29","first-page":"211","article-title":"The accuracy of fast phylogenetic methods for large datasets","volume-title":"Proceedings of the 7th Pacific Symposium on BioComputing (PSB02)","author":"Nakhleh","year":"2002"},{"key":"2023012512394046800_B30","article-title":"Improved methods for phylogenetics","volume-title":"PhD. Thesis","author":"Nelesen","year":"2009"},{"key":"2023012512394046800_B31","doi-asserted-by":"crossref","first-page":"2403","DOI":"10.1093\/bioinformatics\/btn457","article-title":"StatAlign: an extendable software package for joint Bayesian estimation of alignments and evolutionary trees","volume":"24","author":"Nov\u00e1k","year":"2008","journal-title":"Bioinformatics"},{"key":"2023012512394046800_B32","doi-asserted-by":"crossref","first-page":"e9490","DOI":"10.1371\/journal.pone.0009490","article-title":"FastTree 2 - approximately maximum-likelihood trees for large alignments","volume":"5","author":"Price","year":"2010","journal-title":"PLoS ONE"},{"key":"2023012512394046800_B33","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1080\/10635150590947041","article-title":"Joint Bayesian estimation of alignment and phylogeny","volume":"54","author":"Redelings","year":"2005","journal-title":"Syst. Biol."},{"key":"2023012512394046800_B34","doi-asserted-by":"crossref","first-page":"1376","DOI":"10.1126\/science.1182300","article-title":"Toward extracting all phylogenetic information by matrices of evolutionary distances","volume":"327","author":"Roch","year":"2010","journal-title":"Science"},{"key":"2023012512394046800_B35","first-page":"98","article-title":"Rec-I-DCM3: A fast algorithmic technique for reconstructing large phylogenetic trees","volume-title":"Proc. Comp. Syst. Bioinf. Conf. 2004","author":"Roshan","year":"2004"},{"key":"2023012512394046800_B36","doi-asserted-by":"crossref","DOI":"10.1186\/1471-2148-9-37","article-title":"Mega-phylogeny approach for comparative biology: an alternative to supertree and supermatrix approaches","volume":"9","author":"Smith","year":"2009","journal-title":"BMC Evol. Biol."},{"key":"2023012512394046800_B37","first-page":"196","article-title":"Performance study of phylogenetic methods: (unweighted) quartet methods and neighbor-joining","volume-title":"Proc. ACM\/SIAM Symposium on Discrete Algorithms (SODA01)","author":"St. John","year":"2001"},{"key":"2023012512394046800_B38","doi-asserted-by":"crossref","first-page":"2688","DOI":"10.1093\/bioinformatics\/btl446","article-title":"RAxML-VI-HPC: maximum likelihood-based phylogenetic analyses with thousands of taxa and mixed models","volume":"22","author":"Stamatakis","year":"2006","journal-title":"Bioinformatics"},{"key":"2023012512394046800_B39","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1093\/sysbio\/syr092","article-title":"SuperFine: fast and accurate supertree estimation","volume":"61","author":"Swenson","year":"2011","journal-title":"Syst. Biol."},{"key":"2023012512394046800_B40","doi-asserted-by":"crossref","first-page":"4673","DOI":"10.1093\/nar\/22.22.4673","article-title":"CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice","volume":"22","author":"Thompson","year":"1994","journal-title":"Nucl. Acids Res."},{"issue":"4","key":"2023012512394046800_B41","doi-asserted-by":"crossref","first-page":"1108","DOI":"10.1109\/TCBB.2009.68","article-title":"The impact of multiple protein sequence alignment on phylogenetic estimation","volume":"8","author":"Wang","year":"2011","journal-title":"IEEE\/ACM Trans. Comp. Biol. Bioinf."},{"key":"2023012512394046800_B42","doi-asserted-by":"crossref","DOI":"10.1371\/currents.RRN1308","article-title":"Standard maximum likelihood analyses of alignments with gaps can be statistically inconsistent","author":"Warnow","year":"2012","journal-title":"PLoS Currents: Tree of Life."},{"key":"2023012512394046800_B43","first-page":"186","article-title":"Absolute phylogeny: true trees from short sequences","volume-title":"Proc. 12th Ann. ACM\/SIAM Symposium on Discrete Algorithms (SODA01)","author":"Warnow","year":"2001"},{"key":"2023012512394046800_B44","doi-asserted-by":"crossref","first-page":"i559","DOI":"10.1093\/bioinformatics\/btm226","article-title":"Multiple alignment by aligning alignments","volume":"23","author":"Wheeler","year":"2007","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/28\/12\/i274\/48884169\/bioinformatics_28_12_i274.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/28\/12\/i274\/48884169\/bioinformatics_28_12_i274.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,25]],"date-time":"2024-04-25T06:50:46Z","timestamp":1714027846000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/28\/12\/i274\/268639"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,6,9]]},"references-count":44,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2012,6,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bts218","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2012,6,15]]},"published":{"date-parts":[[2012,6,9]]}}}