{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T15:29:48Z","timestamp":1742916588920,"version":"3.40.3"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319193144"},{"type":"electronic","value":"9783319193151"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-19315-1_32","type":"book-chapter","created":{"date-parts":[[2015,6,6]],"date-time":"2015-06-06T10:42:08Z","timestamp":1433587328000},"page":"364-375","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Lossless Seeds for Searching Short Patterns with High Error Rates"],"prefix":"10.1007","author":[{"given":"Christophe","family":"Vroland","sequence":"first","affiliation":[]},{"given":"Mika\u00ebl","family":"Salson","sequence":"additional","affiliation":[]},{"given":"H\u00e9l\u00e8ne","family":"Touzet","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,6,7]]},"reference":[{"issue":"1","key":"32_CR1","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, R.A., Perleberg, C.H.: Fast and practical approximate string matching. Inf. Process. Lett. 59(1), 21\u201327 (1996)","journal-title":"Inf. Process. Lett."},{"key":"32_CR2","doi-asserted-by":"crossref","unstructured":"Belazzougui, D.: Improved space-time tradeoffs for approximate full-text indexing with one edit error. Algorithmica, pp. 1\u201327 (2014)","DOI":"10.1007\/s00453-014-9873-9"},{"key":"32_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/978-3-642-40450-4_12","volume-title":"Algorithms \u2013 ESA 2013","author":"D Belazzougui","year":"2013","unstructured":"Belazzougui, D., Cunial, F., K\u00e4rkk\u00e4inen, J., M\u00e4kinen, V.: Versatile succinct representations of the bidirectional burrows-wheeler transform. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol. 8125, pp. 133\u2013144. Springer, Heidelberg (2013)"},{"issue":"4","key":"32_CR4","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1016\/j.jda.2011.04.004","volume":"9","author":"HL Chan","year":"2011","unstructured":"Chan, H.L., Lam, T.W., Sung, W.K., Tam, S.L., Wong, S.S.: A linear size index for approximate pattern matching. J. Discrete Algorithms 9(4), 358\u2013364 (2011)","journal-title":"J. Discrete Algorithms"},{"key":"32_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1007\/3-540-45995-2_20","volume-title":"LATIN 2002: Theoretical Informatics","author":"E Ch\u00e1vez","year":"2002","unstructured":"Ch\u00e1vez, E., Navarro, G.: A metric index for approximate string matching. In: Rajsbaum, S. (ed.) LATIN 2002. LNCS, vol. 2286, pp. 181\u2013195. Springer, Heidelberg (2002)"},{"issue":"1","key":"32_CR6","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1186\/1471-2105-9-11","volume":"9","author":"A D\u00f6ring","year":"2008","unstructured":"D\u00f6ring, A., Weese, D., Rausch, T., Reinert, K.: SeqAn an efficient, generic C++ library for sequence analysis. BMC Bioinformatics 9(1), 11\u201319 (2008)","journal-title":"BMC Bioinformatics"},{"key":"32_CR7","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Gonz\u00e1lez, R., Navarro, G., Venturini, R.: Compressed text indexes: from theory to practice. J. Exp. Algorithmics (JEA) 13, 12 (2009)","DOI":"10.1145\/1412228.1455268"},{"issue":"4","key":"32_CR8","doi-asserted-by":"publisher","first-page":"552","DOI":"10.1145\/1082036.1082039","volume":"52","author":"P Ferragina","year":"2005","unstructured":"Ferragina, P., Manzini, G.: Indexing compressed text. J. ACM (JACM) 52(4), 552\u2013581 (2005)","journal-title":"J. ACM (JACM)"},{"key":"32_CR9","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Manzini, G., M\u00e4kinen, V., Navarro, G.: Compressed representations of sequences and full-text indexes. ACM Trans. Alg. (TALG) 3(2) (2007)","DOI":"10.1145\/1240233.1240243"},{"issue":"1","key":"32_CR10","first-page":"29","volume":"10","author":"H Hyyr\u00f6","year":"2003","unstructured":"Hyyr\u00f6, H.: A bit-vector algorithm for computing levenshtein and damerau edit distances. Nord. J. Comput. 10(1), 29\u201339 (2003)","journal-title":"Nord. J. Comput."},{"issue":"4","key":"32_CR11","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1038\/nmeth.1923","volume":"9","author":"B Langmead","year":"2012","unstructured":"Langmead, B., Salzberg, S.L.: Fast gapped-read alignment with Bowtie 2. Nat. Meth. 9(4), 357\u2013359 (2012)","journal-title":"Nat. Meth."},{"issue":"14","key":"32_CR12","doi-asserted-by":"publisher","first-page":"1754","DOI":"10.1093\/bioinformatics\/btp324","volume":"25","author":"H Li","year":"2009","unstructured":"Li, H., Durbin, R.: Fast and accurate short read alignment with burrows-wheeler transform. bioinformatics 25(14), 1754\u20131760 (2009). (Oxford, England)","journal-title":"bioinformatics"},{"issue":"4","key":"32_CR13","doi-asserted-by":"publisher","first-page":"662","DOI":"10.1016\/j.jda.2006.11.001","volume":"5","author":"MG Maa\u00df","year":"2007","unstructured":"Maa\u00df, M.G., Nowak, J.: Text indexing with errors. J. Discrete Algorithms 5(4), 662\u2013681 (2007)","journal-title":"J. Discrete Algorithms"},{"issue":"3","key":"32_CR14","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1145\/316542.316550","volume":"46","author":"G Myers","year":"1999","unstructured":"Myers, G.: A fast bit-vector algorithm for approximate string matching based on dynamic programming. J. ACM 46(3), 395\u2013415 (1999)","journal-title":"J. ACM"},{"issue":"1","key":"32_CR15","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/375360.375365","volume":"33","author":"G Navarro","year":"2001","unstructured":"Navarro, G.: A guided tour to approximate string matching. ACM comput. surv. (CSUR) 33(1), 31\u201388 (2001)","journal-title":"ACM comput. surv. (CSUR)"},{"key":"32_CR16","first-page":"19","volume":"1","author":"G Navarro","year":"2001","unstructured":"Navarro, G., Baeza-Yates, R.: A hybrid indexing method for approximate string matching. J. Discrete Algorithms 1, 19\u201327 (2001)","journal-title":"J. Discrete Algorithms"},{"key":"32_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1007\/3-540-45123-4_29","volume-title":"Combinatorial Pattern Matching","author":"G Navarro","year":"2000","unstructured":"Navarro, G., Sutinen, E., Tanninen, J., Tarhio, J.: Indexing text with approximate q-grams. In: Giancarlo, R., Sankoff, D. (eds.) CPM 2000. LNCS, vol. 1848, pp. 350\u2013363. Springer, Heidelberg (2000)"},{"key":"32_CR18","doi-asserted-by":"crossref","unstructured":"Petri, M., Culpepper, J.S.: Efficient indexing algorithms for approximate pattern matching in text. In: Proceedings of the Seventeenth Australasian Document Computing Symposium, ADCS 2012, pp. 9\u201316. ACM, New York (2012)","DOI":"10.1145\/2407085.2407087"},{"issue":"3","key":"32_CR19","doi-asserted-by":"publisher","first-page":"1105","DOI":"10.3390\/a2031105","volume":"2","author":"L Russo","year":"2009","unstructured":"Russo, L., Navarro, G., Oliveira, A.L., Morales, P.: Approximate string matching with compressed indexes. Algorithms 2(3), 1105\u20131136 (2009)","journal-title":"Algorithms"},{"issue":"6","key":"32_CR20","doi-asserted-by":"publisher","first-page":"796","DOI":"10.1089\/cmb.2012.0022","volume":"19","author":"S Schbath","year":"2012","unstructured":"Schbath, S., Martin, V., Zytnicki, M., Fayolle, J., Loux, V., Gibrat, J.F.: Mapping reads on a genomic sequence: an algorithmic overview and a practical comparative analysis. J. Comput. Biol. 19(6), 796\u2013813 (2012)","journal-title":"J. Comput. Biol."},{"key":"32_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1007\/978-3-642-13509-5_5","volume-title":"Combinatorial Pattern Matching","author":"T Schnattinger","year":"2010","unstructured":"Schnattinger, T., Ohlebusch, E., Gog, S.: Bidirectional search in a string with wavelet trees. In: Amir, A., Parida, L. (eds.) CPM 2010. LNCS, vol. 6129, pp. 40\u201350. Springer, Heidelberg (2010)"},{"issue":"1","key":"32_CR22","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1042\/BST0370023","volume":"37","author":"SA Shah","year":"2009","unstructured":"Shah, S.A., Hansen, N.R., Garrett, R.A.: Distribution of CRISPR spacer matches in viruses and plasmids of crenarchaeal acidothermophiles and implications for their inhibitory mechanism. Biochem. Soc. Trans. 37(1), 23 (2009)","journal-title":"Biochem. Soc. Trans."},{"key":"32_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/1471-2105-6-31","volume":"6","author":"GSC Slater","year":"2005","unstructured":"Slater, G.S.C., Birney, E.: Automated generation of heuristics for biological sequence comparison. BMC Bioinformatics 6, 1\u201311 (2005)","journal-title":"BMC Bioinformatics"},{"issue":"8","key":"32_CR24","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/j.tig.2010.05.008","volume":"26","author":"A Stern","year":"2010","unstructured":"Stern, A., Keren, L., Wurtzel, O., Amitai, G., Sorek, R.: Self-targeting by CRISPR: gene regulation or autoimmunity? Trends Genet. 26(8), 335\u2013340 (2010)","journal-title":"Trends Genet."},{"key":"32_CR25","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1146\/annurev.biochem.74.082803.133136","volume":"74","author":"G Storz","year":"2005","unstructured":"Storz, G., Altuvia, S., Wassarman, K.M.: An abundance of RNA regulators. Annu. Rev. Biochem. 74, 199\u2013217 (2005)","journal-title":"Annu. Rev. Biochem."},{"issue":"20","key":"32_CR26","doi-asserted-by":"publisher","first-page":"2592","DOI":"10.1093\/bioinformatics\/bts505","volume":"28","author":"D Weese","year":"2012","unstructured":"Weese, D., Holtgrewe, M., Reinert, K.: RazerS 3: faster, fully sensitive read mapping. Bioinformatics 28(20), 2592\u20132599 (2012)","journal-title":"Bioinformatics"},{"issue":"10","key":"32_CR27","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 35(10), 83\u201391 (1992)","journal-title":"Commun. ACM"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-19315-1_32","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T17:19:28Z","timestamp":1675271968000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-19315-1_32"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319193144","9783319193151"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-19315-1_32","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"7 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}