EUVIMEDEUVIMED entdecken
Open Access

Where the Patterns Are: Repetition-Aware Compression for Colored de Bruijn Graphs *

Alessio Campanelli, Giulio Ermanno Pibiri iD, Jason Fan iD, Rob Patro iD

Journal of Computational Biology · 01.10.2024 · 31 (10) · 1022-1044

DOI: 10.1089/cmb.2024.0714 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Computational Biology, online erschienen am 30.10.2024. Verfasst von Alessio Campanelli und 3 weiteren Autor:innen. Beteiligte Einrichtung: DAIS, Ca' Foscari University of Venice, Venice, Italy. Hauptthemen laut MEDLINE: Algorithms, Data Compression. Die Arbeit wurde bisher 15-mal zitiert (Crossref) und nennt 49 Literaturangaben. Der Volltext ist frei in PubMed Central verfügbar. Gefördert von: NHGRI NIH HHS.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We describe lossless compressed data structures for the colored de Bruijn graph (or c-dBG). Given a collection of reference sequences, a c-dBG can be essentially regarded as a map from k -mers to their color sets . The color set of a k -mer is the set of all identifiers, or colors , of the references that contain the k -mer. While these maps find countless applications in computational biology (e.g., basic query, reading mapping, abundance estimation, etc.), their memory usage represents a serious challenge for large-scale sequence indexing. Our solutions leverage on the intrinsic repetitiveness of the color sets when indexing large collections of related genomes. Hence, the described algorithms factorize the color sets into patterns that repeat across the entire collection and represent these patterns once instead of redundantly replicating their representation as would happen if the sets were encoded as atomic lists of integers. Experimental results across a range of datasets and query workloads show that these representations substantially improve over the space effectiveness of the best previous solutions (sometimes, even dramatically, yielding indexes that are smaller by an order of magnitude). Despite the space reduction, these indexes only moderately impact the efficiency of the queries compared to the fastest indexes.

Schlagwörter

MeSH-Schlagwörter (MEDLINE)

AlgorithmsData CompressionComputational BiologyHumansSequence Analysis, DNA

Stichwörter der Autor:innen

colored de Bruijn graphdata compressionhashingpseudoalignment

Autor:innen und Institutionen

  • DAIS, Ca' Foscari University of Venice, Venice, Italy.
  • ISTI-CNR, Pisa, Italy.
  • Fulcrum Genomics LLC, Somerville, Massachusetts, USA.
  • Department of Computer Science, University of Maryland, College Park, Maryland, USA.

ORCID-Profile: Giulio Ermanno Pibiri, Jason Fan, Rob Patro

Förderung

  • NHGRI NIH HHS

Zitieren

APA

Campanelli, A., Pibiri, G. E., Fan, J., & Patro, R. (2024). Where the Patterns Are: Repetition-Aware Compression for Colored de Bruijn Graphs *. Journal of Computational Biology, 31(10), 1022-1044. https://doi.org/10.1089/cmb.2024.0714

Vancouver

Campanelli A, Pibiri GE, Fan J, Patro R. Where the Patterns Are: Repetition-Aware Compression for Colored de Bruijn Graphs *. Journal of Computational Biology. 2024;31(10):1022-1044. doi:10.1089/cmb.2024.0714

BibTeX
@article{Campanelli2024,
  author = {Campanelli, Alessio and Pibiri, Giulio Ermanno and Fan, Jason and Patro, Rob},
  title = {Where the Patterns Are: Repetition-Aware Compression for Colored de Bruijn Graphs *},
  journal = {Journal of Computational Biology},
  year = {2024},
  volume = {31},
  number = {10},
  pages = {1022--1044},
  doi = {10.1089/cmb.2024.0714}
}
Kostenlos starten →