{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T15:51:55Z","timestamp":1768924315255,"version":"3.49.0"},"reference-count":29,"publisher":"Oxford University Press (OUP)","issue":"7","license":[{"start":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:00:00Z","timestamp":1750291200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100002661","name":"Belgian National Fund for Scientific Research","doi-asserted-by":"publisher","award":["FNRS PDR 40007831"],"award-info":[{"award-number":["FNRS PDR 40007831"]}],"id":[{"id":"10.13039\/501100002661","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,7,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>\u2002<\/jats:title>\n                  <jats:p>Summary: Recent advances in the combinatorics of the Balanced Minimum Evolution Problem (BMEP) enabled the characterization of the mathematical properties that a symmetric integer matrix of order n\u22653 must satisfy to encode the Path-Length Matrix of an Unrooted Binary Tree. This result, together with the identification of fundamental facet-defining inequalities for the convex hull of BMEP solutions, has led to an integer linear programming formulation that currently serves as the reference exact solution algorithm. Here, we show how to exploit these advances to improve the approximation algorithms for the problem. We first leverage the tight linear programming relaxation of this formulation to develop an enhanced Neighbor Joining\u2013like heuristic. Next, we embed this heuristic into a Beam Search framework to further improve the quality of the solutions. Computational experiments show that the proposed algorithms outperform existing heuristics, making their use highly desirable in practice.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>Codes and data are available at https:\/\/github.com\/HenriDeh\/BME_BeamSearch.git and archived at https:\/\/zenodo.org\/records\/15631441 (DOI: 10.5281\/zenodo.15631440).<\/jats:p>\n               <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btaf361","type":"journal-article","created":{"date-parts":[[2025,6,27]],"date-time":"2025-06-27T17:19:01Z","timestamp":1751044741000},"source":"Crossref","is-referenced-by-count":1,"title":["New heuristics for phylogeny estimation under the balanced minimum evolution criterion"],"prefix":"10.1093","volume":"41","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9427-1562","authenticated-orcid":false,"given":"Daniele","family":"Catanzaro","sequence":"first","affiliation":[{"name":"Center for Operations Research and Econometrics, Universit\u00e9 Catholique de Louvain , 1348 Louvain-la-Neuve,","place":["Belgium"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1276-9859","authenticated-orcid":false,"given":"Henri","family":"Dehaybe","sequence":"additional","affiliation":[{"name":"Center for Operations Research and Econometrics, Universit\u00e9 Catholique de Louvain , 1348 Louvain-la-Neuve,","place":["Belgium"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5890-4238","authenticated-orcid":false,"given":"Raffaele","family":"Pesenti","sequence":"additional","affiliation":[{"name":"Department of Management, Universit\u00e0 Ca\u2019 Foscari , I-30121 Venezia,","place":["Italy"]}]}],"member":"286","published-online":{"date-parts":[[2025,6,19]]},"reference":[{"key":"2025071304171100000_btaf361-B1","doi-asserted-by":"crossref","first-page":"48","DOI":"10.1016\/0095-8956(74)90047-1","article-title":"A note on the metric properties of trees","volume":"17","author":"Buneman","year":"1974","journal-title":"J Comb Theory"},{"key":"2025071304171100000_btaf361-B2","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":"2025071304171100000_btaf361-B3","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1016\/j.orl.2020.04.010","article-title":"An information theory perspective on the balanced minimum evolution problem","volume":"48","author":"Catanzaro","year":"2020","journal-title":"Oper Res Lett"},{"key":"2025071304171100000_btaf361-B4","doi-asserted-by":"crossref","first-page":"708","DOI":"10.1093\/bioinformatics\/btk001","article-title":"A non-linear optimization procedure to estimate distances and instantaneous substitution rate matrices under the GTR model","volume":"22","author":"Catanzaro","year":"2006","journal-title":"Bioinformatics"},{"key":"2025071304171100000_btaf361-B5","doi-asserted-by":"crossref","first-page":"100570","DOI":"10.1016\/j.disopt.2020.100570","article-title":"On the balanced minimum evolution polytope","volume":"36","author":"Catanzaro","year":"2020","journal-title":"Discrete Optim"},{"key":"2025071304171100000_btaf361-B6","doi-asserted-by":"crossref","DOI":"10.1007\/s10107-025-02226-z","article-title":"Optimizing over path-length matrices of unrooted binary trees","author":"Catanzaro","year":"2025","journal-title":"Math Program"},{"key":"2025071304171100000_btaf361-B7","doi-asserted-by":"crossref","first-page":"1202","DOI":"10.1007\/s11538-010-9556-x","article-title":"Polyhedral geometry of phylogenetic rogue taxa","volume":"73","author":"Cueto","year":"2011","journal-title":"Bull Math Biol"},{"key":"2025071304171100000_btaf361-B8","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":"2025071304171100000_btaf361-B9","volume-title":"Inferring Phylogenies","author":"Felsenstein","year":"2004"},{"key":"2025071304171100000_btaf361-B10","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":"2025071304171100000_btaf361-B11","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1007\/s00285-015-0957-1","article-title":"Facets of the balanced minimal evolution polytope","volume":"73","author":"Forcey","year":"2016","journal-title":"J Math Biol"},{"key":"2025071304171100000_btaf361-B12","doi-asserted-by":"crossref","first-page":"975","DOI":"10.1007\/s11538-017-0264-7","article-title":"Split-facets for balanced minimal evolution polytopes and the permutoassociahedron","volume":"79","author":"Forcey","year":"2017","journal-title":"Bull Math Biol"},{"key":"2025071304171100000_btaf361-B13","doi-asserted-by":"crossref","first-page":"2321","DOI":"10.1007\/s11590-020-01677-x","article-title":"On the approximability of the fixed-tree balanced minimum evolution problem","volume":"15","author":"Frohn","year":"2021","journal-title":"Optim Lett"},{"key":"2025071304171100000_btaf361-B14","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198566106.001.0001","volume-title":"Mathematics of Evolution and Phylogeny","author":"Gascuel","year":"2005"},{"key":"2025071304171100000_btaf361-B15","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":"2025071304171100000_btaf361-B16","doi-asserted-by":"crossref","first-page":"btad660","DOI":"10.1093\/bioinformatics\/btad660","article-title":"An evolution strategy approach for the balanced minimum evolution problem","volume":"39","author":"Gasparin","year":"2023","journal-title":"Bioinformatics"},{"key":"2025071304171100000_btaf361-B17","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":"2025071304171100000_btaf361-B18","doi-asserted-by":"crossref","first-page":"2627","DOI":"10.1007\/s11538-011-9640-x","article-title":"Optimality of the neighbor joining algorithm and faces of the balanced minimum evolution polytope","volume":"73","author":"Haws","year":"2011","journal-title":"Bull Math Biol"},{"key":"2025071304171100000_btaf361-B19","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":"2025071304171100000_btaf361-B20","author":"Lowerre","year":"1976"},{"key":"2025071304171100000_btaf361-B21","author":"Pardi","year":"2009"},{"key":"2025071304171100000_btaf361-B22","doi-asserted-by":"crossref","first-page":"1820","DOI":"10.1007\/s11538-010-9510-y","article-title":"Robustness of phylogenetic inference based on minimum evolution","volume":"72","author":"Pardi","year":"2010","journal-title":"Bull Math Biol"},{"key":"2025071304171100000_btaf361-B23","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":"2025071304171100000_btaf361-B25","article-title":"The neighbor-joining method: a new method for reconstructing phylogenetic trees","author":"Saitou","year":"1987","journal-title":"Mol Biol Evol"},{"key":"2025071304171100000_btaf361-B26","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/978-3-030-10837-3_11","volume-title":"Bioinformatics and Phylogenetics. Computational Biology","author":"Schwartz","year":"2019"},{"key":"2025071304171100000_btaf361-B27","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1016\/S0196-8858(03)00098-8","article-title":"Cyclic permutations and evolutionary trees","volume":"32","author":"Semple","year":"2004","journal-title":"Adv Appl Math"},{"key":"2025071304171100000_btaf361-B28","doi-asserted-by":"crossref","first-page":"343","DOI":"10.2140\/pjm.1967.21.343","article-title":"Concerning nonnegative matrices and doubly stochastic matrices","volume":"21","author":"Sinkhorn","year":"1967","journal-title":"Pacific J Math"},{"key":"2025071304171100000_btaf361-B29","author":"Stamatakis","year":"2005"},{"key":"2025071304171100000_btaf361-B30","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0022-5193(77)90351-4","article-title":"Additive evolutionary trees","volume":"64","author":"Waterman","year":"1977","journal-title":"J Theor Biol"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btaf361\/63528024\/btaf361.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/41\/7\/btaf361\/63528024\/btaf361.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/41\/7\/btaf361\/63528024\/btaf361.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,13]],"date-time":"2025-07-13T08:17:21Z","timestamp":1752394641000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/doi\/10.1093\/bioinformatics\/btaf361\/8169325"}},"subtitle":[],"editor":[{"given":"Russell","family":"Schwartz","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2025,6,19]]},"references-count":29,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2025,7,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btaf361","relation":{},"ISSN":["1367-4811"],"issn-type":[{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2025,7]]},"published":{"date-parts":[[2025,6,19]]},"article-number":"btaf361"}}