The balanced minimum evolution problem under uncertain data

Daniele Catanzaro*, Martine Labbe, Raffaele Pesenti

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

2 Citations (Scopus)
77 Downloads (Pure)

Abstract

We investigate the Robust Deviation Balanced Minimum Evolution Problem (RDBMEP), a combinatorial optimization problem that arises in computational biology when the evolutionary distances from taxa are uncertain and varying inside intervals. By exploiting some fundamental properties of the objective function, we present a mixed integer programming model to exactly solve instances of the RDBMEP and discuss the biological impact of uncertainty on the solutions to the problem. Our results give perspective on the mathematics of the RDBMEP and suggest new directions to tackle phylogeny estimation problems affected by uncertainty. (c) 2013 Elsevier B.V. All rights reserved.

Original languageEnglish
Pages (from-to)1789-1804
Number of pages16
JournalDiscrete Applied Mathematics
Volume161
Issue number13-14
DOIs
Publication statusPublished - Sept-2013

Keywords

  • Network design
  • Combinatorial optimization
  • Robust optimization
  • Bender's decomposition
  • Computational biology
  • Balanced minimum evolution
  • Combinatorial inequalities
  • Kraft equality
  • SPANNING TREE PROBLEM
  • INTERVAL DATA
  • PHYLOGENY RECONSTRUCTION
  • MATRICES
  • MODEL

Cite this