Efficient reconstruction of haplotype structure via perfect phylogeny

Area of Science:

• Genomics
• Computational Biology
• Population Genetics

Background:

• Human genomes contain two copies of each chromosome, but genotypes do not specify individual chromosome sequences (haplotypes).
• Determining haplotypes is essential for understanding genetic variation and complex disease inheritance.
• The haplotype mapping project aims to identify common human haplotypes.

Purpose of the Study:

• To develop efficient algorithms for computing haplotypes from genotypes, as genotype determination is less expensive than haplotype determination.
• To leverage the observation that human genomes contain short blocks with few distinct haplotypes, often consistent with a perfect phylogeny model.

Main Methods:

• Developed a polynomial-time algorithm for inferring haplotypes from genotypes assuming a perfect phylogeny.
• Extended the algorithm using a reduction to 2-SAT to handle parental and child genotype constraints.
• Investigated the hardness of removing individuals to ensure perfect phylogeny consistency.

Main Results:

• Presented a simple and efficient algorithm for haplotype inference under the perfect phylogeny model.
• Successfully extended the algorithm to incorporate parental and child genotype data.
• Algorithms were tested on real data, yielding biologically meaningful results.

Conclusions:

• The developed algorithms provide an efficient means to infer haplotypes from genotype data.
• The approach is valuable for population genetics studies and understanding disease inheritance.
• A publicly available webserver facilitates haplotype prediction from genotype data.