Path Costs in Evolutionary Tree Reconstruction
Abstract
This paper describes a dynamic programming algorithm to solve a
family of problems in the reconstruction of evolutionary trees from
protein sequence data, that of constructing ``minimal'' colorings.
This dynamic programming formulation can be modified to efficiently enumerate
the number of minimal colorings, and thereby be used to calculate the average
cost of any given edge, where the average is taken over the entire set of
minimal colorings. An extension of our dynamic programming formulation allows
for the calculation of average path costs amongst all minimal colorings.
Our results resolve questions raised in [HP87]; in particular,
we develop polynomial time procedures to find the minimum, maximum,
and average (expected) cost of an edge, and more generally of a path, for a minimal coloring.
Our algorithm is distinguished in its flexibility to address further
distribution and statistical questions relating to the minimal colorings.
Furthermore, the more general concept of calculating statistics describing
the set of optimal solutions may be of interest in other combinatorial problems.
Download Information
Click on the following title to view and download the paper in PostScript format.
- Path Costs in Evolutionary Tree Reconstruction (17 pages, 183 KB)
,
- Dorit S. Hochbaum and Anu Pathria. Journal of computational biology, 4(2), 1997, 163-175.
dorit@hochbaum.ieor.berkeley.edu
7/29/98