{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:12:54Z","timestamp":1759637574841},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642135088"},{"type":"electronic","value":"9783642135095"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-13509-5_8","type":"book-chapter","created":{"date-parts":[[2010,6,22]],"date-time":"2010-06-22T09:19:57Z","timestamp":1277198397000},"page":"76-87","source":"Crossref","is-referenced-by-count":6,"title":["Approximate All-Pairs Suffix\/Prefix Overlaps"],"prefix":"10.1007","author":[{"given":"Niko","family":"V\u00e4lim\u00e4ki","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Susana","family":"Ladra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Veli","family":"M\u00e4kinen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"8_CR1","unstructured":"Burrows, M., Wheeler, D.: A block sorting lossless data compression algorithm. Technical Report 124, Digital Equipment Corporation (1994)"},{"key":"8_CR2","unstructured":"Roche Company. 454 life sciences, http:\/\/www.454.com\/"},{"key":"8_CR3","doi-asserted-by":"publisher","first-page":"1117","DOI":"10.1101\/gr.089532.108","volume":"19","author":"J.T. Simpson","year":"2009","unstructured":"Simpson, J.T., et al.: Abyss: A parallel assembler for short read sequence data. Genome Res.\u00a019, 1117\u20131123 (2009)","journal-title":"Genome Res."},{"issue":"1","key":"8_CR4","doi-asserted-by":"publisher","first-page":"81","DOI":"10.2144\/000112900","volume":"45","author":"R.D. Morin","year":"2008","unstructured":"Morin, R.D., et al.: Profiling the hela s3 transcriptome using randomly primed cdna and massively parallel short-read sequencing. BioTechniques\u00a045(1), 81\u201394 (2008)","journal-title":"BioTechniques"},{"issue":"15","key":"8_CR5","doi-asserted-by":"publisher","first-page":"1966","DOI":"10.1093\/bioinformatics\/btp336","volume":"25","author":"R. Li","year":"2009","unstructured":"Li, R., et al.: Soap2. Bioinformatics\u00a025(15), 1966\u20131967 (2009)","journal-title":"Bioinformatics"},{"issue":"1","key":"8_CR6","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1186\/1471-2164-7-275","volume":"7","author":"T. Wicker","year":"2006","unstructured":"Wicker, T., et al.: 454 sequencing put to the test using the complex genome of barley. BMC Genomics\u00a07(1), 275 (2006)","journal-title":"BMC Genomics"},{"issue":"4","key":"8_CR7","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 texts. Journal of the ACM\u00a052(4), 552\u2013581 (2005)","journal-title":"Journal of the ACM"},{"issue":"2","key":"8_CR8","doi-asserted-by":"crossref","first-page":"20","DOI":"10.1145\/1240233.1240243","volume":"3","author":"P. Ferragina","year":"2007","unstructured":"Ferragina, P., Manzini, G., M\u00e4kinen, V., Navarro, G.: Compressed representations of sequences and full-text indexes. ACM Transactions on Algorithms (TALG)\u00a03(2), article 20 (2007)","journal-title":"ACM Transactions on Algorithms (TALG)"},{"key":"8_CR9","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology","author":"D. Gusfield","year":"1997","unstructured":"Gusfield, D.: Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press, Cambridge (1997)"},{"issue":"3","key":"8_CR10","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/s00453-004-1108-z","volume":"41","author":"H. Hyyr\u00f6","year":"2005","unstructured":"Hyyr\u00f6, H., Navarro, G.: Bit-parallel witnesses and their applications to approximate string matching. Algorithmica\u00a041(3), 203\u2013231 (2005)","journal-title":"Algorithmica"},{"key":"8_CR11","first-page":"84","volume-title":"Proc. ALENEX 2007","author":"J. K\u00e4rkk\u00e4inen","year":"2007","unstructured":"K\u00e4rkk\u00e4inen, J., Na, J.C.: Faster filters for approximate string matching. In: Proc. ALENEX 2007, pp. 84\u201390. SIAM, Philadelphia (2007)"},{"key":"8_CR12","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1007\/BF01188580","volume":"13","author":"J.D. Kececioglu","year":"1995","unstructured":"Kececioglu, J.D., Myers, E.W.: Combinatorial algorithms for dna sequence assembly. Algorithmica\u00a013, 7\u201351 (1995)","journal-title":"Algorithmica"},{"issue":"6","key":"8_CR13","doi-asserted-by":"publisher","first-page":"791","DOI":"10.1093\/bioinformatics\/btn032","volume":"24","author":"T.W. Lam","year":"2008","unstructured":"Lam, T.W., Sung, W.K., Tam, S.L., Wong, C.K., Yiu, S.M.: Compressed indexing and local alignment of dna. Bioinformatics\u00a024(6), 791\u2013797 (2008)","journal-title":"Bioinformatics"},{"key":"8_CR14","doi-asserted-by":"crossref","unstructured":"Langmead, B., Trapnell, C., Pop, M., Salzberg, S.L.: Ultrafast and memory-efficient alignment of short dna sequences to the human genome. Genome Biology\u00a010(3), R25 (2009)","DOI":"10.1186\/gb-2009-10-3-r25"},{"issue":"8","key":"8_CR15","first-page":"707","volume":"10","author":"V.I. Levenshtein","year":"1966","unstructured":"Levenshtein, V.I.: Binary codes capable of correcting deletions, insertions and reversals. Soviet Physics Doklady\u00a010(8), 707\u2013710 (1966)","journal-title":"Soviet Physics Doklady"},{"key":"8_CR16","doi-asserted-by":"crossref","unstructured":"Li, H., Durbin, R.: Fast and accurate short read alignment with burrows-wheeler transform. Bioinformatics (2009), Advance access","DOI":"10.1093\/bioinformatics\/btp324"},{"key":"8_CR17","volume-title":"LNCS Festschrifts","author":"V. M\u00e4kinen","year":"2010","unstructured":"M\u00e4kinen, V., V\u00e4lim\u00e4ki, N., Laaksonen, A., Katainen, R.: Unifying view of backward backtracking in short read mapping. In: Elomaa, T., Mannila, H., Orponen, P. (eds.) LNCS Festschrifts. Springer, Heidelberg (to appear 2010)"},{"key":"8_CR18","doi-asserted-by":"crossref","unstructured":"M\u00e4kinen, V., Navarro, G.: Dynamic entropy-compressed sequences and full-text indexes. ACM Transactions on Algorithms\u00a04(3) (2008)","DOI":"10.1145\/1367064.1367072"},{"issue":"5","key":"8_CR19","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U. Manber","year":"1993","unstructured":"Manber, U., Myers, G.: Suffix arrays: a new method for on-line string searches. SIAM Journal on Computing\u00a022(5), 935\u2013948 (1993)","journal-title":"SIAM Journal on Computing"},{"issue":"3","key":"8_CR20","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\u00a046(3), 395\u2013415 (1999)","journal-title":"J. ACM"},{"issue":"1","key":"8_CR21","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. Surveys\u00a033(1), 31\u201388 (2001)","journal-title":"ACM Comput. Surveys"},{"key":"8_CR22","doi-asserted-by":"crossref","unstructured":"Navarro, G., M\u00e4kinen, V.: Compressed full-text indexes. ACM Computing Surveys\u00a039(1), article 2 (2007)","DOI":"10.1145\/1216370.1216372"},{"issue":"17","key":"8_CR23","doi-asserted-by":"publisher","first-page":"9748","DOI":"10.1073\/pnas.171285098","volume":"98","author":"P. Pevzner","year":"2001","unstructured":"Pevzner, P., Tang, H., Waterman, M.: An eulerian path approach to dna fragment assembly. Proc. Natl. Acad. Sci.\u00a098(17), 9748\u20139753 (2001)","journal-title":"Proc. Natl. Acad. Sci."},{"key":"8_CR24","doi-asserted-by":"crossref","first-page":"142","DOI":"10.1016\/j.tig.2007.12.006","volume":"24","author":"M. Pop","year":"2008","unstructured":"Pop, M., Salzberg, S.L.: Bioinformatics challenges of new sequencing technology. Trends Genet.\u00a024, 142\u2013149 (2008)","journal-title":"Trends Genet."},{"key":"8_CR25","unstructured":"Salmela, L.: Personal communication (2010)"},{"issue":"4","key":"8_CR26","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1016\/0196-6774(80)90016-4","volume":"1","author":"P. Sellers","year":"1980","unstructured":"Sellers, P.: The theory and computation of evolutionary distances: Pattern recognition. Journal of Algorithms\u00a01(4), 359\u2013373 (1980)","journal-title":"Journal of Algorithms"},{"issue":"1","key":"8_CR27","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1038\/nrg2484","volume":"10","author":"Z. Wang","year":"2009","unstructured":"Wang, Z., Gerstein, M., Snyder, M.: Rna-seq: a revolutionary tool for transcriptomics. Nature Reviews Genetics\u00a010(1), 57\u201363 (2009)","journal-title":"Nature Reviews Genetics"},{"key":"8_CR28","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern matching algorithm. In: Proc. 14th Annual IEEE Symposium on Switching and Automata Theory, pp. 1\u201311 (1973)","DOI":"10.1109\/SWAT.1973.13"},{"issue":"5","key":"8_CR29","doi-asserted-by":"publisher","first-page":"821","DOI":"10.1101\/gr.074492.107","volume":"18","author":"D.R. Zerbino","year":"2008","unstructured":"Zerbino, D.R., Birney, E.: Velvet: algorithms for de novo short read assembly using de bruijn graphs. Genome Research\u00a018(5), 821\u2013829 (2008)","journal-title":"Genome Research"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-13509-5_8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T02:39:11Z","timestamp":1606185551000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-13509-5_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642135088","9783642135095"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-13509-5_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}