{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T01:57:11Z","timestamp":1778637431156,"version":"3.51.4"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,2,11]],"date-time":"2021-02-11T00:00:00Z","timestamp":1613001600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"},{"start":{"date-parts":[[2021,2,11]],"date-time":"2021-02-11T00:00:00Z","timestamp":1613001600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Govt. of India","award":["J. C. Bose Fellowship (SB\/S1\/JCB-033\/2016)"],"award-info":[{"award-number":["J. C. Bose Fellowship (SB\/S1\/JCB-033\/2016)"]}]},{"name":"G\u00f6ttingen University"},{"name":"Projekt DEAL"}],"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>\n                  <jats:sec>\n                    <jats:title>Background<\/jats:title>\n                    <jats:p>The advancement of SMRT technology has unfolded new opportunities of genome analysis with its longer read length and low GC bias. Alignment of the reads to their appropriate positions in the respective reference genome is the first but costliest step of any analysis pipeline based on SMRT sequencing. However, the state-of-the-art aligners often fail to identify distant homologies due to lack of conserved regions, caused by frequent genetic duplication and recombination. Therefore, we developed a novel alignment-free method of sequence mapping that is fast and accurate.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>\n                      We present a new mapper called S-conLSH that uses\n                      <jats:bold>S<\/jats:bold>\n                      paced\n                      <jats:bold>con<\/jats:bold>\n                      text based\n                      <jats:bold>L<\/jats:bold>\n                      ocality\n                      <jats:bold>S<\/jats:bold>\n                      ensitive\n                      <jats:bold>H<\/jats:bold>\n                      ashing. With multiple spaced patterns, S-conLSH facilitates a gapped mapping of noisy long reads to the corresponding target locations of a reference genome. We have examined the performance of the proposed method on 5 different real and simulated datasets. S-conLSH is at least 2 times faster than the recently developed method lordFAST. It achieves a sensitivity of 99%, without using any traditional base-to-base alignment, on human simulated sequence data. By default, S-conLSH provides an alignment-free mapping in PAF format. However, it has an option of generating aligned output as SAM-file, if it is required for any downstream processing.\n                    <\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Conclusions<\/jats:title>\n                    <jats:p>\n                      S-conLSH is one of the first alignment-free reference genome mapping tools achieving a high level of sensitivity. The\n                      <jats:italic>spaced<\/jats:italic>\n                      -context is especially suitable for extracting distant similarities. The variable-length spaced-seeds or patterns add flexibility to the proposed algorithm by introducing gapped mapping of the noisy long reads. Therefore, S-conLSH may be considered as a prominent direction towards alignment-free sequence analysis.\n                    <\/jats:p>\n                  <\/jats:sec>","DOI":"10.1186\/s12859-020-03918-3","type":"journal-article","created":{"date-parts":[[2021,2,11]],"date-time":"2021-02-11T12:04:01Z","timestamp":1613045041000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["S-conLSH: alignment-free gapped mapping of noisy long reads"],"prefix":"10.1186","volume":"22","author":[{"given":"Angana","family":"Chakraborty","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Burkhard","family":"Morgenstern","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6370-2083","authenticated-orcid":false,"given":"Sanghamitra","family":"Bandyopadhyay","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,2,11]]},"reference":[{"issue":"5","key":"3918_CR1","doi-asserted-by":"publisher","first-page":"278","DOI":"10.1016\/j.gpb.2015.08.002","volume":"13","author":"A Rhoads","year":"2015","unstructured":"Rhoads A, Au KF. PacBio sequencing and its applications. Genom Proteom Bioinform. 2015;13(5):278\u201389.","journal-title":"Genom Proteom Bioinform"},{"issue":"8","key":"3918_CR2","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1038\/nmeth.3444","volume":"12","author":"NJ Loman","year":"2015","unstructured":"Loman NJ, Quick J, Simpson JT. A complete bacterial genome assembled de novo using only nanopore sequencing data. Nat Methods. 2015;12(8):733.","journal-title":"Nat Methods"},{"issue":"5","key":"3918_CR3","doi-asserted-by":"publisher","first-page":"2159","DOI":"10.1093\/nar\/gky066","volume":"46","author":"S Ardui","year":"2018","unstructured":"Ardui S, Ameur A, Vermeesch JR, Hestand MS. Single molecule real-time (SMRT) sequencing comes of age: applications and utilities for medical diagnostics. Nucleic Acids Res. 2018;46(5):2159\u201368.","journal-title":"Nucleic Acids Res"},{"key":"3918_CR4","unstructured":"Li H. Aligning sequence reads, clone sequences and assembly contigs with BWA-MEM. arXiv preprint arXiv:1303.3997 (2013)."},{"issue":"1","key":"3918_CR5","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1186\/1471-2105-13-238","volume":"13","author":"MJ Chaisson","year":"2012","unstructured":"Chaisson MJ, Tesler G. Mapping single molecule sequencing reads using basic local alignment with successive refinement (BLASR): application and theory. BMC Bioinform. 2012;13(1):238.","journal-title":"BMC Bioinform"},{"issue":"11","key":"3918_CR6","doi-asserted-by":"publisher","first-page":"1625","DOI":"10.1093\/bioinformatics\/btv662","volume":"32","author":"B Liu","year":"2015","unstructured":"Liu B, Guan D, Teng M, Wang Y. rHAT: fast alignment of noisy long reads with regional hashing. Bioinformatics. 2015;32(11):1625\u201331.","journal-title":"Bioinformatics"},{"issue":"18","key":"3918_CR7","doi-asserted-by":"publisher","first-page":"3094","DOI":"10.1093\/bioinformatics\/bty191","volume":"34","author":"H Li","year":"2018","unstructured":"Li H. Minimap2: pairwise alignment for nucleotide sequences. Bioinformatics. 2018;34(18):3094\u2013100.","journal-title":"Bioinformatics"},{"issue":"1","key":"3918_CR8","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1093\/bioinformatics\/bty544","volume":"35","author":"E Haghshenas","year":"2018","unstructured":"Haghshenas E, Sahinalp SC, Hach F. lordFAST: sensitive and fast alignment search tool for long noisy read sequencing data. Bioinformatics. 2018;35(1):20\u20137.","journal-title":"Bioinformatics"},{"issue":"12","key":"3918_CR9","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1093\/bioinformatics\/btq217","volume":"26","author":"JT Simpson","year":"2010","unstructured":"Simpson JT, Durbin R. Efficient construction of an assembly string graph using the FM-index. Bioinformatics. 2010;26(12):367\u201373.","journal-title":"Bioinformatics"},{"issue":"1","key":"3918_CR10","doi-asserted-by":"publisher","first-page":"1005944","DOI":"10.1371\/journal.pcbi.1005944","volume":"14","author":"G Mar\u00e7ais","year":"2018","unstructured":"Mar\u00e7ais G, Delcher AL, Phillippy AM, Coston R, Salzberg SL, Zimin A. MUMmer4: a fast and versatile genome alignment system. PLoS Comput Biol. 2018;14(1):1005944.","journal-title":"PLoS Comput Biol"},{"issue":"1","key":"3918_CR11","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1186\/s13059-017-1319-7","volume":"18","author":"A Zielezinski","year":"2017","unstructured":"Zielezinski A, Vinga S, Almeida J, Karlowski WM. Alignment-free sequence comparison: benefits, applications, and tools. Genome Biol. 2017;18(1):186.","journal-title":"Genome Biol"},{"key":"3918_CR12","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1146\/annurev-biodatasci-080917-013431","volume":"1","author":"J Ren","year":"2018","unstructured":"Ren J, Bai X, Lu YY, Tang K, Wang Y, Reinert G, Sun F. Alignment-free sequence analysis and applications. Annu Rev Biomed Data Sci. 2018;1:93\u2013114.","journal-title":"Annu Rev Biomed Data Sci"},{"key":"3918_CR13","doi-asserted-by":"publisher","first-page":"426","DOI":"10.1093\/bib\/bbx067","volume":"22","author":"G Bernard","year":"2019","unstructured":"Bernard G, Chan CX, Chan Y-B, Chua X-Y, Cong Y, Hogan JM, Maetschke SR, Ragan MA. Alignment-free inference of hierarchical and reticulate phylogenomic relationships. Brief Bioinform. 2019;22:426\u201335.","journal-title":"Brief Bioinform"},{"key":"3918_CR14","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1186\/s13059-019-1755-7","volume":"20","author":"A Zielezinski","year":"2019","unstructured":"Zielezinski A, Girgis HZ, Bernard G, Leimeister C-A, Tang K, Dencker T, Lau AK, R\u00f6hling S, Choi J, Waterman MS, Comin M, Kim S-H, Vinga S, Almeida JS, Chan CX, James B, Sun F, Morgenstern B, Karlowski WM. Benchmarking of alignment-free sequence comparison methods. Genome Biol. 2019;20:144.","journal-title":"Genome Biol"},{"issue":"14","key":"3918_CR15","doi-asserted-by":"publisher","first-page":"2103","DOI":"10.1093\/bioinformatics\/btw152","volume":"32","author":"H Li","year":"2016","unstructured":"Li H. Minimap and miniasm: fast mapping and de novo assembly for noisy long sequences. Bioinformatics. 2016;32(14):2103\u201310.","journal-title":"Bioinformatics"},{"key":"3918_CR16","doi-asserted-by":"publisher","first-page":"107206","DOI":"10.1016\/j.compbiolchem.2020.107206","volume":"85","author":"A Chakraborty","year":"2020","unstructured":"Chakraborty A, Bandyopadhyay S. conLSH: context based locality sensitive hashing for mapping of noisy SMRT reads. Comput Biol Chem. 2020;85:107206.","journal-title":"Comput Biol Chem"},{"key":"3918_CR17","doi-asserted-by":"crossref","unstructured":"Indyk P, Motwani R. Approximate nearest neighbors: towards removing the curse of dimensionality. In: Proceedings of the thirtieth annual ACM symposium on theory of computing. ACM; 1998. p. 604\u201313.","DOI":"10.1145\/276698.276876"},{"key":"3918_CR18","doi-asserted-by":"crossref","unstructured":"Andoni A, Indyk P. Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. In: Communications of the ACM\u201450th anniversary issue. ACM; 2008. p. 117\u201322.","DOI":"10.1145\/1327452.1327494"},{"issue":"5","key":"3918_CR19","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1093\/bioinformatics\/17.5.419","volume":"17","author":"J Buhler","year":"2001","unstructured":"Buhler J. Efficient large-scale sequence comparison by locality-sensitive hashing. Bioinformatics. 2001;17(5):419\u201328.","journal-title":"Bioinformatics"},{"key":"3918_CR20","doi-asserted-by":"crossref","unstructured":"Chakraborty A, Bandyopadhyay S. Ultrafast genomic database search using layered locality sensitive hashing. In: Fifth international conference on emerging applications of information technology. IEEE; 2018. p. 1\u20134.","DOI":"10.1109\/EAIT.2018.8470442"},{"issue":"6","key":"3918_CR21","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1038\/nbt.3238","volume":"33","author":"K Berlin","year":"2015","unstructured":"Berlin K, Koren S, Chin C-S, Drake JP, Landolin JM, Phillippy AM. Assembling large genomes with single-molecule sequencing and locality-sensitive hashing. Nat Biotechnol. 2015;33(6):623\u201330.","journal-title":"Nat Biotechnol"},{"issue":"3","key":"3918_CR22","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1093\/bioinformatics\/18.3.440","volume":"18","author":"B Ma","year":"2002","unstructured":"Ma B, Tromp J, Li M. Patternhunter: faster and more sensitive homology search. Bioinformatics. 2002;18(3):440\u20135.","journal-title":"Bioinformatics"},{"key":"3918_CR23","first-page":"164","volume":"14","author":"M Li","year":"2003","unstructured":"Li M, Ma B, Kisman D, Tromp J. PatternHunter II: Highly sensitive and fast homology search. Genome Inform. 2003;14:164\u201375.","journal-title":"Genome Inform"},{"issue":"17","key":"3918_CR24","doi-asserted-by":"publisher","first-page":"2433","DOI":"10.1093\/bioinformatics\/btr368","volume":"27","author":"L Ilie","year":"2011","unstructured":"Ilie L, Ilie S, Mansouri Bigvand A. Speed: fast computation of sensitive spaced seeds. Bioinformatics. 2011;27(17):2433\u20134.","journal-title":"Bioinformatics"},{"key":"3918_CR25","doi-asserted-by":"publisher","first-page":"1005107","DOI":"10.1371\/journal.pcbi.1005107","volume":"12","author":"L Hahn","year":"2016","unstructured":"Hahn L, Leimeister C-A, Ounit R, Lonardi S, Morgenstern B. rasbhari: optimizing spaced seeds for database searching, read mapping and alignment-free sequence comparison. PLoS Comput Biol. 2016;12:1005107.","journal-title":"PLoS Comput Biol"},{"issue":"14","key":"3918_CR26","doi-asserted-by":"publisher","first-page":"1991","DOI":"10.1093\/bioinformatics\/btu177","volume":"30","author":"C-A Leimeister","year":"2014","unstructured":"Leimeister C-A, Boden M, Horwege S, Lindner S, Morgenstern B. Fast alignment-free sequence comparison using spaced-word frequencies. Bioinformatics. 2014;30(14):1991\u20139.","journal-title":"Bioinformatics"},{"key":"3918_CR27","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1186\/s13015-015-0032-x","volume":"10","author":"B Morgenstern","year":"2015","unstructured":"Morgenstern B, Zhu B, Horwege S, Leimeister C-A. Estimating evolutionary distances between genomic sequences from spaced-word matches. Algorithms Mol Biol. 2015;10:5.","journal-title":"Algorithms Mol Biol"},{"key":"3918_CR28","doi-asserted-by":"crossref","first-page":"971","DOI":"10.1093\/bioinformatics\/btw776","volume":"33","author":"C-A Leimeister","year":"2017","unstructured":"Leimeister C-A, Sohrabi-Jahromi S, Morgenstern B. Fast and accurate phylogeny reconstruction using filtered spaced-word matches. Bioinformatics. 2017;33:971\u20139.","journal-title":"Bioinformatics"},{"issue":"16","key":"3918_CR29","doi-asserted-by":"publisher","first-page":"2078","DOI":"10.1093\/bioinformatics\/btp352","volume":"25","author":"H Li","year":"2009","unstructured":"Li H, Handsaker B, Wysoker A, Fennell T, Ruan J, Homer N, Marth G, Abecasis G, Durbin R. The sequence alignment\/map format and samtools. Bioinformatics. 2009;25(16):2078\u20139.","journal-title":"Bioinformatics"},{"issue":"1","key":"3918_CR30","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1093\/bioinformatics\/bts649","volume":"29","author":"Y Ono","year":"2012","unstructured":"Ono Y, Asai K, Hamada M. Pbsim: Pacbio reads simulator-toward accurate genome assembly. Bioinformatics. 2012;29(1):119\u201321.","journal-title":"Bioinformatics"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-020-03918-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s12859-020-03918-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s12859-020-03918-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,20]],"date-time":"2023-10-20T21:30:20Z","timestamp":1697837420000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/s12859-020-03918-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,11]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["3918"],"URL":"https:\/\/doi.org\/10.1186\/s12859-020-03918-3","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/801118","asserted-by":"object"}]},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2,11]]},"assertion":[{"value":"22 July 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 December 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 February 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 April 2021","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The funding note was not incorporated in the original publication. The article has been updated to rectify the error.","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with ethical standards"}},{"value":"No ethics approval was required for the study.","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":"64"}}