The DOI matches its Crossref record; 17 of the 17 references it cites were found in a registry or an index.
HapCUT: an efficient and accurate algorithm for the haplotype assembly problem
Open accessAbstract
Motivation: The goal of the haplotype assembly problem is to reconstruct the two haplotypes (chromosomes) for an individual using a mix of sequenced fragments from the two chromosomes. This problem has been shown to be computationally intractable for various optimization criteria. Polynomial time algorithms have been proposed for restricted versions of the problem. In this article, we consider the haplotype assembly problem in the most general setting, i.e. fragments of any length and with an arbitrary number of gaps. Results: We describe a novel combinatorial approach for the haplotype assembly problem based on computing max-cuts in certain graphs derived from the sequenced fragments. Levy et al. have sequenced the complete genome of a human individual and used a greedy heuristic to assemble the haplotypes for this individual. We have applied our method HapCUTto infer haplotypes from this data and demonstrate that the haplotypes inferred using HapCUT are significantly more accurate (20–25% lower maximum error correction scores for all chromosomes) than the greedy heuristic and a previously published method, Fast Hare. We also describe a maximum likelihood based estimator of the absolute accuracy of the sequence-based haplotypes using population haplotypes from the International HapMap project. Availability: A program implementing HapCUT is available on request. Contact: vibansal@cs.ucsd.edu
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
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
(1979) · Cited by 43,841
A New Statistical Method for Haplotype Reconstruction from Population Data
Stephens, M., Smith, N. J., & Donnelly, P. (2001) · The American Journal of Human Genetics · doi:10.1086/319501 · Cited by 7,493
A haplotype map of the human genome
The International HapMap Consortium (2005) · Nature · doi:10.1038/nature04226 · Cited by 5,858
The 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 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
Algorithmic strategies for the single nucleotide polymorphism haplotype assembly problem
Lippert, R. (2002) · Briefings in Bioinformatics · doi:10.1093/bib/3.1.23 · Cited by 204
SNPs Problems, Complexity, and Algorithms
Lancia, G., Bafna, V., Istrail, S., Lippert, R., & Schwartz, R. (2001) · Lecture Notes in Computer Science · doi:10.1007/3-540-44676-1_15 · Cited by 198
Self-citationHaplotype reconstruction from SNP fragments by minimum error correction
Wang, R., Wu, L.-Y., Li, Z.-P., & Zhang, X.-S. (2005) · Computer applications in the biosciences · doi:10.1093/bioinformatics/bti352 · Cited by 142
Haplotyping as Perfect Phylogeny: A Direct Approach
Bafna, V., Gusfield, D., Lancia, G., & Yooseph, S. (2003) · Journal of Computational Biology · doi:10.1089/10665270360688048 · Cited by 137
Self-citationEFFICIENT RECONSTRUCTION OF HAPLOTYPE STRUCTURE VIA PERFECT PHYLOGENY
ESKIN, E., HALPERIN, E., & KARP, R. M. (2003) · Journal of Bioinformatics and Computational Biology · doi:10.1142/s0219720003000174 · Cited by 131
Cited by
Phased diploid genome assembly with single-molecule real-time sequencing
Chin, C.-S., Peluso, P., Sedlazeck, F. J., Nattestad, M., Concepcion, G. T., Clum, A., Dunn, C., O'Malley, R., Figueroa-Balderas, R., Morales-Cruz, A., et al. (2016) · Nature Methods · doi:10.1038/nmeth.4035 · Cited by 1,904
Chromatin architecture reorganization during stem cell differentiation
Dixon, J. R., Jung, I., Selvaraj, S., Shen, Y., Antosiewicz-Bourget, J. E., Lee, A. Y., Ye, Z., Kim, A., Rajagopal, N., Xie, W., et al. (2015) · Nature · doi:10.1038/nature14222 · Cited by 1,646
Haplotype phasing: existing methods and new developments
Browning, S. R., & Browning, B. L. (2011) · Nature Reviews Genetics · doi:10.1038/nrg3054 · Cited by 655
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
Self-citationNagarajan, N., & Pop, M. (2013) · Nature Reviews Genetics · doi:10.1038/nrg3367 · Cited by 474
Metadata
- Authors
- Bansal, V., & Bafna, V.
- Venue
- Bioinformatics
- Publisher
- Oxford University Press (OUP)
- Published
- 2008-08-09
- Volume
- 24
- Issue
- 16
- Pages
- i153-i159
- ISSN
- 1367-4803 (ISSN-L)
- 1367-4811
- OpenAlex
- W2164971951
- Cited by
- 262
- References
- 17
- FWCI
- 3.10
- Type
- journal article
- 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
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: HapCUT: an efficient and accurate algorithm for the haplotype assembly problem. https://app.cochat.ai/papers/10.1093/bioinformatics/btn298
- The paper
- Bansal, V., & Bafna, V. (2008). HapCUT: an efficient and accurate algorithm for the haplotype assembly problem. Bioinformatics. https://doi.org/10.1093/bioinformatics/btn298
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.