Seminar Details
2021-03-02 (14h) : The Balanced Minimum Evolution Problem: Introduction, Combinatorics, and Recent Advances
At MS Teams
Organized by Mathematical Engineering
Speaker :
Daniele Catanzaro (UCLouvain)
Abstract :
Balanced Minimum Evolution (BME) is one of the most important criteria to estimate phylogenies from molecular data (such as DNA, RNA, codon sequences, or whole genomes).
This criterion can be stated in terms of a combinatorial optimization problem, called the Balanced Minimum Evolution Problem (BMEP), which is characterized by highly nonlinear objective
function and constraints and which is proven to be APX-hard. The optimal solution to the BMEP is highly desirable in practice due to its properties of statistical consistency. Unfortunately,
the exact methods currently described in the literature struggle to solve even relatively small instances of the problem. In this talk we introduce the audience to the BMEP. We present some
fundamental characteristics of the BMEP polytope, the connections between the BMEP and information entropy, as well as a massively parallel branch-and-bound algorithm which redefine
the current state-of-the-art for the problem.