Email updates

Keep up to date with the latest news and content from Algorithms for Molecular Biology and BioMed Central.

Open Access Research

A mixed integer linear programming model to reconstruct phylogenies from single nucleotide polymorphism haplotypes under the maximum parsimony criterion

Daniele Catanzaro1*, Ramamoorthi Ravi2 and Russell Schwartz3

Author Affiliations

1 Graphes et Optimisation Mathématique (G.O.M.), Computer Science Department, Université Libre de Bruxelles (U.L.B.), Boulevard du Triomphe, CP 210/01, B-1050, Brussels, Belgium

2 Tepper School of Business, Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, PA 15213-3890

3 Department of Biological Sciences and Lane Center for Computational Biology, Carnegie Mellon University, 4400 Fifth Avenue, Pittsburgh, PA, 15213

For all author emails, please log on.

Algorithms for Molecular Biology 2013, 8:3  doi:10.1186/1748-7188-8-3

Published: 23 January 2013

Abstract

Background

Phylogeny estimation from aligned haplotype sequences has attracted more and more attention in the recent years due to its importance in analysis of many fine-scale genetic data. Its application fields range from medical research, to drug discovery, to epidemiology, to population dynamics. The literature on molecular phylogenetics proposes a number of criteria for selecting a phylogeny from among plausible alternatives. Usually, such criteria can be expressed by means of objective functions, and the phylogenies that optimize them are referred to as optimal. One of the most important estimation criteria is the parsimony which states that the optimal phylogeny Tfor a set <a onClick="popup('http://www.almob.org/content/8/1/3/mathml/M1','MathML',630,470);return false;" target="_blank" href="http://www.almob.org/content/8/1/3/mathml/M1">View MathML</a>of n haplotype sequences over a common set of variable loci is the one that satisfies the following requirements: (i) it has the shortest length and (ii) it is such that, for each pair of distinct haplotypes <a onClick="popup('http://www.almob.org/content/8/1/3/mathml/M2','MathML',630,470);return false;" target="_blank" href="http://www.almob.org/content/8/1/3/mathml/M2">View MathML</a>, the sum of the edge weights belonging to the path from hi to hj in T is not smaller than the observed number of changes between hi and hj. Finding the most parsimonious phylogeny for <a onClick="popup('http://www.almob.org/content/8/1/3/mathml/M3','MathML',630,470);return false;" target="_blank" href="http://www.almob.org/content/8/1/3/mathml/M3">View MathML</a>involves solving an optimization problem, called the Most Parsimonious Phylogeny Estimation Problem (MPPEP), which is <a onClick="popup('http://www.almob.org/content/8/1/3/mathml/M4','MathML',630,470);return false;" target="_blank" href="http://www.almob.org/content/8/1/3/mathml/M4">View MathML</a>-hard in many of its versions.

Results

In this article we investigate a recent version of the MPPEP that arises when input data consist of single nucleotide polymorphism haplotypes extracted from a population of individuals on a common genomic region. Specifically, we explore the prospects for improving on the implicit enumeration strategy of implicit enumeration strategy used in previous work using a novel problem formulation and a series of strengthening valid inequalities and preliminary symmetry breaking constraints to more precisely bound the solution space and accelerate implicit enumeration of possible optimal phylogenies. We present the basic formulation and then introduce a series of provable valid constraints to reduce the solution space. We then prove that these constraints can often lead to significant reductions in the gap between the optimal solution and its non-integral linear programming bound relative to the prior art as well as often substantially faster processing of moderately hard problem instances.

Conclusion

We provide an indication of the conditions under which such an optimal enumeration approach is likely to be feasible, suggesting that these strategies are usable for relatively large numbers of taxa, although with stricter limits on numbers of variable sites. The work thus provides methodology suitable for provably optimal solution of some harder instances that resist all prior approaches.

Keywords:
Combinatorial optimization; Exact algorithms; Mixed integer programming; Phylogeny estimation; Haplotype estimation; Maximum parsimony; Single nucleotide polymorphism; Computational biology