New heuristics for phylogeny estimation under the balanced minimum evolution criterion
Bioinformatics · 2025
DOI: 10.1093/bioinformatics/btaf361 ↗Kurz gefasst
Fachartikel in der Zeitschrift Bioinformatics, 2025. Verfasst von Daniele Catanzaro und 2 weiteren Autor:innen. Beteiligte Einrichtung: Center for Operations Research and Econometrics, Université Catholique de Louvain, 1348 Louvain-la-Neuve, Belgium. Hauptthemen laut MEDLINE: Algorithms, Phylogeny, Heuristics, Computational Biology. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 29 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Belgian National Fund for Scientific Research.
Abstract (Originalsprache)
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≥3 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–like 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. Availability and implementation 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).
Schlagwörter
MeSH-Schlagwörter (MEDLINE)
Autor:innen und Institutionen
- Center for Operations Research and Econometrics, Université Catholique de Louvain, 1348 Louvain-la-Neuve, Belgium.
- Department of Management, Università Ca' Foscari, I-30121 Venezia, Italy.
ORCID-Profile: Daniele Catanzaro, Henri Dehaybe, Raffaele Pesenti
Förderung
- Belgian National Fund for Scientific Research
Zitieren
APA
Catanzaro, D., Dehaybe, H., & Pesenti, R. (2025). New heuristics for phylogeny estimation under the balanced minimum evolution criterion. Bioinformatics. https://doi.org/10.1093/bioinformatics/btaf361
Vancouver
Catanzaro D, Dehaybe H, Pesenti R. New heuristics for phylogeny estimation under the balanced minimum evolution criterion. Bioinformatics. 2025. doi:10.1093/bioinformatics/btaf361
BibTeX
@article{Catanzaro2025,
author = {Catanzaro, Daniele and Dehaybe, Henri and Pesenti, Raffaele},
title = {New heuristics for phylogeny estimation under the balanced minimum evolution criterion},
journal = {Bioinformatics},
year = {2025},
doi = {10.1093/bioinformatics/btaf361}
}
EUVIMED