{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T04:23:36Z","timestamp":1743049416177,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642296994"},{"type":"electronic","value":"9783642297007"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-29700-7_27","type":"book-chapter","created":{"date-parts":[[2012,4,28]],"date-time":"2012-04-28T12:25:56Z","timestamp":1335615956000},"page":"291-302","source":"Crossref","is-referenced-by-count":8,"title":["Fast Relative Lempel-Ziv Self-index for Similar Sequences"],"prefix":"10.1007","author":[{"given":"Huy Hoang","family":"Do","sequence":"first","affiliation":[]},{"given":"Jesper","family":"Jansson","sequence":"additional","affiliation":[]},{"given":"Kunihiko","family":"Sadakane","sequence":"additional","affiliation":[]},{"given":"Wing-Kin","family":"Sung","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"7319","key":"27_CR1","doi-asserted-by":"crossref","first-page":"1061","DOI":"10.1038\/nature09534","volume":"467","author":"The 1000 Genomes Project Consortium","year":"2010","unstructured":"The 1000 Genomes Project Consortium: A map of human genome variation from population-scale sequencing. Nature\u00a0467(7319), 1061\u20131073 (2010)","journal-title":"Nature"},{"key":"27_CR2","doi-asserted-by":"crossref","unstructured":"Bille, P., Landau, G.M., Raman, R., Sadakane, K., Satti, S.R., Weimann, O.: Random access to grammar-compressed strings. In: SODA, pp. 373\u2013389 (2011)","DOI":"10.1137\/1.9781611973082.30"},{"key":"27_CR3","doi-asserted-by":"crossref","unstructured":"Cao, M.D., Dix, T.I., Allison, L., Mears, C.: A simple statistical algorithm for biological sequence compression. In: DCC, pp. 43\u201352 (2007)","DOI":"10.1109\/DCC.2007.7"},{"key":"27_CR4","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Larsen, K.G., P\u0103tra\u015fcu, M.: Orthogonal range searching on the RAM, revisited. In: SoCG, pp. 1\u201310 (2011)","DOI":"10.1145\/1998196.1998198"},{"issue":"2","key":"27_CR5","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1093\/bioinformatics\/btn582","volume":"25","author":"S. Christley","year":"2009","unstructured":"Christley, S., Lu, Y., Li, C., Xie, X.: Human genomes as email attachments. Bioinformatics\u00a025(2), 274\u2013275 (2009)","journal-title":"Bioinformatics"},{"key":"27_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/978-3-642-03816-7_21","volume-title":"Mathematical Foundations of Computer Science 2009","author":"F. Claude","year":"2009","unstructured":"Claude, F., Navarro, G.: Self-indexed Text Compression Using Straight-Line Programs. In: Kr\u00e1lovi\u010d, R., Niwi\u0144ski, D. (eds.) MFCS 2009. LNCS, vol.\u00a05734, pp. 235\u2013246. Springer, Heidelberg (2009)"},{"key":"27_CR7","unstructured":"Ferragina, P., Manzini, G.: Compression boosting in optimal linear time using the Burrows-Wheeler Transform. In: SODA, pp. 655\u2013663 (2004)"},{"issue":"4","key":"27_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. Journal of the ACM\u00a052(4), 552\u2013581 (2005)","journal-title":"Journal of the ACM"},{"key":"27_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"459","DOI":"10.1007\/978-3-540-74450-4_41","volume-title":"Combinatorics, Algorithms, Probabilistic and Experimental Methodologies","author":"J. Fischer","year":"2007","unstructured":"Fischer, J., Heun, V.: A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array. In: Chen, B., Paterson, M., Zhang, G. (eds.) ESCAPE 2007. LNCS, vol.\u00a04614, pp. 459\u2013470. Springer, Heidelberg (2007)"},{"key":"27_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1007\/978-3-642-28332-1_21","volume-title":"Language and Automata Theory and Applications","author":"T. Gagie","year":"2012","unstructured":"Gagie, T., Gawrychowski, P., K\u00e4rkk\u00e4inen, J., Nekrich, Y., Puglisi, S.J.: A Faster Grammar-Based Self-index. In: Dediu, A.-H., Mart\u00edn-Vide, C. (eds.) LATA 2012. LNCS, vol.\u00a07183, pp. 240\u2013251. Springer, Heidelberg (2012)"},{"key":"27_CR11","doi-asserted-by":"crossref","unstructured":"Golynski, A., Munro, J.I., Rao, S.S.: Rank\/select operations on large alphabets: a tool for text indexing. In: SODA, pp. 368\u2013373 (2006)","DOI":"10.1145\/1109557.1109599"},{"key":"27_CR12","doi-asserted-by":"crossref","unstructured":"Grumbach, S., Tahi, F.: Compression of DNA sequences. In: DCC, pp. 340\u2013350 (1993)","DOI":"10.1109\/DCC.1993.253115"},{"key":"27_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/978-3-642-14355-7_19","volume-title":"Algorithmic Aspects in Information and Management","author":"S. Huang","year":"2010","unstructured":"Huang, S., Lam, T.W., Sung, W.K., Tam, S.L., Yiu, S.M.: Indexing Similar DNA Sequences. In: Chen, B. (ed.) AAIM 2010. LNCS, vol.\u00a06124, pp. 180\u2013190. Springer, Heidelberg (2010)"},{"key":"27_CR14","doi-asserted-by":"crossref","unstructured":"Kreft, S., Navarro, G.: LZ77-like compression with fast random access. In: DCC, pp. 239\u2013248 (2010)","DOI":"10.1109\/DCC.2010.29"},{"key":"27_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-3-642-21458-5_6","volume-title":"Combinatorial Pattern Matching","author":"S. Kreft","year":"2011","unstructured":"Kreft, S., Navarro, G.: Self-indexing Based on LZ77. In: Giancarlo, R., Manzini, G. (eds.) CPM 2011. LNCS, vol.\u00a06661, pp. 41\u201354. Springer, Heidelberg (2011)"},{"key":"27_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/978-3-642-16321-0_20","volume-title":"String Processing and Information Retrieval","author":"S. Kuruppu","year":"2010","unstructured":"Kuruppu, S., Puglisi, S.J., Zobel, J.: Relative Lempel-Ziv Compression of Genomes for Large-Scale Storage and Retrieval. In: Chavez, E., Lonardi, S. (eds.) SPIRE 2010. LNCS, vol.\u00a06393, pp. 201\u2013206. Springer, Heidelberg (2010)"},{"key":"27_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1007\/978-3-642-24583-1_41","volume-title":"String Processing and Information Retrieval","author":"S. Kuruppu","year":"2011","unstructured":"Kuruppu, S., Puglisi, S.J., Zobel, J.: Reference Sequence Construction for Relative Compression of Genomes. In: Grossi, R., Sebastiani, F., Silvestri, F. (eds.) SPIRE 2011. LNCS, vol.\u00a07024, pp. 420\u2013425. Springer, Heidelberg (2011)"},{"key":"27_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/978-3-540-75530-2_21","volume-title":"String Processing and Information Retrieval","author":"V. M\u00e4kinen","year":"2007","unstructured":"M\u00e4kinen, V., Navarro, G.: Implicit Compression Boosting with Applications to Self-indexing. In: Ziviani, N., Baeza-Yates, R. (eds.) SPIRE 2007. LNCS, vol.\u00a04726, pp. 229\u2013241. Springer, Heidelberg (2007)"},{"issue":"3","key":"27_CR19","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1089\/cmb.2009.0169","volume":"17","author":"V. M\u00e4kinen","year":"2010","unstructured":"M\u00e4kinen, V., Navarro, G., Sir\u00e9n, J., V\u00e4lim\u00e4ki, N.: Storage and retrieval of highly repetitive sequence collections. J. of Computational Biology\u00a017(3), 281\u2013308 (2010)","journal-title":"J. of Computational Biology"},{"key":"27_CR20","unstructured":"Muthukrishnan, S.: Efficient algorithms for document retrieval problems. In: SODA, pp. 657\u2013666 (2002)"},{"issue":"4","key":"27_CR21","doi-asserted-by":"publisher","first-page":"342","DOI":"10.1016\/j.comgeo.2008.09.001","volume":"42","author":"Y. Nekrich","year":"2009","unstructured":"Nekrich, Y.: Orthogonal range searching in linear and almost-linear space. Computational Geometry\u00a042(4), 342\u2013351 (2009)","journal-title":"Computational Geometry"},{"key":"27_CR22","doi-asserted-by":"crossref","unstructured":"P\u0103tra\u015fcu, M.: Succincter. In: FOCS, pp. 305\u2013313 (2008)","DOI":"10.1109\/FOCS.2008.83"},{"key":"27_CR23","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/S0304-3975(02)00777-6","volume":"302","author":"W. Rytter","year":"2003","unstructured":"Rytter, W.: Application of Lempel-Ziv factorization to the approximation of grammar-based compression. Theoretical Computer Science\u00a0302, 211\u2013222 (2003)","journal-title":"Theoretical Computer Science"},{"key":"27_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1007\/978-3-540-89097-3_17","volume-title":"String Processing and Information Retrieval","author":"J. Sir\u00e9n","year":"2008","unstructured":"Sir\u00e9n, J., V\u00e4lim\u00e4ki, N., M\u00e4kinen, V., Navarro, G.: Run-Length Compressed Indexes Are Superior for Highly Repetitive Sequence Collections. In: Amir, A., Turpin, A., Moffat, A. (eds.) SPIRE 2008. LNCS, vol.\u00a05280, pp. 164\u2013175. Springer, Heidelberg (2008)"},{"issue":"2","key":"27_CR25","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0020-0190(83)90075-3","volume":"17","author":"D.E. Willard","year":"1983","unstructured":"Willard, D.E.: Log-logarithmic worst-case range queries are possible in space \u0398(N). Information Processing Letters\u00a017(2), 81\u201384 (1983)","journal-title":"Information Processing Letters"},{"issue":"3","key":"27_CR26","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","volume":"23","author":"J. Ziv","year":"1977","unstructured":"Ziv, J., Lempel, A.: A universal algorithm for sequential data compression. IEEE Transactions on Information Theory\u00a023(3), 337\u2013343 (1977)","journal-title":"IEEE Transactions on Information Theory"}],"container-title":["Lecture Notes in Computer Science","Frontiers in Algorithmics and Algorithmic Aspects in Information and Management"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-29700-7_27.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T21:54:21Z","timestamp":1743026061000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-29700-7_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642296994","9783642297007"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-29700-7_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}