An MCMC algorithm for haplotype assembly from whole-genome sequence data
Open accessThe DOI matches its Crossref record; 15 of the 15 references it cites were found in a registry or an index.
Abstract
In comparison to genotypes, knowledge about haplotypes (the combination of alleles present on a single chromosome) is much more useful for whole-genome association studies and for making inferences about human evolutionary history. Haplotypes are typically inferred from population genotype data using computational methods. Whole-genome sequence data represent a promising resource for constructing haplotypes spanning hundreds of kilobases for an individual. In this article, we propose a Markov chain Monte Carlo (MCMC) algorithm, HASH (h aplotype a ssembly for s ingle h uman), for assembling haplotypes from sequenced DNA fragments that have been mapped to a reference genome assembly. The transitions of the Markov chain are generated using min-cut computations on graphs derived from the sequenced fragments. We have applied our method to infer haplotypes using whole-genome shotgun sequence data from a recently sequenced human individual. The high sequence coverage and presence of mate pairs result in fairly long haplotypes (N50 length ∼ 350 kb). Based on comparison of the sequenced fragments against the individual haplotypes, we demonstrate that the haplotypes for this individual inferred using HASH are significantly more accurate than the haplotypes estimated using a previously proposed greedy heuristic and a simple MCMC method. Using haplotypes from the HapMap project, we estimate the switch error rate of the haplotypes inferred using HASH to be quite low, ∼1.1%. Our Markov chain Monte Carlo algorithm represents a general framework for haplotype assembly that can be applied to sequence data generated by other sequencing technologies. The code implementing the methods and the phased individual haplotypes can be downloaded from http://www.cse.ucsd.edu/users/vibansal/HASH/.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
dbSNP: the NCBI database of genetic variation
Sherry, S. T. (2001) · Nucleic Acids Research · doi:10.1093/nar/29.1.308 · Cited by 7,502
A haplotype map of the human genome
The International HapMap Consortium (2005) · Nature · doi:10.1038/nature04226 · Cited by 5,858
Base-Calling of Automated Sequencer Traces Using Phred. II. Error Probabilities
Ewing, B., & Green, P. (1998) · Genome Research · doi:10.1101/gr.8.3.186 · Cited by 5,439 · cited 1×
“For example, the quality scores might be obtained using phred ( Ewing and Green 1998 ).”
MethodA second generation human haplotype map of over 3.1 million SNPs
The International HapMap Consortium (2007) · Nature · doi:10.1038/nature06258 · Cited by 4,438
A genome-wide association study identifies novel risk loci for type 2 diabetes
Sladek, R., Rocheleau, G., Rung, J., Dina, C., Shen, L., Serre, D., Boutin, P., Vincent, D., Belisle, A., Hadjadj, S., et al. (2007) · Nature · doi:10.1038/nature05616 · Cited by 2,993
A new multipoint method for genome-wide association studies by imputation of genotypes
Marchini, J., Howie, B., Myers, S., McVean, G., & Donnelly, P. (2007) · Nature Genetics · doi:10.1038/ng2088 · Cited by 2,609
Genome-wide association study identifies novel breast cancer susceptibility loci
Easton, D. F., Pooley, K. A., Dunning, A. M., Pharoah, P. D. P., Thompson, D., Ballinger, D. G., Struewing, J. P., Morrison, J., Field, H., Luben, R., et al. (2007) · Nature · doi:10.1038/nature05887 · Cited by 2,319
Genome-wide detection and characterization of positive selection in human populations
The International HapMap Consortium, Sabeti, P. C., Varilly, P., Fry, B., Lohmueller, J., Hostetter, E., Cotsapas, C., Xie, X., Byrne, E. H., McCarroll, S. A., et al. (2007) · Nature · doi:10.1038/nature06250 · Cited by 2,131 · cited 1×
“, estimate the fine-scale distribution of recombination events and identify genes that show signs of positive selection (The International HapMap Consortium 2005; Sabeti et al. 2007).”
BackgroundMaximum-likelihood estimation of molecular haplotype frequencies in a diploid population.
(1995) · Molecular Biology and Evolution · doi:10.1093/oxfordjournals.molbev.a040269 · Cited by 1,950 · cited 1×
“In the absence of molecular methods for determining haplotypes, haplotypes are inferred computationally from SNPs genotyped in a sample of individuals from a population (Clark 1990; Excoffier and Slatkin 1995; Stephens et al. 2001; Niu et al. 2002; Stephens and Donnelly 2003).”
MethodThe complete genome of an individual by massively parallel DNA sequencing
Wheeler, D. A., Srinivasan, M., Egholm, M., Shen, Y., Chen, L., McGuire, A., He, W., Chen, Y.-J., Makhijani, V., Roth, G. T., et al. (2008) · Nature · doi:10.1038/nature06884 · Cited by 1,838 · cited 1×
“Many individual genomes have been sequenced (Levy et al. 2007; Wheeler et al. 2008), and hundreds of human individuals are proposed to be sequenced in the future (Kaiser 2008).”
BackgroundThe Diploid Genome Sequence of an Individual Human
Levy, S., Sutton, G., Ng, P. C., Feuk, L., Halpern, A. L., Walenz, B. P., Axelrod, N., Huang, J., Kirkness, E. F., Denisov, G., et al. (2007) · PLoS Biology · doi:10.1371/journal.pbio.0050254 · Cited by 1,778
Self-citationA Common Variant on Chromosome 9p21 Affects the Risk of Myocardial Infarction
Helgadottir, A., Thorleifsson, G., Manolescu, A., Gretarsdottir, S., Blondal, T., Jonasdottir, A., Jonasdottir, A., Sigurdsson, A., Baker, A., Palsson, A., et al. (2007) · Science · doi:10.1126/science.1142842 · Cited by 1,594
A Common Allele on Chromosome 9 Associated with Coronary Heart Disease
McPherson, R., Pertsemlidis, A., Kavaslar, N., Stewart, A., Roberts, R., Cox, D. R., Hinds, D. A., Pennacchio, L. A., Tybjaerg-Hansen, A., Folsom, A. R., et al. (2007) · Science · doi:10.1126/science.1142447 · Cited by 1,587
Inference of haplotypes from PCR-amplified samples of diploid populations.
(1990) · Molecular Biology and Evolution · doi:10.1093/oxfordjournals.molbev.a040591 · Cited by 765
A Comparison of Phasing Algorithms for Trios and Unrelated Individuals
Marchini, J., Cutler, D., Patterson, N., Stephens, M., Eskin, E., Halperin, E., Lin, S., Qin, Z. S., Munro, H. M., Abecasis, G. R., et al. (2006) · The American Journal of Human Genetics · doi:10.1086/500808 · Cited by 341
Cited by
Hon, G. C., Hawkins, R. D., Caballero, O. L., Lo, C., Lister, R., Pelizzola, M., Valsesia, A., Ye, Z., Kuan, S., Edsall, L. E., et al. (2012) · Genome Research · doi:10.1101/gr.125872.111 · Cited by 583
“sequenced reads to link SNPs together, we employed the previously developed error-correcting algorithms HASH and HapCUT to identify 269,392 phased haplotype blocks (Bansal and Bafna 2008; Bansal et al. 2008) with an N50 of 290 bp (Fig.”
MethodSelf-citationAssembly and diploid architecture of an individual human genome via single-molecule technologies
Pendleton, M., Sebra, R., Pang, A. W. C., Ummat, A., Franzen, O., Rausch, T., Stütz, A. M., Stedman, W., Anantharaman, T., Hastie, A., et al. (2015) · Nature Methods · doi:10.1038/nmeth.3454 · Cited by 474
W hats H ap : Weighted Haplotype Assembly for Future-Generation Sequencing Reads
Patterson, M., Marschall, T., Pisanti, N., van Iersel, L., Stougie, L., Klau, G. W., & Schönhuth, A. (2015) · Journal of Computational Biology · doi:10.1089/cmb.2014.0157 · Cited by 453
De Novo Discovery of Mutated Driver Pathways in Cancer
Vandin, F., Upfal, E., & Raphael, B. J. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-20036-6_44 · Cited by 434
HapCUT2: robust and accurate haplotype assembly for diverse sequencing technologies
Edge, P., Bafna, V., & Bansal, V. (2017) · Genome Research · doi:10.1101/gr.213462.116 · Cited by 379
Self-citation
Metadata
- Authors
- Bansal, V., Halpern, A. L., Axelrod, N., & Bafna, V.
- Venue
- Genome Research
- Publisher
- Cold Spring Harbor Laboratory
- Published
- 2008-08
- Volume
- 18
- Issue
- 8
- Pages
- 1336-1346
- ISSN
- 1088-9051 (ISSN-L)
- OpenAlex
- W2152559981
- Cited by
- 125
- References
- 15
- Type
- posted content
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.