Multi-State Perfect Phylogeny Problem
is an extension of the
Perfect Phylogeny Problem, allowing characters to take on more than two states. In this paper we consider three problems that extend the utility of the multi-state perfect phylogeny model:
The Missing Data (MD) Problem
where some entries in the input are missing and the question is whether (bounded) values for the missing data can be imputed so that the resulting data has a multi-state perfect phylogeny;
The Character-Removal (CR) Problem
where we want to minimize the number of characters to remove from the data so that the resulting data has a multi-state perfect phylogeny; and
The Missing-Data Character-Removal (MDCR) Problem
where the input has missing data and we want to impute values for the missing data to
the solution to the resulting Character-Removal Problem.
We detail Integer Linear Programming (ILP) solutions to these problems for the special case of three permitted states per character and report on extensive empirical testing of these solutions. Then we develop a general theory to solve the MD problem for an
number of permitted states, using chordal graph theory and results on minimal triangulation of non-chordal graphs. This establishes new necessary and sufficient conditions for the existence of a perfect phylogeny with (or without) missing data. We implement the general theory using integer linear programming, although other optimization methods are possible. We extensively explore the empirical behavior of the general solution, showing that the methods are very practical for data of size and complexity that is characteristic of many current applications in phylogenetics. Some of the empirical results for the MD problem with an arbitrary number of permitted states are very surprising, suggesting the existence of additional combinatorial structure in multi-state perfect phylogenies.