Inferring Evolutionary History From DNA Sequences

Abstract

One of the longstanding problems in computational molecular biology is the Character Compatibility Problem, which is concerned with the construction of phylogenetic trees for species sets, where the species are defined by characters. The character compatibility problem is NP-Complete in general. In this paper an $O(n^2 k)$ time algorithm is described for the case where the species are described by quaternary characters. This algorithm can be used to construct phylogenetic trees from DNA sequences.