{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T00:35:43Z","timestamp":1778632543770,"version":"3.51.4"},"reference-count":36,"publisher":"Oxford University Press (OUP)","issue":"3","license":[{"start":{"date-parts":[[2019,9,4]],"date-time":"2019-09-04T00:00:00Z","timestamp":1567555200000},"content-version":"vor","delay-in-days":1,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"publisher","award":["308030"],"award-info":[{"award-number":["308030"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"publisher","award":["314170"],"award-info":[{"award-number":["314170"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"publisher","award":["294143"],"award-info":[{"award-number":["294143"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"publisher","award":["319454"],"award-info":[{"award-number":["319454"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1618814"],"award-info":[{"award-number":["1618814"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,2,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec><jats:title>Motivation<\/jats:title><jats:p>Optical mapping data is used in many core genomics applications, including structural variation detection, scaffolding assembled contigs and mis-assembly detection. However, the pervasiveness of spurious and deleted cut sites in the raw data, which are called Rmaps, make assembly and alignment of them challenging. Although there exists another method to error correct Rmap data, named cOMet, it is unable to scale to even moderately large sized genomes. The challenge faced in error correction is in determining pairs of Rmaps that originate from the same region of the same genome.<\/jats:p><\/jats:sec><jats:sec><jats:title>Results<\/jats:title><jats:p>We create an efficient method for determining pairs of Rmaps that contain significant overlaps between them. Our method relies on the novel and nontrivial adaption and application of spaced seeds in the context of optical mapping, which allows for spurious and deleted cut sites to be accounted for. We apply our method to detecting and correcting these errors. The resulting error correction method, referred to as Elmeri, improves upon the results of state-of-the-art correction methods but in a fraction of the time. More specifically, cOMet required 9.9 CPU days to error correct Rmap data generated from the human genome, whereas Elmeri required less than 15 CPU hours and improved the quality of the Rmaps by more than four times compared to cOMet.<\/jats:p><\/jats:sec><jats:sec><jats:title>Availability and implementation<\/jats:title><jats:p>Elmeri is publicly available under GNU Affero General Public License at https:\/\/github.com\/LeenaSalmela\/Elmeri.<\/jats:p><\/jats:sec><jats:sec><jats:title>Supplementary information<\/jats:title><jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p><\/jats:sec>","DOI":"10.1093\/bioinformatics\/btz663","type":"journal-article","created":{"date-parts":[[2019,8,30]],"date-time":"2019-08-30T11:48:44Z","timestamp":1567165724000},"page":"682-689","source":"Crossref","is-referenced-by-count":7,"title":["Fast and accurate correction of optical mapping data via spaced seeds"],"prefix":"10.1093","volume":"36","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0756-543X","authenticated-orcid":false,"given":"Leena","family":"Salmela","sequence":"first","affiliation":[{"name":"Department of Computer Science, Helsinki Institute for Information Technology HIIT , FI-00014 University of Helsinki, Helsinki 00100, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1647-8741","authenticated-orcid":false,"given":"Kingshuk","family":"Mukherjee","sequence":"additional","affiliation":[{"name":"Department of Computer and Information Science and Engineering , University of Florida, Gainesville, FL 32611, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Simon J","family":"Puglisi","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Helsinki Institute for Information Technology HIIT , FI-00014 University of Helsinki, Helsinki 00100, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9283-0049","authenticated-orcid":false,"given":"Martin D","family":"Muggli","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Colorado State University , Fort Collins, CO 80523, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christina","family":"Boucher","sequence":"additional","affiliation":[{"name":"Department of Computer and Information Science and Engineering , University of Florida, Gainesville, FL 32611, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2019,9,3]]},"reference":[{"key":"2023013110020535200_btz663-B1","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","article-title":"Basic local alignment search tool","volume":"215","author":"Altschul","year":"1990","journal-title":"J. Mol. Biol"},{"key":"2023013110020535200_btz663-B2","doi-asserted-by":"crossref","first-page":"170044.","DOI":"10.1038\/sdata.2017.44","article-title":"Construction of a map-based reference genome sequence for barley, Hordeum vulgare L","volume":"4","author":"Beier","year":"2017","journal-title":"Sci. Data"},{"key":"2023013110020535200_btz663-B3","first-page":"42","article-title":"Optimal spaced seeds for hidden Markov models, with application to homologous coding regions","author":"Brejov\u00e1","year":"2003","journal-title":"Proc. of CPM"},{"key":"2023013110020535200_btz663-B4","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1016\/j.jcss.2004.12.003","article-title":"Designing seeds for similarity search in genomic DNA","volume":"70","author":"Buhler","year":"2005","journal-title":"J. Comput. Syst. Sci"},{"key":"2023013110020535200_btz663-B5","first-page":"51","article-title":"Better filtering with gapped q-grams","volume":"56","author":"Burkhardt","year":"2003","journal-title":"Fundamenta Informaticae"},{"key":"2023013110020535200_btz663-B6","doi-asserted-by":"crossref","first-page":"238.","DOI":"10.1186\/1471-2105-13-238","article-title":"Mapping single molecule sequencing reads using basic local alignment with successive refinement (BLASR): application and theory","volume":"13","author":"Chaisson","year":"2012","journal-title":"BMC Bioinformatics"},{"key":"2023013110020535200_btz663-B7","doi-asserted-by":"crossref","first-page":"1053","DOI":"10.1093\/bioinformatics\/bth037","article-title":"Good spaced seeds for homology search","volume":"20","author":"Choi","year":"2004","journal-title":"Bioinformatics"},{"key":"2023013110020535200_btz663-B8","doi-asserted-by":"crossref","first-page":"1099","DOI":"10.1038\/ng.3886","article-title":"High-quality de novo assembly of the apple genome and methylome dynamics of early fruit development","volume":"49","author":"Daccord","year":"2017","journal-title":"Nat. Genet"},{"key":"2023013110020535200_btz663-B9","doi-asserted-by":"crossref","first-page":"5293","DOI":"10.1021\/ac0496401","article-title":"A microfluidic system for large DNA molecule arrays","volume":"76","author":"Dimalanta","year":"2004","journal-title":"Anal. Chem"},{"key":"2023013110020535200_btz663-B10","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1038\/nbt.2478","article-title":"Sequencing and automated whole-genome optical mapping of the genome of a domestic goat (Capra hircus)","volume":"31","author":"Dong","year":"2013","journal-title":"Nat. Biotechnol"},{"key":"2023013110020535200_btz663-B11","doi-asserted-by":"crossref","first-page":"1144","DOI":"10.1016\/j.jcss.2013.03.002","article-title":"Better spaced seeds using quadratic residues","volume":"79","author":"Egidi","year":"2013","journal-title":"J. Comput. Syst. Sci"},{"key":"2023013110020535200_btz663-B12","doi-asserted-by":"crossref","first-page":"11.","DOI":"10.1186\/2047-217X-3-11","article-title":"High-coverage sequencing and annotated assemblies of the budgerigar genome","volume":"3","author":"Ganapathy","year":"2014","journal-title":"GigaScience"},{"key":"2023013110020535200_btz663-B13","doi-asserted-by":"crossref","first-page":"2969","DOI":"10.1093\/bioinformatics\/btm422","article-title":"Multiple spaced seeds for homology search","volume":"23","author":"Ilie","year":"2007","journal-title":"Bioinformatics"},{"key":"2023013110020535200_btz663-B14","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1038\/nature21370","article-title":"The genome of Chenopodium quinoa","volume":"542","author":"Jarvis","year":"2017","journal-title":"Nature"},{"key":"2023013110020535200_btz663-B15","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1016\/S0166-218X(03)00382-2","article-title":"On spaced seeds for similarity search","volume":"138","author":"Keich","year":"2004","journal-title":"Discret. Appl. Math"},{"key":"2023013110020535200_btz663-B16","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1093\/bioinformatics\/btw620","article-title":"OMBlast: alignment tool for optical mapping using a seed-and-extend approach","volume":"33","author":"Leung","year":"2017","journal-title":"Bioinformatics"},{"key":"2023013110020535200_btz663-B17","first-page":"67","article-title":"Towards a more accurate error model for BioNano optical maps","author":"Li","year":"2016","journal-title":"Proc of ISBRA"},{"key":"2023013110020535200_btz663-B18","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1142\/S0219720004000661","article-title":"PatternHunter II: highly sensitive and fast homology search","volume":"2","author":"Li","year":"2004","journal-title":"J. Bioinf. Comput. Biol"},{"key":"2023013110020535200_btz663-B19","doi-asserted-by":"crossref","first-page":"189.","DOI":"10.1186\/1471-2105-13-189","article-title":"AGORA: assembly guided by optical restriction alignment","volume":"13","author":"Lin","year":"2012","journal-title":"BMC Bioinformatics"},{"key":"2023013110020535200_btz663-B20","doi-asserted-by":"crossref","first-page":"1558","DOI":"10.1126\/science.285.5433.1558","article-title":"Whole-genome shotgun optical mapping of Deinococcus radiodurans","volume":"285","author":"Lin","year":"1999","journal-title":"Science"},{"key":"2023013110020535200_btz663-B21","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1093\/bioinformatics\/18.3.440","article-title":"PatternHunter: faster and more sensitive homology search","volume":"18","author":"Ma","year":"2002","journal-title":"Bioinformatics"},{"key":"2023013110020535200_btz663-B22","doi-asserted-by":"crossref","first-page":"1016","DOI":"10.1093\/bioinformatics\/btv711","article-title":"Maligner: a fast ordered restriction map aligner","volume":"32","author":"Mendelowitz","year":"2016","journal-title":"Bioinformatics"},{"key":"2023013110020535200_btz663-B23","doi-asserted-by":"crossref","first-page":"2740","DOI":"10.1093\/bioinformatics\/btx293","article-title":"OMSim: a simulator for optical map data","volume":"33","author":"Miclotte","year":"2017","journal-title":"Bioinformatics"},{"key":"2023013110020535200_btz663-B24","first-page":"68","article-title":"Efficient indexed alignment of contigs to optical maps","author":"Muggli","year":"2014","journal-title":"Proc of WABI"},{"key":"2023013110020535200_btz663-B25","first-page":"12.1","article-title":"A succinct solution to Rmap alignment","author":"Muggli","year":"2018","journal-title":"Proc of WABI"},{"key":"2023013110020535200_btz663-B26","doi-asserted-by":"crossref","first-page":"i80","DOI":"10.1093\/bioinformatics\/btv262","article-title":"Misassembly detection using paired-end sequence reads and optical mapping data","volume":"31","author":"Muggli","year":"2015","journal-title":"Bioinformatics"},{"key":"2023013110020535200_btz663-B27","doi-asserted-by":"crossref","first-page":"giy061.","DOI":"10.1093\/gigascience\/giy061","article-title":"Error correcting optical mapping data","volume":"7","author":"Mukherjee","year":"2018","journal-title":"GigaScience"},{"key":"2023013110020535200_btz663-B28","doi-asserted-by":"crossref","first-page":"1229","DOI":"10.1093\/bioinformatics\/btn102","article-title":"Scaffolding and validation of bacterial genome assemblies using optical restriction maps","volume":"24","author":"Nagarajan","year":"2008","journal-title":"Bioinformatics"},{"key":"2023013110020535200_btz663-B29","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","article-title":"A general method applicable to the search for similarities in the amino acid sequence of two proteins","volume":"48","author":"Needleman","year":"1970","journal-title":"J. Mol. Biol"},{"key":"2023013110020535200_btz663-B30","article-title":"OMGS: optical map-based genome scaffolding","author":"Pan","year":"2019","journal-title":"Proc. of RECOMB"},{"key":"2023013110020535200_btz663-B31","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1101\/gr.5.1.1","article-title":"Optical mapping: a novel, single-molecule approach to genomic analysis","volume":"5","author":"Samad","year":"1995","journal-title":"Genome Res"},{"key":"2023013110020535200_btz663-B32","doi-asserted-by":"crossref","first-page":"12065.","DOI":"10.1038\/ncomms12065","article-title":"Long-read sequencing and de novo assembly of a Chinese genome","volume":"7","author":"Shi","year":"2016","journal-title":"Nat. Commun"},{"key":"2023013110020535200_btz663-B33","doi-asserted-by":"crossref","first-page":"10848","DOI":"10.1073\/pnas.0914638107","article-title":"High-resolution human genome structure by single-molecule analysis","volume":"107","author":"Teague","year":"2010","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023013110020535200_btz663-B34","doi-asserted-by":"crossref","first-page":"442","DOI":"10.1089\/cmb.2006.13.442","article-title":"Alignment of optical maps","volume":"13","author":"Valouev","year":"2006","journal-title":"J. Comput. Biol"},{"key":"2023013110020535200_btz663-B35","doi-asserted-by":"crossref","first-page":"15770","DOI":"10.1073\/pnas.0604040103","article-title":"An algorithm for assembly of ordered restriction maps from single DNA molecules","volume":"103","author":"Valouev","year":"2006","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"2023013110020535200_btz663-B36","doi-asserted-by":"crossref","first-page":"e1005954.","DOI":"10.1371\/journal.pgen.1005954","article-title":"Chromosomal-level assembly of the Asian seabass genome using long sequence reads and multi-layered scaffolding","volume":"12","author":"Vij","year":"2016","journal-title":"PLoS Genet"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btz663\/30022154\/btz663.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/36\/3\/682\/48981628\/bioinformatics_36_3_682.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/36\/3\/682\/48981628\/bioinformatics_36_3_682.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,19]],"date-time":"2023-09-19T17:41:01Z","timestamp":1695145261000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/36\/3\/682\/5559485"}},"subtitle":[],"editor":[{"given":"John","family":"Hancock","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2019,9,3]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,2,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btz663","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2020,2,1]]},"published":{"date-parts":[[2019,9,3]]}}}