{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,18]],"date-time":"2026-06-18T10:51:30Z","timestamp":1781779890416,"version":"3.54.5"},"reference-count":19,"publisher":"Oxford University Press (OUP)","issue":"3","license":[{"start":{"date-parts":[[2019,8,22]],"date-time":"2019-08-22T00:00:00Z","timestamp":1566432000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"name":"NSF","award":["DBI-1356529"],"award-info":[{"award-number":["DBI-1356529"]}]},{"name":"NSF","award":["CCF-551439057"],"award-info":[{"award-number":["CCF-551439057"]}]},{"name":"NSF","award":["IIS-1453527"],"award-info":[{"award-number":["IIS-1453527"]}]},{"DOI":"10.13039\/100000002","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["R01GM130691"],"award-info":[{"award-number":["R01GM130691"]}],"id":[{"id":"10.13039\/100000002","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020,2,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>Algorithmic solutions to index and search biological databases are a fundamental part of bioinformatics, providing underlying components to many end-user tools. Inexpensive next generation sequencing has filled publicly available databases such as the Sequence Read Archive beyond the capacity of traditional indexing methods. Recently, the Sequence Bloom Tree (SBT) and its derivatives were proposed as a way to efficiently index such data for queries about transcript presence.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>We build on the SBT framework to construct the HowDe-SBT data structure, which uses a novel partitioning of information to reduce the construction and query time as well as the size of the index. Compared to previous SBT methods, on real RNA-seq data, HowDe-SBT can construct the index in less than 36% of the time and with 39% less space and can answer small-batch queries at least five times faster. We also develop a theoretical framework in which we can analyze and bound the space and query performance of HowDe-SBT compared to other SBT methods.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability and implementation<\/jats:title>\n                    <jats:p>HowDe-SBT is available as a free open source program on https:\/\/github.com\/medvedevgroup\/HowDeSBT.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Supplementary information<\/jats:title>\n                    <jats:p>Supplementary data are available at Bioinformatics online.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1093\/bioinformatics\/btz662","type":"journal-article","created":{"date-parts":[[2019,8,20]],"date-time":"2019-08-20T15:16:59Z","timestamp":1566314219000},"page":"721-727","source":"Crossref","is-referenced-by-count":47,"title":["Improved representation of sequence bloom trees"],"prefix":"10.1093","volume":"36","author":[{"given":"Robert S","family":"Harris","sequence":"first","affiliation":[{"name":"Department of Biology , PA 16801, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paul","family":"Medvedev","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering , PA 16801, USA"},{"name":"Department of Biochemistry and Molecular Biology , PA 16801, USA"},{"name":"Center for Computational Biology and Bioinformatics, The Pennsylvania State University , University Park, PA 16801, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"286","published-online":{"date-parts":[[2019,8,22]]},"reference":[{"key":"2023013110074785200_btz662-B1","author":"Almodaresi","year":"2017"},{"key":"2023013110074785200_btz662-B2","first-page":"464222","author":"Almodaresi","year":"2018"},{"key":"2023013110074785200_btz662-B3","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1145\/362686.362692","article-title":"Space\/time trade-offs in hash coding with allowable errors","volume":"13","author":"Bloom","year":"1970","journal-title":"Commun. ACM"},{"key":"2023013110074785200_btz662-B4","author":"Bradley","year":"2017"},{"key":"2023013110074785200_btz662-B5","doi-asserted-by":"crossref","first-page":"421.","DOI":"10.1186\/1471-2105-10-421","article-title":"BLAST+: architecture and applications","volume":"10","author":"Camacho","year":"2009","journal-title":"BMC Bioinformatics"},{"key":"2023013110074785200_btz662-B6","doi-asserted-by":"crossref","first-page":"311","DOI":"10.1016\/j.is.2015.01.002","article-title":"Bloofi: multidimensional Bloom filters","volume":"54","author":"Crainiceanu","year":"2015","journal-title":"Inform. Syst"},{"key":"2023013110074785200_btz662-B7","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"},{"key":"2023013110074785200_btz662-B8","author":"Holley","year":"2019"},{"key":"2023013110074785200_btz662-B9","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/978-3-662-48221-6_16","volume-title":"International Workshop on Algorithms in Bioinformatics","author":"Holley","year":"2015"},{"key":"2023013110074785200_btz662-B10","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139940023","volume-title":"Genome-Scale Algorithm Design","author":"M\u00e4kinen","year":"2015"},{"key":"2023013110074785200_btz662-B11","doi-asserted-by":"crossref","first-page":"764","DOI":"10.1093\/bioinformatics\/btr011","article-title":"A fast, lock-free approach for efficient parallel counting of occurrences of k-mers","volume":"27","author":"Mar\u00e7ais","year":"2011","journal-title":"Bioinformatics"},{"key":"2023013110074785200_btz662-B12","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":"2023013110074785200_btz662-B13","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1093\/bioinformatics\/bty632","article-title":"Dynamic compression schemes for graph coloring","volume":"35","author":"Mustafa","year":"2018","journal-title":"Bioinformatics"},{"key":"2023013110074785200_btz662-B14","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":"2023013110074785200_btz662-B15","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. Algorithms (TALG)"},{"key":"2023013110074785200_btz662-B16","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":"2023013110074785200_btz662-B17","first-page":"257","volume-title":"International Conference on Research in Computational Molecular Biology","author":"Solomon","year":"2017"},{"key":"2023013110074785200_btz662-B18","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1089\/cmb.2017.0258","article-title":"AllSome sequence bloom trees","volume":"25","author":"Sun","year":"2018","journal-title":"J. Comput. Biol"},{"key":"2023013110074785200_btz662-B19","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":"http:\/\/academic.oup.com\/bioinformatics\/advance-article-pdf\/doi\/10.1093\/bioinformatics\/btz662\/29203234\/btz662.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/36\/3\/721\/48981496\/btz662.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/36\/3\/721\/48981496\/btz662.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T14:33:13Z","timestamp":1675175593000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/36\/3\/721\/5553093"}},"subtitle":[],"editor":[{"given":"Inanc","family":"Birol","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[2019,8,22]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,2,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/btz662","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/501452","asserted-by":"object"}]},"ISSN":["1367-4803","1367-4811"],"issn-type":[{"value":"1367-4803","type":"print"},{"value":"1367-4811","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2020,2,1]]},"published":{"date-parts":[[2019,8,22]]}}}