{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,28]],"date-time":"2025-11-28T17:22:23Z","timestamp":1764350543057,"version":"3.37.3"},"reference-count":29,"publisher":"Oxford University Press (OUP)","issue":"19","license":[{"start":{"date-parts":[[2020,4,20]],"date-time":"2020-04-20T00:00:00Z","timestamp":1587340800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1619081","IIS-1633215","CCF-1844234"],"award-info":[{"award-number":["CCF-1619081","IIS-1633215","CCF-1844234"]}],"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,12,8]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:sec>\n                  <jats:title>Motivation<\/jats:title>\n                  <jats:p>Third generation sequencing techniques, such as the Single Molecule Real Time technique from PacBio and the MinION technique from Oxford Nanopore, can generate long, error-prone sequencing reads which pose new challenges for fragment assembly algorithms. In this paper, we study the overlap detection problem for error-prone reads, which is the first and most critical step in the de novo fragment assembly. We observe that all the state-of-the-art methods cannot achieve an ideal accuracy for overlap detection (in terms of relatively low precision and recall) due to the high sequencing error rates, especially when the overlap lengths between reads are relatively short (e.g. &amp;lt;2000 bases). This limitation appears inherent to these algorithms due to their usage of q-gram-based seeds under the seed-extension framework.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Results<\/jats:title>\n                  <jats:p>We propose smooth q-gram, a variant of q-gram that captures q-gram pairs within small edit distances and design a novel algorithm for detecting overlapping reads using smooth q-gram-based seeds. We implemented the algorithm and tested it on both PacBio and Nanopore sequencing datasets. Our benchmarking results demonstrated that our algorithm outperforms the existing q-gram-based overlap detection algorithms, especially for reads with relatively short overlapping lengths.<\/jats:p>\n               <\/jats:sec>\n               <jats:sec>\n                  <jats:title>Availability and implementation<\/jats:title>\n                  <jats:p>The source code of our implementation in C++ is available at https:\/\/github.com\/FIGOGO\/smoothq.<\/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\/btaa252","type":"journal-article","created":{"date-parts":[[2020,4,14]],"date-time":"2020-04-14T03:28:10Z","timestamp":1586834890000},"page":"4838-4845","source":"Crossref","is-referenced-by-count":8,"title":["Overlap detection on long, error-prone sequencing reads via smooth <i>q<\/i>-gram"],"prefix":"10.1093","volume":"36","author":[{"given":"Yan","family":"Song","sequence":"first","affiliation":[{"name":"Department of Computer Science, Indiana University Bloomington , Bloomington, IN 47405, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haixu","family":"Tang","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Indiana University Bloomington , Bloomington, IN 47405, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haoyu","family":"Zhang","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Indiana University Bloomington , Bloomington, IN 47405, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Qin","family":"Zhang","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Indiana University Bloomington , Bloomington, IN 47405, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2020,4,20]]},"reference":[{"key":"2023062504242835500_btaa252-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"},{"first-page":"51","year":"2016","author":"Belazzougui","key":"2023062504242835500_btaa252-B2"},{"key":"2023062504242835500_btaa252-B3","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1038\/nbt.3238","article-title":"Assembling large genomes with single-molecule sequencing and locality-sensitive hashing","volume":"33","author":"Berlin","year":"2015","journal-title":"Nat. Biotechnol"},{"key":"2023062504242835500_btaa252-B4","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1101\/gr.926603","article-title":"Lagan and multi-lagan: efficient tools for large-scale multiple alignment of genomic DNA","volume":"13","author":"Brudno","year":"2003","journal-title":"Genome Res"},{"first-page":"73","year":"2001","author":"Burkhardt","key":"2023062504242835500_btaa252-B5"},{"first-page":"225","year":"2002","author":"Burkhardt","key":"2023062504242835500_btaa252-B6"},{"key":"2023062504242835500_btaa252-B7","first-page":"51","article-title":"Better filtering with gapped q-grams","volume":"56","author":"Burkhardt","year":"2003","journal-title":"Fundam. Inform"},{"key":"2023062504242835500_btaa252-B8","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): theory and application","volume":"13","author":"Chaisson","year":"2012","journal-title":"BMC Bioinform"},{"first-page":"712","year":"2016","author":"Chakraborty","key":"2023062504242835500_btaa252-B9"},{"key":"2023062504242835500_btaa252-B10","doi-asserted-by":"crossref","first-page":"987","DOI":"10.1038\/nbt.2023","article-title":"How to apply de Bruijn graphs to genome assembly","volume":"29","author":"Compeau","year":"2011","journal-title":"Nat. Biotechnol"},{"key":"2023062504242835500_btaa252-B11","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1038\/nmeth.3290","article-title":"Improved data analysis for the minion nanopore sequencer","volume":"12","author":"Jain","year":"2015","journal-title":"Nat. Methods"},{"key":"2023062504242835500_btaa252-B12","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":"Discrete Appl. Math"},{"key":"2023062504242835500_btaa252-B13","doi-asserted-by":"crossref","first-page":"R12","DOI":"10.1186\/gb-2004-5-2-r12","article-title":"Versatile and open software for comparing large genomes","volume":"5","author":"Kurtz","year":"2004","journal-title":"Genome Biol"},{"key":"2023062504242835500_btaa252-B14","doi-asserted-by":"crossref","first-page":"2103","DOI":"10.1093\/bioinformatics\/btw152","article-title":"Minimap and miniasm: fast mapping and de novo assembly for noisy long sequences","volume":"32","author":"Li","year":"2016","journal-title":"Bioinformatics"},{"key":"2023062504242835500_btaa252-B15","doi-asserted-by":"crossref","first-page":"3094","DOI":"10.1093\/bioinformatics\/bty191","article-title":"Minimap2: pairwise alignment for nucleotide sequences","volume":"34","author":"Li","year":"2018","journal-title":"Bioinformatics"},{"key":"2023062504242835500_btaa252-B16","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"},{"volume-title":"Foundations of Statistical Natural Language Processing","year":"1999","author":"Manning","key":"2023062504242835500_btaa252-B17"},{"key":"2023062504242835500_btaa252-B18","doi-asserted-by":"crossref","first-page":"1097","DOI":"10.1111\/1755-0998.12324","article-title":"A first look at the Oxford Nanopore minion sequencer","volume":"14","author":"Mikheyev","year":"2014","journal-title":"Mol. Ecol. Resourc"},{"key":"2023062504242835500_btaa252-B19","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/j.ygeno.2010.03.001","article-title":"Assembly algorithms for next-generation sequencing data","volume":"95","author":"Miller","year":"2010","journal-title":"Genomics"},{"first-page":"52","year":"2014","author":"Myers","key":"2023062504242835500_btaa252-B20"},{"key":"2023062504242835500_btaa252-B21","doi-asserted-by":"crossref","first-page":"9748","DOI":"10.1073\/pnas.171285098","article-title":"An Eulerian path approach to DNA fragment assembly","volume":"98","author":"Pevzner","year":"2001","journal-title":"Proc. Natl. Acad. Sci. USA"},{"first-page":"1033","year":"2011","author":"Qin","key":"2023062504242835500_btaa252-B22"},{"key":"2023062504242835500_btaa252-B23","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1186\/gb-2013-14-6-405","article-title":"The advantages of SMRT sequencing","volume":"14","author":"Roberts","year":"2013","journal-title":"Genome Biol"},{"key":"2023062504242835500_btaa252-B24","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1101\/gr.809403","article-title":"Human\u2013mouse alignments with BLASTZ","volume":"13","author":"Schwartz","year":"2003","journal-title":"Genome Res"},{"key":"2023062504242835500_btaa252-B25","doi-asserted-by":"crossref","first-page":"11307","DOI":"10.1038\/ncomms11307","article-title":"Fast and sensitive mapping of nanopore sequencing reads with graphmap","volume":"7","author":"Sovi\u0107","year":"2016","journal-title":"Nat. Commun"},{"first-page":"85","year":"2012","author":"Wang","key":"2023062504242835500_btaa252-B26"},{"key":"2023062504242835500_btaa252-B27","first-page":"933","article-title":"Ed-join: an efficient algorithm for similarity joins with edit distance constraints","volume":"1","author":"Xiao","year":"2008","journal-title":"PVLDB"},{"key":"2023062504242835500_btaa252-B28","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1093\/gigascience\/gix010","article-title":"NanoSim: nanopore sequence read simulator based on statistical characterization","volume":"6","author":"Yang","year":"2017","journal-title":"GigaScience"},{"first-page":"585","year":"2017","author":"Zhang","key":"2023062504242835500_btaa252-B29"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btaa252\/34160866\/btaa252.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/36\/19\/4838\/50692478\/btaa252.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/36\/19\/4838\/50692478\/btaa252.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,25]],"date-time":"2023-06-25T04:25:15Z","timestamp":1687667115000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/36\/19\/4838\/5822881"}},"subtitle":[],"editor":[{"given":"Ponty","family":"Yann","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2020,4,20]]},"references-count":29,"journal-issue":{"issue":"19","published-print":{"date-parts":[[2020,12,8]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btaa252","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"type":"print","value":"1367-4803"},{"type":"electronic","value":"1367-4811"}],"subject":[],"published-other":{"date-parts":[[2020,10,1]]},"published":{"date-parts":[[2020,4,20]]}}}