The Perfect Phylogeny Problem

A phylogeny is a tree representation of the evolutionary history of a set of taxa (organisms, biological sequences, populations, or languages). Thus, phylogeny construction is among the basic computational problems in biology and linguistics. We will be concerned here with taxa described by the states they exhibit on a set of characters. A sample data set and a phylogeny for it (both adapted from [41]) are shown in Figure 1. The data is binary and in matrix form, rows are indexed by taxa and columns by characters. Entry (i, j) is “1” if taxon i has character j and it is “0” if the character is absent. The phylogeny shown is rooted and assumes that the taxa descend from a common ancestor where all characters are absent. Points at which characters emerge are indicated by labeled bars. 1