An O(nmα(m)) time algorithm is given for inferring haplotypes from genotypes of non-recombinant pedigree data, where n is the number of members, m is the number of sites, and α(m) is the inverse of the Ackermann function. The algorithm works on both tree and general pedigree structures with cycles. Constraints between pairs of heterozygous sites are used to resolve unresolved sites for the pedigree, enabling the algorithm to avoid problems previously experienced for non-tree pedigrees.
Get full access to this article
View all access options for this article.
References
1.
ChanM.Y.et al.2006. Linear-time haplotype inference on pedigrees without recombinations. Lect. Notes comput. Sci., 4175:56–67.
2.
GabrielS.et al.2002. The structure of haplotype blocks in the human genome. Science, 296:2225–2229.
3.
GusfieldD.2004. An overview of combinatorial methods for haplotype inference. Lect. Notes comput. Sci., 2983:9–25.
4.
LiJ., JiangT.2003a. Efficient inference of haplotypes from genotypes on a pedigree. J. Bioinform. Comput. Biol., 1:41–70.
5.
LiJ., JiangT.2003b. Efficient rule-based haplotyping algorithms for pedigree data. Proc. RECOMB ’03, 197–206.
6.
LiJ., JiangT.2004. An exact solution for finding minimum recombinant haplotype configurations on pedigrees with missing data by integer linear programming. Proc. RECOMB ’04, 20–29.
7.
LiX., LiJ.2008. Efficient haplotype inference from pedigrees with missing data using linear systems with disjoint-set data structures. Proc. 7th Annu. Int. Con. Comput. Syst. Bioinform., 297–308.
8.
LiuL.et al.2005. Complexity and approximation of the minimum recombination haplotype configuration problem. Proc. ISAAC05, 370–379.
9.
O'ConnellJ., WeeksD.1999. An optimal algorithm for automatic genotype elimination. Am. J. Hum. Genet., 65:1733–1740.
10.
QianD., BeckmannL.2002. Minimum-recombinant haplotyping in pedigrees. Am. J. Hum. Genet., 70:1434–1445.
11.
QinZ.S.et al.2002. Partition-ligation-expectation-maximization algorithm for haplotype inference with single-nucleotide polymorphisms. Am. J. Hum. Genet., 71:1242–1247.
12.
TarjanR.E.1975. Efficiency of a good but not linear set union algorithm. J. ACM, 22:215–225.
13.
XiaoJ.et al.2007. Fast elimination of redundant linear equations and reconstruction of recombination-free mendelian inheritance on a pedigree. Proc. 18th Annu. ACM-SIAM Symp. Discrete Algorithms, 655–664.
14.
ZhangK.et al.2005. HAPLORE: a program for haplotype reconstruction in general pedigrees without recombination. Bioinformatics, 21:90–103.
