{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T16:54:27Z","timestamp":1725555267947},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642130885"},{"type":"electronic","value":"9783642130892"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-13089-2_43","type":"book-chapter","created":{"date-parts":[[2010,5,7]],"date-time":"2010-05-07T12:05:27Z","timestamp":1273233927000},"page":"512-523","source":"Crossref","is-referenced-by-count":4,"title":["A Randomized Numerical Aligner (rNA)"],"prefix":"10.1007","author":[{"given":"Alberto","family":"Policriti","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexandru I.","family":"Tomescu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Francesco","family":"Vezzi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"6","key":"43_CR1","doi-asserted-by":"publisher","first-page":"1039","DOI":"10.1137\/0216067","volume":"16","author":"K. Abrahamson","year":"1987","unstructured":"Abrahamson, K.: Generalized string matching. SIAM Journal on Computing\u00a016(6), 1039\u20131051 (1987)","journal-title":"SIAM Journal on Computing"},{"issue":"17","key":"43_CR2","doi-asserted-by":"publisher","first-page":"3389","DOI":"10.1093\/nar\/25.17.3389","volume":"25","author":"S.F. Altschul","year":"1997","unstructured":"Altschul, S.F., Madden, T.L., Sch\u00e4ffer, A.A., Zhang, J., Zhang, Z., Miller, W., Lipman, D.J.: Gapped BLAST and PSI-BLAST: a new generation of protein database search programs. Nucleic Acids Research\u00a025(17), 3389\u20133402 (1997)","journal-title":"Nucleic Acids Research"},{"key":"43_CR3","doi-asserted-by":"publisher","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.: Faster algorithms for string matching with k mismatches. Journal of Algorithms\u00a050, 257\u2013275 (2004)","journal-title":"Journal of Algorithms"},{"issue":"10","key":"43_CR4","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1145\/359842.359859","volume":"20","author":"R.S. Boyer","year":"1977","unstructured":"Boyer, R.S., Moore, J.S.: A fast string searching algorithm. Commun. ACM\u00a020(10), 762\u2013772 (1977)","journal-title":"Commun. ACM"},{"key":"43_CR5","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. MIT Press, McGraw-Hill Book Company (2001)"},{"key":"43_CR6","unstructured":"Ferragina, P.: String algorithms and data structures. CoRR abs\/0801.2378 (2008)"},{"issue":"4","key":"43_CR7","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1145\/8307.8309","volume":"17","author":"Z. Galil","year":"1986","unstructured":"Galil, Z., Giancarlo, R.: Improved string matching with k mismatches. SIGACT News\u00a017(4), 52\u201354 (1986)","journal-title":"SIGACT News"},{"issue":"2","key":"43_CR8","doi-asserted-by":"publisher","first-page":"378","DOI":"10.1137\/S0097539702402354","volume":"35","author":"R. Grossi","year":"2005","unstructured":"Grossi, R., Vitter, J.S.: Compressed suffix arrays and suffix trees with applications to text indexing and string matching. SIAM J. Comput.\u00a035(2), 378\u2013407 (2005)","journal-title":"SIAM J. Comput."},{"key":"43_CR9","doi-asserted-by":"crossref","unstructured":"Horner, D.S., Pavesi, G., Castrignano, T., De Meo, P.D., Liuni, S., Sammeth, M., Picardi, E., Pesole, G.: Bioinformatics approaches for genomics and post genomics applications of next-generation sequencing. Brief. Bioinform., bbp046+ (2009)","DOI":"10.1093\/bib\/bbp046"},{"issue":"1","key":"43_CR10","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1016\/j.tcs.2005.11.022","volume":"352","author":"T.N.D. Huynh","year":"2006","unstructured":"Huynh, T.N.D., Hon, W.K., Lam, T.W., Sung, W.K.: Approximate string matching using compressed suffix arrays. Theor. Comput. Sci.\u00a0352(1), 240\u2013249 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"43_CR11","doi-asserted-by":"crossref","unstructured":"Jokinen, P., Ukkonen, E.: Two algorithms for approximate string matching in static texts. In: Proc. 2nd Ann. Symp. on Mathematical Foundations of Computer Science, vol.\u00a0520, pp. 240\u2013248 (1991)","DOI":"10.1007\/3-540-54345-7_67"},{"issue":"2","key":"43_CR12","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1147\/rd.312.0249","volume":"31","author":"R. Karp","year":"1987","unstructured":"Karp, R., Rabin, M.: Efficient randomized pattern-matching algorithms. IBM J. Res. Develop.\u00a031(2), 249\u2013260 (1987)","journal-title":"IBM J. Res. Develop."},{"issue":"4","key":"43_CR13","doi-asserted-by":"crossref","first-page":"656","DOI":"10.1101\/gr.229202","volume":"12","author":"W.J. Kent","year":"2002","unstructured":"Kent, W.J.: BLAT\u2014The BLAST-like Alignment Tool. Genome research\u00a012(4), 656\u2013664 (2002)","journal-title":"Genome research"},{"issue":"2","key":"43_CR14","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"D.E. Knuth","year":"1977","unstructured":"Knuth, D.E., Morris, J.H., Pratt, V.R.: Fast pattern matching in strings. SIAM Journal on Computing\u00a06(2), 323\u2013350 (1977)","journal-title":"SIAM Journal on Computing"},{"key":"43_CR15","doi-asserted-by":"crossref","unstructured":"Landau, G.M., Vishkin, U.: Efficient string matching in the presence of errors. In: Proceedings of the 26th IEEE Symposium on Foundations of Computer Science, pp. 126\u2013136 (1985)","DOI":"10.1109\/SFCS.1985.22"},{"key":"43_CR16","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/0304-3975(86)90178-7","volume":"43","author":"G.M. Landau","year":"1986","unstructured":"Landau, G.M., Vishkin, U.: Efficient string matching with k mismatches. Theoretical Computer Science\u00a043, 239\u2013249 (1986)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"43_CR17","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1186\/gb-2009-10-3-r25","volume":"10","author":"B. Langmead","year":"2009","unstructured":"Langmead, B., Trapnell, C., Pop, M., Salzberg, S.: Ultrafast and memory-efficient alignment of short DNA sequences to the human genome. Genome Biology\u00a010(3), R25 (2009)","journal-title":"Genome Biology"},{"issue":"14","key":"43_CR18","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\u00a025(14), 1754\u20131760 (2009)","journal-title":"Bioinformatics"},{"issue":"15","key":"43_CR19","doi-asserted-by":"publisher","first-page":"1966","DOI":"10.1093\/bioinformatics\/btp336","volume":"25","author":"R. Li","year":"2009","unstructured":"Li, R., Yu, C., Li, Y., Lam, T.W., Yiu, S.M., Kristiansen, K., Wang, J.: SOAP2: an improved ultrafast tool for short read alignment. Bioinformatics\u00a025(15), 1966\u20131967 (2009)","journal-title":"Bioinformatics"},{"key":"43_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/11496656_8","volume-title":"Combinatorial Pattern Matching","author":"Z. Liu","year":"2005","unstructured":"Liu, Z., Chen, X., Borneman, J., Jiang, T.: A fast algorithm for approximate string matching on gene sequences. In: Apostolico, A., Crochemore, M., Park, K. (eds.) CPM 2005. LNCS, vol.\u00a03537, pp. 79\u201390. Springer, Heidelberg (2005)"},{"key":"43_CR21","first-page":"319","volume-title":"SODA \u201990: Proc. 1st Ann. ACM-SIAM Symp. on Discrete Algorithms","author":"U. Manber","year":"1990","unstructured":"Manber, U., Myers, G.: Suffix arrays: A new method for on-line string searches. In: SODA \u201990: Proc. 1st Ann. ACM-SIAM Symp. on Discrete Algorithms, pp. 319\u2013327. Society for Industrial and Applied Mathematics, Philadelphia (1990)"},{"key":"43_CR22","doi-asserted-by":"crossref","unstructured":"Muth, R., Manber, U.: Approximate multiple string search. In: Proc. 7th Ann. Symp. on Combinatorial Pattern Matching, Laguna Beach, CA, pp. 75\u201386 (1996)","DOI":"10.1007\/3-540-61258-0_7"},{"key":"43_CR23","doi-asserted-by":"crossref","unstructured":"Policriti, A., Tomescu, A.I., Vezzi, F.: A Randomized Numerical Aligner (rNA) (2010), http:\/\/sole.dimi.uniud.it\/~alexandru.tomescu\/files\/rNA-ext.pdf","DOI":"10.1007\/978-3-642-13089-2_43"},{"key":"43_CR24","doi-asserted-by":"crossref","unstructured":"Salmela, L., Tarhio, J., Kalsi, P.: Approximate Boyer-Moore string matching for small alphabets. Algorithmica (to appear)","DOI":"10.1007\/s00453-009-9286-3"},{"key":"43_CR25","doi-asserted-by":"crossref","unstructured":"Ukkonen, E.: Approximate string matching over suffix trees. In: Proc. 4th Ann. Symp. on Combinatorial Pattern Matching, pp. 228\u2013242 (1993)","DOI":"10.1007\/BFb0029808"},{"key":"43_CR26","first-page":"158","volume-title":"IEEE Symposium on Computer Arithmetic","author":"R. Zimmermann","year":"1999","unstructured":"Zimmermann, R.: Efficient VLSI Implementation of Modulo (2 n \u00b11) Addition and Multiplication. In: IEEE Symposium on Computer Arithmetic, pp. 158\u2013167. IEEE Computer Society, Los Alamitos (1999)"}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-13089-2_43.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T03:01:03Z","timestamp":1606186863000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-13089-2_43"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642130885","9783642130892"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-13089-2_43","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}