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

Non-recombination vs. recombination, showing haplotypes of members.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 1: Non-recombination vs. recombination, showing haplotypes of members.

Mentions: When there is no recombination event in a pedigree, a child member receives one entire haplotype from its father and another entire haplotype from its mother. Figure 1a shows member c receiving the entire left haplotype of parental member u and the entire left haplotype of parental member v. However, during the meiosis process, haplotypes of a parent sometimes shuffle due to the crossover of chromosomes and one of the shuffled copies is transferred to the child. This phenomenon is called a recombination and the result is called a recombinant. Figure 1b shows a recombination event between site 1 and site 2 of member u. As the result, member c receives a combined haplotype from site 1 of the left haplotype, and from sites 2 and 3 of the right haplotype of member u.


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

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

Non-recombination vs. recombination, showing haplotypes of members.
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 1: Non-recombination vs. recombination, showing haplotypes of members.
Mentions: When there is no recombination event in a pedigree, a child member receives one entire haplotype from its father and another entire haplotype from its mother. Figure 1a shows member c receiving the entire left haplotype of parental member u and the entire left haplotype of parental member v. However, during the meiosis process, haplotypes of a parent sometimes shuffle due to the crossover of chromosomes and one of the shuffled copies is transferred to the child. This phenomenon is called a recombination and the result is called a recombinant. Figure 1b shows a recombination event between site 1 and site 2 of member u. As the result, member c receives a combined haplotype from site 1 of the left haplotype, and from sites 2 and 3 of the right haplotype of member u.

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