Rahman Amatur, Dufresne Yoann, Medvedev Paul
Department of Computer Science and Engineering, The Pennsylvania State University, University Park, PA, USA.
Institut Pasteur, Université Paris Cité, G5 Sequence Bioinformatics, Paris, France.
Lebniz Int Proc Inform. 2023 Sep;273. doi: 10.4230/LIPIcs.WABI.2023.17. Epub 2023 Aug 29.
A colored de Bruijn graph (also called a set of k-mer sets), is a set of k-mers with every k-mer assigned a set of colors. Colored de Bruijn graphs are used in a variety of applications, including variant calling, genome assembly, and database search. However, their size has posed a scalability challenge to algorithm developers and users. There have been numerous indexing data structures proposed that allow to store the graph compactly while supporting fast query operations. However, disk compression algorithms, which do not need to support queries on the compressed data and can thus be more space-efficient, have received little attention. The dearth of specialized compression tools has been a detriment to tool developers, tool users, and reproducibility efforts. In this paper, we develop a new tool that compresses colored de Bruijn graphs to disk, building on previous ideas for compression of k-mer sets and indexing colored de Bruijn graphs. We test our tool, called ESS-color, on various datasets, including both sequencing data and whole genomes. ESS-color achieves better compression than all evaluated tools and all datasets, with no other tool able to consistently achieve less than 44% space overhead.
彩色德布鲁因图（也称为k-mer集的集合）是一组k-mer，每个k-mer都被赋予一组颜色。彩色德布鲁因图被用于多种应用中，包括变异检测、基因组组装和数据库搜索。然而，它们的规模给算法开发者和用户带来了可扩展性挑战。已经提出了许多索引数据结构，这些结构允许在支持快速查询操作的同时紧凑地存储图。然而，磁盘压缩算法由于不需要支持对压缩数据的查询，因此可以更节省空间，但却很少受到关注。缺乏专门的压缩工具对工具开发者、工具用户和可重复性工作都造成了不利影响。在本文中，我们基于之前对k-mer集压缩和彩色德布鲁因图索引的想法，开发了一种新工具，将彩色德布鲁因图压缩到磁盘上。我们在各种数据集上测试了我们的工具ESS-color，包括测序数据和全基因组。ESS-color在所有评估工具和所有数据集上都实现了更好的压缩效果，没有其他工具能够始终实现低于44%的空间开销。
