Related Experiment Video
Updated: Aug 8, 2026

A Practical Guide to Phylogenetics for Nonexperts
Published on: February 5, 2014
Phylogenetic inference under the balanced minimum evolution criterion via semidefinite programming
1School of Computing, University of Connecticut, Storrs, CT 06269, United States.
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 and data are available at https://github.com/compbel/SDPTree (DOI 10.5281/zenodo.20838318).
Related Concept Videos
Evolutionary Relationships through Genome Comparisons
Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
Microbial Phylogeny
Multi-species Conserved Sequences
Although the genome of each species varies greatly from each other, a few sequences are highly conserved. Such conserved DNA...
Convergent Evolution
One-Compartment Open Model: Wagner-Nelson and Loo Riegelman Method for ka Estimation
On...

