An FPT haplotyping algorithm on pedigrees with a small number of sites.
Bottom Line:
A computational method to infer haplotypes from genotype data is therefore important.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.
Affiliation: Faculty of Computer Science, University of New Brunswick, Fredericton, New Brunswick, Canada. pevans@unb.ca.
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. No MeSH data available. Related in: MedlinePlus |
Related In:
Results -
Collection
License getmorefigures.php?uid=PMC3108306&req=5
Mentions: Given a general pedigree with n members, where each member has m sites, we set up a pedigree graph G = (V, E) and parity-constraint sets Spc to compute the minimum number of recombination events in the pedigree. A recombination event can only be detected if there is at least one heterozygous site on each side of a recombination breakpoint, e.g. we cannot detect if a recombination event happens between homozygous sites 1 and 3 of member u in Figure 2a because the states at the two haplotypes for each homozygous site are the same. The graph captures constraints between pairs of closest heterozygous sites and pairs of closest homozygous sites, which will enable the detection of possible recombination events in pedigrees. A vertex in the pedigree graph represents a pair of homozygous sites or a pair of heterozygous sites, and is colored to represent the relationship between the haplotypes of the sites. |
View Article: PubMed Central - HTML - PubMed
Affiliation: Faculty of Computer Science, University of New Brunswick, Fredericton, New Brunswick, Canada. pevans@unb.ca.
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.
No MeSH data available.