{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,27]],"date-time":"2024-08-27T05:11:18Z","timestamp":1724735478778},"reference-count":18,"publisher":"World Scientific Pub Co Pte Lt","issue":"08","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2018,12]]},"abstract":"<jats:p> Compressed suffix trees and bidirectional FM-indexes can store a set of strings and support queries that let us explore the set of substrings they contain, adding and deleting characters on both the left and right, but they can use much more space than a de Bruijn graph for the strings. Bowe et al.\u2019s BWT-based de Bruijn graph representation (Proc. Workshop on Algorithms for Bioinformatics, pp. 225\u2013235, 2012) can be made bidirectional as well, at the cost of increasing its space usage by a small constant, but it fixes the length of the substrings. Boucher et al. (Proc. Data Compression Conference, pp. 383\u2013392, 2015) generalized Bowe et al.\u2019s representation to support queries about variable-length substrings, but at the cost of bidirectionality. In this paper we show how to make Boucher et al.\u2019s variable-order implementation of de Bruijn graphs bidirectional. <\/jats:p>","DOI":"10.1142\/s0129054118430037","type":"journal-article","created":{"date-parts":[[2018,12,27]],"date-time":"2018-12-27T02:58:46Z","timestamp":1545879526000},"page":"1279-1295","source":"Crossref","is-referenced-by-count":7,"title":["Bidirectional Variable-Order de Bruijn Graphs"],"prefix":"10.1142","volume":"29","author":[{"given":"Djamal","family":"Belazzougui","sequence":"first","affiliation":[{"name":"CERIST, Algeria"}]},{"given":"Travis","family":"Gagie","sequence":"additional","affiliation":[{"name":"Diego Portales University and CEBIB, Chile"}]},{"given":"Veli","family":"M\u00e4kinen","sequence":"additional","affiliation":[{"name":"Helsinki Institute for Information Technology, University of Helsinki, Finland"}]},{"given":"Marco","family":"Previtali","sequence":"additional","affiliation":[{"name":"University of Milano-Bicocca, Italy"}]},{"given":"Simon J.","family":"Puglisi","sequence":"additional","affiliation":[{"name":"University of Helsinki, Finland"}]}],"member":"219","published-online":{"date-parts":[[2018,12,26]]},"reference":[{"key":"S0129054118430037BIB001","doi-asserted-by":"publisher","DOI":"10.3390\/a6020319"},{"key":"S0129054118430037BIB002","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2012.0021"},{"key":"S0129054118430037BIB003","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.02.002"},{"key":"S0129054118430037BIB009","first-page":"btt310","author":"Chikhi R.","year":"2013","journal-title":"Bioinformatics"},{"key":"S0129054118430037BIB010","first-page":"758","volume":"49","author":"de Bruijn N. G.","year":"1946","journal-title":"Koninklijke Nederlandse Akademie van Wetenschappen"},{"key":"S0129054118430037BIB011","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082039"},{"key":"S0129054118430037BIB012","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.12.002"},{"key":"S0129054118430037BIB015","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.10.043"},{"key":"S0129054118430037BIB017","first-page":"btv033","author":"Li D.","year":"2015","journal-title":"Bioinformatics"},{"key":"S0129054118430037BIB019","doi-asserted-by":"publisher","DOI":"10.1137\/0222058"},{"key":"S0129054118430037BIB020","doi-asserted-by":"publisher","DOI":"10.1145\/1216370.1216372"},{"key":"S0129054118430037BIB021","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781316588284"},{"key":"S0129054118430037BIB023","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btr216"},{"key":"S0129054118430037BIB024","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bts174"},{"key":"S0129054118430037BIB025","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.171285098"},{"issue":"4","key":"S0129054118430037BIB026","first-page":"53","volume":"7","author":"Russo L.","year":"2011","journal-title":"ACM Transactions on Algorithms (TALG)"},{"key":"S0129054118430037BIB027","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-006-1198-x"},{"key":"S0129054118430037BIB028","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2011.03.007"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054118430037","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T16:58:37Z","timestamp":1565110717000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054118430037"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12]]},"references-count":18,"journal-issue":{"issue":"08","published-online":{"date-parts":[[2018,12,26]]},"published-print":{"date-parts":[[2018,12]]}},"alternative-id":["10.1142\/S0129054118430037"],"URL":"https:\/\/doi.org\/10.1142\/s0129054118430037","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,12]]}}}