ANALYSES OF HAPLOTYPE INFERENCE ALGORITHMS

Sean Cleary (USA) and Katherine St. John (USA)

Received July 14, 2007; Revised December 17, 2007

References:

[1] David Aldous, Stochastic models and descriptive statistics for phylogenetic trees, from Yule to today, Statistical Science 16 (2001), (revision of “Visualizing Phylogenetic Tree Balance”). [2] V. Banfa, D. Gusfield, G. Lancia and S. Yooseph, Haplotyping as perfect phylogeny: A direct approach, Journal of Computational Biology 10(3) (2003), 323-340. [3] A. G. Clark, Inference of haplotypes from pcr-amplified samples of diploid populations, Mol. Biol. Evol. 7 (1990), 111-122. [4] The International HapMap Consortium, A haplotype map of the human genome, Nature 437 (2005), 1299-1320. [5] W. J. Ewens, The sampling theory of selectively neutral alleles, Theoretical Population Biology 3 (1972), 87-112. [6] L. Excoffier and M. Slatkin, Maximum-likelihood estimation of molecular haplotype frequencies in a diploid population, Mol. Biol. Evol. 12 (1995), 921-927. [7] William Feller, An Introduction to Probability Theory and its Applications, Vol. I, John Wiley & Sons Inc., New York, 1968. [8] D. B. Goldstein and M. E. Weale, Population genomics: Linkage disequilibrium holds the key, Curr. Biol. 11 (2001), R576-R579. [9] Dan Gusfield, Haplotying as perfect phylogeny: Conceptual framework and efficient solutions, Proceedings of the Sixth Annual International Conference on Computational Biology, ACM, 2002, pp. 166-175. [10] Dan Gusfield, An overview of combinatorial methods for haplotype inference, Computational Methods for SNPs and Haplotype Inference, Volume 2983 of Lecture Notes in Computer Science, Springer, 2004, pp. 9-25. [11] Dan Gusfield and R. H. Chung, Empirical exploration of perfect phylogeny haplotyping and haplotypers, Proceedings of the 2003 Cocoon Conference, 2003. [12] B. F. J. Manly, The Statistics of Natural Selection, Chapman and Hall, 1985. [13] C. C. McGeoch, Analyzing algorithms by simulation: variance reduction techniques and simulation speedups, ACM Comp. Surveys 24 (1992), 195-212. [14] Andy McKenzie and Mike Steel, Distributions of cherries for two models of trees, Math. Biosci. 164(1) (2000), 81-92. [15] B. M. E. Moret, Towards a discipline of experimental algorithmics, In Data Structures, Near Neighbor Searches and Methodology: Fifth and Sixth DIMACS Implementation Challenges, DIMACS, 2002. [16] National Institutes of Health Haplotype Map Project, Developing a haplotype map of the human genome for finding genes related to health and disease, 2001. Available at http://www.genome.gov/page.cfm?pageID=10001665. [17] National Institutes of Health Haplotype Map Project, The haplotype map project, 2001. Available at http://www.genome.gov/page.cfm?pageID=10001688. [18] D. E. Reich, M. Cargill, S. Bolk, J. Ireland, P. C. Sabeti, D. J. Richter, T. Lavery, R. Kouyoumjian, S. F. Farhadian, R. Ward and E. S. Lander, Linkage disequilibrium in the human genome, Nature 411 (2001), 199-204. [19] Michael J. Sanderson, r8s version 1.06(beta): Analysis of rates (r8s) of evolution, 2002. Software available at http://ginger.ucdavis.edu/r8s/. [20] Mike Steel and Andy McKenzie, Properties of phylogenetic trees generated by Yule-type speciation models, Math. Biosci. 170(1) (2001), 91-112. [21] Matthew Stephens, Nicholas J. Smith and Peter Donnelly, A new statistical method for haplotype reconstruction from population data, Am. J. Hum. Genet. 68 (2001), 978-989.

Keywords and phrases: combinatorial algorithms, molecular biology, trees.