The balanced minimum evolution problem under uncertain data

被引：2
作者：
Catanzaro, Daniele [1 ,2 ]
Labbe, Martine [1 ]
Pesenti, Raffaele [3 ]
机构：
[1] Univ Libre Brussels, Dept Comp Sci, B-1050 Brussels, Belgium
[2] Univ Groningen, Dept Econometr & Operat Res, NL-9700 AV Groningen, Netherlands
[3] Univ Ca Foscari, Dept Management, I-30121 Venice, Italy
来源：
DISCRETE APPLIED MATHEMATICS | 2013年 / 161卷 / 13-14期
关键词：
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;
D O I：
10.1016/j.dam.2013.03.012
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
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.
引用
收藏
页码：1789 / 1804
页数：16
相关论文
共 36 条
  • [1] [Anonymous], 2004, Inferring phylogenies
  • [2] [Anonymous], 2001, TECHNICAL REPORT
  • [3] Optimal solutions for the balanced minimum evolution problem
    Aringhieri, Roberto
    Catanzaro, Daniele
    Di Summa, Marco
    [J]. COMPUTERS & OPERATIONS RESEARCH, 2011, 38 (12) : 1845 - 1854
  • [4] On the complexity of the robust spanning tree problem with interval data
    Aron, ID
    Van Hentenryck, P
    [J]. OPERATIONS RESEARCH LETTERS, 2004, 32 (01) : 36 - 40
  • [5] Industrial applications of high-performance computing for phylogeny reconstruction
    Bader, DA
    Moret, BME
    Vawter, L
    [J]. COMMERCIAL APPLICATIONS FOR HIGH-PERFORMANCE COMPUTING, 2001, 4528 : 159 - 168
  • [6] BEYER W A, 1974, Mathematical Biosciences, V19, P9, DOI 10.1016/0025-5564(74)90028-5
  • [7] Testing for phylogenetic signal in comparative data: Behavioral traits are more labile
    Blomberg, SP
    Garland, T
    Ives, AR
    [J]. EVOLUTION, 2003, 57 (04) : 717 - 745
  • [8] Predicting the evolution of human influenza A
    Bush, RM
    Bender, CA
    Subbarao, K
    Cox, NJ
    Fitch, WM
    [J]. SCIENCE, 1999, 286 (5446) : 1921 - 1925
  • [9] A non-linear optimization procedure to estimate distances and instantaneous substitution rate matrices under the GTR model
    Catanzaro, D
    Pesenti, R
    Milinkovitch, MC
    [J]. BIOINFORMATICS, 2006, 22 (06) : 708 - 715
  • [10] The Balanced Minimum Evolution Problem
    Catanzaro, Daniele
    Labbe, Martine
    Pesenti, Raffaele
    Salazar-Gonzalez, Juan-Jose
    [J]. INFORMS JOURNAL ON COMPUTING, 2012, 24 (02) : 276 - 294
1234