{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,7]],"date-time":"2025-11-07T08:53:36Z","timestamp":1762505616629},"reference-count":28,"publisher":"Oxford University Press (OUP)","issue":"18","license":[{"start":{"date-parts":[[2016,10,2]],"date-time":"2016-10-02T00:00:00Z","timestamp":1475366400000},"content-version":"vor","delay-in-days":2275,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/2.0\/uk\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010,9,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: Single nucleotide polymorphisms are the most common form of variation in human DNA, and are involved in many research fields, from molecular biology to medical therapy. The technological opportunity to deal with long DNA sequences using shotgun sequencing has raised the problem of fragment recombination. In this regard, Single Individual Haplotyping (SIH) problem has received considerable attention over the past few years.<\/jats:p>\n               <jats:p>Results: In this article, we survey seven recent approaches to the SIH problem and evaluate them extensively using real human haplotype data from the HapMap project. We also implemented a data generator tailored to the current shotgun sequencing technology that uses haplotypes from the HapMap project.<\/jats:p>\n               <jats:p>Availability: The data we used to compare the algorithms are available on demand, since we think they represent an important benchmark that can be used to easily compare novel algorithmic ideas with the state of the art. Moreover, we had to re-implement six of the algorithms surveyed because the original code was not available to us. Five of these algorithms and the data generator used in this article endowed with a Web interface are available at http:\/\/bioalgo.iit.cnr.it\/rehap<\/jats:p>\n               <jats:p>Contact: \u00a0filippo.geraci@iit.cnr.it<\/jats:p>","DOI":"10.1093\/bioinformatics\/btq411","type":"journal-article","created":{"date-parts":[[2010,7,13]],"date-time":"2010-07-13T00:41:08Z","timestamp":1278981668000},"page":"2217-2225","source":"Crossref","is-referenced-by-count":57,"title":["A comparison of several algorithms for the single individual SNP haplotyping reconstruction problem"],"prefix":"10.1093","volume":"26","author":[{"given":"Filippo","family":"Geraci","sequence":"first","affiliation":[{"name":"Istituto di Informatica e Telemetica, CNR, V. Moruzzi 1, Pisa, Italy"}]}],"member":"286","published-online":{"date-parts":[[2010,7,11]]},"reference":[{"key":"2023012508232957900_B1","first-page":"153","article-title":"HapCUT: an efficient and accurate algorithm for the haplotype assembly problem","volume-title":"European Conference on Computational Biology","author":"Bansal","year":"2008"},{"key":"2023012508232957900_B2","doi-asserted-by":"crossref","first-page":"1336","DOI":"10.1101\/gr.077065.108","article-title":"An MCMC algorithm for haplotype assembly from whole-genome sequence data","volume":"18","author":"Bansal","year":"2008","journal-title":"Genome Res"},{"key":"2023012508232957900_B3","doi-asserted-by":"crossref","first-page":"535","DOI":"10.1089\/cmb.2008.0003","article-title":"Linear time probabilistic algorithms for the singular haplotype reconstruction problem from SNP fragments","volume":"15","author":"Chen","year":"2008","journal-title":"J. Comput. Biol"},{"key":"2023012508232957900_B4","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/s00453-007-0029-z","article-title":"On the complexity of the single individual SNP haplotyping problem","volume":"49","author":"Cilibrasi","year":"2007","journal-title":"Algorithmica"},{"key":"2023012508232957900_B5","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1038\/ng1001-229","article-title":"High-resolution haplotype structure in the human genome","volume":"29","author":"Daly","year":"2001","journal-title":"Nat. Genet"},{"key":"2023012508232957900_B6","doi-asserted-by":"crossref","first-page":"851","DOI":"10.1038\/nature06258","article-title":"A second generation human haplotype map of over 3.1 million SNPs","volume":"449","author":"Frazer","year":"2007","journal-title":"Nature"},{"key":"2023012508232957900_B7","first-page":"49","article-title":"A fast and accurate heuristic for the single individual SNP haplotyping problem with many gaps, high reading error rate and low coverage","volume-title":"Workshop on Algorithms in Bioinformatics, Philadelphia, PA, Lecture Notes in Computer Science","author":"Genovese","year":"2007"},{"key":"2023012508232957900_B8","doi-asserted-by":"crossref","first-page":"492","DOI":"10.1109\/TCBB.2008.67","article-title":"SpeedHap: an accurate heuristic for the single individual SNP haplotyping problem with many gaps, high reading error rate and low coverage","volume":"5","author":"Genovese","year":"2008","journal-title":"EEE\/ACM Trans. Comput. Biol. Bioinform"},{"key":"2023012508232957900_B9","doi-asserted-by":"crossref","first-page":"1299","DOI":"10.1038\/nature04226","article-title":"A haplotype map of the human genome","volume":"437","author":"HapMap","year":"2005","journal-title":"Nature"},{"key":"2023012508232957900_B10","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","article-title":"Reducibility among combinatorial problems","author":"Karp","year":"1972","journal-title":"Complex. Comput. Comput"},{"key":"2023012508232957900_B11","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/0166-218X(91)90086-C","article-title":"An introduction to randomized algorithms","volume":"34","author":"Karp","year":"1991","journal-title":"Discrete Appl. Math"},{"key":"2023012508232957900_B12","first-page":"182","article-title":"SNPs problems, complexity, and algorithms","volume-title":"Proceedings of the Ninth European Symposium on Algorithms, Aarhus, Denmark, Lecture Notes in Computer Science","author":"Lancia","year":"2001"},{"key":"2023012508232957900_B13","doi-asserted-by":"crossref","first-page":"2113","DOI":"10.1371\/journal.pbio.0050254","article-title":"The diploid genome sequence of an individual human","volume":"5","author":"Levy","year":"2007","journal-title":"PLoS Biol"},{"key":"2023012508232957900_B14","first-page":"207","article-title":"Haplotype reconstruction from SNP alignment","volume-title":"Proceedings of the Seventh International Conference on Computational Molecular Biology, Lisbon, Portugal, Lecture Notes in Computer Science","author":"Li","year":"2003"},{"key":"2023012508232957900_B15","first-page":"281","article-title":"Some methods for classification and analysis of multivariate observations","volume-title":"Fifth Berkeley Symposium on Mathematics, Statistics, and Probability, Statistical Laboratory of the University of California, Berkeley","author":"McQueen","year":"1967"},{"key":"2023012508232957900_B16","doi-asserted-by":"crossref","first-page":"1767","DOI":"10.1101\/gr.3770505","article-title":"Emerging technologies in DNA sequencing","volume":"15","author":"Metzker","year":"2005","journal-title":"Genome Res"},{"key":"2023012508232957900_B17","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/j.ygeno.2008.07.001","article-title":"Applications of next-generation sequencing technologies in functional genomics","volume":"5","author":"Morozova","year":"2008","journal-title":"J. Genomics"},{"key":"2023012508232957900_B18","first-page":"202","article-title":"A dataset generator for whole genome shotgun sequencing","volume-title":"Proceedings of the Seventh International Conference on Intelligent Systems for Molecular Biology","author":"Myers","year":"1999"},{"key":"2023012508232957900_B19","first-page":"266","article-title":"Fast hare: a fast heuristic for single individual SNP haplotype reconstruction","volume-title":"Workshop on Algorithms in Bioinformatics, Bergen, Norway, Lecture Notes in Computer Science","author":"Panconesi","year":"2004"},{"key":"2023012508232957900_B20","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1109\/SWAT.1974.22","article-title":"P-complete problems and approximate solutions","volume":"23","author":"Sahni","year":"1974","journal-title":"Annu. Symp. Switching Automata Theory"},{"key":"2023012508232957900_B21","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1186\/gm124","article-title":"The 1000 genomes project: new opportunities for research and social challenges","volume":"2","author":"Via","year":"2010","journal-title":"Genome Med"},{"key":"2023012508232957900_B22","doi-asserted-by":"crossref","first-page":"2456","DOI":"10.1093\/bioinformatics\/bti352","article-title":"Haplotype reconstruction from SNP fragments by minimum error correction","volume":"21","author":"Wang","year":"2005","journal-title":"Bioinformatics"},{"key":"2023012508232957900_B23","first-page":"162","article-title":"A markov chain model for haplotype assembly from SNP fragments","volume":"17","author":"Wang","year":"2006","journal-title":"Genome Inform"},{"key":"2023012508232957900_B24","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1016\/j.compbiolchem.2007.02.001","article-title":"A clustering algorithm based on two distance functions for MEC model","volume":"31","author":"Wang","year":"2007","journal-title":"J. Comput. Biol. Chem"},{"key":"2023012508232957900_B25","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1007\/s00453-007-9150-2","article-title":"An improved (and practical) parameterized algorithm for the individual haplotyping problem MFR with mate-pairs","volume":"52","author":"Xie","year":"2008","journal-title":"Algorithmica"},{"key":"2023012508232957900_B26","doi-asserted-by":"crossref","first-page":"72","DOI":"10.1109\/BMEI.2008.122","article-title":"A practical exact algorithm for the individual haplotyping problem MEC","volume-title":"BMEI : Proceedings of the 2008 International Conference on BioMedical Engineering and Informatics","author":"Xie","year":"2008"},{"key":"2023012508232957900_B27","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/j.compbiolchem.2005.05.001","article-title":"Haplotype assembly from aligned weighted SNP fragments","volume":"29","author":"Zhao","year":"2005","journal-title":"J. Comput. Biol. Chem"},{"key":"2023012508232957900_B28","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1007\/s11704-007-0027-y","article-title":"An overview of the haplotype problems and algorithms","volume":"1","author":"Zhao","year":"2007","journal-title":"Front. Comput. Sci. China"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/18\/2217\/48858333\/bioinformatics_26_18_2217.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/26\/18\/2217\/48858333\/bioinformatics_26_18_2217.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,25]],"date-time":"2023-01-25T08:24:06Z","timestamp":1674635046000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/26\/18\/2217\/208073"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,7,11]]},"references-count":28,"journal-issue":{"issue":"18","published-print":{"date-parts":[[2010,9,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btq411","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2010,9,15]]},"published":{"date-parts":[[2010,7,11]]}}}