{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T19:26:10Z","timestamp":1781119570941,"version":"3.54.1"},"reference-count":42,"publisher":"Oxford University Press (OUP)","issue":"11","license":[{"start":{"date-parts":[[2023,10,27]],"date-time":"2023-10-27T00:00:00Z","timestamp":1698364800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,11,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>The Balanced Minimum Evolution (BME) is a powerful distance based phylogenetic estimation model introduced by Desper and Gascuel and nowadays implemented in popular tools for phylogenetic analyses. It was proven to be computationally less demanding than more sophisticated estimation methods, e.g. maximum likelihood or Bayesian inference while preserving the statistical consistency and the ability to run with almost any kind of data for which a dissimilarity measure is available. BME can be stated in terms of a nonlinear non-convex combinatorial optimization problem, usually referred to as the Balanced Minimum Evolution Problem (BMEP). Currently, the state-of-the-art among approximate methods for the BMEP is represented by FastME (version 2.0), a software which implements several deterministic phylogenetic construction heuristics combined with a local search on specific neighbourhoods derived by classical topological tree rearrangements. These combinations, however, may not guarantee convergence to close-to-optimal solutions to the problem due to the lack of solution space exploration, a phenomenon which is exacerbated when tackling molecular datasets characterized by a large number of taxa.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>To overcome such convergence issues, in this article, we propose a novel metaheuristic, named PhyloES, which exploits the combination of an exploration phase based on Evolution Strategies, a special type of evolutionary algorithm, with a refinement phase based on two local search algorithms. Extensive computational experiments show that PhyloES consistently outperforms FastME, especially when tackling larger datasets, providing solutions characterized by a shorter tree length but also significantly different from the topological perspective.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>The software and the data are available at https:\/\/github.com\/andygaspar\/PHYLOES.<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btad660","type":"journal-article","created":{"date-parts":[[2023,10,27]],"date-time":"2023-10-27T17:27:12Z","timestamp":1698427632000},"source":"Crossref","is-referenced-by-count":5,"title":["An evolution strategy approach for the balanced minimum evolution problem"],"prefix":"10.1093","volume":"39","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-5496-5830","authenticated-orcid":false,"given":"Andrea","family":"Gasparin","sequence":"first","affiliation":[{"name":"Dipartimento di Ingegneria e Architettura, Universit\u00e0 degli Studi di Trieste , Trieste 34127, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3030-5772","authenticated-orcid":false,"given":"Federico Julian","family":"Camerota Verd\u00f9","sequence":"additional","affiliation":[{"name":"Dipartimento di Matematica e Geoscienze, Universit\u00e0 degli Studi di Trieste , Trieste 34128, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Daniele","family":"Catanzaro","sequence":"additional","affiliation":[{"name":"Center for Operations Research and Econometrics (CORE), Universit\u00e9 Catholique de Louvain , Louvain-la-Neuve 1348, Belgium"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5621-0934","authenticated-orcid":false,"given":"Lorenzo","family":"Castelli","sequence":"additional","affiliation":[{"name":"Dipartimento di Ingegneria e Architettura, Universit\u00e0 degli Studi di Trieste , Trieste 34127, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2023,10,27]]},"reference":[{"key":"2023111304140934900_btad660-B1","doi-asserted-by":"crossref","first-page":"1983","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":"2023111304140934900_btad660-B2","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780195099713.001.0001","volume-title":"Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms","author":"B\u00e4ck","year":"1996"},{"key":"2023111304140934900_btad660-B3","doi-asserted-by":"crossref","first-page":"105599","DOI":"10.1016\/j.asoc.2019.105599","article-title":"Multi-level diversity promotion strategies for grammar-guided genetic programming","volume":"83","author":"Bartoli","year":"2019","journal-title":"Applied Soft Computing"},{"key":"2023111304140934900_btad660-B4","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1109\/TCBB.2008.37","article-title":"Consistency of topological moves based on the balanced minimum evolution principle of phylogenetic inference","volume":"6","author":"Bordewich","year":"2009","journal-title":"IEEE\/ACM Trans Comput Biol Bioinform"},{"key":"2023111304140934900_btad660-B5","doi-asserted-by":"crossref","first-page":"1717","DOI":"10.1093\/oxfordjournals.molbev.a003994","article-title":"Genetic algorithms and parallel processing in maximum-likelihood phylogeny inference","volume":"19","author":"Brauer","year":"2002","journal-title":"Mol Biol Evol"},{"key":"2023111304140934900_btad660-B6","doi-asserted-by":"crossref","first-page":"276","DOI":"10.1287\/ijoc.1110.0455","article-title":"The balanced minimum evolution problem","volume":"24","author":"Catanzaro","year":"2012","journal-title":"INFORMS J Comput"},{"key":"2023111304140934900_btad660-B7","doi-asserted-by":"crossref","first-page":"753","DOI":"10.1016\/j.ejor.2015.02.019","article-title":"A branch-price-and-cut algorithm for the minimum evolution problem","volume":"244","author":"Catanzaro","year":"2015","journal-title":"Eur J Oper Res"},{"key":"2023111304140934900_btad660-B8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.ejor.2021.08.004","article-title":"A tutorial on the balanced minimum evolution problem","volume":"300","author":"Catanzaro","year":"2022","journal-title":"Eur J Oper Res"},{"key":"2023111304140934900_btad660-B9","doi-asserted-by":"crossref","first-page":"687","DOI":"10.1089\/106652702761034136","article-title":"Fast and accurate phylogeny reconstruction algorithms based on the minimum evolution principle","volume":"9","author":"Desper","year":"2002","journal-title":"J Comput Biol"},{"key":"2023111304140934900_btad660-B10","doi-asserted-by":"crossref","first-page":"587","DOI":"10.1093\/molbev\/msh049","article-title":"Theoretical foundations of the balanced minimum evolution method of phylogenetic inference and its relationship to the weighted least-squares tree fitting","volume":"21","author":"Desper","year":"2004","journal-title":"Mol Biol Evol"},{"key":"2023111304140934900_btad660-B11","volume-title":"Inferring Phylogenies","author":"Felsenstein","year":"2004"},{"key":"2023111304140934900_btad660-B12","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1093\/oxfordjournals.molbev.a025575","article-title":"A hidden markov model approach to variation among sites in rate of evolution","volume":"13","author":"Felsenstein","year":"1996","journal-title":"Mol Biol Evol"},{"key":"2023111304140934900_btad660-B13","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/j.orl.2011.10.003","article-title":"Approximating the balanced minimum evolution problem","volume":"40","author":"Fiorini","year":"2012","journal-title":"Oper Res Lett"},{"key":"2023111304140934900_btad660-B14","doi-asserted-by":"crossref","first-page":"685","DOI":"10.1093\/oxfordjournals.molbev.a025808","article-title":"BIONJ: an improved version of the NJ algorithm based on a simple model of sequence data","volume":"14","author":"Gascuel","year":"1997","journal-title":"Mol Biol Evol"},{"key":"2023111304140934900_btad660-B15","author":"Gascuel"},{"key":"2023111304140934900_btad660-B16","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198566106.001.0001","volume-title":"Mathematics of Evolution and Phylogeny","author":"Gascuel","year":"2005"},{"key":"2023111304140934900_btad660-B17","doi-asserted-by":"crossref","first-page":"1997","DOI":"10.1093\/molbev\/msl072","article-title":"Neighbor-joining revealed","volume":"23","author":"Gascuel","year":"2006","journal-title":"Mol Biol Evol"},{"key":"2023111304140934900_btad660-B18","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":"2023111304140934900_btad660-B19","doi-asserted-by":"crossref","first-page":"691","DOI":"10.1007\/s00180-010-0197-1","article-title":"Genetic algorithms with shrinking population size","volume":"25","author":"Hallam","year":"2010","journal-title":"Comput Stat"},{"key":"2023111304140934900_btad660-B20","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":"Hasegawa","year":"1981","journal-title":"J Mol Evol"},{"key":"2023111304140934900_btad660-B21","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":"2023111304140934900_btad660-B22","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":"2006","journal-title":"Bioinformatics"},{"key":"2023111304140934900_btad660-B23","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/B978-1-4832-3211-9.50009-7","volume-title":"Mammalian Protein Metabolism","author":"Jukes","year":"1969"},{"key":"2023111304140934900_btad660-B24","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"},{"key":"2023111304140934900_btad660-B25","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":"2023111304140934900_btad660-B26","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511819049","volume-title":"The Phylogenetic Handbook: A Practical Approach to Phylogenetic Analysis and Hypothesis Testing","author":"Lemey","year":"2009"},{"key":"2023111304140934900_btad660-B27","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":"2023111304140934900_btad660-B28","volume-title":"Essentials of Metaheuristics","author":"Luke"},{"key":"2023111304140934900_btad660-B29","first-page":"512","author":"Matsuda"},{"key":"2023111304140934900_btad660-B30","author":"Pardi","year":"2009"},{"key":"2023111304140934900_btad660-B31","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/s002390010065","article-title":"Direct calculation of a tree length using a distance matrix","volume":"51","author":"Pauplin","year":"2000","journal-title":"J Mol Evol"},{"key":"2023111304140934900_btad660-B32","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/s00500-005-0495-7","article-title":"Multi-objective evolutionary algorithms and phylogenetic inference with multiple data sets","volume":"10","author":"Poladian","year":"2006","journal-title":"Soft Comput"},{"key":"2023111304140934900_btad660-B33","author":"Rechenberg","year":"1973"},{"key":"2023111304140934900_btad660-B34","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":"2023111304140934900_btad660-B35","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1016\/S0092-8240(83)80039-1","article-title":"Numbering binary trees with labeled terminal vertices","volume":"45","author":"Rohlf","year":"1983","journal-title":"Bull Math Biol"},{"key":"2023111304140934900_btad660-B36","first-page":"945","article-title":"A simple method for estimating and testing minimum-evolution trees","volume":"9","author":"Rzhetsky","year":"1992","journal-title":"Mol Biol Evol"},{"key":"2023111304140934900_btad660-B37","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":"2023111304140934900_btad660-B38","volume-title":"Bioinformatics and Phylogenetics","author":"Schwartz","year":"2019"},{"key":"2023111304140934900_btad660-B39","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198509424.001.0001","volume-title":"Phylogenetics","author":"Semple","year":"2003"},{"key":"2023111304140934900_btad660-B40","first-page":"1409","article-title":"A statistical method for evaluating systematic relationships","volume":"38","author":"Sokal","year":"1958","journal-title":"Univ Kans Sci Bull"},{"key":"2023111304140934900_btad660-B41","doi-asserted-by":"crossref","first-page":"198b","DOI":"10.1109\/IPDPS.2005.90","volume-title":"Parallel and Distributed Processing Symposium, International","author":"Stamatakis","year":"2005"},{"key":"2023111304140934900_btad660-B42","volume-title":"Genetic Algorithm Approaches for the Phylogenetic Analysis of Large Biological Sequence Datasets Under the Maximum Likelihood Criterion","author":"Zwickl","year":"2006"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btad660\/52632909\/btad660.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/39\/11\/btad660\/53343748\/btad660.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/39\/11\/btad660\/53343748\/btad660.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,13]],"date-time":"2023-11-13T04:14:45Z","timestamp":1699848885000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/doi\/10.1093\/bioinformatics\/btad660\/7331089"}},"subtitle":[],"editor":[{"given":"Pier Luigi","family":"Martelli","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[2023,10,27]]},"references-count":42,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2023,11,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btad660","relation":{},"ISSN":["1367-4811"],"issn-type":[{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2023,11,1]]},"published":{"date-parts":[[2023,10,27]]},"article-number":"btad660"}}