DROPS

Artifact

Software

IBB

Authors: Enno Adler, Stefan Böttcher, Rita Hartel, and Cederic Alexander Steininger

Abstract

Cite as

Enno Adler, Stefan Böttcher, Rita Hartel, Cederic Alexander Steininger. IBB (Software). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-23784,
   title = {{IBB}}, 
   author = {Adler, Enno and B\"{o}ttcher, Stefan and Hartel, Rita and Steininger, Cederic Alexander},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:42d4aa3c09d658e12540f4090749c8c3d7966642;origin=https://github.com/adlerenno/ibb;visit=swh:1:snp:1f4197f4eab25d389acbe5116bdc5aecebfd28f8;anchor=swh:1:rev:4fbfb1419c64c901c7221d4df6adf104bcb3a23a}{\texttt{swh:1:dir:42d4aa3c09d658e12540f4090749c8c3d7966642}} (visited on 2025-07-15)},
   url = {https://github.com/adlerenno/ibb},
   doi = {10.4230/artifacts.23784},
}

Document

DOI: 10.4230/LIPIcs.SEA.2025.2

IBB: Fast Burrows-Wheeler Transform Construction for Length-Diverse DNA Data

Authors: Enno Adler, Stefan Böttcher, Rita Hartel, and Cederic Alexander Steininger

Published in: LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025)

Abstract

The Burrows-Wheeler transform (BWT) is integral to the FM-index, which is used extensively in text compression, indexing, pattern search, and bioinformatic problems as de novo assembly and read alignment. Thus, efficient construction of the BWT in terms of time and memory usage is key to these applications. We present a novel external-memory algorithm called Improved-Bucket Burrows-Wheeler transform (IBB) for constructing the BWT of DNA datasets with highly diverse sequence lengths. IBB uses a right-aligned approach to efficiently handle sequences of varying lengths, a tree-based data structure to manage relative insert positions and ranks, and fine buckets to reduce the necessary amount of input and output to external memory. Our experiments demonstrate that IBB is 10% to 40% faster than the best existing state-of-the-art BWT construction algorithms on most datasets while maintaining competitive memory consumption.

Cite as

Enno Adler, Stefan Böttcher, Rita Hartel, and Cederic Alexander Steininger. IBB: Fast Burrows-Wheeler Transform Construction for Length-Diverse DNA Data. In 23rd International Symposium on Experimental Algorithms (SEA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 338, pp. 2:1-2:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{adler_et_al:LIPIcs.SEA.2025.2,
  author =	{Adler, Enno and B\"{o}ttcher, Stefan and Hartel, Rita and Steininger, Cederic Alexander},
  title =	{{IBB: Fast Burrows-Wheeler Transform Construction for Length-Diverse DNA Data}},
  booktitle =	{23rd International Symposium on Experimental Algorithms (SEA 2025)},
  pages =	{2:1--2:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-375-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{338},
  editor =	{Mutzel, Petra and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.2},
  URN =		{urn:nbn:de:0030-drops-232402},
  doi =		{10.4230/LIPIcs.SEA.2025.2},
  annote =	{Keywords: burrows-wheeler transform, self-indexes, external-memory}
}

Search Results

Documents authored by Hartel, Rita

IBB

Abstract

Cite as

IBB: Fast Burrows-Wheeler Transform Construction for Length-Diverse DNA Data

Abstract

Cite as

Thanks for your feedback!

Could not send message