{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T16:20:15Z","timestamp":1780330815993,"version":"3.54.1"},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2017,11,20]],"date-time":"2017-11-20T00:00:00Z","timestamp":1511136000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","award":["2017R1D1A1B03030348"],"award-info":[{"award-number":["2017R1D1A1B03030348"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Supercomput"],"published-print":{"date-parts":[[2018,5]]},"DOI":"10.1007\/s11227-017-2192-6","type":"journal-article","created":{"date-parts":[[2017,11,20]],"date-time":"2017-11-20T05:10:27Z","timestamp":1511154627000},"page":"1815-1834","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["New algorithms for fixed-length approximate string matching and approximate circular string matching under the Hamming distance"],"prefix":"10.1007","volume":"74","author":[{"given":"ThienLuan","family":"Ho","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Seung-Rohk","family":"Oh","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5017-3995","authenticated-orcid":false,"given":"HyunJin","family":"Kim","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2017,11,20]]},"reference":[{"issue":"1","key":"2192_CR1","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/375360.375365","volume":"33","author":"G Navarro","year":"2001","unstructured":"Navarro G (2001) A guided tour to approximate string matching. ACM Comput Surv (CSUR) 33(1):31\u201388","journal-title":"ACM Comput Surv (CSUR)"},{"key":"2192_CR2","doi-asserted-by":"crossref","first-page":"523","DOI":"10.1016\/j.procs.2013.05.067","volume":"17","author":"X Kefu","year":"2013","unstructured":"Kefu X, Cui W, Yue H, Guo L (2013) Bit-parallel multiple approximate string matching based on GPU. Proc Comput Sci 17:523\u2013529","journal-title":"Proc Comput Sci"},{"key":"2192_CR3","doi-asserted-by":"crossref","unstructured":"Man D, Nakano K, Ito Y (2013) The approximate string matching on the hierarchical memory machine, with performance evaluation. In: Proceedings of the 7th IEEE international symposium embedded multicore socs (MCSoC). IEEE, pp 79\u201384","DOI":"10.1109\/MCSoC.2013.22"},{"key":"2192_CR4","doi-asserted-by":"crossref","unstructured":"Michailidis PD, Margaritis KG (2005) A programmable array processor architecture for flexible approximate string matching algorithms. In: 2005 International Conference on Parallel Processing Workshops (ICPPW\u201905). IEEE, pp 201\u2013209","DOI":"10.1109\/ICPPW.2005.15"},{"key":"2192_CR5","doi-asserted-by":"crossref","unstructured":"Guo Longjiang, Du Shufang, Ren Meirui, Liu Yu, Li Jinbao, He Jing, Tian Ning, Li Keqin (2013) Parallel algorithm for approximate string matching with k-differences. In: Proceedings of the 8th IEEE International Conference Networking, Architecture and Storage (NAS). IEEE, pp 257\u2013261","DOI":"10.1109\/NAS.2013.40"},{"issue":"1","key":"2192_CR6","first-page":"29","volume":"10","author":"H Hyyr\u00f6","year":"2003","unstructured":"Hyyr\u00f6 H (2003) A bit-vector algorithm for computing Levenshtein and Damerau edit distances. Nord. J. Comput. 10(1):29\u201339","journal-title":"Nord. J. Comput."},{"issue":"10","key":"2192_CR7","doi-asserted-by":"crossref","first-page":"e0186251","DOI":"10.1371\/journal.pone.0186251","volume":"12","author":"TL Ho","year":"2017","unstructured":"Ho TL, Seung-Rohk O, Kim HJ (2017) A parallel approximate string matching under Levenshtein distance on graphics processing units using warp-shuffle operations. PLoS ONE 12(10):e0186251","journal-title":"PLoS ONE"},{"issue":"2","key":"2192_CR8","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/S0196-6774(03)00097-X","volume":"50","author":"A Amir","year":"2004","unstructured":"Amir A, Lewenstein M, Porat E (2004) Faster algorithms for string matching with $$k$$ k -mismatches. Journal of Algorithms 50(2):257\u2013275","journal-title":"Journal of Algorithms"},{"issue":"1","key":"2192_CR9","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1186\/1748-7188-9-9","volume":"9","author":"C Barton","year":"2014","unstructured":"Barton C, Iliopoulos CS, Pissis SP (2014) Fast algorithms for approximate circular string matching. Algorithms Mol Biol 9(1):9","journal-title":"Algorithms Mol Biol"},{"key":"2192_CR10","doi-asserted-by":"crossref","unstructured":"Liu Y, Guo L, Li J, Ren M, Li K (2012) Parallel algorithms for approximate string matching with $$k$$ k -mismatches on CUDA. In: Proceedings of the 26th IEEE International Conference on Parallel and Distributed Processing Symposium Workshops & Ph.D. forum (IPDPSW). IEEE, pp 2414\u20132422","DOI":"10.1109\/IPDPSW.2012.298"},{"key":"2192_CR11","first-page":"1726","volume":"99","author":"TL Ho","year":"2016","unstructured":"Ho TL, Seung-Rohk O, Kim HJ (2016) Circular bit-vector-mismatches: a new approximate circular string matching with $$k$$ k -mismatches. IEICE Trans Fundam Electron Commun Comput Sci 99:1726\u20131729","journal-title":"IEICE Trans Fundam Electron Commun Comput Sci"},{"key":"2192_CR12","doi-asserted-by":"crossref","unstructured":"Iliopoulos CS, Mouchard L, Pinzon YJ (2001) The Max-Shift algorithm for approximate string matching. In: Brodal GS, Frigioni D, Marchetti-Spaccamela A (eds) Algorithm engineering. Springer, Berlin, Heidelberg, pp 13\u201325","DOI":"10.1007\/3-540-44688-5_2"},{"issue":"2","key":"2192_CR13","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1137\/S0097539794264810","volume":"27","author":"GM Landau","year":"1998","unstructured":"Landau GM, Myers EW, Schmidt JP (1998) Incremental string comparison. SIAM J Comput 27(2):557\u2013582","journal-title":"SIAM J Comput"},{"key":"2192_CR14","first-page":"150","volume":"19","author":"B Chapman","year":"2010","unstructured":"Chapman B et al (2010) A parallel algorithm for the fixed-length approximate string matching problem for high throughput sequencing technologies. Parallel Comput From Multicores GPU\u2019s Petascale 19:150","journal-title":"Parallel Comput From Multicores GPU\u2019s Petascale"},{"key":"2192_CR15","doi-asserted-by":"crossref","unstructured":"Crochemore M, Iliopoulos CS, Pissis SP (2010) A parallel algorithm for fixed-length approximate string-matching with $$k$$ k -mismatches. In: Elomaa T, Mannila H, Orponen P (eds) Algorithms and applications. Springer, Berlin, Heidelberg, pp 92\u2013101","DOI":"10.1007\/978-3-642-12476-1_6"},{"key":"2192_CR16","doi-asserted-by":"crossref","unstructured":"Pissis S, Retha A (2015) Generalised implementation for fixed-length approximate string matching under Hamming distance and applications. In: Proceedings of IEEE international workshop parallel distributed processing symposium (IPDPSW). IEEE, pp 367\u2013374","DOI":"10.1109\/IPDPSW.2015.106"},{"key":"2192_CR17","doi-asserted-by":"crossref","unstructured":"Barton C, Iliopoulos CS, Kundu R, Pissis SP, Retha A, Vayani F (2015) Accurate and efficient methods to improve multiple circular sequence alignment. In: Bampis E (ed) Experimental algorithms. Springer, Cham, Switzerland, pp 247\u2013258","DOI":"10.1007\/978-3-319-20086-6_19"},{"key":"2192_CR18","doi-asserted-by":"crossref","unstructured":"Pissis SP, Stamatakis A, Pavlidis P(2013) MoTeX: a word-based HPC tool for MoTif eXtraction. In: Proceedings of the International Conference on Bioinformatics, Computational Biology and Biomedical Informatics, Computational Biology and Biomedical Informatics. ACM, pp\u00a013","DOI":"10.1145\/2506583.2506587"},{"issue":"1","key":"2192_CR19","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1186\/1471-2105-15-235","volume":"15","author":"SP Pissis","year":"2014","unstructured":"Pissis SP (2014) MoTeX-II: structured MoTif eXtraction from large-scale datasets. BMC Bioinform 15(1):235","journal-title":"BMC Bioinform"},{"key":"2192_CR20","unstructured":"NVIDIA (2017) GeForce GTX 1080. https:\/\/www.nvidia.com\/en-us\/geforce\/products\/10series\/geforce-gtx-1080 . Accessed 27 Oct 2017"},{"key":"2192_CR21","unstructured":"Intel (2017) Xeon CPU E5-2630 V3. https:\/\/ark.intel.com\/products\/83356\/Intel-Xeon-Processor-E5-2630-v3-20M-Cache-2_40-GHz . Accessed 27 Oct 2017"},{"key":"2192_CR22","unstructured":"Stothard P (2017) Ramdom DNA pattern, bioinformatics. http:\/\/www.bioinformatics.org\/sms2\/dna_pattern.html . Accessed 4 Mar 2017"},{"key":"2192_CR23","unstructured":"Saccharomyces Genome\u00a0Database (2017) DNA sequences. http:\/\/downloads.yeastgenome.org\/sequence\/S288C_reference\/orf_dna . Accessed 4 Mar 2017"},{"issue":"10","key":"2192_CR24","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1145\/135239.135243","volume":"35","author":"R Baeza-Yates","year":"1992","unstructured":"Baeza-Yates R, Gonnet GH (1992) A new approach to text searching. Commun ACM 35(10):74\u201382","journal-title":"Commun ACM"},{"issue":"5","key":"2192_CR25","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1016\/j.ipl.2007.08.021","volume":"105","author":"S Grabowski","year":"2008","unstructured":"Grabowski S, Fredriksson K (2008) Bit-parallel string matching under Hamming distance in O(n[m\/w]) worst case time. Inf Process Lett 105(5):182\u2013187","journal-title":"Inf Process Lett"},{"key":"2192_CR26","doi-asserted-by":"crossref","unstructured":"Lin CH, Wang GH, Huang CC (2014) Hierarchical parallelism of bit-parallel algorithm for approximate string matching on GPUs. In: Proceedings of IEEE symposium on computer applications and communications (SCAC). IEEE, pp 76\u201381","DOI":"10.1109\/SCAC.2014.23"},{"issue":"7","key":"2192_CR27","first-page":"1523","volume":"99","author":"TL Ho","year":"2016","unstructured":"Ho TL, Seung-Rohk O, Kim HJ (2016) PAC-k: a parallel Aho\u2013Corasick string matching approach on graphic processing units using non-overlapped threads. IEICE Trans Commun 99(7):1523\u20131531","journal-title":"IEICE Trans Commun"},{"key":"2192_CR28","unstructured":"NVIDIA (2017). http:\/\/www.nvidia.com\/page\/home.html . Accessed 4 Mar 2017"},{"key":"2192_CR29","doi-asserted-by":"crossref","unstructured":"Fang J, Varbanescu AL, Sips H (2011) A comprehensive performance comparison of CUDA and OpenCL. In: 2011 International Conference on Parallel Processing (ICPP). IEEE, pp 216\u2013225","DOI":"10.1109\/ICPP.2011.45"},{"key":"2192_CR30","unstructured":"NVIDIA (2017) GeForce GTX 780. https:\/\/www.geforce.com\/hardware\/desktop-gpus\/geforce-gtx-780\/specifications . Accessed 27 Oct 2017"},{"key":"2192_CR31","unstructured":"NVIDIA (2017) GeForce GTX 660. http:\/\/www.geforce.com\/hardware\/desktop-gpus\/geforce-gtx-660 . Accessed 27 Oct 2017"}],"updated-by":[{"DOI":"10.1007\/s11227-018-2324-7","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2018,3,20]],"date-time":"2018-03-20T00:00:00Z","timestamp":1521504000000}}],"container-title":["The Journal of Supercomputing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11227-017-2192-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-017-2192-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-017-2192-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,7]],"date-time":"2022-08-07T17:28:24Z","timestamp":1659893304000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11227-017-2192-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,11,20]]},"references-count":31,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2018,5]]}},"alternative-id":["2192"],"URL":"https:\/\/doi.org\/10.1007\/s11227-017-2192-6","relation":{"correction":[{"id-type":"doi","id":"10.1007\/s11227-018-2324-7","asserted-by":"object"}]},"ISSN":["0920-8542","1573-0484"],"issn-type":[{"value":"0920-8542","type":"print"},{"value":"1573-0484","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,11,20]]}}}