Chordal graph theory and its applications to perfect phylogeny

The Multi-State Perfect Phylogeny Problem is a classic problem in computational biology where taxa are described by the states they take on a set of characters and one wishes to build a tree describing how the taxa evolve. When no perfect phylogeny exists it is natural to consider the Multi-State Character Removal Problem where we remove characters to find perfect phylogenies. One may also consider the case where some characters are undefined for certain taxa, or there is missing data. Perfect phylogeny is fixed parameter tractable in the number of states when no data is missing, but NP-hard when the number of states is unbounded. Finding a perfect phylogeny for missing data is NP-hard, even when the data is binary. In this thesis we discuss existing chordal graph theory to formulate solutions to perfect phylogeny with and without missing data, and provide a solution to the multi-state character removal problem, which was previously unsolved.