Artificial Intelligence in Medicine
Volume 45, Issue 2 , Pages 135-150 , February 2009

Fully non-homogeneous hidden Markov model double net: A generative model for haplotype reconstruction and block discovery

  • Alessandro Perina

      Affiliations

    • Department of Computer Science, University of Verona, Strada le Grazie 15, 37134 Verona, Italy
    • Corresponding Author InformationCorresponding author. Tel.: +39 045 8027803; fax: +39 045 8027068.
    • ,
  • Marco Cristani

      Affiliations

    • Department of Computer Science, University of Verona, Strada le Grazie 15, 37134 Verona, Italy
    • ,
  • Luciano Xumerle

      Affiliations

    • Department of Mother and Child, Biology and Genetics, Section Biology and Genetics, University of Verona, Strada le Grazie 8, 37134 Verona, Italy
    • ,
  • Vittorio Murino

      Affiliations

    • Department of Computer Science, University of Verona, Strada le Grazie 15, 37134 Verona, Italy
    • ,
  • Pier Franco Pignatti

      Affiliations

    • Department of Mother and Child, Biology and Genetics, Section Biology and Genetics, University of Verona, Strada le Grazie 8, 37134 Verona, Italy
    • ,
  • Giovanni Malerba

      Affiliations

    • Department of Mother and Child, Biology and Genetics, Section Biology and Genetics, University of Verona, Strada le Grazie 8, 37134 Verona, Italy

Received 31 October 2007 ,Revised 21 August 2008 ,Accepted 22 August 2008.

