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 条

[11] Catanzaro D, 2011, MATHEMATICAL APPROACHES TO POLYMER SEQUENCE ANALYSIS AND RELATED PROBLEMS, P149, DOI 10.1007/978-1-4419-6800-5_8
[12] The Minimum Evolution Problem: Overview and Classification
Catanzaro, Daniele
[J]. NETWORKS, 2009, 53 (02) : 112 - 125
[13] Mathematical Models to Reconstruct Phylogenetic Trees Under the Minimum Evolution Criterion
Catanzaro, Daniele
Labbe, Martine
Pesenti, Raffaele
Salazar-Gonzalez, Juan-Jose
[J]. NETWORKS, 2009, 53 (02) : 126 - 140
[14] Recreating ancestral proteins
Chang, BSW
Donoghue, MJ
[J]. TRENDS IN ECOLOGY & EVOLUTION, 2000, 15 (03) : 109 - 114
[15] Fast and accurate phylogeny reconstruction algorithms based on the minimum-evolution principle
Desper, R
Gascuel, O
[J]. JOURNAL OF COMPUTATIONAL BIOLOGY, 2002, 9 (05) : 687 - 705
[16] A ROBUST MODEL FOR FINDING OPTIMAL EVOLUTIONARY TREES
FARACH, M
KANNAN, S
WARNOW, T
[J]. ALGORITHMICA, 1995, 13 (1-2) : 155 - 179
[17] Fiorini S., 2011, TECHNICAL REPORT
[18] Harvey P, 1996, New uses for new phylogenies
[19] HAYASAKA K, 1988, MOL BIOL EVOL, V5, P626
[20] Kouvelis P., 1997, NONCONVEX OPTIMIZATI

← 1 2 3 4 →