Pavel Skums
We show how SDP relaxations can be designed and used for phylogenetic inference. We consider the Balanced Minimum Evolution (BME) problem, a widely used model in distance-based phylogenetics, and introduce an algorithm that combines an SDP relaxation with a rounding scheme that iteratively converts relaxed solutions into valid tree topologies. Experiments on simulated and empirical datasets show that the method enables accurate phylogenetic reconstruction.
MOTIVATION: In this study, we investigate the application of Semidefinite Programming (SDP) to phylogenetics. SDP is a powerful optimization framework that seeks to optimize a linear objective function over the cone of positive semidefinite matrices. As a convex optimization problem, SDP generalizes linear programming and provides relaxations for many combinatorial optimization problems. However, despite its many applications, SDP remains largely unused in computational biology.
RESULTS: We show how SDP relaxations can be designed and used for phylogenetic inference. We consider the Balanced Minimum Evolution (BME) problem, a widely used model in distance-based phylogenetics, and introduce an algorithm that combines an SDP relaxation with a rounding scheme that iteratively converts relaxed solutions into valid tree topologies. Experiments on simulated and empirical datasets show that the method enables accurate phylogenetic reconstruction.
AVAILABILITY AND IMPLEMENTATION: The code is available at https://github.com/compbel/SDPTree (DOI 10.5281/zenodo.20838318).
SUPPLEMENTARY INFORMATION: Supplementary results and figures are available at Bioinformatics online.