Bioinformatics Advance Access originally published online on February 26, 2004
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Bioinformatics 20(12) © Oxford University Press 2004; all rights reserved.
Haplotype reconstruction from genotype data using Imperfect Phylogeny
1 CS Division, University of California Berkeley, Berkeley, CA 92093-0114 USA and 2 School of Computer Science and Engineering, Hebrew University, Jerusalem, 91904 Israel
Received on November 27, 2002; revised on October 23, 2003; accepted on October 24, 2003
Advance Access Publication February 26, 2004
Critical to the understanding of the genetic basis for complex diseases is the modeling of human variation. Most of this variation can be characterized by single nucleotide polymorphisms (SNPs) which are mutations at a single nucleotide position. To characterize the genetic variation between different people, we must determine an individual's haplotype or which nucleotide base occurs at each position of these common SNPs for each chromosome. In this paper, we present results for a highly accurate method for haplotype resolution from genotype data. Our method leverages a new insight into the underlying structure of haplotypes that shows that SNPs are organized in highly correlated ‘blocks’. In a few recent studies, considerable parts of the human genome were partitioned into blocks, such that the majority of the sequenced genotypes have one of about four common haplotypes in each block. Our method partitions the SNPs into blocks, and for each block, we predict the common haplotypes and each individual's haplotype. We evaluate our method over biological data. Our method predicts the common haplotypes perfectly and has a very low error rate (<2% over the data) when taking into account the predictions for the uncommon haplotypes. Our method is extremely efficient compared with previous methods such as PHASE and HAPLOTYPER. Its efficiency allows us to find the block partition of the haplotypes, to cope with missing data and to work with large datasets.
Availability: The algorithm is available via a Web server at http://www.calit2.net/compbio/hap/
Contact: eran{at}eecs.berkeley.edu
* To whom correspondence should be addressed.
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  M. M. Fung, Y. Chen, M. S. Lipkowitz, R. M. Salem, V. Bhatnagar, M. Mahata, C. M. Nievergelt, F. Rao, S. K. Mahata, N. J. Schork, et al. Adrenergic beta-1 receptor genetic variation predicts longitudinal rate of GFR decline in hypertensive nephrosclerosis Nephrol. Dial. Transplant., December 1, 2009; 24(12): 3677 - 3686. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 B. K. Rana, J. Wessel, V. Mahboubi, F. Rao, J. Haeller, J. R. Gayen, E. Eskin, A. M. Valle, M. Das, S. K. Mahata, et al. Natural Variation within the Neuronal Nicotinic Acetylcholine Receptor Cluster on Human Chromosome 15q24: Influence on Heritable Autonomic Traits in Twin Pairs J. Pharmacol. Exp. Ther., November 1, 2009; 331(2): 419 - 428. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 P.-a. B. Shih, L. Wang, S. Chiron, G. Wen, C. Nievergelt, M. Mahata, S. Khandrika, F. Rao, M. M. Fung, S. K. Mahata, et al. Peptide YY (PYY) Gene Polymorphisms in the 3'-Untranslated and Proximal Promoter Regions Regulate Cellular Gene Expression and PYY Secretion and Metabolic Syndrome Traits in Vivo J. Clin. Endocrinol. Metab., November 1, 2009; 94(11): 4557 - 4566. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 Y. Chen, M. Mahata, F. Rao, S. Khandrika, M. Courel, M. M. Fung, K. Zhang, M. Stridsberg, M. G. Ziegler, B. A. Hamilton, et al. Chromogranin A Regulates Renal Function by Triggering Weibel-Palade Body Exocytosis J. Am. Soc. Nephrol., July 1, 2009; 20(7): 1623 - 1632. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 K. Zhang, F. Rao, B. K. Rana, J. R. Gayen, F. Calegari, A. King, P. Rosa, W. B. Huttner, M. Stridsberg, M. Mahata, et al. Autonomic Function in Hypertension: Role of Genetic Variation at the Catecholamine Storage Vesicle Protein Chromogranin B Circ Cardiovasc Genet, February 1, 2009; 2(1): 46 - 56. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 E. Gaitan-Solis, I.-Y. Choi, C. Quigley, P. Cregan, and J. Tohme Single Nucleotide Polymorphisms in Common Bean: Their Discovery and Genotyping Using a Multiplex Detection System The Plant Genome, November 1, 2008; 1(2): 125 - 134. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 Y. Chen, F. Rao, J. L. Rodriguez-Flores, M. Mahata, M. M. Fung, M. Stridsberg, S. M. Vaingankar, G. Wen, R. M. Salem, M. Das, et al. Naturally Occurring Human Genetic Variation in the 3'-Untranslated Region of the Secretory Protein Chromogranin A Is Associated With Autonomic Blood Pressure Regulation and Hypertension in a Sex-Dependent Fashion J. Am. Coll. Cardiol., October 28, 2008; 52(18): 1468 - 1481. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 Z. Ding, T. Mailund, and Y. S. Song Efficient whole-genome association mapping using local phylogenies for unphased genotype data Bioinformatics, October 1, 2008; 24(19): 2215 - 2221. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
K. L. Ayers and K. Lange Penalized estimation of haplotype frequencies Bioinformatics, July 15, 2008; 24(14): 1596 - 1602. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 A. Sundquist, E. Fratkin, C. B. Do, and S. Batzoglou Effect of genetic divergence in identifying ancestral origin using HAPAA Genome Res., April 1, 2008; 18(4): 676 - 682. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 F. Graziano, A. Ruzzo, F. Loupakis, E. Canestrari, D. Santini, V. Catalano, R. Bisonni, U. Torresi, I. Floriani, G. Schiavon, et al. Pharmacogenetic Profiling for Cetuximab Plus Irinotecan Therapy in Patients With Refractory Advanced Colorectal Cancer J. Clin. Oncol., March 20, 2008; 26(9): 1427 - 1434. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 H. M. Kang, N. A. Zaitlen, C. M. Wade, A. Kirby, D. Heckerman, M. J. Daly, and E. Eskin Efficient Control of Population Structure in Model Organism Association Mapping Genetics, March 1, 2008; 178(3): 1709 - 1723. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
L. M. Matzkin The Molecular Basis of Host Adaptation in Cactophilic Drosophila: Molecular Evolution of a Glutathione S-Transferase Gene (GstD1) in Drosophila mojavensis Genetics, February 1, 2008; 178(2): 1073 - 1083. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
G. Lin, Z. Wang, L. Wang, Y.-L. Lau, and W. Yang Identification of linked regions using high-density SNP genotype data in linkage analysis Bioinformatics, January 1, 2008; 24(1): 86 - 93. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
B. Kirkpatrick, C. S. Armendariz, R. M. Karp, and E. Halperin HAPLOPOOL: improving haplotype frequency estimation through DNA pools and phylogenetic modeling Bioinformatics, November 15, 2007; 23(22): 3048 - 3055. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
J. H. Kim, M. S. Waterman, and L. M. Li Diploid genome reconstruction of Ciona intestinalis and comparative analysis with Ciona savignyi Genome Res., July 1, 2007; 17(7): 1101 - 1110. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 J. E. Povey, F. Darakhshan, K. Robertson, Y. Bisset, M. Mekky, J. Rees, V. Doherty, G. Kavanagh, N. Anderson, H. Campbell, et al. DNA repair gene polymorphisms and genetic predisposition to cutaneous melanoma Carcinogenesis, May 1, 2007; 28(5): 1087 - 1093. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 F. Rao, J. Wessel, G. Wen, L. Zhang, B. K. Rana, B. P. Kennedy, T. A. Greenwood, R. M. Salem, Y. Chen, S. Khandrika, et al. Renal Albumin Excretion: Twin Studies Identify Influences of Heredity, Environment, and Adrenergic Pathway Polymorphism Hypertension, May 1, 2007; 49(5): 1015 - 1031. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 F. Rao, G. Wen, J. R. Gayen, M. Das, S. M. Vaingankar, B. K. Rana, M. Mahata, B. P. Kennedy, R. M. Salem, M. Stridsberg, et al. Catecholamine Release-Inhibitory Peptide Catestatin (Chromogranin A352-372): Naturally Occurring Amino Acid Variant Gly364Ser Causes Profound Changes in Human Autonomic Activity and Alters Risk for Hypertension Circulation, May 1, 2007; 115(17): 2271 - 2281. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 K. B. Beckman, K. J. Abel, A. Braun, and E. Halperin Using DNA pools for genotyping trios Nucleic Acids Res., November 14, 2006; 34(19): e129 - e129. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
T. M. Seasholtz, J. Wessel, F. Rao, B. K. Rana, S. Khandrika, B. P. Kennedy, E. O. Lillie, M. G. Ziegler, D. W. Smith, N. J. Schork, et al. Rho Kinase Polymorphism Influences Blood Pressure and Systemic Vascular Resistance in Human Twins: Role of Heredity Hypertension, May 1, 2006; 47(5): 937 - 947. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
E. L. Riddle, B. K. Rana, K. K. Murthy, F. Rao, E. Eskin, D. T. O'Connor, and P. A. Insel Polymorphisms and Haplotypes of the Regulator of G Protein Signaling-2 Gene in Normotensives and Hypertensives Hypertension, March 1, 2006; 47(3): 415 - 420. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
D. Brinza and A. Zelikovsky 2SNP: scalable phasing based on 2-SNP haplotypes Bioinformatics, February 1, 2006; 22(3): 371 - 373. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
N. A. Zaitlen, H. M. Kang, M. L. Feolo, S. T. Sherry, E. Halperin, and E. Eskin Inference and analysis of haplotypes from combined genotyping studies deposited in dbSNP Genome Res., November 1, 2005; 15(11): 1594 - 1600. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 T. D. Cannon, W. Hennah, T. G. M. van Erp, P. M. Thompson, J. Lonnqvist, M. Huttunen, T. Gasperoni, A. Tuulio-Henriksson, T. Pirkola, A. W. Toga, et al. Association of DISC1/TRAX Haplotypes With Schizophrenia, Reduced Prefrontal Gray Matter, and Impaired Short- and Long-term Memory Arch Gen Psychiatry, November 1, 2005; 62(11): 1205 - 1213. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
S. J. Lindsay, J. K. Bonfield, and M. E. Hurles Shotgun haplotyping: a novel method for surveying allelic sequence variation Nucleic Acids Res., October 12, 2005; 33(18): e152 - e152. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
Z. Li, W. Zhou, X.-S. Zhang, and L. Chen A parsimonious tree-grow method for haplotype inference Bioinformatics, September 1, 2005; 21(17): 3475 - 3481. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
J. P. Etzel, B. K. Rana, G. Wen, R. J. Parmer, N. J. Schork, D. T. O'Connor, and P. A. Insel Genetic Variation at the Human {alpha}2B-Adrenergic Receptor Locus: Role in Blood Pressure Variation and Yohimbine Response Hypertension, June 1, 2005; 45(6): 1207 - 1213. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
R.-S. Wang, L.-Y. Wu, Z.-P. Li, and X.-S. Zhang Haplotype reconstruction from SNP fragments by minimum error correction Bioinformatics, May 15, 2005; 21(10): 2456 - 2462. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 D. A. Hinds, L. L. Stuve, G. B. Nilsen, E. Halperin, E. Eskin, D. G. Ballinger, K. A. Frazer, and D. R. Cox Whole-Genome Patterns of Common DNA Variation in Three Human Populations Science, February 18, 2005; 307(5712): 1072 - 1079. [Abstract] [Full Text] [PDF]
|
|