Academic Journals Database
Disseminating quality controlled scientific knowledge

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

Author(s): Doan Duong | Evans Patricia

Journal: Algorithms for Molecular Biology
ISSN 1748-7188

Volume: 6;
Issue: 1;
Start page: 8;
Date: 2011;
Original page

Abstract Background Genetic disease studies investigate relationships between changes in chromosomes and genetic diseases. Single haplotypes provide useful information for these studies but extracting single haplotypes directly by biochemical methods is expensive. A computational method to infer haplotypes from genotype data is therefore important. We investigate the problem of computing the minimum number of recombination events for general pedigrees with a small number of sites for all members. Results We show that this NP-hard problem can be parametrically reduced to the Bipartization by Edge Removal problem with additional parity constraints. We solve this problem with an exact algorithm that runs in time, where n is the number of members, m is the number of sites, and k is the number of recombination events. Conclusions This algorithm infers haplotypes for a small number of sites, which can be useful for genetic disease studies to track down how changes in haplotypes such as recombinations relate to genetic disease.
Save time & money - Smart Internet Solutions      Why do you need a reservation system?