{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T05:39:12Z","timestamp":1771652352425,"version":"3.50.1"},"reference-count":37,"publisher":"Oxford University Press (OUP)","issue":"Supplement_1","license":[{"start":{"date-parts":[[2022,6,27]],"date-time":"2022-06-27T00:00:00Z","timestamp":1656288000000},"content-version":"vor","delay-in-days":3,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Edmond J. Safra Center for Bioinformatics at Tel Aviv University"},{"name":"The Council for Higher Education"},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["993\/17"],"award-info":[{"award-number":["993\/17"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["802\/16"],"award-info":[{"award-number":["802\/16"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["2818\/21"],"award-info":[{"award-number":["2818\/21"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,6,24]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec><jats:title>Motivation<\/jats:title><jats:p>In recent years, full-genome sequences have become increasingly available and as a result many modern phylogenetic analyses are based on very long sequences, often with over 100\u00a0000 sites. Phylogenetic reconstructions of large-scale alignments are challenging for likelihood-based phylogenetic inference programs and usually require using a powerful computer cluster. Current tools for alignment trimming prior to phylogenetic analysis do not promise a significant reduction in the alignment size and are claimed to have a negative effect on the accuracy of the obtained tree.<\/jats:p><\/jats:sec><jats:sec><jats:title>Results<\/jats:title><jats:p>Here, we propose an artificial-intelligence-based approach, which provides means to select the optimal subset of sites and a formula by which one can compute the log-likelihood of the entire data based on this subset. Our approach is based on training a regularized Lasso-regression model that optimizes the log-likelihood prediction accuracy while putting a constraint on the number of sites used for the approximation. We show that computing the likelihood based on 5% of the sites already provides accurate approximation of the tree likelihood based on the entire data. Furthermore, we show that using this Lasso-based approximation during a tree search decreased running-time substantially while retaining the same tree-search performance.<\/jats:p><\/jats:sec><jats:sec><jats:title>Availability and implementation<\/jats:title><jats:p>The code was implemented in Python version 3.8 and is available through GitHub (https:\/\/github.com\/noaeker\/lasso_positions_sampling). The datasets used in this paper were retrieved from Zhou et al. (2018) as described in section 3.<\/jats:p><\/jats:sec><jats:sec><jats:title>Supplementary information<\/jats:title><jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p><\/jats:sec>","DOI":"10.1093\/bioinformatics\/btac252","type":"journal-article","created":{"date-parts":[[2022,4,14]],"date-time":"2022-04-14T11:10:15Z","timestamp":1649934615000},"page":"i118-i124","source":"Crossref","is-referenced-by-count":7,"title":["A LASSO-based approach to sample sites for phylogenetic tree search"],"prefix":"10.1093","volume":"38","author":[{"given":"Noa","family":"Ecker","sequence":"first","affiliation":[{"name":"The Shmunis School of Biomedicine and Cancer Research, George S. Wise Faculty of Life Sciences, Tel Aviv University , Tel Aviv 69978, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dana","family":"Azouri","sequence":"additional","affiliation":[{"name":"The Shmunis School of Biomedicine and Cancer Research, George S. Wise Faculty of Life Sciences, Tel Aviv University , Tel Aviv 69978, Israel"},{"name":"School of Plant Sciences and Food Security, George S. Wise Faculty of Life Sciences, Tel Aviv University , Tel Aviv 69978, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ben","family":"Bettisworth","sequence":"additional","affiliation":[{"name":"Computational Molecular Evolution Group, Heidelberg Institute for Theoretical Studies , 69118 Heidelberg, Germany"},{"name":"Institute of Theoretical Informatics, Karlsruhe Institute of Technology , 76128 Karlsruhe, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexandros","family":"Stamatakis","sequence":"additional","affiliation":[{"name":"Computational Molecular Evolution Group, Heidelberg Institute for Theoretical Studies , 69118 Heidelberg, Germany"},{"name":"Institute of Theoretical Informatics, Karlsruhe Institute of Technology , 76128 Karlsruhe, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yishay","family":"Mansour","sequence":"additional","affiliation":[{"name":"The Blavatnik School of Computer Science, Raymond & Beverly Sackler Faculty of Exact Sciences, Tel Aviv University , Tel Aviv 69978, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Itay","family":"Mayrose","sequence":"additional","affiliation":[{"name":"School of Plant Sciences and Food Security, George S. Wise Faculty of Life Sciences, Tel Aviv University , Tel Aviv 69978, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9463-2575","authenticated-orcid":false,"given":"Tal","family":"Pupko","sequence":"additional","affiliation":[{"name":"The Shmunis School of Biomedicine and Cancer Research, George S. Wise Faculty of Life Sciences, Tel Aviv University , Tel Aviv 69978, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2022,6,27]]},"reference":[{"key":"2023041407560664200_","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00026-001-8006-8","article-title":"Subtree transfer operations and their induced metrics on evolutionary trees","volume":"5","author":"Allen","year":"2001","journal-title":"Ann. Comb"},{"key":"2023041407560664200_","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1038\/s41467-021-22073-8","article-title":"Harnessing machine learning to guide phylogenetic-tree search algorithms","volume":"12","author":"Azouri","year":"2021","journal-title":"Nat. Commun"},{"key":"2023041407560664200_","doi-asserted-by":"crossref","first-page":"i97","DOI":"10.1093\/bioinformatics\/bti1027","article-title":"Maximum likelihood of evolutionary trees: hardness and approximation","volume":"21","author":"Chor","year":"2005","journal-title":"Bioinformatics"},{"key":"2023041407560664200_","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1016\/j.tree.2009.01.009","article-title":"Gene tree discordance, phylogenetic inference and the multispecies coalescent","volume":"24","author":"Degnan","year":"2009","journal-title":"Trends Ecol. Evol"},{"key":"2023041407560664200_","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1007\/BF01734359","article-title":"Journal of molecular evolution evolutionary trees from DNA sequences: a maximum likelihood approach","volume":"17","author":"Felsenstein","year":"1981","journal-title":"J. Mol. Evol"},{"key":"2023041407560664200_","volume-title":"Inferring Phylogenies","author":"Felsenstein","year":"2004"},{"key":"2023041407560664200_","doi-asserted-by":"crossref","first-page":"782","DOI":"10.1038\/425782a","article-title":"Ending incongruence","volume":"425","author":"Gee","year":"2003","journal-title":"Nature"},{"key":"2023041407560664200_","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":"2023041407560664200_","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1186\/1471-2105-11-379","article-title":"MetaPIGA v2.0: maximum likelihood large phylogeny estimation using the metapopulation genetic algorithm and other stochastic heuristics","volume":"11","author":"Helaers","year":"2010","journal-title":"BMC Bioinformatics"},{"key":"2023041407560664200_","doi-asserted-by":"crossref","first-page":"4338","DOI":"10.1093\/bioinformatics\/bti713","article-title":"Improving the efficiency of SPR moves in phylogenetic tree search methods based on maximum likelihood","volume":"21","author":"Hordijk","year":"2005","journal-title":"Bioinformatics"},{"key":"2023041407560664200_","doi-asserted-by":"crossref","first-page":"1320","DOI":"10.1126\/science.1253451","article-title":"Whole-genome analyses resolve early branches in the tree of life of modern birds","volume":"346","author":"Jarvis","year":"2014","journal-title":"Science"},{"key":"2023041407560664200_","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1093\/sysbio\/syp061","article-title":"Estimating species trees: methods of phylogenetic analysis when there is incongruence across genes","volume":"58","author":"Knowles","year":"2009","journal-title":"Syst. Biol"},{"key":"2023041407560664200_","first-page":"205","article-title":"Efficient detection of repeating sites to accelerate phylogenetic likelihood calculations","volume":"66","author":"Kobert","year":"2017","journal-title":"Syst. Biol"},{"key":"2023041407560664200_","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":"2023041407560664200_","doi-asserted-by":"crossref","first-page":"4674","DOI":"10.1093\/molbev\/msab227","article-title":"Evolutionary sparse learning for phylogenomics","volume":"38","author":"Kumar","year":"2021","journal-title":"Mol. Biol. Evol"},{"key":"2023041407560664200_","doi-asserted-by":"crossref","first-page":"4325","DOI":"10.1073\/pnas.1720115115","article-title":"Earth BioGenome project: sequencing life for the future of life","volume":"115","author":"Lewin","year":"2018","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023041407560664200_","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1093\/oxfordjournals.molbev.a025924","article-title":"A genetic algorithm for maximum-likelihood phylogeny inference using nucleotide sequence data","volume":"15","author":"Lewis","year":"1998","journal-title":"Mol. Biol. Evol"},{"key":"2023041407560664200_","doi-asserted-by":"crossref","first-page":"423","DOI":"10.1016\/0022-5193(73)90251-8","article-title":"An iterative approach from the standpoint of the additive hypothesis to the dendrogram problem posed by molecular data sets","volume":"38","author":"Moore","year":"1973","journal-title":"J. Theor. Biol"},{"key":"2023041407560664200_","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":"2023041407560664200_","first-page":"568","article-title":"Relationships between gene trees and species trees","volume":"5","author":"Pamilo","year":"1988","journal-title":"Mol. Biol. Evol"},{"key":"2023041407560664200_","first-page":"2825","article-title":"Scikit-learn: machine learning in Python","volume":"12","author":"Pedregosa","year":"2011","journal-title":"J. Mach. Learn. Res"},{"key":"2023041407560664200_","author":"Pinheiro","year":"2020","journal-title":"nlme: Linear and Nonlinear Mixed Effects Models. R package version 3.1\u2013151"},{"key":"2023041407560664200_","doi-asserted-by":"crossref","first-page":"S71","DOI":"10.1093\/bioinformatics\/18.suppl_1.S71","article-title":"Rate4Site: an algorithmic tool for the identification of functional regions in proteins by surface mapping of evolutionary determinants within their homologues","volume":"18","author":"Pupko","year":"2002","journal-title":"Bioinformatics"},{"key":"2023041407560664200_","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0095-8956(71)90020-7","article-title":"Comparison of labeled trees with valency three","volume":"11","author":"Robinson","year":"1971","journal-title":"J. Comb. Theory Ser. B"},{"key":"2023041407560664200_","doi-asserted-by":"crossref","first-page":"539","DOI":"10.1093\/sysbio\/sys029","article-title":"Mrbayes 3.2: efficient Bayesian phylogenetic inference and model choice across a large model space","volume":"61","author":"Ronquist","year":"2012","journal-title":"Syst. Biol"},{"key":"2023041407560664200_","first-page":"406","article-title":"The neighbor-joining method: a new method for reconstructing phylogenetic trees","volume":"4","author":"Saitou","year":"1987","journal-title":"Mol. Biol. Evol"},{"key":"2023041407560664200_","doi-asserted-by":"crossref","first-page":"eabd0079","DOI":"10.1126\/sciadv.abd0079","article-title":"Genome-scale phylogeny and contrasting modes of genome evolution in the fungal phylum Ascomycota","volume":"6","author":"Shen","year":"2020","journal-title":"Sci. Adv"},{"key":"2023041407560664200_","first-page":"8","volume-title":"2005","author":"Stamatakis","year":"2005"},{"key":"2023041407560664200_","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 of large phylogenies","volume":"30","author":"Stamatakis","year":"2014","journal-title":"Bioinformatics"},{"key":"2023041407560664200_","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1007\/s11265-007-0067-4","article-title":"Exploring new search algorithms and hardware for phylogenetics: RAxML meets the IBM cell","volume":"48","author":"Stamatakis","year":"2007","journal-title":"J. VLSI Sign. Process. Syst. Sign. Process"},{"key":"2023041407560664200_","doi-asserted-by":"crossref","first-page":"e3001007","DOI":"10.1371\/journal.pbio.3001007","article-title":"ClipKIT: a multiple sequence alignment trimming software for accurate phylogenomic inference","volume":"18","author":"Steenwyk","year":"2020","journal-title":"PLoS Biol"},{"key":"2023041407560664200_","doi-asserted-by":"crossref","first-page":"778","DOI":"10.1093\/sysbio\/syv033","article-title":"Current methods for automated filtering of multiple sequence alignments frequently worsen Single-Gene phylogenetic inference","volume":"64","author":"Tan","year":"2015","journal-title":"Syst. Biol"},{"key":"2023041407560664200_","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1111\/j.2517-6161.1996.tb02080.x","article-title":"Regression shrinkage and selection via the lasso","volume":"58","author":"Tibshirani","year":"1996","journal-title":"J. R. Stat. Soc. Ser. B"},{"key":"2023041407560664200_","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":"2023041407560664200_","author":"Zhang","year":"2021"},{"key":"2023041407560664200_","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":"2023041407560664200_","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1111\/j.1467-9868.2005.00503.x","article-title":"Regularization and variable selection via the elastic net","volume":"67","author":"Zou","year":"2005","journal-title":"J. R. Stat. Soc. B"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/38\/Supplement_1\/i118\/49886831\/btac252.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/38\/Supplement_1\/i118\/49886831\/btac252.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,22]],"date-time":"2024-09-22T06:55:48Z","timestamp":1726988148000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/38\/Supplement_1\/i118\/6617489"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,24]]},"references-count":37,"journal-issue":{"issue":"Supplement_1","published-print":{"date-parts":[[2022,6,24]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btac252","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2022,7,1]]},"published":{"date-parts":[[2022,6,24]]}}}