EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

New heuristics for phylogeny estimation under the balanced minimum evolution criterion

Daniele Catanzaro iD, Henri Dehaybe iD, Raffaele Pesenti iD

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.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

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)

AlgorithmsPhylogenyHeuristicsComputational BiologyEvolution, MolecularSoftware

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}
}
Kostenlos starten →