{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T00:36:21Z","timestamp":1774312581101,"version":"3.50.1"},"reference-count":24,"publisher":"Oxford University Press (OUP)","issue":"17","license":[{"start":{"date-parts":[[2018,9,1]],"date-time":"2018-09-01T00:00:00Z","timestamp":1535760000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/about_us\/legal\/notices"}],"funder":[{"name":"Coordena\u00e7\u00e3o de Aperfei-\u00e7oamento de Pessoal de N\u00edvel Superior"},{"DOI":"10.13039\/501100002322","name":"CAPES","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100017564","name":"Ci\u00eancia sem Fronteiras","doi-asserted-by":"crossref","award":["BEX 13472\/13-5"],"award-info":[{"award-number":["BEX 13472\/13-5"]}],"id":[{"id":"10.13039\/501100017564","id-type":"DOI","asserted-by":"crossref"}]},{"name":"InfectControl 2020 Project"},{"DOI":"10.13039\/501100003107","name":"BMG","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003107","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Metagenome Analysis Tool","award":["2515NIK043"],"award-info":[{"award-number":["2515NIK043"]}]},{"name":"IMPRS for Scientific Computing and Computational Biology"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018,9,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Motivation<\/jats:title>\n                    <jats:p>Mapping-based approaches have become limited in their application to very large sets of references since computing an FM-index for very large databases (e.g. &amp;gt;10 GB) has become a bottleneck. This affects many analyses that need such index as an essential step for approximate matching of the NGS reads to reference databases. For instance, in typical metagenomics analysis, the size of the reference sequences has become prohibitive to compute a single full-text index on standard machines. Even on large memory machines, computing such index takes about 1 day of computing time. As a result, updates of indices are rarely performed. Hence, it is desirable to create an alternative way of indexing while preserving fast search times.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>To solve the index construction and update problem we propose the DREAM (Dynamic seaRchablE pArallel coMpressed index) framework and provide an implementation. The main contributions are the introduction of an approximate search distributor via a novel use of Bloom filters. We combine several Bloom filters to form an interleaved Bloom filter and use this new data structure to quickly exclude reads for parts of the databases where they cannot match. This allows us to keep the databases in several indices which can be easily rebuilt if parts are updated while maintaining a fast search time. The second main contribution is an implementation of DREAM-Yara a distributed version of a fully sensitive read mapper under the DREAM framework.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Availability and implementation<\/jats:title>\n                    <jats:p>https:\/\/gitlab.com\/pirovc\/dream_yara\/<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1093\/bioinformatics\/bty567","type":"journal-article","created":{"date-parts":[[2018,7,5]],"date-time":"2018-07-05T21:20:56Z","timestamp":1530825656000},"page":"i766-i772","source":"Crossref","is-referenced-by-count":36,"title":["DREAM-Yara: an exact read mapper for very large databases with short update time"],"prefix":"10.1093","volume":"34","author":[{"given":"Temesgen Hailemariam","family":"Dadi","sequence":"first","affiliation":[{"name":"Algorithmic Bioinformatics, Institute for Bioinformatics, FU Berlin, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Enrico","family":"Siragusa","sequence":"additional","affiliation":[{"name":"Computational Genomics, IBM Thomas J Watson Research Center, Yorktown Heights, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vitor C","family":"Piro","sequence":"additional","affiliation":[{"name":"Bioinformatics Unit (MF1), Robert Koch Institute, Berlin, Germany"},{"name":"CAPES Foundation, Ministry of Education of Brazil, Bras\u00edlia DF, Brazil"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"Andrusch","sequence":"additional","affiliation":[{"name":"Centre for Biological Threats and Special Pathogens (ZBS1), Robert Koch Institute, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Enrico","family":"Seiler","sequence":"additional","affiliation":[{"name":"Algorithmic Bioinformatics, Institute for Bioinformatics, FU Berlin, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bernhard Y","family":"Renard","sequence":"additional","affiliation":[{"name":"Bioinformatics Unit (MF1), Robert Koch Institute, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Knut","family":"Reinert","sequence":"additional","affiliation":[{"name":"Algorithmic Bioinformatics, Institute for Bioinformatics, FU Berlin, Berlin, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2018,9,8]]},"reference":[{"key":"2023061313520268600_bty567-B1","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1007\/978-3-642-21458-5_20","article-title":"Lightweight bwt construction for very large string collections","volume-title":"Combinatorial Pattern Matching","author":"Bauer","year":"2011"},{"key":"2023061313520268600_bty567-B2","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":"2023061313520268600_bty567-B3","doi-asserted-by":"crossref","DOI":"10.1101\/234955","article-title":"Real-time search of all bacterial and viral genomic data","author":"Bradley","year":"2017"},{"key":"2023061313520268600_bty567-B4","doi-asserted-by":"crossref","first-page":"136","DOI":"10.1093\/bioinformatics\/btv524","article-title":"Rnf: a general framework to evaluate ngs read mappers","volume":"32","author":"B\u0159inda","year":"2016","journal-title":"Bioinformatics"},{"key":"2023061313520268600_bty567-B5","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/j.ipl.2003.12.001","article-title":"Approximation algorithms for a hierarchically structured bin packing problem","volume":"89","author":"Codenotti","year":"2004","journal-title":"Information Process. Lett."},{"key":"2023061313520268600_bty567-B6","first-page":"118","article-title":"Computational pan-genomics: status, promises and challenges","volume":"19","author":"Consortium","year":"2018","journal-title":"Brief. Bioinformatics"},{"key":"2023061313520268600_bty567-B7","doi-asserted-by":"crossref","first-page":"e3138","DOI":"10.7717\/peerj.3138","article-title":"SLIMM: species level identification of microorganisms from metagenomes","volume":"5","author":"Dadi","year":"2017","journal-title":"PeerJ"},{"key":"2023061313520268600_bty567-B8","doi-asserted-by":"crossref","first-page":"D136","DOI":"10.1093\/nar\/gkr1178","article-title":"The NCBI Taxonomy database","volume":"40","author":"Federhen","year":"2012","journal-title":"Nucleic Acids Res."},{"key":"2023061313520268600_bty567-B9","doi-asserted-by":"crossref","first-page":"390","DOI":"10.1109\/SFCS.2000.892127","article-title":"Opportunistic data structures with applications","volume-title":"Proceedings 41st Annual Symposium on Foundations of Computer Science","author":"Ferragina","year":"2000"},{"key":"2023061313520268600_bty567-B10","first-page":"10","article-title":"RefSeq: an update on prokaryotic genome annotation and curation","volume":"1","author":"Haft","year":"2017","journal-title":"Nucleic Acids Res."},{"key":"2023061313520268600_bty567-B11","doi-asserted-by":"crossref","first-page":"i349","DOI":"10.1093\/bioinformatics\/btu439","article-title":"Lambda: the local aligner for massive biological data","volume":"30","author":"Hauswedell","year":"2014","journal-title":"Bioinformatics"},{"key":"2023061313520268600_bty567-B12","doi-asserted-by":"crossref","first-page":"210","DOI":"10.1186\/1471-2105-12-210","article-title":"A novel and well-defined benchmarking method for second generation read mapping","volume":"12","author":"Holtgrewe","year":"2011","journal-title":"BMC Bioinformatics"},{"key":"2023061313520268600_bty567-B13","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","year":"2012","journal-title":"Nat. Methods"},{"key":"2023061313520268600_bty567-B14","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","year":"2009","journal-title":"Genome Biol."},{"key":"2023061313520268600_bty567-B15","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1093\/bioinformatics\/btp698","article-title":"Fast and accurate long-read alignment with burrows\u2013wheeler transform","volume":"26","author":"Li","year":"2010","journal-title":"Bioinformatics"},{"key":"2023061313520268600_bty567-B16","doi-asserted-by":"crossref","first-page":"1185","DOI":"10.1038\/nmeth.2221","article-title":"The gem mapper: fast, accurate and versatile alignment by filtration","volume":"9","author":"Marco-Sola","year":"2012","journal-title":"Nat. Methods"},{"key":"2023061313520268600_bty567-B17","doi-asserted-by":"crossref","first-page":"e0126409","DOI":"10.1371\/journal.pone.0126409","article-title":"DIDA: distributed indexing dispatched alignment","volume":"10","author":"Mohamadi","year":"2015","journal-title":"PLoS One"},{"key":"2023061313520268600_bty567-B18","doi-asserted-by":"crossref","first-page":"2272","DOI":"10.1093\/bioinformatics\/btw150","article-title":"DUDes: a top-down taxonomic profiler for metagenomics","volume":"32","author":"Piro","year":"2016","journal-title":"Bioinformatics"},{"key":"2023061313520268600_bty567-B19","doi-asserted-by":"crossref","first-page":"3499","DOI":"10.1093\/bioinformatics\/btu438","article-title":"Journaled string tree-a scalable data structure for analyzing thousands of similar genomes on your laptop","volume":"30","author":"Rahn","year":"2014","journal-title":"Bioinformatics"},{"key":"2023061313520268600_bty567-B20","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/j.jbiotec.2017.07.017","article-title":"The SeqAn C++ template library for efficient sequence analysis: a resource for programmers","volume":"261","author":"Reinert","year":"2017","journal-title":"J. Biotechnol."},{"key":"2023061313520268600_bty567-B21","doi-asserted-by":"crossref","first-page":"R98","DOI":"10.1186\/gb-2009-10-9-r98","article-title":"Simultaneous alignment of short reads against multiple genomes","volume":"10","author":"Schneeberger","year":"2009","journal-title":"Genome Biol."},{"key":"2023061313520268600_bty567-B22","unstructured":"Siragusa\n       \u00a0E.\n           (2013) \nApproximate string matching for high-throughput sequencing. PhD Thesis, Freie Universit\u00e4t, Berlin."},{"key":"2023061313520268600_bty567-B23","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1007\/978-3-642-03784-9_7","article-title":"Compressed suffix arrays for massive data","volume-title":"String Processing and Information Retrieval","author":"Sir\u00e9n","year":"2009"},{"key":"2023061313520268600_bty567-B24","doi-asserted-by":"crossref","first-page":"2592","DOI":"10.1093\/bioinformatics\/bts505","article-title":"Razers 3: faster, fully sensitive read mapping","volume":"28","author":"Weese","year":"2012","journal-title":"Bioinformatics"}],"container-title":["Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/34\/17\/i766\/50582656\/bioinformatics_34_17_i766.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article-pdf\/34\/17\/i766\/50582656\/bioinformatics_34_17_i766.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,6,13]],"date-time":"2023-06-13T09:55:03Z","timestamp":1686650103000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/bioinformatics\/article\/34\/17\/i766\/5093228"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,1]]},"references-count":24,"journal-issue":{"issue":"17","published-print":{"date-parts":[[2018,9,1]]}},"URL":"https:\/\/doi.org\/10.1093\/bioinformatics\/bty567","relation":{"has-preprint":[{"id-type":"doi","id":"10.1101\/256354","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":[[2018,9,1]]},"published":{"date-parts":[[2018,9,1]]}}}