{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T10:42:41Z","timestamp":1775644961032,"version":"3.50.1"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithms Mol Biol"],"published-print":{"date-parts":[[2014,1]]},"DOI":"10.1186\/1748-7188-9-9","type":"journal-article","created":{"date-parts":[[2014,3,22]],"date-time":"2014-03-22T12:01:33Z","timestamp":1395489693000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":27,"title":["Fast algorithms for approximate circular string matching"],"prefix":"10.1186","volume":"9","author":[{"given":"Carl","family":"Barton","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Costas S","family":"Iliopoulos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Solon P","family":"Pissis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,3,22]]},"reference":[{"issue":"4","key":"211_CR1","doi-asserted-by":"publisher","first-page":"730","DOI":"10.1073\/pnas.50.4.730","volume":"50","author":"R Weil","year":"1963","unstructured":"Weil R, Vinograd J:The cyclic helix and cyclic coil forms of polyoma viral DNA. Proc Natl Acad Sci. 1963, 50 (4): 730-738.","journal-title":"Proc Natl Acad Sci"},{"issue":"2","key":"211_CR2","doi-asserted-by":"publisher","first-page":"236","DOI":"10.1073\/pnas.50.2.236","volume":"50","author":"R Dulbecco","year":"1963","unstructured":"Dulbecco R, Vogt M:Evidence for a ring structure of polyoma virus DNA. Proc Natl Acad Sci. 1963, 50 (2): 236-243.","journal-title":"Proc Natl Acad Sci"},{"issue":"3","key":"211_CR3","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1002\/jcb.20519","volume":"96","author":"M Thanbichler","year":"2005","unstructured":"Thanbichler M, Wang SC, Shapiro L:The bacterial nucleoid: A highly organized and dynamic structure. J Cell Biochem. 2005, 96 (3): 506-521. [http:\/\/dx.doi.org\/10.1002\/jcb.20519], []","journal-title":"J Cell Biochem"},{"key":"211_CR4","volume-title":"Plasmids: Current Research and Future Trends","author":"G Lipps","year":"2008","unstructured":"Lipps G: Plasmids: Current Research and Future Trends. 2008, Norfolk, UK: Caister Academic Press."},{"key":"211_CR5","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1038\/nrg1504","volume":"6","author":"T Allers","year":"2005","unstructured":"Allers T, Mevarech M:Archaeal genetics \u2014 the third way. Nat Rev Genet. 2005, 6: 58-73.","journal-title":"Nat Rev Genet"},{"key":"211_CR6","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees and Sequences","author":"D Gusfield","year":"1997","unstructured":"Gusfield D: Algorithms on Strings, Trees and Sequences. 1997, New York, NY, USA: Cambridge University Press."},{"key":"211_CR7","first-page":"93","volume-title":"German Conference on Bioinformatics, Volume 83 of LNI","author":"A Mosig","year":"2006","unstructured":"Mosig A, Hofacker IL, Stadler PF, Zell A:Comparative analysis of cyclic sequences: viroids and other small circular RNAs. German Conference on Bioinformatics, Volume 83 of LNI. Edited by: Huson DH, Kohlbacher O, Lupas AN, Nieselt K. 2006, 93-102. GI."},{"key":"211_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/1471-2105-10-230","volume":"10","author":"F Fernandes","year":"2009","unstructured":"Fernandes F, Pereira L, Freitas A:CSA: An efficient algorithm to improve circular DNA multiple alignment. BMC Bioinformatics. 2009, 10: 1-13.","journal-title":"BMC Bioinformatics"},{"key":"211_CR9","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1007\/978-3-642-13509-5_28","volume-title":"Proceedings of the 21st annual Conference on Combinatorial Pattern Matching","author":"T Lee","year":"2010","unstructured":"Lee T, Na JC, Park H, Park K, Sim JS:Finding optimal alignment and consensus of circular strings. Proceedings of the 21st annual Conference on Combinatorial Pattern Matching. 2010, 310-322. CPM\u201910, Berlin, Heidelberg: Springer-Verlag."},{"key":"211_CR10","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546853","volume-title":"Algorithms on Strings","author":"M Crochemore","year":"2007","unstructured":"Crochemore M, Hancart C, Lecroq T: Algorithms on Strings. 2007, New York, NY, USA: Cambridge University Press."},{"key":"211_CR11","volume-title":"Applied Combinatorics on Words","year":"2005","unstructured":"Applied Combinatorics on Words. Edited by: Lothaire M. 2005, New York, NY, USA: Cambridge University Press."},{"issue":"4","key":"211_CR12","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1016\/j.jda.2008.09.001","volume":"7","author":"K Fredriksson","year":"2009","unstructured":"Fredriksson K, Grabowski S:Average-optimal string matching. J Discrete Algorithms. 2009, 7 (4): 579-594. 10.1016\/j.jda.2008.09.001.","journal-title":"J Discrete Algorithms"},{"key":"211_CR13","volume-title":"Comput J","author":"KH Chen","year":"2013","unstructured":"Chen KH, Huang GS, Lee RCT:Bit-parallel algorithms for exact circular string matching. Comput J. 2013, doi:10.1093\/comjnl\/bxt023."},{"key":"211_CR14","first-page":"46","volume-title":"Proceedings of the 2nd International Conference on Algorithms and Computation","author":"CS Iliopoulos","year":"2008","unstructured":"Iliopoulos CS, Rahman MS:Indexing circular patterns. Proceedings of the 2nd International Conference on Algorithms and Computation. 2008, 46-57. WALCOM\u201908, Berlin, Heidelberg: Springer-Verlag."},{"issue":"7","key":"211_CR15","doi-asserted-by":"publisher","first-page":"897","DOI":"10.1093\/comjnl\/bxr126","volume":"55","author":"J Lin","year":"2012","unstructured":"Lin J, Adjeroh D:All-against-all circular pattern matching. Comput J. 2012, 55 (7): 897-906. 10.1093\/comjnl\/bxr126.","journal-title":"Comput J"},{"key":"211_CR16","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1007\/3-540-58094-8_23","volume-title":"Proceedings of the 5th Annual Symposium on Combinatorial Pattern Matching","author":"WI Chang","year":"1994","unstructured":"Chang WI, Marr TG:Approximate string matching and local similarity. Proceedings of the 5th Annual Symposium on Combinatorial Pattern Matching. 1994, 259-273. CPM \u201994, London, UK: Springer-Verlag."},{"key":"211_CR17","volume-title":"J Exp Algorithmics","author":"K Fredriksson","year":"2004","unstructured":"Fredriksson K, Navarro G:Average-optimal single and multiple approximate string matching. J Exp Algorithmics. 2004, 9:http:\/\/dl.acm.org\/citation.cfm?id=1041513,"},{"issue":"10","key":"211_CR18","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1145\/135239.135244","volume":"35","author":"S Wu","year":"1992","unstructured":"Wu S, Manber U:Fast text searching: allowing errors. Commun ACM. 1992, 35 (10): 83-91. 10.1145\/135239.135244.","journal-title":"Commun ACM"},{"key":"211_CR19","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1137\/0205003","volume":"5","author":"R Rivest","year":"1976","unstructured":"Rivest R:Partial-match retrieval algorithms. SIAM J Comput. 1976, 5: 19-50. 10.1137\/0205003.","journal-title":"SIAM J Comput"},{"key":"211_CR20","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1145\/1854776.1854801","volume-title":"Proceedings of the First ACM International Conference on Bioinformatics and Computational Biology","author":"K Frousios","year":"2010","unstructured":"Frousios K, Iliopoulos CS, Mouchard L, Pissis SP, Tischler G:REAL: an efficient REad ALigner for next generation sequencing reads. Proceedings of the First ACM International Conference on Bioinformatics and Computational Biology. 2010, 154-159. BCB \u201910, USA: ACM."},{"key":"211_CR21","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1109\/DCC.2009.42","volume-title":"Proceedings of the 2009 Data Compression Conference","author":"G Nong","year":"2009","unstructured":"Nong G, Zhang S, Chan WH:Linear suffix array construction by almost pure induced-sorting. Proceedings of the 2009 Data Compression Conference. 2009, 193-202. DCC \u201909, Washington, DC, USA: IEEE Computer Society."},{"issue":"4","key":"211_CR22","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1016\/j.jda.2010.08.004","volume":"8","author":"L Ilie","year":"2010","unstructured":"Ilie L, Navarro G, Tinta L:The longest common extension problem revisited and applications to approximate string searching. J Discrete Algorithms. 2010, 8 (4): 418-428. 10.1016\/j.jda.2010.08.004.","journal-title":"J Discrete Algorithms"},{"key":"211_CR23","first-page":"374","volume-title":"Algorithms and Data Structures, Volume 6844 of Lecture Notes in Computer Science","author":"J Fischer","year":"2011","unstructured":"Fischer J:Inducing the LCP-Array. Algorithms and Data Structures, Volume 6844 of Lecture Notes in Computer Science. Edited by: Dehne F, Iacono J, Sack JR. 2011, 374-385. Berlin Heidelberg: Springer."},{"issue":"2","key":"211_CR24","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1137\/090779759","volume":"40","author":"J Fischer","year":"2011","unstructured":"Fischer J, Heun V:Space-efficient preprocessing schemes for range minimum queries on static arrays. SIAM J Comput. 2011, 40 (2): 465-492. 10.1137\/090779759.","journal-title":"SIAM J Comput"},{"issue":"2","key":"211_CR25","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/j.ipl.2005.11.019","volume":"98","author":"S Dori","year":"2006","unstructured":"Dori S, Landau GM:Construction of Aho Corasick automaton in linear time for integer alphabets. Inf Process Lett. 2006, 98 (2): 66-72. 10.1016\/j.ipl.2005.11.019.","journal-title":"Inf Process Lett"},{"key":"211_CR26","volume-title":"Higher Algebra","author":"HS Hall","year":"1950","unstructured":"Hall HS, Knight SR: Higher Algebra. 1950, London, UK: MacMillan."},{"key":"211_CR27","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0020-0190(96)00083-X","volume":"59","author":"RA Baeza-Yates","year":"1996","unstructured":"Baeza-Yates RA, Perleberg CH:Fast and practical approximate string matching. Inform Process Lett. 1996, 59: 21-27.0.1016\/0020-0190(96)00083-X.http:\/\/www.sciencedirect.com\/science\/article\/pii\/002001909600083X],","journal-title":"Inform Process Lett"},{"key":"211_CR28","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1145\/321796.321811","volume":"21","author":"RA Wagner","year":"1974","unstructured":"Wagner RA, Fischer MJ:The string-to-string correction problem. J ACM. 1974, 21: 168-173. 10.1145\/321796.321811.","journal-title":"J ACM"},{"issue":"6","key":"211_CR29","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1145\/360825.360861","volume":"18","author":"DS Hirschberg","year":"1975","unstructured":"Hirschberg DS:A linear space algorithm for computing maximal common subsequences. Commun ACM. 1975, 18 (6): 341-343. 10.1145\/360825.360861.","journal-title":"Commun ACM"},{"key":"211_CR30","unstructured":"Pizza & Chili. http:\/\/pizzachili.dcc.uchile.cl\/ 2013,"},{"issue":"3","key":"211_CR31","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1016\/j.jda.2007.03.003","volume":"6","author":"P Peterlongo","year":"2008","unstructured":"Peterlongo P, Pisanti N, Boyer F, do Lago AP, Sagot MF:Lossless filter for multiple repetitions with Hamming distance. J Discrete Algorithms. 2008, 6 (3): 497-509. 10.1016\/j.jda.2007.03.003.","journal-title":"J Discrete Algorithms"},{"key":"211_CR32","volume-title":"Algorithms Molecular Biol","author":"P Peterlongo","year":"2009","unstructured":"Peterlongo P, Sacomoto GAT, do Lago AP, Pisanti N, Sagot MF:Lossless filter for multiple repeats with bounded edit distance. Algorithms Molecular Biol. 2009,4.http:\/\/www.almob.org\/content\/pdf\/1748-7188-4-3.pdf,"}],"container-title":["Algorithms for Molecular Biology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1748-7188-9-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,2]],"date-time":"2021-09-02T03:32:53Z","timestamp":1630553573000},"score":1,"resource":{"primary":{"URL":"https:\/\/almob.biomedcentral.com\/articles\/10.1186\/1748-7188-9-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["211"],"URL":"https:\/\/doi.org\/10.1186\/1748-7188-9-9","relation":{},"ISSN":["1748-7188"],"issn-type":[{"value":"1748-7188","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]},"assertion":[{"value":"19 September 2013","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 March 2014","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 March 2014","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"9"}}