{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T18:40:13Z","timestamp":1772908813062,"version":"3.50.1"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"13","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2013,8,29]]},"abstract":"<jats:p>Until recently, genomics has concentrated on comparing sequences between species. However, due to the sharply falling cost of sequencing technology, studies of populations of individuals of the same species are now feasible and promise advances in areas such as personalized medicine and treatment of genetic diseases. A core operation in such studies is read mapping, i.e., finding all parts of a set of genomes which are within edit distance<jats:italic>k<\/jats:italic>to a given query sequence (<jats:italic>k<\/jats:italic>-approximate search). To achieve sufficient speed, current algorithms solve this problem only for one to-be-searched genome and compute only approximate solutions, i.e., they miss some<jats:italic>k<\/jats:italic>- approximate occurrences.<\/jats:p><jats:p>We present RCSI, Referentially Compressed Search Index, which scales to a thousand genomes and computes the exact answer. It exploits the fact that genomes of different individuals of the same species are highly similar by first compressing the to-be-searched genomes with respect to a reference genome. Given a query, RCSI then searches the reference and all genome-specific individual differences. We propose efficient data structures for representing compressed genomes and present algorithms for scalable compression and similarity search. We evaluate our algorithms on a set of 1092 human genomes, which amount to approx. 3 TB of raw data. RCSI compresses this set by a ratio of 450:1 (26:1 including the search index) and answers similarity queries on a mid-class server in 15 ms on average even for comparably large error thresholds, thereby significantly outperforming other methods. Furthermore, we present a fast and adaptive heuristic for choosing the best reference sequence for referential compression, a problem that was never studied before at this scale.<\/jats:p>","DOI":"10.14778\/2536258.2536265","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"1534-1545","source":"Crossref","is-referenced-by-count":31,"title":["RCSI"],"prefix":"10.14778","volume":"6","author":[{"given":"Sebastian","family":"Wandelt","sequence":"first","affiliation":[{"name":"Humboldt-Universit\u00e4t zu Berlin, Wissensmanagement in der Bioinformatik, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Johannes","family":"Starlinger","sequence":"additional","affiliation":[{"name":"Humboldt-Universit\u00e4t zu Berlin, Wissensmanagement in der Bioinformatik, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marc","family":"Bux","sequence":"additional","affiliation":[{"name":"Humboldt-Universit\u00e4t zu Berlin, Wissensmanagement in der Bioinformatik, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ulf","family":"Leser","sequence":"additional","affiliation":[{"name":"Humboldt-Universit\u00e4t zu Berlin, Wissensmanagement in der Bioinformatik, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,8]]},"reference":[{"issue":"7422","key":"e_1_2_1_1_1","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1038\/nature11632","article-title":"integrated map of genetic variation from 1,092 human genomes","volume":"491","year":"2012","journal-title":"Nature"},{"issue":"7319","key":"e_1_2_1_2_1","doi-asserted-by":"crossref","first-page":"1061","DOI":"10.1038\/nature09534","article-title":"A map of human genome variation from population-scale sequencing","volume":"467","author":"1000 Genomes Project Consortium","year":"2010","journal-title":"Nature"},{"issue":"3","key":"e_1_2_1_3_1","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","article-title":"Basic local alignment search tool","volume":"215","author":"Altschul S. F.","year":"1990","journal-title":"Journal of Molecular Biology"},{"issue":"1","key":"e_1_2_1_4_1","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/0020-0190(96)00083-X","article-title":"Fast and practical approximate string matching","volume":"59","author":"Baeza-Yates R. A.","year":"1996","journal-title":"Information Processing Letters"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"S. Bao R. Jiang W. Kwan B. Wang X. Ma and Y. Song. Evaluation of next-generation sequencing software in mapping and assembly. Journal of human genetics 56(6):406-414 2011. S. Bao R. Jiang W. Kwan B. Wang X. Ma and Y. Song. Evaluation of next-generation sequencing software in mapping and assembly. Journal of human genetics 56(6):406-414 2011.","DOI":"10.1038\/jhg.2011.43"},{"issue":"2","key":"e_1_2_1_6_1","first-page":"274","article-title":"Human genomes as email attachments. Bioinformatics (Oxford","volume":"25","author":"Christley S.","year":"2009","journal-title":"England)"},{"key":"e_1_2_1_7_1","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1145\/1007352.1007374","volume-title":"Proceedings of STOC","author":"Cole R.","year":"2004"},{"issue":"6822","key":"e_1_2_1_8_1","doi-asserted-by":"crossref","first-page":"860","DOI":"10.1038\/35057062","article-title":"Initial sequencing and analysis of the human genome","volume":"409","author":"I. H. G. S. Consortium","year":"2001","journal-title":"Nature"},{"issue":"7291","key":"e_1_2_1_9_1","doi-asserted-by":"crossref","first-page":"993","DOI":"10.1038\/nature08987","article-title":"International network of cancer genome projects","volume":"464","author":"Consortium ICG","year":"2010","journal-title":"Nature"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"P. Danecek A. Auton G. Abecasis and 1000 Genomes Project Analysis Group. The variant call format and VCFtools. Bioinformatics (Oxford England) 27(15):2156-2158 Aug. 2011. P. Danecek A. Auton G. Abecasis and 1000 Genomes Project Analysis Group. The variant call format and VCFtools. Bioinformatics (Oxford England) 27(15):2156-2158 Aug. 2011.","DOI":"10.1093\/bioinformatics\/btr330"},{"issue":"12","key":"e_1_2_1_11_1","doi-asserted-by":"crossref","first-page":"e1002384","DOI":"10.1371\/journal.pgen.1002384","article-title":"Repetitive elements may comprise over two-thirds of the human genome","volume":"7","author":"de Koning A. P. J.","year":"2011","journal-title":"PLoS Genetics"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"S. Deorowicz and S. Grabowski. Robust Relative Compression of Genomes with Random Access. Bioinformatics (Oxford England) Sept. 2011. S. Deorowicz and S. Grabowski. Robust Relative Compression of Genomes with Random Access. Bioinformatics (Oxford England) Sept. 2011.","DOI":"10.1093\/bioinformatics\/btr505"},{"key":"e_1_2_1_13_1","first-page":"291","volume-title":"Proceedings of FAW-AAIM 2012","volume":"7285","author":"Do H. H.","year":"2012"},{"key":"e_1_2_1_14_1","unstructured":"P. Ferragina. String algorithms and data structures. CoRR abs\/0801.2378 2008. P. Ferragina. String algorithms and data structures. CoRR abs\/0801.2378 2008."},{"key":"e_1_2_1_15_1","first-page":"152","volume-title":"Proceedings of 19th Annual Symposium on Combinatorial Pattern Matching (CPM), LNCS 5029","author":"Fischer J.","year":"2008"},{"key":"e_1_2_1_16_1","first-page":"240","volume-title":"LATA-12","author":"Gagie T.","year":"2012"},{"key":"e_1_2_1_17_1","first-page":"81","volume-title":"Proceedings of SIGKDD","author":"Ge X.","year":"2000"},{"key":"e_1_2_1_18_1","volume-title":"Cambridge University Press","author":"Goldberg L. A.","year":"2009"},{"key":"e_1_2_1_19_1","volume-title":"Cambridge University Press","author":"Gusfield D.","year":"1997"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"O. Harismendy P. Ng etal Evaluation of next generation sequencing platforms for population targeted sequencing studies. Genome Biology 10(3):R32+ 2009. O. Harismendy P. Ng et al. Evaluation of next generation sequencing platforms for population targeted sequencing studies. Genome Biology 10(3):R32+ 2009.","DOI":"10.1186\/gb-2009-10-3-r32"},{"issue":"4","key":"e_1_2_1_21_1","first-page":"656","volume":"12","author":"W","year":"2002","journal-title":"J. Kent. BLAT-The BLAST-Like Alignment Tool. Genome Research"},{"issue":"6","key":"e_1_2_1_22_1","doi-asserted-by":"crossref","first-page":"996","DOI":"10.1101\/gr.229102","article-title":"The human genome browser at UCSC","volume":"12","author":"Kent W. J.","year":"2002","journal-title":"Genome Research"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of ICDE","author":"Kim Y.","year":"2010"},{"key":"e_1_2_1_24_1","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 S.","year":"2013","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"e_1_2_1_25_1","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1038\/nmeth.1923","article-title":"Fast gapped-read alignment with bowtie 2","volume":"9","author":"Langmead B.","year":"2012","journal-title":"Nat Meth"},{"issue":"3","key":"e_1_2_1_26_1","doi-asserted-by":"crossref","first-page":"R25","DOI":"10.1186\/gb-2009-10-3-r25","article-title":"Ultrafast and memory-efficient alignment of short DNA sequences to the human genome","volume":"10","author":"Langmead B.","year":"2009","journal-title":"Genome Biology"},{"issue":"14","key":"e_1_2_1_27_1","first-page":"1754","article-title":"Fast and accurate short read alignment with burrows-wheeler transform. Bioinformatics (Oxford","volume":"25","author":"Li H.","year":"2009","journal-title":"England)"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of Data","author":"Li Y.","year":"2011"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1145\/2213836.2213868","volume-title":"Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data","author":"Li Z.","year":"2012"},{"issue":"7","key":"e_1_2_1_30_1","doi-asserted-by":"crossref","first-page":"627","DOI":"10.1038\/nbt.2241","article-title":"Compressive genomics","volume":"30","author":"Loh P.-R.","year":"2012","journal-title":"Nature Biotechnology"},{"issue":"5","key":"e_1_2_1_31_1","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 U.","year":"1993","journal-title":"SIAM J. Comput."},{"issue":"1","key":"e_1_2_1_32_1","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/375360.375365","article-title":"A guided tour to approximate string matching","volume":"33","author":"Navarro G.","year":"2001","journal-title":"ACM Computing Surveys"},{"key":"e_1_2_1_33_1","first-page":"274","volume-title":"Proceedings 23rd International Workshop on Combinatorial Algorithms (IWOCA), LNCS 7643","author":"Navarro G.","year":"2012"},{"key":"e_1_2_1_34_1","volume-title":"Cambridge University Press","author":"Navarro G.","year":"2002"},{"key":"e_1_2_1_35_1","first-page":"322","volume-title":"SPIRE-10","author":"Ohlebusch E.","year":"2010"},{"issue":"1","key":"e_1_2_1_36_1","doi-asserted-by":"crossref","first-page":"205","DOI":"10.14778\/1687627.1687651","article-title":"Reference-based alignment in large sequence databases","volume":"2","author":"Papapetrou P.","year":"2009","journal-title":"Proceedings of the VLDB Endowment"},{"issue":"6018","key":"e_1_2_1_37_1","doi-asserted-by":"crossref","first-page":"666","DOI":"10.1126\/science.331.6018.666","article-title":"Will Computers Crash Genomics?","volume":"331","author":"Pennisi E.","year":"2011","journal-title":"Science"},{"issue":"1","key":"e_1_2_1_38_1","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1038\/ng947","article-title":"Human genome sequence variation and the influence of gene history, mutation and recombination","volume":"32","author":"Reich D. E.","year":"2002","journal-title":"Nature Genetics"},{"key":"e_1_2_1_39_1","first-page":"519","volume-title":"Proceedings of the 22nd SSDBM","author":"Rheinl\u00e4nder A.","year":"2010"},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","unstructured":"E. E. Schadt S. Turner and A. Kasarskis. A window into third-generation sequencing. Human molecular genetics 19(R2):R227-R240 Oct. 2010. E. E. Schadt S. Turner and A. Kasarskis. A window into third-generation sequencing. Human molecular genetics 19(R2):R227-R240 Oct. 2010.","DOI":"10.1093\/hmg\/ddq416"},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","unstructured":"K. Schneeberger J. Hagmann S. Ossowski N. Warthmann S. Gesing O. Kohlbacher and D. Weigel. Simultaneous alignment of short reads against multiple genomes. Genome biology 10(9):R98+ Sept. 2009. K. Schneeberger J. Hagmann S. Ossowski N. Warthmann S. Gesing O. Kohlbacher and D. Weigel. Simultaneous alignment of short reads against multiple genomes. Genome biology 10(9):R98+ Sept. 2009.","DOI":"10.1186\/gb-2009-10-9-r98"},{"key":"e_1_2_1_42_1","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1007\/978-3-642-23038-7_23","volume-title":"Proceedings of the 11th international conference on Algorithms in bioinformatics, WABI-11","author":"Sir\u00e9n J.","year":"2011"},{"key":"e_1_2_1_43_1","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1007\/3-540-60313-1_153","volume-title":"Proceedings of the Third Annual European Symposium on Algorithms, ESA -95","author":"Sutinen E.","year":"1995"},{"key":"e_1_2_1_44_1","first-page":"14","article-title":"Engineering a compressed suffix tree implementation","author":"Vaelimaeki N.","year":"2009","journal-title":"ACM Journal of Experimental Algorithmics"},{"key":"e_1_2_1_45_1","doi-asserted-by":"crossref","first-page":"30","DOI":"10.1186\/1748-7188-7-30","article-title":"Adaptive efficient compression of genomes","volume":"7","author":"Wandelt S.","year":"2012","journal-title":"Algorithms for Molecular Biology"},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the 4th Int. Conf. on Knowledge Discovery and Information Retrieval","author":"Wandelt S.","year":"2012"},{"key":"e_1_2_1_47_1","first-page":"85","volume-title":"SIGMOD Conference","author":"Wang J.","year":"2012"},{"key":"e_1_2_1_48_1","doi-asserted-by":"crossref","first-page":"759","DOI":"10.1145\/1559845.1559925","volume-title":"Proceedings of the ACM SIGMOD International Conference on Management of data","author":"Wang W.","year":"2009"},{"key":"e_1_2_1_49_1","volume-title":"Proceedings of the IEEE International Conference on Data Engineering (ICDE), Australia (to appear; preprint at http:\/\/www.ics.uci.edu\/xhx\/publications\/genomecompress.pdf).","author":"Yang X."},{"issue":"11","key":"e_1_2_1_50_1","doi-asserted-by":"crossref","first-page":"1579","DOI":"10.14778\/2350229.2350271","article-title":"A generic framework for efficient and effective subsequence retrieval","volume":"5","author":"Zhu H.","year":"2012","journal-title":"Proceedings VLDB Endow."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2536258.2536265","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,14]],"date-time":"2023-07-14T14:44:33Z","timestamp":1689345873000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2536258.2536265"}},"subtitle":["scalable similarity search in thousand(s) of genomes"],"short-title":[],"issued":{"date-parts":[[2013,8]]},"references-count":50,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2013,8,29]]}},"alternative-id":["10.14778\/2536258.2536265"],"URL":"https:\/\/doi.org\/10.14778\/2536258.2536265","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2013,8]]}}}