The main focus of this work is in the area of algorithms for reconstructing evolutionary history. The evolutionary history for a set of species S is described by a rooted tree called an evolutionary tree (also called phylogenetic tree or phylogeny) in which the leaves represent the species in S and the internal nodes represent the common ancestors. There is a wide range of methods for constructing phylogenetic trees given in the literature, and most of these are based upon optimization criteria. That is, an optimization criterion is given with which to evaluate a given phylogeny, and the objective is to find a phylogeny with an optimal score with respect to that criterion. Almost all of the optimization problems have been shown to be NP-hard score with respect to that criterion. Despite this, a plethora of heuristics have been developed for constructing phylogenetic trees. The standard modus operandi is to analyze the data set using many different methods for tree construction, and compare the outcomes of these methods in order to select a phylogenetic tree. This research effort with respect to phylogeny construction has three basic components: (1) the development of a comprehensive mathematical framework by which current methodologies can be compared; (2) the development of efficient algorithms for phylogeny construction with meaningful output; and (3) application of these techniques to problems in biology and linguistics.
