{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T11:57:06Z","timestamp":1772366226848,"version":"3.50.1"},"reference-count":26,"publisher":"Oxford University Press (OUP)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016,6,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Motivation: \u00a0Haplotype assembly is the computational problem of reconstructing haplotypes in diploid organisms and is of fundamental importance for characterizing the effects of single-nucleotide polymorphisms on the expression of phenotypic traits. Haplotype assembly highly benefits from the advent of \u2018future-generation\u2019 sequencing technologies and their capability to produce long reads at increasing coverage. Existing methods are not able to deal with such data in a fully satisfactory way, either because accuracy or performances degrade as read length and sequencing coverage increase or because they are based on restrictive assumptions.<\/jats:p>\n               <jats:p>Results: By exploiting a feature of future-generation technologies\u2014the uniform distribution of sequencing errors\u2014we designed an exact algorithm, called HapCol, that is exponential in the maximum number of corrections for each single-nucleotide polymorphism position and that minimizes the overall error-correction score. We performed an experimental analysis, comparing HapCol with the current state-of-the-art combinatorial methods both on real and simulated data. On a standard benchmark of real data, we show that HapCol is competitive with state-of-the-art methods, improving the accuracy and the number of phased positions. Furthermore, experiments on realistically simulated datasets revealed that HapCol requires significantly less computing resources, especially memory. Thanks to its computational efficiency, HapCol can overcome the limits of previous approaches, allowing to phase datasets with higher coverage and without the traditional all-heterozygous assumption.<\/jats:p>\n               <jats:p>Availability and implementation: Our source code is available under the terms of the GNU General Public License at http:\/\/hapcol.algolab.eu\/.<\/jats:p>\n               <jats:p>Contact: \u00a0bonizzoni@disco.unimib.it<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btv495","type":"journal-article","created":{"date-parts":[[2015,8,28]],"date-time":"2015-08-28T00:18:54Z","timestamp":1440721134000},"page":"1610-1617","source":"Crossref","is-referenced-by-count":41,"title":["H<scp>ap<\/scp>C<scp>ol<\/scp>: accurate and memory-efficient haplotype assembly from long reads"],"prefix":"10.1093","volume":"32","author":[{"given":"Yuri","family":"Pirola","sequence":"first","affiliation":[{"name":"1 Dipartimento di Informatica Sistemistica e Comunicazione (DISCo), Univ. degli Studi di Milano-Bicocca, Milan, Italy,"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Simone","family":"Zaccaria","sequence":"additional","affiliation":[{"name":"1 Dipartimento di Informatica Sistemistica e Comunicazione (DISCo), Univ. degli Studi di Milano-Bicocca, Milan, Italy,"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Riccardo","family":"Dondi","sequence":"additional","affiliation":[{"name":"2 Dipartimento di Scienze Umane e Sociali, Univ. degli Studi di Bergamo, Bergamo, Italy,"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gunnar W.","family":"Klau","sequence":"additional","affiliation":[{"name":"3 Life Sciences group, Centrum Wiskunde & Informatica (CWI), Amsterdam, The Netherlands,"},{"name":"4 ERABLE Team, INRIA, Lyon, France and"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nadia","family":"Pisanti","sequence":"additional","affiliation":[{"name":"4 ERABLE Team, INRIA, Lyon, France and"},{"name":"5 Dipartimento di Informatica, Univ. degli Studi di Pisa, Pisa, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Paola","family":"Bonizzoni","sequence":"additional","affiliation":[{"name":"1 Dipartimento di Informatica Sistemistica e Comunicazione (DISCo), Univ. degli Studi di Milano-Bicocca, Milan, Italy,"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2015,8,26]]},"reference":[{"key":"2023020112283395100_btv495-B1","doi-asserted-by":"crossref","first-page":"577","DOI":"10.1089\/cmb.2012.0084","article-title":"HapCompass: a fast cycle basis algorithm for accurate haplotype assembly of sequence data","volume":"19","author":"Aguiar","year":"2012","journal-title":"J. Comput. Biol."},{"key":"2023020112283395100_btv495-B2","doi-asserted-by":"crossref","first-page":"i153","DOI":"10.1093\/bioinformatics\/btn298","article-title":"HapCUT: an efficient and accurate algorithm for the haplotype assembly problem","volume":"24","author":"Bansal","year":"2008","journal-title":"Bioinformatics"},{"key":"2023020112283395100_btv495-B3","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-19929-0_9","article-title":"On the fixed parameter tractability and approximability of the minimum error correction problem","volume-title":"CPM","author":"Bonizzoni","year":"2015"},{"key":"2023020112283395100_btv495-B4","doi-asserted-by":"crossref","first-page":"703","DOI":"10.1038\/nrg3054","article-title":"Haplotype phasing: existing methods and new developments","volume":"12","author":"Browning","year":"2011","journal-title":"Nat. Rev. Genet."},{"key":"2023020112283395100_btv495-B5","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1186\/1471-2164-13-375","article-title":"Pacific biosciences sequencing technology for genotyping and variation discovery in human data","volume":"13","author":"Carneiro","year":"2012","journal-title":"BMC Genomics"},{"key":"2023020112283395100_btv495-B6","doi-asserted-by":"crossref","first-page":"1938","DOI":"10.1093\/bioinformatics\/btt349","article-title":"Exact algorithms for haplotype assembly from whole-genome sequence data","volume":"29","author":"Chen","year":"2013","journal-title":"Bioinformatics"},{"key":"2023020112283395100_btv495-B7","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/s00453-007-0029-z","article-title":"The complexity of the single individual SNP haplotyping problem","volume":"49","author":"Cilibrasi","year":"2007","journal-title":"Algorithmica"},{"key":"2023020112283395100_btv495-B8","doi-asserted-by":"crossref","first-page":"491","DOI":"10.1038\/ng.806","article-title":"A framework for variation discovery and genotyping using next-generation DNA sequencing data","volume":"43","author":"DePristo","year":"2011","journal-title":"Nat. Genet."},{"key":"2023020112283395100_btv495-B9","first-page":"160","article-title":"ReFHap: a reliable and fast algorithm for single individual haplotyping","volume-title":"BCB","author":"Duitama","year":"2010"},{"key":"2023020112283395100_btv495-B10","doi-asserted-by":"crossref","first-page":"2041","DOI":"10.1093\/nar\/gkr1042","article-title":"Fosmid-based whole genome haplotyping of a HapMap trio child: evaluation of single individual haplotyping techniques","volume":"40","author":"Duitama","year":"2012","journal-title":"Nucleic Acids Res."},{"key":"2023020112283395100_btv495-B11","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1287\/ijoc.1040.0073","article-title":"Opportunities for combinatorial optimization in computational biology","volume":"16","author":"Greenberg","year":"2004","journal-title":"INFORMS J. Comput."},{"key":"2023020112283395100_btv495-B12","doi-asserted-by":"crossref","first-page":"i183","DOI":"10.1093\/bioinformatics\/btq215","article-title":"Optimal algorithms for haplotype assembly from whole-genome sequence data","volume":"26","author":"He","year":"2010","journal-title":"Bioinformatics"},{"key":"2023020112283395100_btv495-B13","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1089\/cmb.2012.0091","article-title":"Hap-seq: an optimal algorithm for haplotype phasing with imputation using sequencing data","volume":"20","author":"He","year":"2013","journal-title":"J. Comput. Biol."},{"key":"2023020112283395100_btv495-B14","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1038\/nmeth.3290","article-title":"Improved data analysis for the minion nanopore sequencer","volume":"12","author":"Jain","year":"2015","journal-title":"Nat. Methods"},{"key":"2023020112283395100_btv495-B15","volume-title":"The Art of Computer Programming","author":"Knuth","year":"2005"},{"key":"2023020112283395100_btv495-B16","doi-asserted-by":"crossref","first-page":"i379","DOI":"10.1093\/bioinformatics\/btu484","article-title":"Probabilistic single-individual haplotyping","volume":"30","author":"Kuleshov","year":"2014","journal-title":"Bioinformatics"},{"key":"2023020112283395100_btv495-B17","doi-asserted-by":"crossref","first-page":"261, 266","DOI":"10.1038\/nbt.2833","article-title":"Whole-genome haplotyping using long reads and statistical methods","volume":"32","author":"Kuleshov","year":"2014","journal-title":"Nat. Biotechnol."},{"key":"2023020112283395100_btv495-B18","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-44676-1_15","article-title":"SNPs problems, complexity, and algorithms","volume-title":"ESA","author":"Lancia","year":"2001"},{"key":"2023020112283395100_btv495-B19","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1093\/bib\/3.1.23","article-title":"Algorithmic strategies for the single nucleotide polymorphism haplotype assembly problem","volume":"3","author":"Lippert","year":"2002","journal-title":"Brief. Bioinform."},{"key":"2023020112283395100_btv495-B20","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1038\/nrg2986","article-title":"Genotype and SNP calling from next-generation sequencing data","volume":"12","author":"Nielsen","year":"2011","journal-title":"Nat. Rev. Genet."},{"key":"2023020112283395100_btv495-B21","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-319-05269-4_19","article-title":"WhatsHap: haplotype assembly for future-generation sequencing reads","volume-title":"RECOMB","author":"Patterson","year":"2014"},{"key":"2023020112283395100_btv495-B22","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1089\/cmb.2014.0157","article-title":"WhatsHap: weighted haplotype assembly for future-generation sequencing reads","volume":"6","author":"Patterson","year":"2015","journal-title":"J. Comput. Biol."},{"key":"2023020112283395100_btv495-B23","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1109\/TCBB.2011.51","article-title":"An efficient algorithm for haplotype inference on pedigrees with recombinations and mutations","volume":"9","author":"Pirola","year":"2012","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"2023020112283395100_btv495-B24","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1186\/gb-2013-14-6-405","article-title":"The advantages of SMRT sequencing","volume":"14","author":"Roberts","year":"2013","journal-title":"Genome Biol."},{"key":"2023020112283395100_btv495-B25","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1038\/nature11016","article-title":"Validation of ITD mutations in FLT3 as a therapeutic target in human acute myeloid leukaemia","volume":"485","author":"Smith","year":"2012","journal-title":"Nature"},{"key":"2023020112283395100_btv495-B26","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":"Comput. Biol. Chem."}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/11\/1610\/49019139\/bioinformatics_32_11_1610.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/11\/1610\/49019139\/bioinformatics_32_11_1610.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T22:31:52Z","timestamp":1675290712000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/32\/11\/1610\/1742594"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,8,26]]},"references-count":26,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2016,6,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btv495","relation":{},"ISSN":["1367-4811","1367-4803"],"issn-type":[{"value":"1367-4811","type":"electronic"},{"value":"1367-4803","type":"print"}],"subject":[],"published-other":{"date-parts":[[2016,6,1]]},"published":{"date-parts":[[2015,8,26]]}}}