Years aud Authors of Summarized Original Work
2009; Chan, Chan, Chin, Fung, Kao
Problem Definition
In many diploid organisms like humans, chromosomes come in pairs. Genetic variation occurs in some “positions” along the chromosomes. These genetic variations are commonly modelled in the form of single nucleotide polymorphisms (SNPs) [5], which are the nucleotide sites where more than one nucleotide can occur. A haplotype is the sequence of linked SNP genetic markers (small segments of DNA) on a single chromosome. However, experiments often yield genotypes, which is a blend of the two haplotypes of the chromosome pair. It is more useful to have information on the haplotypes, thus giving rise to the computational problem of inferring haplotypes from genotypes.
The physical position of a marker on a chromosome is called a locus and its state is called an allele. SNP are often biallelic, i.e., the allele can take on two different states, corresponding to two different nucleotides. In the...
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Recommended Reading
Chan MY, Chan WT, Chin FYL, Fung SPY, Kao MY (2009) Linear-time haplotype inference on pedigrees without recombinations and mating loops. SIAM J Comput 38(6):2179–2197
Lai EY, Wang WB, Jiang T, Wu KP (2012) A linear-time algorithm for reconstructing zero-recombinant haplotype configuration on a pedigree. BMC Bioinformatics 13(S-17):S19
Li J, Jiang T (2003) Efficient inference of haplotypes from genotypes on a pedigree. J. Bioinformatics Comput Biol 1(1):41–69
Liu L and Jiang T (2010) A linear-time algorithm for reconstructing zero-recombinant haplotype configuration on pedigrees without mating loops. J Combin Optim 19:217–240
Russo E, Smaglik P (1999) Single nucleotide polymorphism: big pharmacy hedges its bets. The Scientist, 13(15):1, July 19, 1999
**ao J, Liu L, **a L, Jiang T (2009) Efficient algorithms for reconstructing zero-recombinant haplotypes on a pedigree based on fast elimination of redundant linear equations. SIAM J Comput 38(6):2198–2219
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer Science+Business Media New York
About this entry
Cite this entry
Chan, M., Chan, WT., Chin, F.Y.L., Fung, S.P.Y., Kao, MY. (2016). Haplotype Inference on Pedigrees Without Recombinations. In: Kao, MY. (eds) Encyclopedia of Algorithms. Springer, New York, NY. https://doi.org/10.1007/978-1-4939-2864-4_802
Download citation
DOI: https://doi.org/10.1007/978-1-4939-2864-4_802
Published:
Publisher Name: Springer, New York, NY
Print ISBN: 978-1-4939-2863-7
Online ISBN: 978-1-4939-2864-4
eBook Packages: Computer ScienceReference Module Computer Science and Engineering