{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T20:00:24Z","timestamp":1774555224427,"version":"3.50.1"},"reference-count":19,"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":2315,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.0\/uk\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010,6,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: The current molecular data explosion poses new challenges for large-scale phylogenomic analyses that can comprise hundreds or even thousands of genes. A property that characterizes phylogenomic datasets is that they tend to be gappy, i.e. can contain taxa with (many and disparate) missing genes. In current phylogenomic analyses, this type of alignment gappyness that is induced by missing data frequently exceeds 90%. We present and implement a generally applicable mechanism that allows for reducing memory footprints of likelihood-based [maximum likelihood (ML) or Bayesian] phylogenomic analyses proportional to the amount of missing data in the alignment. We also introduce a set of algorithmic rules to efficiently conduct tree searches via subtree pruning and re-grafting moves using this mechanism.<\/jats:p>\n               <jats:p>Results: On a large phylogenomic DNA dataset with 2177 taxa, 68 genes and a gappyness of 90%, we achieve a memory footprint reduction from 9 GB down to 1 GB, a speedup for optimizing ML model parameters of 11, and accelerate the Subtree Pruning Regrafting tree search phase by factor 16. Thus, our approach can be deployed to improve efficiency for the two most important resources, CPU time and memory, by up to one order of magnitude.<\/jats:p>\n               <jats:p>Availability: Current open-source version of RAxML v7.2.6 available at http:\/\/wwwkramer.in.tum.de\/exelixis\/software.html.<\/jats:p>\n               <jats:p>Contact: \u00a0stamatak@cs.tum.edu<\/jats:p>","DOI":"10.1093\/bioinformatics\/btq205","type":"journal-article","created":{"date-parts":[[2010,6,7]],"date-time":"2010-06-07T07:28:13Z","timestamp":1275895693000},"page":"i132-i139","source":"Crossref","is-referenced-by-count":99,"title":["Time and memory efficient likelihood-based tree searches on phylogenomic alignments with missing data"],"prefix":"10.1093","volume":"26","author":[{"given":"Alexandros","family":"Stamatakis","sequence":"first","affiliation":[{"name":"The Exelixis Lab (I12), Department of Computer Science, Technische Universit\u00e4t M\u00fcnchen, Boltzmannstr. 3, D-85748, Garching b. M\u00fcnchen, Germany"}]},{"given":"Nikolaos","family":"Alachiotis","sequence":"additional","affiliation":[{"name":"The Exelixis Lab (I12), Department of Computer Science, Technische Universit\u00e4t M\u00fcnchen, Boltzmannstr. 3, D-85748, Garching b. M\u00fcnchen, Germany"}]}],"member":"286","published-online":{"date-parts":[[2010,6,1]]},"reference":[{"key":"2023012508043395400_B1","article-title":"Accuracy and performance of single versus double precision arithmetics for Maximum Likelihood Phylogeny Reconstruction","volume-title":"Proceedings of PBC09, Parallel Biocomputing Workshop","author":"Berger","year":"2009"},{"key":"2023012508043395400_B2","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1007\/BF01734359","article-title":"Evolutionary trees from DNA sequences: a maximum likelihood approach","volume":"17","author":"Felsenstein","year":"1981","journal-title":"J. Mol. Evol."},{"key":"2023012508043395400_B3","doi-asserted-by":"crossref","first-page":"3889","DOI":"10.1098\/rstb.2008.0182","article-title":"Introduction. statistical and computational challenges in molecular phylogenetics and evolution","volume":"363","author":"Goldman","year":"2008","journal-title":"Philos. Trans. R. Soc. B, Biol. Sci."},{"key":"2023012508043395400_B4","doi-asserted-by":"crossref","first-page":"696","DOI":"10.1080\/10635150390235520","article-title":"A simple, fast and accurate algorithm to estimate large phylogenies by Maximum Likelihood","volume":"52","author":"Guindon","year":"2003","journal-title":"Syst. Biol."},{"key":"2023012508043395400_B5","doi-asserted-by":"crossref","first-page":"4261","DOI":"10.1098\/rspb.2009.0896","article-title":"Rooting the bilaterian tree with scalable phylogenomic and supercomputing tools","volume":"276","author":"Hejnol","year":"2009","journal-title":"Proc. R. Soc. B"},{"key":"2023012508043395400_B6","author":"Lartillot","year":"2007","journal-title":"PhyloBayes. v2. 3."},{"key":"2023012508043395400_B7","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1109\/ICPP.2009.30","article-title":"Fine-grain parallelism for the phylogenetic likelihood functions on Multi-cores, Cell\/BE, and GPUs","volume-title":"Proceedings of the 2009 International Conference on Parallel Processing","author":"Pratas","year":"2009"},{"key":"2023012508043395400_B8","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":"2023012508043395400_B9","doi-asserted-by":"crossref","first-page":"1572","DOI":"10.1093\/bioinformatics\/btg180","article-title":"MrBayes 3: Bayesian phylogenetic inference under mixed models","volume":"19","author":"Ronquist","year":"2003","journal-title":"Bioinformatics"},{"key":"2023012508043395400_B10","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":"2023012508043395400_B11","doi-asserted-by":"crossref","DOI":"10.1109\/IPDPS.2006.1639535","article-title":"Phylogenetic models of Rate Heterogeneity: A High Performance Computing Perspective","volume-title":"Proceedings of IPDPS2006 HICOMB Workshop, Proceedings on CD","author":"Stamatakis","year":"2006"},{"key":"2023012508043395400_B12","doi-asserted-by":"crossref","first-page":"424","DOI":"10.1007\/978-3-540-88436-1_36","article-title":"Exploiting Fine-Grained Parallelism in the Phylogenetic Likelihood Function with MPI, Pthreads, and OpenMP: A Performance Study","volume-title":"Partition Recognition for Bioinformatics","author":"Stamatakis","year":"2008"},{"key":"2023012508043395400_B13","doi-asserted-by":"crossref","first-page":"3977","DOI":"10.1098\/rstb.2008.0163","article-title":"Efficient computation of the phylogenetic likelihood function on multi-gene alignments and multi-core architectures","volume":"363","author":"Stamatakis","year":"2008","journal-title":"Philos. Trans. R. Soc. B, Biol. Sci."},{"key":"2023012508043395400_B14","doi-asserted-by":"crossref","first-page":"1370","DOI":"10.1093\/bioinformatics\/btp244","article-title":"Many-core algorithms for statistical phylogenetics","volume":"25","author":"Suchard","year":"2009","journal-title":"Bioinformatics"},{"key":"2023012508043395400_B15","first-page":"57","article-title":"Some probabilistic and statistical problems in the analysis of DNA sequences","volume-title":"Some Mathematical Questions in Biology-DNA Sequence Analysis","author":"Tavar\u00e9","year":"1986"},{"key":"2023012508043395400_B16","volume-title":"Advances in Computers.","author":"Tzeng","year":"2006"},{"key":"2023012508043395400_B17","doi-asserted-by":"crossref","first-page":"691","DOI":"10.1093\/oxfordjournals.molbev.a003851","article-title":"A general empirical model of protein evolution derived from multiple protein families using a maximum-likelihood approach","volume":"18","author":"Whelan","year":"2001","journal-title":"Mol. Biol. Evol."},{"key":"2023012508043395400_B18","doi-asserted-by":"crossref","first-page":"306","DOI":"10.1007\/BF00160154","article-title":"Maximum likelihood phylogenetic estimation from DNA sequences with variable rates over sites","volume":"39","author":"Yang","year":"1994","journal-title":"J. Mol. Evol."},{"key":"2023012508043395400_B19","article-title":"Genetic Algorithm Approaches for the Phylogenetic Analysis of Large Biological Sequence Datasets under the Maximum Likelihood Criterion","volume-title":"PhD Thesis","author":"Zwickl","year":"2006"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/12\/i132\/48856713\/bioinformatics_26_12_i132.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/12\/i132\/48856713\/bioinformatics_26_12_i132.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T08:08:12Z","timestamp":1674634092000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/26\/12\/i132\/284771"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6,1]]},"references-count":19,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2010,6,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btq205","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2010,6,15]]},"published":{"date-parts":[[2010,6,1]]}}}