{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T23:51:39Z","timestamp":1773273099951,"version":"3.50.1"},"reference-count":21,"publisher":"Oxford University Press (OUP)","issue":"18","license":[{"start":{"date-parts":[[2019,1,25]],"date-time":"2019-01-25T00:00:00Z","timestamp":1548374400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019,9,15]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Summary<\/jats:title>\n                    <jats:p>Haplotype assembly of polyploids is an open issue in plant genomics. Recent experimental studies on highly heterozygous autotetraploid potato have shown that available methods do not deliver satisfying results in practice. We propose an optimal method to assemble haplotypes of highly heterozygous polyploids from Illumina short-sequencing reads. Our method is based on a generalization of the existing minimum fragment removal model to the polyploid case and on new integer linear programs to reconstruct optimal haplotypes. We validate our methods experimentally by means of a combined evaluation on simulated and experimental data based on 83 previously sequenced autotetraploid potato cultivars. Results on simulated data show that our methods produce highly accurate haplotype assemblies, while results on experimental data confirm a sensible improvement over the state of the art.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability and implementation<\/jats:title>\n                    <jats:p>Executables for Linux at http:\/\/github.com\/Computational Genomics\/HaplotypeAssembler.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Supplementary information<\/jats:title>\n                    <jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btz060","type":"journal-article","created":{"date-parts":[[2019,1,23]],"date-time":"2019-01-23T10:04:56Z","timestamp":1548237896000},"page":"3279-3286","source":"Crossref","is-referenced-by-count":9,"title":["Haplotype assembly of autotetraploid potato using integer linear programing"],"prefix":"10.1093","volume":"35","author":[{"given":"Enrico","family":"Siragusa","sequence":"first","affiliation":[{"name":"IBM T J Watson Research Center, Yorktown Heights , NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Niina","family":"Haiminen","sequence":"additional","affiliation":[{"name":"IBM T J Watson Research Center, Yorktown Heights , NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard","family":"Finkers","sequence":"additional","affiliation":[{"name":"Wageningen UR Plant Breeding , Wageningen, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Richard","family":"Visser","sequence":"additional","affiliation":[{"name":"Wageningen UR Plant Breeding , Wageningen, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Laxmi","family":"Parida","sequence":"additional","affiliation":[{"name":"IBM T J Watson Research Center, Yorktown Heights , NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2019,1,25]]},"reference":[{"key":"2023013108053664100_btz060-B1","doi-asserted-by":"crossref","first-page":"i352","DOI":"10.1093\/bioinformatics\/btt213","article-title":"Haplotype assembly in polyploid genomes and identical by descent shared tracts","volume":"29","author":"Aguiar","year":"2013","journal-title":"Bioinformatics"},{"key":"2023013108053664100_btz060-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":"2023013108053664100_btz060-B3","doi-asserted-by":"crossref","first-page":"e1003502","DOI":"10.1371\/journal.pcbi.1003502","article-title":"Haptree: a novel Bayesian framework for single individual polyplotyping using NGS data","volume":"10","author":"Berger","year":"2014","journal-title":"PLoS Comput. Biol."},{"key":"2023013108053664100_btz060-B4","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1089\/cmb.2015.0220","article-title":"On the minimum error correction problem for haplotype assembly in diploid and polyploid genomes","volume":"23","author":"Bonizzoni","year":"2016","journal-title":"J. Comput. Biol."},{"key":"2023013108053664100_btz060-B5","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":"2023013108053664100_btz060-B6","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1186\/s12864-015-1408-5","article-title":"SDhaP: haplotype assembly for diploids and polyploids via semi-definite programming","volume":"16","author":"Das","year":"2015","journal-title":"BMC Genomics"},{"key":"2023013108053664100_btz060-B7","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1186\/s12859-018-2012-x","article-title":"Better ILP models for haplotype assembly","volume":"19","author":"Etemadi","year":"2018","journal-title":"BMC Bioinformatics"},{"key":"2023013108053664100_btz060-B8","article-title":"Mason\u2013a read simulator for second generation sequencing data","author":"Holtgrewe","year":"2010","journal-title":"Technical report"},{"key":"2023013108053664100_btz060-B9","doi-asserted-by":"crossref","first-page":"2520","DOI":"10.1093\/bioinformatics\/bts480","article-title":"Snakemake: a scalable bioinformatics workflow engine","volume":"28","author":"K\u00f6ster","year":"2012","journal-title":"Bioinformatics"},{"key":"2023013108053664100_btz060-B10","first-page":"182","article-title":"SNPs problems, complexity, and algorithms","volume-title":"European Symposium on Algorithms","author":"Lancia","year":"2001"},{"key":"2023013108053664100_btz060-B11","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. Bioinformatics"},{"key":"2023013108053664100_btz060-B12","doi-asserted-by":"crossref","DOI":"10.1109\/TCBB.2018.2858803","article-title":"Polycluster: minimum fragment disagreement clustering for polyploid phasing","author":"Mazrouee","year":"2018","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"2023013108053664100_btz060-B13","first-page":"387","article-title":"Exploiting next-generation sequencing to solve the haplotyping puzzle in polyploids: a simulation study","volume":"19","author":"Motazedi","year":"2017","journal-title":"Brief. Bioinform."},{"key":"2023013108053664100_btz060-B14","doi-asserted-by":"crossref","first-page":"e0170941","DOI":"10.1371\/journal.pone.0170941","article-title":"Single marker and haplotype-based association analysis of semolina and pasta colour in elite durum wheat breeding lines using a high-density consensus map","volume":"12","author":"N\u2019Diaye","year":"2017","journal-title":"PLoS One"},{"key":"2023013108053664100_btz060-B15","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/j.jbiotec.2017.07.017","article-title":"The seqan c++ template library for efficient sequence analysis: a resource for programmers","volume":"261","author":"Reinert","year":"2017","journal-title":"J. Biotechnol."},{"key":"2023013108053664100_btz060-B16","doi-asserted-by":"crossref","first-page":"23","DOI":"10.4310\/CIS.2010.v10.n1.a2","article-title":"Theory and algorithms for the haplotype assembly problem","volume":"10","author":"Schwartz","year":"2010","journal-title":"Commun. Inform. Syst."},{"key":"2023013108053664100_btz060-B17","article-title":"Linear time algorithms to construct populations fitting multiple constraint distributions at genomic scales","author":"Siragusa","year":"2017","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform"},{"key":"2023013108053664100_btz060-B18","doi-asserted-by":"crossref","first-page":"3310","DOI":"10.1093\/bioinformatics\/btu548","article-title":"Optitype: precision HLA typing from next-generation sequencing data","volume":"30","author":"Szolek","year":"2014","journal-title":"Bioinformatics"},{"key":"2023013108053664100_btz060-B19","doi-asserted-by":"crossref","first-page":"e62355","DOI":"10.1371\/journal.pone.0062355","article-title":"A next-generation sequencing method for genotyping-by-sequencing of highly heterozygous autotetraploid potato","volume":"8","author":"Uitdewilligen","year":"2013","journal-title":"PLoS One"},{"key":"2023013108053664100_btz060-B20","volume-title":"Introduction to Mathematical Programming","author":"Winston","year":"2003"},{"key":"2023013108053664100_btz060-B21","doi-asserted-by":"crossref","first-page":"3735","DOI":"10.1093\/bioinformatics\/btw537","article-title":"H-PoP and H-PoPG: heuristic partitioning algorithms for single individual haplotyping of polyploids","volume":"32","author":"Xie","year":"2016","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btz060\/28993508\/btz060.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/35\/18\/3279\/48975356\/bioinformatics_35_18_3279.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/35\/18\/3279\/48975356\/bioinformatics_35_18_3279.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T08:44:10Z","timestamp":1675154650000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/35\/18\/3279\/5301312"}},"subtitle":[],"editor":[{"given":"Inanc","family":"Birol","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2019,1,25]]},"references-count":21,"journal-issue":{"issue":"18","published-print":{"date-parts":[[2019,9,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btz060","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/346429","asserted-by":"object"}]},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2019,9,15]]},"published":{"date-parts":[[2019,1,25]]}}}