Determining the Evolutionary Tree Using Experiments

Evolutionary trees, also known as phylogenetic trees, are rooted vertex-labeled trees which describe the evolution of a species set S from a common ancestor. The determination of evolutionary trees is a fundamental problem in computational evolutionary biology, and has been studied in great depth. In this paper, we present a new model of computation which assumes that it is possible to determine the true evolutionary tree for each three species, perhaps through the use of Ahlquist-Sibley experimental techniques. We present tight upper and lower bounds for constructing evolutionary trees using experiments.