DETERMINING THE EVOLUTIONARY TREE USING EXPERIMENTS

Evolutionary trees, also known as phylogenetic trees, are rooted verte x-labeled trees which describe the evolution of a species set S from a common ancestor. The determination of evolutionary trees is a fundame ntal problem in computational evolutionary biology, and has been studi ed in great depth. In this paper, we present a new model of computatio n which assumes that it is possible to determine the true evolutionary tree for each three species, perhaps through the use of Ahlquist-Sibl ey experimental techniques. We present tight upper and lower bounds fo r constructing evolutionary trees using experiments. (C) 1996 Academic Press, Inc.