{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T15:37:01Z","timestamp":1781883421473,"version":"3.54.5"},"reference-count":31,"publisher":"Oxford University Press (OUP)","issue":"24","funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61370172, 61232001 and 61420106009"],"award-info":[{"award-number":["61370172, 61232001 and 61420106009"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"US National Science Foundation","doi-asserted-by":"crossref","award":["DBI-1262107"],"award-info":[{"award-number":["DBI-1262107"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016,12,15]]},"abstract":"<jats:p>Motivation: Some economically important plants including wheat and cotton have more than two copies of each chromosome. With the decreasing cost and increasing read length of next-generation sequencing technologies, reconstructing the multiple haplotypes of a polyploid genome from its sequence reads becomes practical. However, the computational challenge in polyploid haplotyping is much greater than that in diploid haplotyping, and there are few related methods.<\/jats:p>\n               <jats:p>Results: This article models the polyploid haplotyping problem as an optimal poly-partition problem of the reads, called the Polyploid Balanced Optimal Partition model. For the reads sequenced from a k-ploid genome, the model tries to divide the reads into k groups such that the difference between the reads of the same group is minimized while the difference between the reads of different groups is maximized. When the genotype information is available, the model is extended to the Polyploid Balanced Optimal Partition with Genotype constraint problem. These models are all NP-hard. We propose two heuristic algorithms, H-PoP and H-PoPG, based on dynamic programming and a strategy of limiting the number of intermediate solutions at each iteration, to solve the two models, respectively. Extensive experimental results on simulated and real data show that our algorithms can solve the models effectively, and are much faster and more accurate than the recent state-of-the-art polyploid haplotyping algorithms. The experiments also show that our algorithms can deal with long reads and deep read coverage effectively and accurately. Furthermore, H-PoP might be applied to help determine the ploidy of an organism.<\/jats:p>\n               <jats:p>Availability and Implementation: \u00a0https:\/\/github.com\/MinzhuXie\/H-PoPG<\/jats:p>\n               <jats:p>Contact: \u00a0xieminzhu@hotmail.com<\/jats:p>\n               <jats:p>Supplementary information: \u00a0Supplementary data are available at Bioinformatics online.<\/jats:p>","DOI":"10.1093\/bioinformatics\/btw537","type":"journal-article","created":{"date-parts":[[2016,8,17]],"date-time":"2016-08-17T02:39:40Z","timestamp":1471401580000},"page":"3735-3744","source":"Crossref","is-referenced-by-count":60,"title":["H-PoP and H-PoPG: heuristic partitioning algorithms for single individual haplotyping of polyploids"],"prefix":"10.1093","volume":"32","author":[{"given":"Minzhu","family":"Xie","sequence":"first","affiliation":[{"name":"1Key Laboratory of Internet of Things Technologies and Application, College of Physics and Information Science, Hunan Normal University, Changsha 410081, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Qiong","family":"Wu","sequence":"additional","affiliation":[{"name":"2State Key Laboratory of Systematic and Evolutionary Botany, Institute of Botany, Chinese Academy of Sciences, Beijing 100093, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jianxin","family":"Wang","sequence":"additional","affiliation":[{"name":"3School of Information Science and Engineering, Central South University, Changsha 410083, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tao","family":"Jiang","sequence":"additional","affiliation":[{"name":"4Department of Computer Science and Engineering, University of California, Riverside, CA 92521, USA"},{"name":"5MOE Key Lab of Bioinformatics and Bioinformatics Division, TNLIST\/Department of Computer Science and Technology, Tsinghua University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2016,8,24]]},"reference":[{"key":"2023020114073377100_btw537-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":"2023020114073377100_btw537-B2","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/j.tcs.2004.12.017","article-title":"Polynomial and APX-hard cases of the individual haplotyping problem","volume":"335","author":"Bafna","year":"2005","journal-title":"Theor. Comput. Sci"},{"key":"2023020114073377100_btw537-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":"2023020114073377100_btw537-B4","first-page":"100","article-title":"On the Fixed Parameter Tractability and Approximability of the Minimum Error Correction Problem","volume-title":"Proc. CPM, Volume 9133 of LNCS","author":"Bonizzoni","year":"2015"},{"key":"2023020114073377100_btw537-B5","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":"2023020114073377100_btw537-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":"2023020114073377100_btw537-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":"2023020114073377100_btw537-B8","doi-asserted-by":"crossref","first-page":"e33840.","DOI":"10.1371\/journal.pone.0033840","article-title":"De-novo assembly and analysis of the heterozygous triploid genome of the wine spoilage yeast Dekkera bruxellensis AWRI1499","volume":"7","author":"Curtin","year":"2012","journal-title":"PLoS One"},{"key":"2023020114073377100_btw537-B9","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":"2023020114073377100_btw537-B10","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1145\/1854776.1854802","volume-title":"Proceedings of the First ACM International Conference on Bioinformatics and Computational Biology","author":"Duitama","year":"2010"},{"key":"2023020114073377100_btw537-B11","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":"IEEE\/ACM Trans. Comput. Biol. Bioinform"},{"key":"2023020114073377100_btw537-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":"2023020114073377100_btw537-B13","doi-asserted-by":"crossref","first-page":"593","DOI":"10.1093\/bioinformatics\/btr708","article-title":"ART: a next-generation sequencing read simulator","volume":"28","author":"Huang","year":"2012","journal-title":"Bioinformatics"},{"key":"2023020114073377100_btw537-B14","doi-asserted-by":"crossref","unstructured":"Lancia\n              \u00a0G., BafnaV., IstrailS., LippertR., SchwartzR. (2001) SNPs problems, complexity and algorithms. In auf der HeideF. M. (ed.), Proceedings of the Annual European Symposium on Algorithms (ESA), volume 2161 of Lecture Notes in Computer Science. Springer, Berlin\/Heidelberg, pp. 182\u2013193.","DOI":"10.1007\/3-540-44676-1_15"},{"key":"2023020114073377100_btw537-B15","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1126\/science.1153585","article-title":"Genomic plasticity and the diversity of polyploid plants","volume":"320","author":"Leitch","year":"2008","journal-title":"Science"},{"key":"2023020114073377100_btw537-B16","doi-asserted-by":"crossref","first-page":"1157","DOI":"10.1093\/bioinformatics\/btr076","article-title":"Improving SNP discovery by base alignment quality","volume":"27","author":"Li","year":"2011","journal-title":"Bioinformatics"},{"key":"2023020114073377100_btw537-B17","doi-asserted-by":"crossref","first-page":"2987","DOI":"10.1093\/bioinformatics\/btr509","article-title":"A statistical framework for SNP calling, mutation discovery, association mapping and population genetical parameter estimation from sequencing data","volume":"27","author":"Li","year":"2011","journal-title":"Bioinformatics"},{"key":"2023020114073377100_btw537-B18","doi-asserted-by":"crossref","first-page":"1754","DOI":"10.1093\/bioinformatics\/btp324","article-title":"Fast and accurate short read alignment with Burrows-Wheeler transform","volume":"25","author":"Li","year":"2009","journal-title":"Bioinformatics"},{"key":"2023020114073377100_btw537-B19","doi-asserted-by":"crossref","first-page":"2078","DOI":"10.1093\/bioinformatics\/btp352","article-title":"The sequence alignment\/map format and samtools","volume":"25","author":"Li","year":"2009","journal-title":"Bioinformatics"},{"key":"2023020114073377100_btw537-B20","doi-asserted-by":"crossref","first-page":"1","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":"2023020114073377100_btw537-B21","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1038\/nature03959","article-title":"Genome sequencing in microfabricated high-density picolitre reactors","volume":"437","author":"Margulies","year":"2005","journal-title":"Nature"},{"key":"2023020114073377100_btw537-B22","doi-asserted-by":"crossref","unstructured":"Panconesi\n              \u00a0A., SozioM. (2004) Fast hare: a fast heuristic for single individual SNP haplotype reconstruction. In JonassenI., KimJ. (eds.) Proc. WABI, volume 3240 of LNCS. Springer, Berlin\/Heidelberg, pp. 266\u2013277.","DOI":"10.1007\/978-3-540-30219-3_23"},{"key":"2023020114073377100_btw537-B23","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":"22","author":"Patterson","year":"2015","journal-title":"J. Comput. Biol"},{"key":"2023020114073377100_btw537-B24","doi-asserted-by":"crossref","first-page":"1610","DOI":"10.1093\/bioinformatics\/btv495","article-title":"HapCol: accurate and memory-efficient haplotype assembly from long reads","volume":"32","author":"Pirola","year":"2016","journal-title":"Bioinformatics"},{"key":"2023020114073377100_btw537-B25","doi-asserted-by":"crossref","DOI":"10.3732\/ajb.1400119","article-title":"Doubling down on genomes: polyploidy and crop plants","author":"Renny-Byfield","year":"2014","journal-title":"Am. J. Bot"},{"key":"2023020114073377100_btw537-B26","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1007\/s00453-009-9288-1","article-title":"A practical exact algorithm for the individual haplotyping problem MEC\/GI","volume":"56","author":"Wang","year":"2010","journal-title":"Algorithmica"},{"key":"2023020114073377100_btw537-B27","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":"2023020114073377100_btw537-B28","doi-asserted-by":"crossref","first-page":"i105","DOI":"10.1093\/bioinformatics\/btn147","article-title":"A model of higher accuracy for the individual haplotyping problem based on weighted SNP fragments and genotype with errors","volume":"24","author":"Xie","year":"2008","journal-title":"Bioinformatics"},{"key":"2023020114073377100_btw537-B29","doi-asserted-by":"crossref","first-page":"18","DOI":"10.2174\/157489310790596411","article-title":"Computational models and algorithms for the single individual haplotyping problem","volume":"5","author":"Xie","year":"2010","journal-title":"Curr. Bioinformatics"},{"key":"2023020114073377100_btw537-B30","doi-asserted-by":"crossref","first-page":"851","DOI":"10.1017\/S096012951000023X","article-title":"A practical parameterised algorithm for the individual haplotyping problem MLF","volume":"20","author":"Xie","year":"2010","journal-title":"Math. Struct. Comput. Sci"},{"key":"2023020114073377100_btw537-B31","doi-asserted-by":"crossref","first-page":"S8.","DOI":"10.1186\/1752-0509-6-S2-S8","article-title":"A fast and accurate algorithm for single individual haplotyping","volume":"6","author":"Xie","year":"2012","journal-title":"BMC Syst. Biol"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/24\/3735\/49027080\/bioinformatics_32_24_3735.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/32\/24\/3735\/49027080\/bioinformatics_32_24_3735.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T23:58:05Z","timestamp":1675295885000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/32\/24\/3735\/2525650"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,24]]},"references-count":31,"journal-issue":{"issue":"24","published-print":{"date-parts":[[2016,12,15]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btw537","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2016,12,15]]},"published":{"date-parts":[[2016,8,24]]}}}