multperf

multperf addresses multi-state perfect phylogeny problems by extending the binary perfect phylogeny model to analyze characters with three to five states and to handle missing data in phylogenetic datasets.

Key Features:

• Multi-State Perfect Phylogeny Model: Extends the binary perfect phylogeny model to allow characters with three, four, or five states.
• Missing Data (MD) Problem: Determines whether bounded values for missing entries can be imputed to obtain a multi-state perfect phylogeny.
• Character-Removal (CR) Problem: Minimizes the number of characters that must be removed for the dataset to admit a multi-state perfect phylogeny.
• Missing-Data Character-Removal (MDCR) Problem: Imputes missing values to minimize the solution size of the CR problem.
• Integer Linear Programming (ILP) Solutions: Employs ILP formulations tailored for datasets with three-, four-, or five-state characters.
• Graph-Theoretic Framework: Uses chordal graph theory and minimal triangulation of non-chordal graphs to provide necessary and sufficient conditions for the MD problem for arbitrary permitted states.
• Empirical Validation and Combinatorial Insights: Extensive empirical testing demonstrated practicality on typical phylogenetic datasets and revealed combinatorial structures in multi-state perfect phylogenies.

Scientific Applications:

• Phylogenetic reconstruction: Tests existence of perfect phylogenies and resolves multi-state character relationships in phylogenetic datasets.
• Handling incomplete datasets: Imputes bounded values and guides character removal to accommodate missing or incomplete information.
• Genetics and evolutionary biology: Applies to analyses of genetic data, evolutionary studies, and comparative genomics involving multi-state characters.

Methodology:

Computational methods include Integer Linear Programming formulations tailored for three-, four-, and five-state characters and a graph-theoretic approach based on chordal graph theory and minimal triangulation of non-chordal graphs for the missing-data problem for arbitrary permitted states.