Rxivist logo

Improved representation of sequence Bloom trees

By Robert S. Harris, Paul Medvedev

Posted 19 Dec 2018
bioRxiv DOI: 10.1101/501452 (published DOI: 10.1093/bioinformatics/btz662)

Motivation 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. Results 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. Availability and implementation HowDe-SBT is available as a free open source program on <https://github.com/medvedevgroup/HowDeSBT>. Contact Paul Medvedev, pzm11{at}psu.edu Supplementary information Supplementary text and figures available as single Supplementary file.

Download data

  • Downloaded 710 times
  • Download rankings, all-time:
    • Site-wide: 31,858
    • In bioinformatics: 3,620
  • Year to date:
    • Site-wide: 45,419
  • Since beginning of last month:
    • Site-wide: 24,616

Altmetric data

Downloads over time

Distribution of downloads per paper, site-wide


Sign up for the Rxivist weekly newsletter! (Click here for more details.)