An FPT haplotyping algorithm on pedigrees with a small number of sites

Area of Science:

• Computational Biology
• Genetics
• Bioinformatics

Background:

• Genetic disease studies link chromosomal changes to diseases.
• Direct haplotype extraction is costly; computational inference is needed.
• Haplotypes are vital for understanding genetic disease mechanisms.

Purpose of the Study:

• To develop an efficient computational method for inferring haplotypes from genotype data.
• To determine the minimum number of recombination events in general pedigrees.
• To support genetic disease studies by providing haplotype information.

Main Methods:

• Investigated haplotype inference using genotype data.
• Formulated the problem as a reduction to Bipartization by Edge Removal with parity constraints.
• Developed an exact algorithm for computing minimum recombination events.

Main Results:

• The NP-hard problem was parametrically reduced to a solvable form.
• An exact algorithm was developed with a runtime of O(2^k * poly(n, m)).
• The algorithm efficiently infers haplotypes for a small number of sites.

Conclusions:

• The developed algorithm aids in inferring haplotypes for genetic disease studies.
• It helps track how haplotype changes, like recombinations, relate to genetic diseases.
• This computational approach offers a cost-effective alternative to biochemical methods.