Testing the theory of evolution: A novel application of combinatorial optimization (Q1084042)

This paper's major interest is an objective test by which Darwin's theory of evolution can be falsified. The theory of evolution implies that the phylogenetic trees for corresponding DNA sequences in different species (e.g., the ones coding for haemoglobin A) should imply an identical pattern of ancestry. The DNA sequences are nodes on a graph; a tentative phylogenetic tree is a tree spanning the nodes. The weight assigned to an edge joining two DNA sequences in the graph is the number of corresponding sites in the sequences which have different letters. Because one allows the possibility of uncatalogued DNA sequences, intermediate nodes other than the known DNA sequences are permitted. One criterion for optimising an evolutionary tree, maximum parsimony, leads to the problem of finding the Steiner minimal tree for the nodes under the given weighting scheme. Combinatorial optimisation is used to generate the minimal tree for five families of sequences. Edge removal from a tree partitions the vertices into two classes; this gives rise to a metric on trees which span the nodes. Equiprobability of all possible spanning trees then provides a null hypothesis for statistical testing. Darwin's theory survives unscathed.