IPP

IPP reconstructs phylogenetic trees from haplotype and genotype data containing missing entries to solve unrestricted versions of the incomplete perfect phylogeny (IPP) and incomplete perfect phylogeny haplotyping (IPPH) problems when the tree root is unknown.

Key Features:

• Problem scope: Handles incomplete haplotype and genotype matrices for both IPP and IPPH formulations.
• Unrestricted root handling: Operates on instances where the phylogeny root is unknown and cannot be trivially inferred from the data.
• Algorithmic approach: Implements efficient enumerative algorithms for solving practical instances of IPP and IPPH.
• Computational complexity awareness: Targets problems that are NP-complete, acknowledging their combinatorial difficulty.
• Empirical evaluation: Algorithms have been tested on simulated datasets and reported high performance in speed and accuracy.

Scientific Applications:

• Phylogeny reconstruction: Reconstructs phylogenetic trees from incomplete genetic data (haplotypes or genotypes) for evolutionary analysis.
• Haplotyping with missing data: Infers haplotype configurations from genotype matrices containing missing entries under IPPH.
• Algorithmic research on NP-complete problems: Provides a framework for studying and benchmarking methods for NP-complete phylogeny problems using simulated data.

Methodology:

Uses efficient enumerative algorithms to solve unrestricted IPP and IPPH instances and was empirically evaluated on simulated datasets.