opph

opph computes optimal perfect-phylogeny haplotypes from genotype data across SNP sites to perform perfect-phylogeny-based haplotype inference.

Key Features:

• Problem solved: Implements Perfect Phylogeny Haplotyping (PPH) to infer haplotypes from genotypes over SNP sites.
• Time complexity: Achieves optimal O(nm) time complexity where n is the number of genotypes and m is the number of SNP sites.
• Space-efficient data structure (FlexTree): Uses the FlexTree to encode all pairwise relationships between SNP sites in O(m) space.
• Pairwise interdependency exploitation: Leverages interdependencies among pairwise relationships between SNP sites to construct a perfect phylogeny.
• Column-ordering strategy: Applies a column-ordering strategy to identify necessary interdependencies among SNP columns.
• Sequential genotype integration: Orders genotypes for sequential addition to the FlexTree to preserve algorithmic efficiency.
• Improved complexity over prior methods: Reduces the computational cost relative to previous O(nm^2) approaches.

Scientific Applications:

• Haplotype reconstruction: Reconstructs haplotypes from genotype data under the perfect-phylogeny assumption for downstream genetic analyses.
• SNP–disease association: Supports linking SNPs to human diseases via accurate haplotype inference for association studies.
• Population and evolutionary analysis: Constructs perfect phylogenies for population-genetic and evolutionary investigations using SNP data.
• Personalized medicine: Provides haplotype information applicable to personalized medicine and genotype-based research.

Methodology:

Leverages interdependencies among pairwise SNP-site relationships, applies a column-ordering strategy, constructs a FlexTree that encodes pairwise relationships in O(m) space, and sequentially adds ordered genotypes to the FlexTree to achieve O(nm) runtime.