EURO-Online login
- New to EURO? Create an account
- I forgot my username and/or my password.
- Help with cookies
(important for IE8 users)
2416. A Large Neighborhood Search Matheuristic for the Balanced Minimum Evolution Problem
Invited abstract in session TC-20: Integrative Approaches in Health and Disease: From Molecular Structures to Clinical Outcomes, stream Computational Biology, Bioinformatics and Medicine.
Tuesday, 12:30-14:00Room: 45 (building: 116)
Authors (first author is the speaker)
| 1. | Henri Dehaybe
|
| Center for Operations Research and Econometrics, Université Catholique de Louvain | |
| 2. | Daniele Catanzaro
|
| Center for Operations Research and Econometrics, Université Catholique de Louvain | |
| 3. | Allan Sapucaia
|
| Amazon |
Abstract
The Balanced Minimum Evolution Problem (BMEP) is a hard combinatorial optimization network design problem arising in the field of phylogeny estimation. In this framework, the phylogeny is represented by an unrooted binary tree where the leaves are the individuals (the taxa), and the internal nodes represent speciation events. Given a matrix of estimated distances between each pair of taxon, the aim is to reconstruct the most accurate phylogeny according to the minimum evolution principle. We propose a Large Neighorhood Search (LNS) procedure to improve locally optimal solutions initially obtained by the state-of-the-art method (FastME). This LNS procedure works by iteratively destroying a subset of the incumbent unrooted binary tree, and then reconstructs it with a matheuristic-based repair operator. Due to its local search nature, this LNS procedure provides a scalable way of obtaining more accurate phylogenies for large datasets by directly improving the solutions found by the state-of-the-art method.
Keywords
- Combinatorial Optimization
- Computational Biology, Bioinformatics and Medicine
- Metaheuristics
Status: accepted
Back to the list of papers