{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T04:10:57Z","timestamp":1772165457014,"version":"3.50.1"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,6,18]],"date-time":"2020-06-18T00:00:00Z","timestamp":1592438400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,6,18]],"date-time":"2020-06-18T00:00:00Z","timestamp":1592438400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Background<\/jats:title>\n                    <jats:p>Haplotype information is essential for many genetic and genomic analyses, including genotype-phenotype associations in human, animals and plants. Haplotype assembly is a method for reconstructing haplotypes from DNA sequencing reads. By the advent of new sequencing technologies, new algorithms are needed to ensure long and accurate haplotypes. While a few linked-read haplotype assembly algorithms are available for diploid genomes, to the best of our knowledge, no algorithms have yet been proposed for polyploids specifically exploiting linked reads.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>The first haplotyping algorithm designed for linked reads generated from a polyploid genome is presented, built on a typical short-read haplotyping method, SDhaP. Using the input aligned reads and called variants, the haplotype-relevant information is extracted. Next, reads with the same barcodes are combined to produce molecule-specific fragments. Then, these fragments are clustered into strongly connected components which are then used as input of a haplotype assembly core in order to estimate accurate and long haplotypes.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Conclusions<\/jats:title>\n                    <jats:p>Hap10 is a novel algorithm for haplotype assembly of polyploid genomes using linked reads. The performance of the algorithms is evaluated in a number of simulation scenarios and its applicability is demonstrated on a real dataset of sweet potato.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1186\/s12859-020-03584-5","type":"journal-article","created":{"date-parts":[[2020,6,18]],"date-time":"2020-06-18T07:02:59Z","timestamp":1592463779000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Hap10: reconstructing accurate and long polyploid haplotypes using linked reads"],"prefix":"10.1186","volume":"21","author":[{"given":"Sina","family":"Majidian","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1920-659X","authenticated-orcid":false,"given":"Mohammad Hossein","family":"Kahaei","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dick","family":"de Ridder","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,6,18]]},"reference":[{"issue":"11","key":"3584_CR1","doi-asserted-by":"crossref","first-page":"836","DOI":"10.1038\/nrg1711","volume":"6","author":"L Comai","year":"2005","unstructured":"Comai L. The advantages and disadvantages of being polyploid. Nat Rev Genet. 2005;6(11):836\u201346.","journal-title":"Nat Rev Genet"},{"key":"3584_CR2","doi-asserted-by":"crossref","first-page":"1534","DOI":"10.3389\/fpls.2017.01534","volume":"8","author":"L Qian","year":"2017","unstructured":"Qian L, Hickey LT, Stahl A, Werner CR, Hayes B, Snowdon RJ, Voss-Fels KP. Exploring and harnessing haplotype diversity to improve yield stability in crops. Front Plant Sci. 2017;8:1534.","journal-title":"Front Plant Sci"},{"issue":"3","key":"3584_CR3","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1136\/jmg.2004.024752","volume":"42","author":"PY Liu","year":"2005","unstructured":"Liu PY, Zhang YY, Lu Y, Long JR, Shen H, Zhao LJ, et al. A survey of haplotype variants at several disease candidate genes: the importance of rare variants for complex diseases. J Med Genet. 2005;42(3):221\u20137.","journal-title":"J Med Genet"},{"issue":"3","key":"3584_CR4","first-page":"387","volume":"19","author":"E Motazedi","year":"2017","unstructured":"Motazedi E, Finkers R, Maliepaard C, de Ridder D. Exploiting next-generation sequencing to solve the haplotyping puzzle in polyploids: a simulation study. Brief Bioinform. 2017;19(3):387\u2013403.","journal-title":"Brief Bioinform"},{"issue":"4","key":"3584_CR5","doi-asserted-by":"crossref","first-page":"e1007308","DOI":"10.1371\/journal.pgen.1007308","volume":"14","author":"Y Choi","year":"2018","unstructured":"Choi Y, Chan AP, Kirkness E, Telenti A, Schork NJ. Comparison of phasing strategies for whole human genomes. PLoS Genet. 2018;14(4):e1007308.","journal-title":"PLoS Genet"},{"key":"3584_CR6","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1016\/j.csbj.2019.11.011","volume":"18","author":"X Zhang","year":"2020","unstructured":"Zhang X, Wu R, Wang Y, Yu J, Tang H. Unzipping haplotypes in diploid and polyploid genomes. Comput Struct Biotechnol J. 2020;18:66\u201372.","journal-title":"Comput Struct Biotechnol J"},{"issue":"3","key":"3584_CR7","doi-asserted-by":"crossref","first-page":"e1003502","DOI":"10.1371\/journal.pcbi.1003502","volume":"10","author":"E Berger","year":"2014","unstructured":"Berger E, Yorukoglu D, Peng J, Berger B. HapTree: a novel Bayesian framework for single individual polyplotyping using NGS data. PLoS Comput Biol. 2014;10(3):e1003502.","journal-title":"PLoS Comput Biol"},{"key":"3584_CR8","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1186\/s12864-015-1408-5","volume":"16","author":"S Das","year":"2015","unstructured":"Das S, Vikalo H. SDhaP: haplotype assembly for diploids and polyploids via semi-definite programming. BMC Genomics. 2015;16:260.","journal-title":"BMC Genomics"},{"issue":"24","key":"3584_CR9","doi-asserted-by":"crossref","first-page":"3735","DOI":"10.1093\/bioinformatics\/btw537","volume":"32","author":"M Xie","year":"2016","unstructured":"Xie M, Wu Q, Wang J, Jiang T. H-PoP and H-PoPG: heuristic partitioning algorithms for single individual haplotyping of polyploids. Bioinformatics. 2016;32(24):3735\u201344.","journal-title":"Bioinformatics"},{"issue":"21","key":"3584_CR10","doi-asserted-by":"crossref","first-page":"4534","DOI":"10.1093\/bioinformatics\/btz511","volume":"35","author":"E Siragusa","year":"2019","unstructured":"Siragusa E, Haiminen N, Finkers R, Visser R, Parida L. Haplotype assembly of autotetraploid potato using integer linear programming. Bioinformatics. 2019;35(21):4534.","journal-title":"Bioinformatics"},{"key":"3584_CR11","doi-asserted-by":"crossref","unstructured":"Schrinner S, Mari RS, Ebler JW, Rautiainen M, Seillier L, Reimer J, Usadel B, Marschall T and Klau GW. \"Haplotype threading: accurate polyploid phasing from long reads. 2020. BioRxiv.\u00a0https:\/\/doi.org\/10.1101\/2020.02.04.933523..","DOI":"10.1101\/2020.02.04.933523"},{"key":"3584_CR12","doi-asserted-by":"publisher","unstructured":"He D, Saha S, Finkers R, Parida L. Efficient algorithms for polyploid haplotype phasing. BMC Genomics. 2018;19(Suppl 2):171-80. Article number 110. https:\/\/doi.org\/10.1186\/s12864-018-4464-9.","DOI":"10.1186\/s12864-018-4464-9"},{"issue":"13","key":"3584_CR13","doi-asserted-by":"crossref","first-page":"i352","DOI":"10.1093\/bioinformatics\/btt213","volume":"29","author":"D Aguiar","year":"2013","unstructured":"Aguiar D, Istrail S. Haplotype assembly in polyploid genomes and identical by descent shared tracts. Bioinformatics. 2013;29(13):i352\u201360.","journal-title":"Bioinformatics."},{"key":"3584_CR14","unstructured":"Moeinzadeh MH. De novo and haplotype assembly of polyploid genomes. PhD thesis. Germany: Freie Universit\u00e4t Berlin; 2019. http:\/\/dx.doi.org\/10.17169\/refubium-2712."},{"issue":"6","key":"3584_CR15","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1038\/nrg.2016.49","volume":"17","author":"S Goodwin","year":"2016","unstructured":"Goodwin S, McPherson JD, McCombie WR. Coming of age: ten years of next-generation sequencing technologies. Nat Rev Genet. 2016;17(6):333\u201351.","journal-title":"Nat Rev Genet"},{"issue":"10","key":"3584_CR16","doi-asserted-by":"crossref","first-page":"1155","DOI":"10.1038\/s41587-019-0217-9","volume":"37","author":"AM Wenger","year":"2019","unstructured":"Wenger AM, Peluso P, Rowell WJ, Chang PC, Hall RJ, Concepcion GT, Ebler J, Fungtammasan A, Kolesnikov A, Olson ND, T\u00f6pfer A. Accurate circular consensus long-read sequencing improves variant detection and assembly of a human genome. Nat Biotechnol. 2019;37(10):1155\u201362.","journal-title":"Nat Biotechnol"},{"issue":"5","key":"3584_CR17","doi-asserted-by":"crossref","first-page":"757","DOI":"10.1101\/gr.214874.116","volume":"27","author":"NI Weisenfeld","year":"2017","unstructured":"Weisenfeld NI, Kumar V, Shah P, Church DM, Jaffe DB. Direct determination of diploid genome sequences. Genome Res. 2017;27(5):757\u201367.","journal-title":"Genome Res"},{"key":"3584_CR18","doi-asserted-by":"crossref","first-page":"i61","DOI":"10.1093\/bioinformatics\/btz349","volume":"35.14","author":"I Tolstoganov","year":"2019","unstructured":"Tolstoganov I, Bankevich A, Chen Z, Pevzner PA. cloudSPAdes: assembly of synthetic long reads using de Bruijn graphs. Bioinformatics. 2019;35.14:i61\u201370.","journal-title":"Bioinformatics"},{"key":"3584_CR19","doi-asserted-by":"crossref","unstructured":"Marks P, Garcia S, Barrio AM, Belhocine K, Bernate J, Bharadwaj R, et al. Resolving the full spectrum of human genome variation using linked-reads. Genome Res. 2019;29(4):635\u201345.","DOI":"10.1101\/gr.234443.118"},{"issue":"5","key":"3584_CR20","doi-asserted-by":"crossref","first-page":"801","DOI":"10.1101\/gr.213462.116","volume":"27","author":"P Edge","year":"2017","unstructured":"Edge P, Bafna V, Bansal V. HapCUT2: robust and accurate haplotype assembly for diverse sequencing technologies. Genome Res. 2017;27(5):801\u201312.","journal-title":"Genome Res"},{"issue":"1","key":"3584_CR21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1038\/s41467-017-01389-4","volume":"8","author":"D Porubsky","year":"2017","unstructured":"Porubsky D, Garg S, Sanders AD, Korbel JO, Guryev V, Lansdorp PM, Marschall T. Dense and accurate whole-chromosome haplotyping of individual genomes. Nat Commun. 2017;8(1):1\u201310.","journal-title":"Nat Commun"},{"issue":"3","key":"3584_CR22","doi-asserted-by":"crossref","first-page":"e0214455","DOI":"10.1371\/journal.pone.0214455","volume":"14","author":"S Majidian","year":"2019","unstructured":"Majidian S, Kahaei MH. NGS based haplotype assembly using matrix completion. PLoS One. 2019;14(3):e0214455.","journal-title":"PLoS One"},{"key":"3584_CR23","unstructured":"Garrison E, Marth G. Haplotype-based variant detection from short-read sequencing.\u00a0 2012.\u00a0\u200barXiv preprint q-bio.GN\/1207.3907."},{"issue":"22","key":"3584_CR24","doi-asserted-by":"crossref","first-page":"3864","DOI":"10.1093\/bioinformatics\/bty442","volume":"34","author":"E Motazedi","year":"2018","unstructured":"Motazedi E, de Ridder D, Finkers R, Baldwin S, Thomson S, Monaghan K, Maliepaard C. TriPoly: haplotype estimation for polyploids using sequencing data of related individuals. Bioinformatics. 2018;34(22):3864\u201372.","journal-title":"Bioinformatics"},{"issue":"5","key":"3584_CR25","doi-asserted-by":"crossref","first-page":"603","DOI":"10.1109\/34.1000236","volume":"24","author":"D Comaniciu","year":"2002","unstructured":"Comaniciu D, Meer P. Mean shift: a robust approach toward feature space analysis. IEEE Trans Pattern Anal Mach Intell. 2002;24(5):603\u201319.","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"key":"3584_CR26","first-page":"2825","volume":"12","author":"F Pedregosa","year":"2011","unstructured":"Pedregosa F, Varoquaux G, Gramfort A, Michel V, Thirion B, Grisel O, et al. Scikit-learn: machine learning in Python. J Mach Learn Res. 2011;12:2825\u201330.","journal-title":"J Mach Learn Res"},{"issue":"8","key":"3584_CR27","doi-asserted-by":"crossref","first-page":"888","DOI":"10.1109\/34.868688","volume":"22","author":"J Shi","year":"2000","unstructured":"Shi J, Malik J. Normalized cuts and image segmentation. IEEE Trans Pattern Anal Mach Intell. 2000;22(8):888\u2013905.","journal-title":"IEEE Trans Pattern Anal Mach Intell"},{"issue":"1","key":"3584_CR28","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/BF02523688","volume":"18","author":"A Frieze","year":"1997","unstructured":"Frieze A, Jerrum M. Improved approximation algorithms for max k-cut and max bisection. Algorithmica. 1997;18(1):67\u201381.","journal-title":"Algorithmica"},{"issue":"3","key":"3584_CR29","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1023\/B:JOCO.0000038911.67280.3f","volume":"8","author":"E de Klerk","year":"2004","unstructured":"de Klerk E, Pasechnik DV, Warners JP. On approximate graph colouring and max-k-cut algorithms based on the \u03b8-function. J Comb Optim. 2004;8(3):267\u201394.","journal-title":"J Comb Optim"},{"key":"3584_CR30","volume-title":"Vandenberghe L","author":"S Boyd","year":"2004","unstructured":"Boyd S. Vandenberghe L. Convex optimization: Cambridge University Press; 2004."},{"key":"3584_CR31","doi-asserted-by":"crossref","unstructured":"Rockafellar RT. Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math Oper Res USA.\u00a01976;1(2):97\u2013116.","DOI":"10.1287\/moor.1.2.97"},{"key":"3584_CR32","unstructured":"Golub GH, Van Loan CF. Matrix computations: Johns Hopkins University Press; 1996."},{"issue":"3","key":"3584_CR33","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1007\/s12532-015-0082-6","volume":"7","author":"L Yang","year":"2015","unstructured":"Yang L, Sun D, Toh KC. SDPNAL++: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints. Math Program Comput. 2015;7(3):331\u201366.","journal-title":"Math Program Comput"},{"key":"3584_CR34","doi-asserted-by":"crossref","first-page":"478","DOI":"10.1016\/j.csbj.2017.10.002","volume":"15","author":"R Luo","year":"2017","unstructured":"Luo R, Sedlazeck FJ, Darby CA, Kelly SM, Schatz MC. LRSim: a linked reads simulator generating insights for better genome partitioning. Comput Struct Biotechnol J. 2017;15:478\u201384.","journal-title":"Comput Struct Biotechnol J"},{"issue":"1","key":"3584_CR35","doi-asserted-by":"crossref","first-page":"4580","DOI":"10.1038\/s41467-018-06983-8","volume":"9","author":"S Wu","year":"2018","unstructured":"Wu S, Lau KH, Cao Q, Hamilton JP, Sun H, Zhou C, et al. Genome sequences of two diploid wild relatives of cultivated sweetpotato reveal targets for genetic improvement. Nat Commun. 2018;9(1):4580.","journal-title":"Nat Commun"},{"issue":"1","key":"3584_CR36","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/s10479-008-0481-4","volume":"188","author":"B Ghaddar","year":"2011","unstructured":"Ghaddar B, Anjos MF, Liers F. A branch-and-cut algorithm based on semidefinite programming for the minimum k-partition problem. Ann Oper Res. 2011;188(1):155\u201374.","journal-title":"Ann Oper Res"},{"issue":"2","key":"3584_CR37","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1007\/s13675-019-00110-y","volume":"7","author":"VJR de Sousa","year":"2019","unstructured":"de Sousa VJR, Anjos MF, Le Digabel S. Improving the linear relaxation of maximum k-cut with semidefinite-based constraints. EURO J Comput Optimization. 2019;7(2):123\u201351.","journal-title":"EURO J Comput Optimization"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-020-03584-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s12859-020-03584-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-020-03584-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,2]],"date-time":"2023-10-02T11:01:32Z","timestamp":1696244492000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/s12859-020-03584-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,18]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["3584"],"URL":"https:\/\/doi.org\/10.1186\/s12859-020-03584-5","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/2020.01.08.899013","asserted-by":"object"}]},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,18]]},"assertion":[{"value":"8 January 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 June 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 June 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Not applicable.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"Author Dick de Ridder is an Associate Editor for BMC Bioinformatics.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"253"}}