{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T10:52:39Z","timestamp":1740135159038,"version":"3.37.3"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,10,30]],"date-time":"2021-10-30T00:00:00Z","timestamp":1635552000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,10,30]],"date-time":"2021-10-30T00:00:00Z","timestamp":1635552000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["31770775","62072435"],"award-info":[{"award-number":["31770775","62072435"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Key Research and Development Program of China","award":["2020YFA0907000"],"award-info":[{"award-number":["2020YFA0907000"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec><jats:title>Background<\/jats:title><jats:p>Optical maps record locations of specific enzyme recognition sites within long genome fragments. This long-distance information enables aligning genome assembly contigs onto optical maps and ordering contigs into scaffolds. The generated scaffolds, however, often contain a large amount of gaps. To fill these gaps, a feasible way is to search genome assembly graph for the best-matching contig paths that connect boundary contigs of gaps. The combination of searching and evaluation procedures might be \u201csearching followed by evaluation\u201d, which is infeasible for long gaps, or \u201csearching by evaluation\u201d, which heavily relies on heuristics and thus usually yields unreliable contig paths.<\/jats:p><\/jats:sec><jats:sec><jats:title>Results<\/jats:title><jats:p>We here report an accurate and efficient approach to filling gaps of genome scaffolds with aids of optical maps. Using simulated data from 12 species and real data from 3 species, we demonstrate the successful application of our approach in gap filling with improved accuracy and completeness of genome scaffolds.<\/jats:p><\/jats:sec><jats:sec><jats:title>Conclusion<\/jats:title><jats:p>Our approach applies a sequential Bayesian updating technique to measure the similarity between optical maps and candidate contig paths. Using this similarity to guide path searching, our approach achieves higher accuracy than the existing \u201csearching by evaluation\u201d strategy that relies on heuristics. Furthermore, unlike the \u201csearching followed by evaluation\u201d strategy enumerating all possible paths, our approach prunes the unlikely sub-paths and extends the highly-probable ones only, thus significantly increasing searching efficiency.<\/jats:p><\/jats:sec>","DOI":"10.1186\/s12859-021-04448-2","type":"journal-article","created":{"date-parts":[[2021,10,30]],"date-time":"2021-10-30T18:03:09Z","timestamp":1635616989000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Filling gaps of genome scaffolds via probabilistic searching optical maps against assembly graph"],"prefix":"10.1186","volume":"22","author":[{"given":"Bin","family":"Huang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guozheng","family":"Wei","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bing","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fusong","family":"Ju","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yi","family":"Zhong","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhuozheng","family":"Shi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shiwei","family":"Sun","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4119-4238","authenticated-orcid":false,"given":"Dongbo","family":"Bu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,10,30]]},"reference":[{"issue":"17","key":"4448_CR1","doi-asserted-by":"publisher","first-page":"9748","DOI":"10.1073\/pnas.171285098","volume":"98","author":"PA Pevzner","year":"2001","unstructured":"Pevzner PA, Tang H, Waterman MS. An Eulerian path approach to DNA fragment assembly. Proc Natl Acad Sci. 2001;98(17):9748\u201353. https:\/\/doi.org\/10.1073\/pnas.171285098.","journal-title":"Proc Natl Acad Sci"},{"issue":"3","key":"4448_CR2","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1038\/nrg3367","volume":"14","author":"N Nagarajan","year":"2013","unstructured":"Nagarajan N, Pop M. Sequence assembly demystified. Nat Rev Genet. 2013;14(3):157.","journal-title":"Nat Rev Genet"},{"issue":"R2","key":"4448_CR3","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1093\/hmg\/ddq416","volume":"19","author":"EE Schadt","year":"2010","unstructured":"Schadt EE, Turner S, Kasarskis A. A window into third-generation sequencing. Hum Mol Genet. 2010;19(R2):227\u201340.","journal-title":"Hum Mol Genet"},{"key":"4448_CR4","doi-asserted-by":"crossref","unstructured":"Lee H, Gurtowski J, Yoo S, Nattestad M, Marcus S, Goodwin S, McCombie WR, Schatz M. Third-generation sequencing and the future of genomics. BioRxiv. 2016;048603.","DOI":"10.1101\/048603"},{"issue":"5","key":"4448_CR5","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1038\/75346","volume":"18","author":"J Parkhill","year":"2000","unstructured":"Parkhill J. In defense of complete genomes. Nat Biotechnol. 2000;18(5):493.","journal-title":"Nat Biotechnol"},{"issue":"1","key":"4448_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13059-021-02328-9","volume":"22","author":"S Garg","year":"2021","unstructured":"Garg S. Computational methods for chromosome-scale haplotype reconstruction. Genome Biol. 2021;22(1):1\u201324.","journal-title":"Genome Biol"},{"issue":"1","key":"4448_CR7","doi-asserted-by":"publisher","first-page":"8688","DOI":"10.1038\/s41598-019-45131-0","volume":"9","author":"M Malmberg","year":"2019","unstructured":"Malmberg M, Spangenberg G, Daetwyler H, Cogan N. Assessment of low-coverage nanopore long read sequencing for SNP genotyping in doubled haploid canola (Brassica napus L.). Sci Rep. 2019;9(1):8688.","journal-title":"Sci Rep"},{"issue":"5130","key":"4448_CR8","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1126\/science.8211116","volume":"262","author":"DC Schwartz","year":"1993","unstructured":"Schwartz DC, Li X, Hernandez LI, Ramnarain SP, Huff EJ, Wang Y-K. Ordered restriction maps of Saccharomyces cerevisiae chromosomes constructed by optical mapping. Science. 1993;262(5130):110\u20134.","journal-title":"Science"},{"issue":"1","key":"4448_CR9","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1186\/2047-217X-1-18","volume":"1","author":"R Luo","year":"2012","unstructured":"Luo R, Liu B, Xie Y, Li Z, Huang W, Yuan J, He G, Chen Y, Pan Q, Liu Y, et al. SOAPdenovo2: an empirically improved memory-efficient short-read de novo assembler. GigaScience. 2012;1(1):18.","journal-title":"GigaScience"},{"issue":"6","key":"4448_CR10","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1186\/gb-2012-13-6-r56","volume":"13","author":"M Boetzer","year":"2012","unstructured":"Boetzer M, Pirovano W. Toward almost closed genomes with GapFiller. Genome Biol. 2012;13(6):56.","journal-title":"Genome Biol"},{"issue":"23","key":"4448_CR11","doi-asserted-by":"crossref","first-page":"3733","DOI":"10.1093\/bioinformatics\/btv465","volume":"31","author":"S Kosugi","year":"2015","unstructured":"Kosugi S, Hirakawa H, Tabata S. GMcloser: closing gaps in assemblies accurately with a likelihood-based selection of contig or long-read alignments. Bioinformatics. 2015;31(23):3733\u201341.","journal-title":"Bioinformatics"},{"issue":"11","key":"4448_CR12","doi-asserted-by":"publisher","first-page":"47768","DOI":"10.1371\/journal.pone.0047768","volume":"7","author":"AC English","year":"2012","unstructured":"English AC, Richards S, Han Y, Wang M, Vee V, Qu J, Qin X, Muzny DM, Reid JG, Worley KC, et al. Mind the gap: upgrading genomes with Pacific Biosciences RS long-read sequencing technology. PLoS ONE. 2012;7(11):47768.","journal-title":"PLoS ONE"},{"issue":"1","key":"4448_CR13","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1093\/gigascience\/giz157","volume":"8","author":"G-C Xu","year":"2018","unstructured":"Xu G-C, Xu T-J, Zhu R, Zhang Y, Li S-Q, Wang H-W, Li J-T. LR\\_Gapcloser: a tiling path-based gap closer that uses long reads to complete genome assembly. GigaScience. 2018;8(1):157.","journal-title":"GigaScience"},{"issue":"10","key":"4448_CR14","doi-asserted-by":"publisher","first-page":"1229","DOI":"10.1093\/bioinformatics\/btn102","volume":"24","author":"N Nagarajan","year":"2008","unstructured":"Nagarajan N, Read TD, Pop M. Scaffolding and validation of bacterial genome assemblies using optical restriction maps. Bioinformatics. 2008;24(10):1229\u201335.","journal-title":"Bioinformatics"},{"key":"4448_CR15","doi-asserted-by":"publisher","first-page":"10150","DOI":"10.7717\/peerj.10150","volume":"8","author":"B Istace","year":"2020","unstructured":"Istace B, Belser C, Aury J-M. Biscot: improving large eukaryotic genome assemblies with optical maps. PeerJ. 2020;8:10150.","journal-title":"PeerJ"},{"issue":"13","key":"4448_CR16","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1093\/bioinformatics\/bty255","volume":"34","author":"W Pan","year":"2018","unstructured":"Pan W, Wanamaker SI, Ah-Fong AM, Judelson HS, Lonardi S. Novo&stitch: accurate reconciliation of genome assemblies via optical maps. Bioinformatics. 2018;34(13):43\u201351.","journal-title":"Bioinformatics"},{"issue":"6","key":"4448_CR17","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1186\/1752-0509-7-S6-S7","volume":"7","author":"Y-M Chen","year":"2013","unstructured":"Chen Y-M, Yu C-H, Hwang C-C, Liu T. OMACC: an optical-map-assisted contig connector for improving de novo genome assembly. BMC Syst Biol. 2013;7(6):7.","journal-title":"BMC Syst Biol"},{"issue":"1","key":"4448_CR18","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1186\/1471-2105-13-189","volume":"13","author":"HC Lin","year":"2012","unstructured":"Lin HC, Goldstein S, Mendelowitz L, Zhou S, Wetzel J, Schwartz DC, Pop M. AGORA: assembly guided by optical restriction alignment. BMC Bioinform. 2012;13(1):189.","journal-title":"BMC Bioinform"},{"key":"4448_CR19","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btz069","author":"K Mukherjee","year":"2018","unstructured":"Mukherjee K, Alipanahi B, Kahveci T, Salmela L, Boucher C. Aligning optical maps to de Bruijn graphs. Bioinformatics. 2018. https:\/\/doi.org\/10.1093\/bioinformatics\/btz069.","journal-title":"Bioinformatics"},{"issue":"17","key":"4448_CR20","doi-asserted-by":"publisher","first-page":"2740","DOI":"10.1093\/bioinformatics\/btx293","volume":"33","author":"G Miclotte","year":"2017","unstructured":"Miclotte G, Plaisance S, Rombauts S, Van de Peer Y, Audenaert P, Fostier J. Omsim: a simulator for optical map data. Bioinformatics. 2017;33(17):2740\u20132.","journal-title":"Bioinformatics"},{"issue":"4","key":"4448_CR21","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1093\/bioinformatics\/btr708","volume":"28","author":"W Huang","year":"2011","unstructured":"Huang W, Li L, Myers JR, Marth GT. ART: a next-generation sequencing read simulator. Bioinformatics. 2011;28(4):593\u20134.","journal-title":"Bioinformatics"},{"key":"4448_CR22","doi-asserted-by":"crossref","unstructured":"Nurk S, Bankevich A, Antipov D, Gurevich A, Korobeynikov A, Lapidus A, Prjibelsky A, Pyshkin A, Sirotkin A, Sirotkin Y, et al. Assembling genomes and mini-metagenomes from highly chimeric reads. In: Annual international conference on research in computational molecular biology, 2013; pp. 158\u2013170. Springer","DOI":"10.1007\/978-3-642-37195-0_13"},{"issue":"1","key":"4448_CR23","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1186\/1752-153X-2-S1-P4","volume":"2","author":"T Kinnunen","year":"2008","unstructured":"Kinnunen T, Nyr\u00f6nen T, Lehtovuori P. SOMA2-open source framework for molecular modelling workflows. Chem Cent J. 2008;2(1):4.","journal-title":"Chem Cent J"},{"issue":"3","key":"4448_CR24","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1093\/bioinformatics\/btw620","volume":"33","author":"AK-Y Leung","year":"2017","unstructured":"Leung AK-Y, Kwok T-P, Wan R, Xiao M, Kwok P-Y, Yip KY, Chan T-F. Omblast: alignment tool for optical mapping using a seed-and-extend approach. Bioinformatics. 2017;33(3):311\u20139.","journal-title":"Bioinformatics"},{"issue":"12","key":"4448_CR25","doi-asserted-by":"publisher","first-page":"1119","DOI":"10.1038\/nbt.2727","volume":"31","author":"JN Burton","year":"2013","unstructured":"Burton JN, Adey A, Patwardhan RP, Qiu R, Kitzman JO, Shendure J. Chromosome-scale scaffolding of de novo genome assemblies based on chromatin interactions. Nat Biotechnol. 2013;31(12):1119\u201325.","journal-title":"Nat Biotechnol"},{"issue":"1","key":"4448_CR26","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1038\/ncomms6695","volume":"5","author":"H Marie-Nelly","year":"2014","unstructured":"Marie-Nelly H, Marbouty M, Cournac A, Flot J-F, Liti G, Parodi DP, Syan S, Guill\u00e9n N, Margeot A, Zimmer C, et al. High-quality genome (re) assembly using chromosomal contact data. Nat Commun. 2014;5(1):1\u201310.","journal-title":"Nat Commun"},{"issue":"1","key":"4448_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13059-020-02041-z","volume":"21","author":"L Baudry","year":"2020","unstructured":"Baudry L, Guiglielmoni N, Marie-Nelly H, Cormier A, Marbouty M, Avia K, Mie YL, Godfroy O, Sterck L, Cock JM, et al. instagraal: chromosome-level quality scaffolding of genomes using a proximity ligation-based scaffolder. Genome Biol. 2020;21(1):1\u201322.","journal-title":"Genome Biol"},{"issue":"6333","key":"4448_CR28","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1126\/science.aal3327","volume":"356","author":"O Dudchenko","year":"2017","unstructured":"Dudchenko O, Batra SS, Omer AD, Nyquist SK, Hoeger M, Durand NC, Shamim MS, Machol I, Lander ES, Aiden AP, et al. De novo assembly of the aedes aegypti genome using hi-c yields chromosome-length scaffolds. Science. 2017;356(6333):92\u20135.","journal-title":"Science"},{"issue":"4","key":"4448_CR29","doi-asserted-by":"publisher","first-page":"771","DOI":"10.1016\/j.cell.2017.12.027","volume":"172","author":"VS Lioy","year":"2018","unstructured":"Lioy VS, Cournac A, Marbouty M, Duigou S, Mozziconacci J, Esp\u00e9li O, Boccard F, Koszul R. Multiscale structuring of the E. coli chromosome by nucleoid-associated and condensin proteins. Cell. 2018;172(4):771\u201383.","journal-title":"Cell"},{"issue":"8","key":"4448_CR30","doi-asserted-by":"publisher","first-page":"1072","DOI":"10.1093\/bioinformatics\/btt086","volume":"29","author":"A Gurevich","year":"2013","unstructured":"Gurevich A, Saveliev V, Vyahhi N, Tesler G. Quast: quality assessment tool for genome assemblies. Bioinformatics. 2013;29(8):1072\u20135.","journal-title":"Bioinformatics"},{"key":"4448_CR31","doi-asserted-by":"crossref","unstructured":"Li M, Mak AC, Lam ET, Kwok P-Y, Xiao M, Yip KY, Chan T-F, Yiu S-M. Towards a more accurate error model for BioNano optical maps. In: International symposium on bioinformatics research and applications, 2016; pp. 67\u201379. Springer","DOI":"10.1007\/978-3-319-38782-6_6"},{"issue":"23","key":"4448_CR32","doi-asserted-by":"publisher","first-page":"3966","DOI":"10.1093\/bioinformatics\/bty456","volume":"34","author":"P Chen","year":"2018","unstructured":"Chen P, Jing X, Ren J, Cao H, Hao P, Li X. Modelling BioNano optical data and simulation study of genome map assembly. Bioinformatics. 2018;34(23):3966\u201374.","journal-title":"Bioinformatics"},{"issue":"18","key":"4448_CR33","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1093\/nar\/gkq673","volume":"38","author":"SK Das","year":"2010","unstructured":"Das SK, Austin MD, Akana MC, Deshpande P, Cao H, Xiao M. Single molecule linear analysis of DNA in nano-channel labeled with sequence specific fluorescent probes. Nucleic Acids Res. 2010;38(18):177.","journal-title":"Nucleic Acids Res"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-021-04448-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s12859-021-04448-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-021-04448-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,12]],"date-time":"2023-11-12T00:19:48Z","timestamp":1699748388000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/s12859-021-04448-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,30]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["4448"],"URL":"https:\/\/doi.org\/10.1186\/s12859-021-04448-2","relation":{},"ISSN":["1471-2105"],"issn-type":[{"type":"electronic","value":"1471-2105"}],"subject":[],"published":{"date-parts":[[2021,10,30]]},"assertion":[{"value":"24 May 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 October 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 October 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare that they have no competing interests.","order":4,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"533"}}