{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T01:12:00Z","timestamp":1648775520662},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2013,5,10]],"date-time":"2013-05-10T00:00:00Z","timestamp":1368144000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2013,10]]},"DOI":"10.1007\/s00453-013-9794-z","type":"journal-article","created":{"date-parts":[[2013,5,9]],"date-time":"2013-05-09T17:09:03Z","timestamp":1368119343000},"page":"125-141","source":"Crossref","is-referenced-by-count":0,"title":["Compressed Directed Acyclic Word Graph with Application in Local Alignment"],"prefix":"10.1007","volume":"67","author":[{"given":"Huy Hoang","family":"Do","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wing Kin","family":"Sung","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,5,10]]},"reference":[{"issue":"3","key":"9794_CR1","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","volume":"215","author":"S. Altschul","year":"1990","unstructured":"Altschul, S., Gish, W., Miller, W., Myers, E., Lipman, D.: Basic local alignment search tool. J. Mol. Biol. 215(3), 403\u2013410 (1990)","journal-title":"J. Mol. Biol."},{"issue":"5","key":"9794_CR2","doi-asserted-by":"crossref","first-page":"572","DOI":"10.1145\/42411.42420","volume":"31","author":"A. Appel","year":"1988","unstructured":"Appel, A., Jacobson, G.: The world\u2019s fastest scrabble program. Commun. ACM 31(5), 572\u2013578 (1988)","journal-title":"Commun. ACM"},{"key":"9794_CR3","first-page":"16","volume-title":"Proceedings of the String Processing and Information Retrieval Symposium","author":"R. Baeza-Yates","year":"1999","unstructured":"Baeza-Yates, R., Gonnet, G.: A fast algorithm on average for all-against-all sequence matching. In: Proceedings of the String Processing and Information Retrieval Symposium, pp. 16\u201323 (1999)"},{"key":"9794_CR4","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/0304-3975(85)90157-4","volume":"40","author":"A. Blumer","year":"1985","unstructured":"Blumer, A., Blumer, J., Haussler, D., Ehrenfeucht, A., Chen, M., Seiferas, J.: The smallest automaton recognizing the subwords of a text. Theor. Comput. Sci. 40, 31\u201355 (1985)","journal-title":"Theor. Comput. Sci."},{"key":"9794_CR5","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1145\/1242572.1242590","volume-title":"Proceedings of the 16th Conference on World Wide Web","author":"H. Chim","year":"2007","unstructured":"Chim, H., Deng, X.: A new suffix tree similarity measure for document clustering. In: Proceedings of the 16th Conference on World Wide Web, pp. 121\u2013130 (2007)"},{"key":"9794_CR6","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1007\/3-540-63246-8_12","volume-title":"Structures in Logic and Computer Science","author":"M. Crochemore","year":"1997","unstructured":"Crochemore, M., V\u00e9rin, R.: On compact directed acyclic word graphs. In: Structures in Logic and Computer Science, vol. 1261, pp. 192\u2013211 (1997)"},{"issue":"4","key":"9794_CR7","doi-asserted-by":"crossref","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 52(4), 552\u2013581 (2005)","journal-title":"J. ACM"},{"key":"9794_CR8","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1145\/1109557.1109599","volume-title":"Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm","author":"A. Golynski","year":"2006","unstructured":"Golynski, A., Munro, J.I., Rao, S.S.: Rank\/select operations on large alphabets: a tool for text indexing. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, pp.\u00a0368\u2013373 (2006)"},{"key":"9794_CR9","first-page":"841","volume-title":"Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"R. Grossi","year":"2003","unstructured":"Grossi, R., Gupta, A., Vitter, J.: High-order entropy-compressed text indexes. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a0841\u2013850 (2003)"},{"key":"9794_CR10","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)"},{"key":"9794_CR11","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1109\/ISDA.2008.365","volume-title":"Eighth International Conference on Intelligent Systems Design and Applications","author":"J. Huang","year":"2008","unstructured":"Huang, J., Powers, D.: Suffix tree based approach for Chinese information retrieval. In: Eighth International Conference on Intelligent Systems Design and Applications, pp.\u00a0393\u2013397 (2008)"},{"key":"9794_CR12","first-page":"197","volume-title":"Proceedings of Prague Stringology Conference","author":"S. Inenaga","year":"2006","unstructured":"Inenaga, S., Takeda, M.: Sparse compact directed acyclic word graphs. In: Proceedings of Prague Stringology Conference, pp.\u00a0197\u2013211 (2006)"},{"issue":"2","key":"9794_CR13","doi-asserted-by":"crossref","first-page":"619","DOI":"10.1016\/j.jcss.2011.09.002","volume":"78","author":"J. Jansson","year":"2012","unstructured":"Jansson, J., Sadakane, K., Sung, W.: Ultra-succinct representation of ordered trees with applications. J. Comput. Syst. Sci. 78(2), 619\u2013631 (2012)","journal-title":"J. Comput. Syst. Sci."},{"key":"9794_CR14","doi-asserted-by":"crossref","first-page":"4633","DOI":"10.1093\/nar\/29.22.4633","volume":"29","author":"S. Kurtz","year":"2001","unstructured":"Kurtz, S., Choudhuri, J.V., Ohlebusch, E., Schleiermacher, C., Stoye, J., Giegerich, R.: Reputer: the manifold applications of repeat analysis on a genomic scale. Nucleic Acids Res. 29, 4633\u20134642 (2001)","journal-title":"Nucleic Acids Res."},{"issue":"6","key":"9794_CR15","doi-asserted-by":"crossref","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 24(6), 791\u2013797 (2008)","journal-title":"Bioinformatics"},{"key":"9794_CR16","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 Biol. 10, R25 (2009)","journal-title":"Genome Biol."},{"key":"9794_CR17","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1109\/DCC.1996.488324","volume-title":"Proceedings of the IEEE Data Compression Conference","author":"N. Larsson","year":"1996","unstructured":"Larsson, N.: Extended application of suffix trees to data compression. In: Proceedings of the IEEE Data Compression Conference, pp.\u00a0190\u2013199 (1996)"},{"issue":"5","key":"9794_CR18","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1093\/bioinformatics\/btp698","volume":"26","author":"H. Li","year":"2010","unstructured":"Li, H., Durbin, R.: Fast and accurate long-read alignment with burrows-wheeler transform. Bioinformatics 26(5), 589\u2013595 (2010)","journal-title":"Bioinformatics"},{"issue":"3","key":"9794_CR19","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1007\/s00453-006-0126-4","volume":"46","author":"M. Maa\u00df","year":"2006","unstructured":"Maa\u00df, M.: Average-case analysis of approximate trie search. Algorithmica 46(3), 469\u2013491 (2006)","journal-title":"Algorithmica"},{"key":"9794_CR20","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/978-3-540-75530-2_21","volume-title":"Proceedings of the String Processing and Information Retrieval Symposium","author":"V. M\u00e4kinen","year":"2007","unstructured":"M\u00e4kinen, V., Navarro, G.: Implicit compression boosting with applications to self-indexing. In: Proceedings of the String Processing and Information Retrieval Symposium, pp.\u00a0229\u2013241 (2007)"},{"key":"9794_CR21","doi-asserted-by":"crossref","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 J. Comput. 22, 935\u2013948 (1993)","journal-title":"SIAM J. Comput."},{"key":"9794_CR22","first-page":"910","volume-title":"Proceedings of the 29th International Conference on Very Large Data Bases","author":"C. Meek","year":"2003","unstructured":"Meek, C., Patel, J., Kasetty, S.: Oasis: an online and accurate technique for local-alignment searches on biological sequences. In: Proceedings of the 29th International Conference on Very Large Data Bases, pp.\u00a0910\u2013921 (2003)"},{"key":"9794_CR23","doi-asserted-by":"crossref","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. 33, 31\u201388 (2001)","journal-title":"ACM Comput. Surv."},{"key":"9794_CR24","first-page":"205","volume":"1","author":"G. Navarro","year":"2000","unstructured":"Navarro, G., Baeza-Yates, R.: A hybrid indexing method for approximate string matching. J. Discrete Algorithms 1, 205\u2013239 (2000)","journal-title":"J. Discrete Algorithms"},{"key":"9794_CR25","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1007\/s00224-006-1198-x","volume":"41","author":"K. Sadakane","year":"2007","unstructured":"Sadakane, K.: Compressed suffix trees with full functionality. Theory Comput. Syst. 41, 589\u2013607 (2007)","journal-title":"Theory Comput. Syst."},{"key":"9794_CR26","first-page":"350","volume-title":"Proceedings of the 31st Conference on Current Trends in Theory and Practice of Computer","author":"M. Senft","year":"2005","unstructured":"Senft, M.: Suffix tree based data compression. In: Proceedings of the 31st Conference on Current Trends in Theory and Practice of Computer, pp.\u00a0350\u2013359 (2005)"},{"key":"9794_CR27","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/0022-2836(81)90087-5","volume":"147","author":"T.F. Smith","year":"1981","unstructured":"Smith, T.F., Waterman, M.S.: Identification of common molecular subsequences. J. Mol. Biol. 147, 195\u2013197 (1981)","journal-title":"J. Mol. Biol."},{"key":"9794_CR28","doi-asserted-by":"crossref","first-page":"408","DOI":"10.1007\/978-0-387-30162-4_188","volume-title":"Encyclopedia of Algorithms","author":"W.-K. Sung","year":"2008","unstructured":"Sung, W.-K.: Indexed approximate string matching. In: Encyclopedia of Algorithms, pp.\u00a0408\u2013410 (2008)"},{"key":"9794_CR29","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/SWAT.1973.13","volume-title":"IEEE 14th Annual Symposium on Switching and Automata Theory","author":"P. Weiner","year":"1973","unstructured":"Weiner, P.: Linear pattern matching algorithms. In: IEEE 14th Annual Symposium on Switching and Automata Theory, pp.\u00a01\u201311 (1973)"},{"key":"9794_CR30","first-page":"1350","volume-title":"IEEE 23rd International Conference on Data Engineering","author":"S. Wong","year":"2007","unstructured":"Wong, S., Sung, W., Wong, L.: CPS-tree: a compact partitioned suffix tree for disk-based indexing on large genome sequences. In: IEEE 23rd International Conference on Data Engineering, pp.\u00a01350\u20131354 (2007)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9794-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-013-9794-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9794-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:12Z","timestamp":1559137512000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-013-9794-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,5,10]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,10]]}},"alternative-id":["9794"],"URL":"https:\/\/doi.org\/10.1007\/s00453-013-9794-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,5,10]]}}}