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

Doan DD, Evans PA - Algorithms Mol Biol (2011)

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.

View Article: PubMed Central - HTML - PubMed

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

Parity conflict between vertices within each member.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC3108306&req=5

Figure 3: Parity conflict between vertices within each member.

Mentions: In Figure 3a, there are five grey vertices created for member u where vertices u12, u23, u34 and u45 are created from closest heterozygous sites, and a supplementary vertex u15 is created for a member adjacent to u. Figure 3b shows an invalid solution with three resolved red vertices u23, u34 and u15 in member u. A valid solution with an even number of red vertices is shown in Figure 3c.


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

Doan DD, Evans PA - Algorithms Mol Biol (2011)

Parity conflict between vertices within each member.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC3108306&req=5

Figure 3: Parity conflict between vertices within each member.
Mentions: In Figure 3a, there are five grey vertices created for member u where vertices u12, u23, u34 and u45 are created from closest heterozygous sites, and a supplementary vertex u15 is created for a member adjacent to u. Figure 3b shows an invalid solution with three resolved red vertices u23, u34 and u15 in member u. A valid solution with an even number of red vertices is shown in Figure 3c.

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.

View Article: PubMed Central - HTML - PubMed

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