Abstract
Recent evidence for a “blocky” haplotype structure to the human genome and for its importance to disease inference studies has created a pressing need for tools that identify patterns of past recombination in sequences of samples of human genes and gene regions. We present two new approaches to the reconstruction of likely recombination patterns from a set of haploid sequences which each combine combinatorial optimization techniques with statistically motivated recombination models. The first breaks the problem into two discrete steps: finding recombination sites then coloring sequences to signify the likely ancestry of each segment. The second poses the problem as optimizing a single probability function for parsing a sequence in terms of ancestral haplotypes. We explain the motivation for each method, present algorithms, show their correctness, and analyze their complexity. We illustrate and analyze the methods with results on real, contrived, and simulated datasets.
To whom correspondence should be addressed
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Baum, L.E., Petrie, T., Soules, G., and Weiss, N. A maximization technique occurring in the statistical analysis of probabilistic functions of Markov chains. Annals Math. Stat., 41, 164–171, 1970.
Clark, A. G. Inference of Haplotypes from PCR-amplified samples of diploid populations. Mol. Biol. Evol., 7, 111–122, 1990.
Daly, M.J., Rioux, J.D., Schaffner, S.F., Hudson, T.J., and Lander, E.S. Highresolution haplotype structure in the human genome. Nature Gen., 29, 229–232, 2001.
Dempster, A.P., Laird, N.M., and Rubin, D.B. Maximum likelihood from incomplete data via the EM algorithm. J. Royal Stat. Soc. B, 39, 1–38, 1977.
Edmonds, J. Paths, trees, and flowers. Canad. J. Math., 17, 449–467, 1965.
Fearnhead, P. and Donnelly, P. Estimating recombination rates from population genetic data. Genetics, 159:1299–1318, 2001.
Gusfield, D. Efficient algorithms for inferring evolutionary history. Networks, 21:19–28, 1991.
Gusfield, D. Haplotyping as perfect phylogeny: Conceptual framework and efficient solutions. In Proc. 6th Intl. Conf. Comp. Biol., RECOMB’02, 166–175, 2002.
Hein, J. A heuristic method to reconstruct the history of sequences subject to recombination. J. Mol. Evol., 20, 402–411, 1993.
Hudson, R.R. Properties of the neutral allele model with intergenic recombination. Theoret. Pop. Biol., 23, 183–201, 1983.
Hudson, R.R. and Kaplan, N.L. Statistical properties of the number of recombination events in the history of a sample of DNA sequences. Genetics, 111, 147–164, 1985.
International Human Genome Sequencing Consortium. Initial sequencing and analysis of the human genome. Nature, 409, 860–921, 2001.
Jeffreys, A.J., Kauppi, L., and Neumann, R. Intensely punctate meiotic recombination in the class II region of the major histocompatibility complex. Nature Gen., 29, 217–222, 2001.
Johnson, G.C.L., Esposito, L., Barratt, B.J., Smith, A.N., Heward, J., Di Genova, G., Ueda, H., Cordell, H.J., Eaves, I.A., Dudbridge, F., Twells, R.C.J., Payne, F., Hughes, W., Nutland, S., Stevens, H., Carr, P., Tuomilehto-Wolf, E., Tuomilehto, J., Gough, S.C.L., Clayton, D.G., and Todd, J.A. Haplotype tagging for the identification of common disease genes. Nature Gen., 29, 233–237, 2001.
Kececioglu, J. and Gusfield, D. Reconstructing a history of recombinations from a set of sequences. Disc. Appl. Math., 88, 239–260, 1998.
Kimura, M. Theoretical foundations of population genetics at the molecular level. Theoret. Pop. Biol., 2, 174–208, 1971.
Maynard Smith, J. Analyzing the mosaic structure of genes. J. Mol. Evol., 34, 126–129, 1992.
Maynard Smith, J. and Smith, N.H. Detecting recombination from gene trees. Mol. Biol. Evol., 15, 590–599, 1998.
Nickerson, D. A., Taylor, S. L., Fullerton, S. M., Weiss, K. M., Clark, A. G., Stengrd, J. H., Salomaa, V., Boerwinkle, E., and Sing, C. F. Sequence diversity and large-scale typing of SNPs in the human apolipoprotein E gene. Gen. Res., 10, 1532–1545, 2000.
Patil, N., Berno, A.J., Hinds, D.A., Barrett, W.A., Doshi, J.M., Hacker, C.R., Kautzer, C.R., Lee, D.H., Marjoribanks, C., McDonough, D.P., Nguyen, B.T.N., Norris, M.C., Sheehan, J.B., Shen, N., Stern, D., Stokowski, R.P., Thomas, D.J., Trulson, M.O., Vyas, K.R., Frazer, K.A., Fodor, S.P.A., and Cox, D.R. Blocks of limited haplotype diversity revealed by high-resolution scanning of human chromosome 21. Science, 294, 1719–1723, 2001.
Posada, D., and Crandall, K.A. Evaluation of methods for detecting recombination from DNA sequences: computer simulations. Proc. Natl. Acad. Sci. USA, 98, 13757–13762, 2001.
Sawyer, S. Statistical tests for detecting gene conversion. Mol. Biol. Evol., 6, 526–536, 1989.
Spang, R., Rehmsmeier, M., and Stoye, J. Sequence database search using jumping alignments. In Proc. Intel. Sys. Mol. Biol., ISMB’00, 367–375, 2000.
Stephens, M., Smith, N.J., and Donnelly, P. A new statistical method for haplotype reconstruction from population data. Am. J. Hum. Gen., 68, 978–989, 2001.
Venter, J.C., Adams, M.D., Myers, E.W., et al. The sequence of the human genome. Science, 291, 1304–1351, 2001.
Wang, L. Zhang, K., and Zhang, L. Perfect phylogentic networks with recombination. J. Comp. Biol., 8, 69–78, 2001.
Weiler, G. F. Phylogenetic profiles: a graphical method for detecting genetic recombinations in homologous sequences. Mol. Biol. Evol., 15, 326–335, 1998.
Wiuf, C., Christensen, T., and Hein, J. A simulation study of the reliability of recombination detection methods. Mol. Biol. Evol., 18,1929–1939, 2001.
Zhang, K., Deng, M., Chen, T., Waterman, M. S., and Sun, F. A dynamic programming algorithm for haplotype block partition. Proc. Natl. Acad. Sci. USA, 99, 7335–7339, 2002.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Schwartz, R., Clark, A.G., Istrail, S. (2002). Methods for Inferring Block-Wise Ancestral History from Haploid Sequences. In: Guigó, R., Gusfield, D. (eds) Algorithms in Bioinformatics. WABI 2002. Lecture Notes in Computer Science, vol 2452. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45784-4_4
Download citation
DOI: https://doi.org/10.1007/3-540-45784-4_4
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44211-0
Online ISBN: 978-3-540-45784-8
eBook Packages: Springer Book Archive