{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T05:27:56Z","timestamp":1725600476001},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642226847"},{"type":"electronic","value":"9783642226854"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011]]},"DOI":"10.1007\/978-3-642-22685-4_44","type":"book-chapter","created":{"date-parts":[[2011,8,10]],"date-time":"2011-08-10T04:54:39Z","timestamp":1312952079000},"page":"503-518","source":"Crossref","is-referenced-by-count":0,"title":["Compressed Directed Acyclic Word Graph with Application in Local Alignment"],"prefix":"10.1007","author":[{"given":"Do Huy","family":"Hoang","sequence":"first","affiliation":[]},{"given":"Sung Wing","family":"Kin","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"44_CR1","doi-asserted-by":"publisher","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. Journal of Molecular Biology\u00a0215(3), 403\u2013410 (1990)","journal-title":"Journal of Molecular Biology"},{"key":"44_CR2","doi-asserted-by":"crossref","unstructured":"Baeza-Yates, R., Gonnet, G.: A fast algorithm on average for all-against-all sequence matching. In: Proc. of SPIRE 1999 (1999)","DOI":"10.1109\/SPIRE.1999.796573"},{"key":"44_CR3","doi-asserted-by":"publisher","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. TCS\u00a040, 31\u201355 (1985)","journal-title":"TCS"},{"key":"44_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","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: Mycielski, J., Rozenberg, G., Salomaa, A. (eds.) Structures in Logic and Computer Science. LNCS, vol.\u00a01261, pp. 192\u2013211. Springer, Heidelberg (1997)"},{"key":"44_CR5","doi-asserted-by":"crossref","unstructured":"Ferragina, P., Manzini, G.: Opportunistic data structures with applications. In: FOCS, p. 390 (2000)","DOI":"10.1109\/SFCS.2000.892127"},{"key":"44_CR6","unstructured":"Grossi, R., Gupta, A., Vitter, J.: High-order entropy-compressed text indexes. In: ACM-SIAM (2003)"},{"key":"44_CR7","doi-asserted-by":"crossref","unstructured":"Huang, J., Powers, D.: Suffix tree based approach for chinese information retrieval. In: 8th Conf. on ISDA (2008)","DOI":"10.1109\/ISDA.2008.365"},{"key":"44_CR8","doi-asserted-by":"crossref","unstructured":"Inenaga, S., Takeda, M.: Sparse compact directed acyclic word graphs. In: Proc. Prague Stringology Conf., pp. 197\u2013211 (2006)","DOI":"10.1007\/11880561_6"},{"key":"44_CR9","unstructured":"Jansson, J., Sadakane, K., Sung, W.K.: Ultra-succinct representation of ordered trees. In: ACM-SIAM (2007)"},{"issue":"6","key":"44_CR10","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":"44_CR11","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 Biol.\u00a010, 25 (2009)","journal-title":"Genome Biol."},{"issue":"5","key":"44_CR12","doi-asserted-by":"publisher","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\u00a026(5), 589 (2010)","journal-title":"Bioinformatics"},{"issue":"3","key":"44_CR13","doi-asserted-by":"publisher","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\u00a046(3), 469\u2013491 (2006)","journal-title":"Algorithmica"},{"key":"44_CR14","volume-title":"Proc. of ACM-SIAM","author":"U. Manber","year":"1990","unstructured":"Manber, U., Myers, G.: Suffix arrays: a new method for on-line string searches. In: Proc. of ACM-SIAM. SIAM, Philadelphia (1990)"},{"key":"44_CR15","doi-asserted-by":"crossref","unstructured":"Meek, C., Patel, J.M., Kasetty, S.: Oasis: an online and accurate technique for local-alignment searches on biological sequences. In: VLDB (2003)","DOI":"10.1016\/B978-012722442-8\/50085-9"},{"key":"44_CR16","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1145\/375360.375365","volume":"33","author":"G. Navarro","year":"2001","unstructured":"Navarro, G.: A guided tour to approximate string matching. CSUR\u00a033, 88 (2001)","journal-title":"CSUR"},{"key":"44_CR17","first-page":"205","volume":"1","author":"G. Navarro","year":"2000","unstructured":"Navarro, G., Baeza-Yates, R.: A hybrid indexing method for approximate string matching. Journal of Discrete Algorithms\u00a01, 205\u2013239 (2000)","journal-title":"Journal of Discrete Algorithms"},{"key":"44_CR18","first-page":"589","volume":"41","author":"K. Sadakane","year":"2007","unstructured":"Sadakane, K.: Compressed suffix trees with full functionality. TOCS\u00a041, 589\u2013607 (2007)","journal-title":"TOCS"},{"key":"44_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"350","DOI":"10.1007\/978-3-540-30577-4_38","volume-title":"SOFSEM 2005: Theory and Practice of Computer Science","author":"M. Senft","year":"2005","unstructured":"Senft, M.: Suffix tree based data compression. In: Vojt\u00e1\u0161, P., Bielikov\u00e1, M., Charron-Bost, B., S\u00fdkora, O. (eds.) SOFSEM 2005. LNCS, vol.\u00a03381, pp. 350\u2013359. Springer, Heidelberg (2005)"},{"key":"44_CR20","doi-asserted-by":"publisher","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.\u00a0147, 195\u2013197 (1981)","journal-title":"J. Mol. Biol."},{"key":"44_CR21","volume-title":"Encyclopedia of Algorithms","author":"W.-K. Sung","year":"2008","unstructured":"Sung, W.-K.: Indexed approximate string matching. In: Encyclopedia of Algorithms. Springer, Heidelberg (2008)"},{"key":"44_CR22","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern matching algorithms. In: IEEE SWAT (1973)","DOI":"10.1109\/SWAT.1973.13"},{"key":"44_CR23","doi-asserted-by":"crossref","unstructured":"Wong, S., Sung, W., Wong, L.: CPS-tree: A compact partitioned suffix tree for disk-based indexing on large genome sequences. In: ICDE (2007)","DOI":"10.1109\/ICDE.2007.369009"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22685-4_44","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,13]],"date-time":"2019-06-13T19:39:29Z","timestamp":1560454769000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22685-4_44"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642226847","9783642226854"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22685-4_44","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}