{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:55:25Z","timestamp":1775638525900,"version":"3.50.1"},"reference-count":31,"publisher":"Oxford University Press (OUP)","issue":"12","license":[{"start":{"date-parts":[[2022,3,23]],"date-time":"2022-03-23T00:00:00Z","timestamp":1647993600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/100000002","name":"NIH","doi-asserted-by":"publisher","award":["R01 HG009937"],"award-info":[{"award-number":["R01 HG009937"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1750472"],"award-info":[{"award-number":["CCF-1750472"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["NSF CCF-1452904"],"award-info":[{"award-number":["NSF CCF-1452904"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["NSF CNS-1763680"],"award-info":[{"award-number":["NSF CNS-1763680"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Applied Mathematics Program of the DOE Office of Advanced Scientific Computing Research","award":["DE-AC02-05CH11231"],"award-info":[{"award-number":["DE-AC02-05CH11231"]}]},{"name":"Exascale Computing Project","award":["17-SC-20-SC"],"award-info":[{"award-number":["17-SC-20-SC"]}]},{"name":"U.S. Department of Energy Office of Science and the National Nuclear Security Administration"},{"name":"NSF CISE Research Infrastructure","award":["1405641"],"award-info":[{"award-number":["1405641"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,6,13]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:sec><jats:title>Motivation<\/jats:title><jats:p>In the past few years, researchers have proposed numerous indexing schemes for searching large datasets of raw sequencing experiments. Most of these proposed indexes are approximate (i.e. with one-sided errors) in order to save space. Recently, researchers have published exact indexes\u2014Mantis, VariMerge and Bifrost\u2014that can serve as colored de Bruijn graph representations in addition to serving as k-mer indexes. This new type of index is promising because it has the potential to support more complex analyses than simple searches. However, in order to be useful as indexes for large and growing repositories of raw sequencing data, they must scale to thousands of experiments and support efficient insertion of new data.<\/jats:p><\/jats:sec><jats:sec><jats:title>Results<\/jats:title><jats:p>In this paper, we show how to build a scalable and updatable exact raw sequence-search index. Specifically, we extend Mantis using the Bentley\u2013Saxe transformation to support efficient updates, called Dynamic Mantis. We demonstrate Dynamic Mantis\u2019s scalability by constructing an index of \u224840K samples from SRA by adding samples one at a time to an initial index of 10K samples. Compared to VariMerge and Bifrost, Dynamic Mantis is more efficient in terms of index-construction time and memory, query time and memory and index size. In our benchmarks, VariMerge and Bifrost scaled to only 5K and 80 samples, respectively, while Dynamic Mantis scaled to more than 39K samples. Queries were over 24\u00d7 faster in Mantis than in Bifrost (VariMerge does not immediately support general search queries we require). Dynamic Mantis indexes were about 2.5\u00d7 smaller than Bifrost\u2019s indexes and about half as big as VariMerge\u2019s indexes.<\/jats:p><\/jats:sec><jats:sec><jats:title>Availability and implementation<\/jats:title><jats:p>Dynamic Mantis implementation is available at https:\/\/github.com\/splatlab\/mantis\/tree\/mergeMSTs.<\/jats:p><\/jats:sec><jats:sec><jats:title>Supplementary information<\/jats:title><jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p><\/jats:sec>","DOI":"10.1093\/bioinformatics\/btac142","type":"journal-article","created":{"date-parts":[[2022,3,22]],"date-time":"2022-03-22T20:11:48Z","timestamp":1647979908000},"page":"3155-3163","source":"Crossref","is-referenced-by-count":11,"title":["An incrementally updatable and scalable system for large-scale sequence search using the Bentley\u2013Saxe transformation"],"prefix":"10.1093","volume":"38","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0993-3600","authenticated-orcid":false,"given":"Fatemeh","family":"Almodaresi","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Maryland , USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5129-9749","authenticated-orcid":false,"given":"Jamshed","family":"Khan","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Maryland , USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sergey","family":"Madaminov","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Stony Brook University , USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Ferdman","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Stony Brook University , USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rob","family":"Johnson","sequence":"additional","affiliation":[{"name":"VMware Research, Palo Alto, CA 94301, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Prashant","family":"Pandey","sequence":"additional","affiliation":[{"name":"VMware Research, Palo Alto, CA 94301, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8463-1675","authenticated-orcid":false,"given":"Rob","family":"Patro","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Maryland , USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2022,3,23]]},"reference":[{"key":"2023041605542339400_","author":"Almodaresi","year":"2017"},{"key":"2023041605542339400_","first-page":"1","author":"Almodaresi","year":"2019"},{"key":"2023041605542339400_","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1089\/cmb.2019.0322","article-title":"An efficient, scalable, and exact representation of high-dimensional color information enabled using de Bruijn graph search","volume":"27","author":"Almodaresi","year":"2020","journal-title":"J. Comput. Biol"},{"key":"2023041605542339400_","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1016\/0196-6774(80)90015-2","article-title":"Decomposable searching problems I. Static-to-dynamic transformation","volume":"1","author":"Bentley","year":"1980","journal-title":"J. Algor"},{"key":"2023041605542339400_","first-page":"285","author":"Bingmann","year":"2019"},{"key":"2023041605542339400_","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1038\/s41587-018-0010-1","article-title":"Ultrafast search of all deposited bacterial and viral genomic data","volume":"37","author":"Bradley","year":"2019","journal-title":"Nat. Biotechnol"},{"key":"2023041605542339400_","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1365815.1365816","article-title":"Bigtable: a distributed storage system for structured data","volume":"26","author":"Chang","year":"2008","journal-title":"ACM Trans. Comput. Syst"},{"key":"2023041605542339400_","doi-asserted-by":"crossref","first-page":"i201","DOI":"10.1093\/bioinformatics\/btw279","article-title":"Compacting de Bruijn graphs from sequencing data quickly and in low memory","volume":"32","author":"Chikhi","year":"2016","journal-title":"Bioinformatics"},{"key":"2023041605542339400_","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1093\/bioinformatics\/btz662","article-title":"Improved representation of sequence bloom trees","volume":"36","author":"Harris","year":"2020","journal-title":"Bioinformatics"},{"key":"2023041605542339400_","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1186\/s13059-020-02135-8","article-title":"Bifrost: highly parallel construction and indexing of colored and compacted de Bruijn graphs","volume":"21","author":"Holley","year":"2020","journal-title":"Genome Biol"},{"key":"2023041605542339400_","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":"2023041605542339400_","doi-asserted-by":"crossref","first-page":"D54","DOI":"10.1093\/nar\/gkr854","article-title":"The sequence read archive: explosive growth of sequencing data","volume":"40","author":"Kodama","year":"2012","journal-title":"Nucleic Acids Res"},{"key":"2023041605542339400_","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1145\/1773912.1773922","article-title":"Cassandra: a decentralized structured storage system","volume":"44","author":"Lakshman","year":"2010","journal-title":"ACM SIGOPS Oper. Syst. Rev"},{"key":"2023041605542339400_","doi-asserted-by":"crossref","first-page":"D19","DOI":"10.1093\/nar\/gkq1019","article-title":"The sequence read archive","volume":"39","author":"Leinonen","year":"2010","journal-title":"Nucleic Acids Res"},{"key":"2023041605542339400_","author":"Limasset","year":"2017"},{"key":"2023041605542339400_","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1101\/gr.260604.119","article-title":"Data structures based on k-mers for querying large collections of sequencing data sets","volume":"31","author":"Marchet","year":"2021","journal-title":"Genome Res"},{"key":"2023041605542339400_","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"},{"key":"2023041605542339400_","doi-asserted-by":"crossref","first-page":"i51","DOI":"10.1093\/bioinformatics\/btz350","article-title":"Building large updatable colored de Bruijn graphs via merging","volume":"35","author":"Muggli","year":"2019","journal-title":"Bioinformatics"},{"key":"2023041605542339400_","year":"2020"},{"key":"2023041605542339400_","doi-asserted-by":"crossref","first-page":"D733","DOI":"10.1093\/nar\/gkv1189","article-title":"Reference sequence (refseq) database at NCBI: current status, taxonomic expansion, and functional annotation","volume":"44","author":"O\u2019Leary","year":"2016","journal-title":"Nucleic Acids Res"},{"key":"2023041605542339400_","doi-asserted-by":"crossref","first-page":"i133","DOI":"10.1093\/bioinformatics\/btx261","article-title":"deBGR: an efficient and near-exact representation of the weighted de Bruijn graph","volume":"33","author":"Pandey","year":"2017","journal-title":"Bioinformatics"},{"key":"2023041605542339400_","first-page":"775","author":"Pandey","year":"2017"},{"key":"2023041605542339400_","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1093\/bioinformatics\/btx636","article-title":"Squeakr: an exact and approximate k-mer counting system","volume":"34","author":"Pandey","year":"2017","journal-title":"Bioinformatics"},{"key":"2023041605542339400_","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/j.cels.2018.05.021","article-title":"Mantis: a fast, small, and exact large-scale sequence-search index","volume":"7","author":"Pandey","year":"2018","journal-title":"Cell Syst"},{"key":"2023041605542339400_","doi-asserted-by":"crossref","first-page":"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. Algor"},{"key":"2023041605542339400_","doi-asserted-by":"crossref","first-page":"3363","DOI":"10.1093\/bioinformatics\/bth408","article-title":"Reducing storage requirements for biological sequence comparison","volume":"20","author":"Roberts","year":"2004","journal-title":"Bioinformatics"},{"key":"2023041605542339400_","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1038\/nbt.3442","article-title":"Fast search of thousands of short-read sequencing experiments","volume":"34","author":"Solomon","year":"2016","journal-title":"Nat. Biotechnol"},{"key":"2023041605542339400_","first-page":"257","author":"Solomon","year":"2017"},{"key":"2023041605542339400_","first-page":"272","author":"Sun","year":"2017"},{"key":"2023041605542339400_","first-page":"601","author":"Vora","year":"2011"},{"key":"2023041605542339400_","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1186\/s13059-018-1535-9","article-title":"Seqothello: querying RNA-seq experiments at scale","volume":"19","author":"Yu","year":"2018","journal-title":"Genome Biol"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btac142\/43055792\/btac142.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/38\/12\/3155\/49885663\/btac142.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/38\/12\/3155\/49885663\/btac142.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,19]],"date-time":"2023-11-19T04:44:28Z","timestamp":1700369068000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/38\/12\/3155\/6553005"}},"subtitle":[],"editor":[{"given":"Valentina","family":"Boeva","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2022,3,23]]},"references-count":31,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2022,6,13]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btac142","relation":{},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2022,6,15]]},"published":{"date-parts":[[2022,3,23]]}}}