{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:12:37Z","timestamp":1760202757891,"version":"3.37.3"},"reference-count":69,"publisher":"Oxford University Press (OUP)","issue":"5","license":[{"start":{"date-parts":[[2017,11,21]],"date-time":"2017-11-21T00:00:00Z","timestamp":1511222400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100004440","name":"Wellcome Trust","doi-asserted-by":"publisher","award":["098051"],"award-info":[{"award-number":["098051"]}],"id":[{"id":"10.13039\/100004440","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018,5,1]]},"DOI":"10.1093\/comjnl\/bxx108","type":"journal-article","created":{"date-parts":[[2017,10,23]],"date-time":"2017-10-23T19:34:54Z","timestamp":1508787294000},"page":"773-788","source":"Crossref","is-referenced-by-count":10,"title":["Relative Suffix Trees"],"prefix":"10.1093","volume":"61","author":[{"given":"Andrea","family":"Farruggia","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Pisa, Largo Bruno Pontecorvo 3, 56127 Pisa PI, Italy"}]},{"given":"Travis","family":"Gagie","sequence":"additional","affiliation":[{"name":"CeBiB\u2014Center for Biotechnology and Bioengineering, Santiago, Chile"},{"name":"Escuela de Inform\u00e1tica y Telecomunicaciones, Diego Portales University, Ej\u00e9rcito 441, Santiago, Chile"}]},{"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[{"name":"CeBiB\u2014Center for Biotechnology and Bioengineering, Santiago, Chile"},{"name":"Department of Computer Science, University of Chile, Beauchef 851, Santiago, Chile"}]},{"given":"Simon J","family":"Puglisi","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Helsinki, Helsinki, Finland"}]},{"given":"Jouni","family":"Sir\u00e9n","sequence":"additional","affiliation":[{"name":"Wellcome Trust Sanger Institute, Hinxton CB10 1SA, UK"}]}],"member":"286","published-online":{"date-parts":[[2017,11,21]]},"reference":[{"year":"1973","author":"Weiner","key":"key\n\t\t\t\t20180425035439_bxx108C1"},{"key":"key\n\t\t\t\t20180425035439_bxx108C2","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology","author":"Gusfield","year":"1997"},{"volume-title":"Bioinformatics Algorithms: Sequence Analysis, Genome Rearrangements, and Phylogenetic Reconstruction","year":"2013","author":"Ohlebusch","key":"key\n\t\t\t\t20180425035439_bxx108C3"},{"key":"key\n\t\t\t\t20180425035439_bxx108C4","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139940023","volume-title":"Genome-Scale Algorithm Design","author":"M\u00e4kinen","year":"2015"},{"key":"key\n\t\t\t\t20180425035439_bxx108C5","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1007\/s00224-006-1198-x","article-title":"Compressed suffix trees with full functionality","volume":"41","author":"Sadakane","year":"2007","journal-title":"Theory Comput. Syst."},{"key":"key\n\t\t\t\t20180425035439_bxx108C6","doi-asserted-by":"crossref","first-page":"5354","DOI":"10.1016\/j.tcs.2009.09.012","article-title":"Faster entropy-bounded compressed suffix trees","volume":"410","author":"Fischer","year":"2009","journal-title":"Theor. Comput. Sci."},{"year":"2009","author":"Ohlebusch","key":"key\n\t\t\t\t20180425035439_bxx108C7"},{"year":"2010","author":"Ohlebusch","key":"key\n\t\t\t\t20180425035439_bxx108C8"},{"key":"key\n\t\t\t\t20180425035439_bxx108C9","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1016\/j.ipl.2010.02.010","article-title":"Wee LCP","volume":"110","author":"Fischer","year":"2010","journal-title":"Inf. Process. Lett."},{"key":"key\n\t\t\t\t20180425035439_bxx108C10","doi-asserted-by":"crossref","first-page":"article 4","DOI":"10.1145\/2000807.2000821","article-title":"Fully compressed suffix trees","volume":"7","author":"Russo","year":"2011","journal-title":"ACM Trans. Algorithms"},{"year":"2011","author":"Gog","key":"key\n\t\t\t\t20180425035439_bxx108C11"},{"key":"key\n\t\t\t\t20180425035439_bxx108C12","doi-asserted-by":"crossref","first-page":"article 2.1","DOI":"10.1145\/2444016.2461327","article-title":"Compressed suffix trees: Efficient computation and storage of lcp-values","volume":"18","author":"Gog","year":"2013","journal-title":"ACM J. Exp. Algorithmics"},{"key":"key\n\t\t\t\t20180425035439_bxx108C13","doi-asserted-by":"crossref","first-page":"319","DOI":"10.3390\/a6020319","article-title":"Practical compressed suffix trees","volume":"6","author":"Abeliuk","year":"2013","journal-title":"Algorithms"},{"year":"2014","author":"Navarro","key":"key\n\t\t\t\t20180425035439_bxx108C14"},{"key":"key\n\t\t\t\t20180425035439_bxx108C15","doi-asserted-by":"crossref","first-page":"article 1.8","DOI":"10.1145\/2851495","article-title":"Faster compressed suffix trees for repetitive text collections","volume":"21","author":"Navarro","year":"2016","journal-title":"ACM J. Exp. Algorithmics"},{"year":"2015","author":"Ocker","key":"key\n\t\t\t\t20180425035439_bxx108C16"},{"year":"2015","author":"Belazzougui","key":"key\n\t\t\t\t20180425035439_bxx108C17"},{"key":"key\n\t\t\t\t20180425035439_bxx108C18","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1038\/nature15393","article-title":"A global reference for human genetic variation","volume":"526","author":"The 1000 Genomes Project Consortium","year":"2015","journal-title":"Nature"},{"key":"key\n\t\t\t\t20180425035439_bxx108C19","doi-asserted-by":"crossref","first-page":"737","DOI":"10.1109\/18.841160","article-title":"Grammar-based codes: a new class of universal lossless source codes","volume":"46","author":"Kieffer","year":"2000","journal-title":"IEEE Trans. Inf. Theory"},{"key":"key\n\t\t\t\t20180425035439_bxx108C20","doi-asserted-by":"crossref","first-page":"2554","DOI":"10.1109\/TIT.2005.850116","article-title":"The smallest grammar problem","volume":"51","author":"Charikar","year":"2005","journal-title":"IEEE Trans. Inf. Theory"},{"key":"key\n\t\t\t\t20180425035439_bxx108C21","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1137\/130936889","article-title":"Random access to grammar-compressed strings and trees","volume":"44","author":"Bille","year":"2015","journal-title":"SIAM J. Comput."},{"key":"key\n\t\t\t\t20180425035439_bxx108C22","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","article-title":"A universal algorithm for sequential data compression","volume":"23","author":"Ziv","year":"1977","journal-title":"IEEE Trans. Inf. Theory"},{"key":"key\n\t\t\t\t20180425035439_bxx108C23","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/j.tcs.2012.02.006","article-title":"On compressing and indexing repetitive sequences","volume":"483","author":"Kreft","year":"2013","journal-title":"Theor. Comput. Sci."},{"year":"2012","author":"Gagie","key":"key\n\t\t\t\t20180425035439_bxx108C24"},{"year":"2014","author":"Gagie","key":"key\n\t\t\t\t20180425035439_bxx108C25"},{"key":"key\n\t\t\t\t20180425035439_bxx108C26","doi-asserted-by":"crossref","first-page":"12","DOI":"10.3389\/fbioe.2015.00012","article-title":"Searching and indexing genomic databases via kernelization","volume":"3","author":"Gagie","year":"2015","journal-title":"Front. Bioeng. Biotechnol."},{"year":"2010","author":"Kuruppu","key":"key\n\t\t\t\t20180425035439_bxx108C27"},{"year":"2011","author":"Kuruppu","key":"key\n\t\t\t\t20180425035439_bxx108C28"},{"key":"key\n\t\t\t\t20180425035439_bxx108C29","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1109\/TCBB.2011.82","article-title":"Iterative dictionary construction for compression of large DNA data sets","volume":"9","author":"Kuruppu","year":"2012","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinformatics"},{"year":"2016","author":"Liao","key":"key\n\t\t\t\t20180425035439_bxx108C30"},{"key":"key\n\t\t\t\t20180425035439_bxx108C31","doi-asserted-by":"crossref","first-page":"2979","DOI":"10.1093\/bioinformatics\/btr505","article-title":"Robust relative compression of genomes with random access","volume":"27","author":"Deorowicz","year":"2011","journal-title":"Bioinformatics"},{"year":"2014","author":"Ferrada","key":"key\n\t\t\t\t20180425035439_bxx108C32"},{"key":"key\n\t\t\t\t20180425035439_bxx108C33","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/j.tcs.2013.07.024","article-title":"Fast relative Lempel\u2013Ziv self-index for similar sequences","volume":"532","author":"Do","year":"2014","journal-title":"Theor. Comput. Sci."},{"year":"2016","author":"Maciuca","key":"key\n\t\t\t\t20180425035439_bxx108C34"},{"year":"2017","author":"Paten","key":"key\n\t\t\t\t20180425035439_bxx108C35"},{"year":"2017","author":"Sir\u00e9n","key":"key\n\t\t\t\t20180425035439_bxx108C36"},{"key":"key\n\t\t\t\t20180425035439_bxx108C37","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1109\/TCBB.2013.2297101","article-title":"Indexing graphs for path queries with applications in genome research","volume":"11","author":"Sir\u00e9n","year":"2014","journal-title":"ACM\/IEEE Trans. Comput. Biol. Bioinformatics"},{"key":"key\n\t\t\t\t20180425035439_bxx108C38","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/j.tcs.2015.08.008","article-title":"FM-index of alignment: a compressed index for similar strings","volume":"638","author":"Na","year":"2016","journal-title":"Theor. Comput. Sci."},{"year":"2017","author":"Na","key":"key\n\t\t\t\t20180425035439_bxx108C39"},{"key":"key\n\t\t\t\t20180425035439_bxx108C40","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1038\/ng.1028","article-title":"De novo assembly and genotyping of variants using colored de Bruijn graphs","volume":"44","author":"Iqbal","year":"2012","journal-title":"Nat. Genet."},{"year":"2013","author":"Na","key":"key\n\t\t\t\t20180425035439_bxx108C41"},{"year":"2013","author":"Na","key":"key\n\t\t\t\t20180425035439_bxx108C42"},{"key":"key\n\t\t\t\t20180425035439_bxx108C43","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0222058","article-title":"Suffix arrays: a new method for on-line string searches","volume":"22","author":"Manber","year":"1993","journal-title":"SIAM J. Comput."},{"year":"2014","author":"Belazzougui","key":"key\n\t\t\t\t20180425035439_bxx108C44"},{"key":"key\n\t\t\t\t20180425035439_bxx108C45","doi-asserted-by":"crossref","first-page":"3181","DOI":"10.1093\/bioinformatics\/btx067","article-title":"Succinct colored de Bruijn graphs","volume":"33","author":"Muggli","year":"2017","journal-title":"Bioinformatics"},{"year":"2017","author":"Alipanahi","key":"key\n\t\t\t\t20180425035439_bxx108C46"},{"year":"2017","author":"Almodaresi","key":"key\n\t\t\t\t20180425035439_bxx108C47"},{"year":"2012","author":"Bowe","key":"key\n\t\t\t\t20180425035439_bxx108C48"},{"key":"key\n\t\t\t\t20180425035439_bxx108C49","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1038\/ng.1028","article-title":"De novo assembly and genotyping of variants using colored de Bruijn graphs","volume":"44","author":"Iqbal","year":"2012","journal-title":"Nat. Genet."},{"key":"key\n\t\t\t\t20180425035439_bxx108C50","doi-asserted-by":"crossref","first-page":"1149","DOI":"10.1002\/(SICI)1097-024X(199911)29:13<1149::AID-SPE274>3.0.CO;2-O","article-title":"Reducing the space requirement of suffix trees","volume":"29","author":"Kurtz","year":"1999","journal-title":"Softw. Pract. Exp."},{"key":"key\n\t\t\t\t20180425035439_bxx108C51","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/S1570-8667(03)00065-0","article-title":"Replacing suffix trees with enhanced suffix arrays","volume":"2","author":"Abouelhoda","year":"2004","journal-title":"J. Discrete Algorithms"},{"year":"2003","author":"Grossi","key":"key\n\t\t\t\t20180425035439_bxx108C52"},{"year":"1994","author":"Burrows","key":"key\n\t\t\t\t20180425035439_bxx108C53"},{"key":"key\n\t\t\t\t20180425035439_bxx108C54","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1016\/S0196-6774(03)00087-7","article-title":"New text indexing functionalities of the compressed suffix arrays","volume":"48","author":"Sadakane","year":"2003","journal-title":"J. Algorithms"},{"key":"key\n\t\t\t\t20180425035439_bxx108C55","doi-asserted-by":"crossref","first-page":"552","DOI":"10.1145\/1082036.1082039","article-title":"Indexing compressed text","volume":"52","author":"Ferragina","year":"2005","journal-title":"J. ACM"},{"key":"key\n\t\t\t\t20180425035439_bxx108C56","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1137\/S0097539702402354","article-title":"Compressed suffix arrays and suffix trees with applications to text indexing and string matching","volume":"35","author":"Grossi","year":"2005","journal-title":"SIAM J. Comput."},{"key":"key\n\t\t\t\t20180425035439_bxx108C57","doi-asserted-by":"crossref","first-page":"article 1.12","DOI":"10.1145\/1412228.1455268","article-title":"Compressed text indexes: from theory to practice","volume":"13","author":"Ferragina","year":"2009","journal-title":"ACM J. Exp. Algorithmics"},{"key":"key\n\t\t\t\t20180425035439_bxx108C58","doi-asserted-by":"crossref","first-page":"article20","DOI":"10.1145\/1240233.1240243","article-title":"Compressed representations of sequences and full-text indexes","volume":"3","author":"Ferragina","year":"2007","journal-title":"ACM Trans. Algorithms"},{"key":"key\n\t\t\t\t20180425035439_bxx108C59","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1016\/j.ipm.2012.08.003","article-title":"DACs: bringing direct access to variable-length codes","volume":"49","author":"Brisaboa","year":"2013","journal-title":"Inf. Process. Manage."},{"year":"2007","author":"Okanohara","key":"key\n\t\t\t\t20180425035439_bxx108C60"},{"year":"2016","author":"Cox","key":"key\n\t\t\t\t20180425035439_bxx108C61"},{"key":"key\n\t\t\t\t20180425035439_bxx108C62","doi-asserted-by":"crossref","first-page":"article 43","DOI":"10.1145\/1290672.1290680","article-title":"Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets","volume":"3","author":"Raman","year":"2007","journal-title":"ACM Trans. Algorithms"},{"year":"2015","author":"Boucher","key":"key\n\t\t\t\t20180425035439_bxx108C63"},{"year":"2009","author":"Sir\u00e9n","key":"key\n\t\t\t\t20180425035439_bxx108C64"},{"year":"2014","author":"Gog","key":"key\n\t\t\t\t20180425035439_bxx108C65"},{"key":"key\n\t\t\t\t20180425035439_bxx108C66","first-page":"40","article-title":"Succinct suffix arrays based on run-length encoding","volume":"12","author":"M\u00e4kinen","year":"2005","journal-title":"Nordic J. Comput."},{"key":"key\n\t\t\t\t20180425035439_bxx108C67","doi-asserted-by":"crossref","first-page":"article522","DOI":"10.1038\/msb.2011.54","article-title":"AlleleSeq: analysis of allele-specific expression and binding in a network framework","volume":"7","author":"Rozowsky","year":"2011","journal-title":"Mol. Syst. Biol."},{"key":"key\n\t\t\t\t20180425035439_bxx108C68","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1007\/BF01185431","article-title":"Sublinear approximate string matching and biological applications","volume":"12","author":"Chang","year":"1994","journal-title":"Algorithmica"},{"year":"2010","author":"Ohlebusch","key":"key\n\t\t\t\t20180425035439_bxx108C69"}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/academic.oup.com\/comjnl\/article-pdf\/61\/5\/773\/24724637\/bxx108.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,20]],"date-time":"2020-10-20T08:58:44Z","timestamp":1603184324000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/61\/5\/773\/4643569"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,11,21]]},"references-count":69,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2017,11,21]]},"published-print":{"date-parts":[[2018,5,1]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxx108","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"type":"print","value":"0010-4620"},{"type":"electronic","value":"1460-2067"}],"subject":[],"published-other":{"date-parts":[[2018,5]]},"published":{"date-parts":[[2017,11,21]]}}}