LPPH

LPPH infers haplotypes from SNP genotype data under the infinite-sites no-recombination model to determine whether the genotypes admit a perfect phylogeny consistent with a coalescent tree.

Key Features:

• Linear-time deterministic algorithm: Employs a deterministic algorithm that runs in linear time to solve the Perfect Phylogeny Haplotyping (PPH) problem.
• Simple data structure: Uses a straightforward data structure and simple operations to support the linear-time algorithm.
• Implementation: Provides a full implementation of the algorithm.
• Performance: Shown in simulations to outperform prior nonlinear methods in computational speed.

Scientific Applications:

• Population genetics: Determines whether SNP genotype sets can be explained by haplotype pairs that evolved on a coalescent tree under the no-recombination infinite-sites model, including assessment of the three- or four-gametes condition depending on tree rooting.
• Inner-loop algorithms: Functions as an efficient linear-time subroutine for larger algorithms that require repeated solutions of the PPH problem.

Methodology:

Solves the Perfect Phylogeny Haplotyping problem using a deterministic linear-time algorithm implemented with a simple data structure and simple operations, and includes assessment of the three- or four-gametes condition under the infinite-sites no-recombination model.