Phylogenetic Analysis Via DC Programming

Steven Ellis (ells1umbc.edu)
Madhu Nayakkankuppam (madhumath.umbc.edu)

Abstract: The evolutionary history of species may be described by a phylogenetic tree whose topology captures ancestral relationships among the species, and whose branch lengths denote evolution times. For a fixed topology and an assumed probabilistic model of nucleotide substitution, we show that the likelihood of a given tree is a d.c. (difference of convex) function of the branch lengths, hence maximum likelihood estimates (of the branch lengths) may be obtained by solving an appropriate d.c. program. Such a formulation is amenable to global optimization techniques, in contrast with existing methods and software codes which could potentially produce only locally optimal solutions. We present the formulation of this optimization problem, its solution via an outer approximation cutting plane algorithm, and illustrative numerical results on small genetic data sets.

Keywords: Phylogenetic analysis, maximum likelihood estimation, d.c. programming, cutting plane algorithm, global optimization

Category 1: Applications -- Science and Engineering (Biomedical Applications )

Category 2: Global Optimization (Applications )

Citation: Preprint, Department of Mathematics & Statistics, UMBC, 1000 Hilltop Circle, Baltimore, MD 21250.

Download: [PDF]

Entry Submitted: 06/15/2005
Entry Accepted: 06/15/2005
Entry Last Modified: 06/15/2005

Modify/Update this entry