References 

  1. Gabriel B, Schaffner SF, Nguyen H, Moore JM, Roy J, Blumenstiel B,, et al. The structure of haplotype blocks in the human genome. Science. 2002;296(5576):2225–2229
  2. Zhang K, Calabrese P, Nordborg M, Sun F. Haplotype block structure and its application to association studies: power and study designs. American Journal of Human Genetics. 2002;71(6):1386–1394
  3. Stephens M, Donnelly P. A comparison of Bayesian methods for haplotype reconstruction from population genotype data. American Journal of Human Genetics. 2003;73(5):1162–1169
  4. Chen Y, Lin CH, Sabatti C. Volume measures for linkage disequilibrium. BMC Genetics. 2006;7(1):54–61
  5. Rastas P, Koivisto M, Mannila H, Ukkonen E. A hidden markov technique for haplotype reconstruction. In:  Casadio R,  Myers G editor. Algorithms in Bioinformatics, vol. 3692 of Lecture Notes in Computer Science. New York, NY, USA: Springer; 2005;p. 140–151
  6. Kimmel G, Shamir R. Gerbil: Genotype resolution and block identification using likelihood. Proceedings of the National Academy of Science of the United States of America (PNAS). 2005;102:158–162
  7. Scheet P, Stephens M. A fast and flexible statistical model for large-scale population genotype data: applications to inferring missing genotypes and haplotypic phase. American Journal of Human Genetics. 2006;78(4):629–644
  8. Niu T, Qin ZS, Xu X, Liu JS. Bayesian haplotype inference for multiple linked single-nucleotide polymorphisms. American Journal of Human Genetics. 2002;78(1):157–169
  9. Zhaohui TN, Qin ZS, Liu JS. Partition–ligation–expectation–maximization algorithm for haplotype inference with single-nucleotide polymorphisms. American Journal of Human Genetics. 2002;71(5):1242–1247
  10. D. Clayton, Snphap: A program for estimating frequencies of large haplotypes of snps (version 1.0), http://www-gene.cimr.cam.ac.uk/clayton/software/snphap.txt, Accessed: 11 December 2007 (2001).
  11. Rabiner L. A tutorial on Hidden Markov Models and selected applications in speech recognition. Proceedings of IEEE. 1989;77(2):257–286
  12. Jordan M, Ghahramani Z, Jaakkola T, Saul L. An introduction to variational methods for graphical models. Machine Learning. 1999;37(2):183–233
  13. Jojic V, Jojic N, Heckerman D. Joint discovery of haplotype blocks and complex trait associations from snp sequences. In:  Chickering DM,  Halpern JY editor. Proceedings of the Uncertainty in artificial intelligence 2004, UAI’04. Arlington, Virginia: UAI Press; 2004;p. 286–292
  14. Duda RO, Hart PE, Stork DG. Pattern Classification. 2nd Edition. Hoboken, NJ: Wiley–Interscience; 2000;
  15. Li W. Dna segmentation as a model selection process. In:  Lengauer T,  Sankoff D,  Istrail S,  Peuvzner P,  Waterman M editor. RECOMB’01: Proceedings of the fifth annual international conference on computational biology. New York, NY, USA: ACM; 2001;p. 204–210
  16. Koivisto M, Perda M, Varilo T, Hennah W, Ekelund J, Lukk M,, et al. An mdl method for finding haplotype blocks and for estimating the strength of haplotype block boundaries. In:  Altman RB,  Dunker AK,  Hunter L,  Jung TA,  Klein TE editor. Proceedings of the Pacific Symposium on Biocomputing (PSB), vol. 8. Singapore: World Scientific; 2003;p. 502–513
  17. Rissanen J. Modelling by shortest data description. Automatica. 1978;14:465–471
  18. Ghahramani Z, Beal M. Graphical models and variational methods. In:  Opper M,  Saad D editor. Advanced mean field methods: theory and practice. Cambridge, MA, USA: MIT Press; 2001;p. 161–178Ch. 11
  19. D. Heckerman, A tutorial on learning with Bayesian networks, Tech. Re MSR-TR-95–06, Microsoft Research, Redmond, WA, USA, revised November, 1996 (1995).
  20. Ghahramani Z. Learning dynamic Bayesian networks. In:  Giles CL,  Gori M editor. Adaptive Processing of Sequences and Data Structures. Berlin: Springer-Verlag; 1998;p. 168–197
  21. Jaakkola T. Tutorial on variational approximation methods. In:  Opper M,  Saad D editor. Advanced mean field methods: theory and practice. Cambridge, MA, USA: MIT Press; 2001;p. 129–160Ch. 10
  22. Jojic N, Winn J, Zitnick L. Escaping local minima through hierarchical model selection: automatic object discovery, segmentation, and tracking in video. In: CVPR’06: Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition. Washington, DC, USA: IEEE Computer Society; 2006;p. 117–124
  23. Dempster A, Laird N, Rubin D. Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society. 1977;39:1–38
  24. Mueller JC. Linkage disequilibrium for different scales and applications. Briefings in Bioinformatics. 2004;5(4):355–364
  25. International HapMap Consortium . The international hapmap project. Nature. 2003;426(6968):789–796
  26. Excoffier L, Slatkin M. Maximum-likelihood estimation of molecular haplotype frequencies in a diploid population. Molecular Biology and Evolution. 1995;12(5):921–927
  27. Adkins RM. Comparison of the accuracy of methods of computational haplotype inference using a large empirical dataset. BMC Genetics. 2004;5:22–28
  28. Horan M, Millar DS, Hedderich J, Lewis G, Newsway V, Mo N,, et al. Human growth hormone 1 (gh1) gene expression: complex haplotype-dependent influence of polymorphic variation in the proximal promoter and locus control region. Human Mutation. 2003;21(4):408–423
  29. Schwartz R, Halldorsson BV, Bafna V, Clark AG, Istrail S. Robustness of inference of haplotype block structure. Journal of Computational Biology. 2003;10(1):13–19
  30. Indap A, Marth G, Struble C, Tonellato P, Olivier M. Analysis of concordance of different haplotype block partitioning algorithms. BMC Bioinformatics. 2005;6(1):303–316
  31. Malerba G, Schaeffer L, Xumerle L. Snps of the fads gene cluster are associated with polyunsaturated fatty acids in a cohort of patients with cardiovascular disease. Lipids. 2008;5(4):355–364
  32. Lewontin RC. The interaction of selection of linkage. Genetics. 1964;49(1):49–67
  33. Carlson C, Eberle M, Rieder M, Yi Q, Kruglyak L, Nickerson D. Selecting a maximally informative set of single-nucleotide polymorphisms for association analyses using linkage disequilibrium. American Journal of Human Genetics. 2004;74(1):106–120
  34. Gohlke H, Illig T, Bahnweg M, Klopp N, Andre E, Altmuller J,, et al. Association of the interleukin-1 receptor antagonist gene with asthma. American Journal Respiratory and Critical Care Medicine. 2004;169(11):1217–1223

PII: S0933-3657(08)00127-9

doi: 10.1016/j.artmed.2008.08.015

Artificial Intelligence in Medicine
Volume 45, Issue 2 , Pages 135-150 , February 2009

Article Tools

* Image Usage & Resolution