Efficient k-mer dataset compression using Eulerian covers of de Bruijn graphs and BWT | Sciact - Система учета научной деятельности ИМ СО РАН

Efficient k-mer dataset compression using Eulerian covers of de Bruijn graphs and BWT Научная публикация

Журнал

RAIRO - Theoretical Informatics and Applications
ISSN: 0988-3754 , E-ISSN: 1290-385X

Вых. Данные

Год: 2025, Том: 59, Номер статьи : 20, Страниц : DOI: 10.1051/ita/2025020

Ключевые слова

de Bruijn graph, compression, BWT

Авторы

Chen Herman Z.Q. ¹ , Kitaev Sergey ² , Lang Xiaoyu ¹ , Pyatkin Artem ^3,4 , Tang Runbin ¹

Организации

1	Chongqing Normal University, PR China
2	Department of Mathematics and Statistics, University of Strathclyde, 26 Richmond Street, Glasgow G1 1XH, UK
3	Sobolev Institute of Mathematics, Koptyug ave, 4, Novosibirsk 630090, Russia
4	Novosibirsk State University, Pirogova str. 2, Novosibirsk 630090, Russia

Информация о финансировании (1)

Институт математики им. С.Л. Соболева СО РАН

FWNF-2022-0019

Transforming an input sequence into its constituent k-mers is a fundamental operation in computational genomics. To reduce storage costs associated with k-mer datasets, we introduce and formally analyze MCTR, a novel two-stage algorithm for lossless compression of the k-mer multiset. Our core method achieves a minimal text representation ( ) by computing an optimal Eulerian cover (minimum string count) of the dataset's de Bruijn graph, enabled by an efficient local Eulerization technique. The resulting strings are then further compressed losslessly using the Burrows-Wheeler Transform (BWT). Leveraging de Bruijn graph properties, MCTR is proven to achieve linear time and space complexity and guarantees complete reconstruction of the original k-mer multiset, including frequencies. Using simulated and real genomic data, we evaluated MCTR's performance (list and frequency representations) against the state-of-the-art lossy unitigging tool greedytigs (from matchtigs). We measured core execution time and the raw compression ratio (cr = weight( )/ weight( ), where is the input sequence data). Benchmarks confirmed MCTR's data fidelity but revealed performance trade-offs inherent to lossless representation. GreedyTigs was significantly faster. Regarding raw compression, GreedyTigs achieved high ratios (cr ≈ 14) on noisy real data for its lossy sequence output. MCTR methods exhibited cr ≈ 1 (list) or even cr < 1 (frequency, due to count overhead) on clean simulated data, indicating minimal raw text reduction or even expansion. On real data, MCTR (frequency) showed moderate raw compression (cr ≈ 1.5–2.7), while MCTR (list) showed none (cr ≈ 1). Importantly, the full MCTR+BWT pipeline significantly outperforms BWT alone for enhanced lossless compression. Our results establish MCTR as a valuable, theoretically grounded tool for applications demanding efficient, lossless storage and analysis of k-mer multisets, complementing lossy methods optimized for sequence summarization.

Chen H.Z.Q. , Kitaev S. , Lang X. , Pyatkin A. , Tang R.
Efficient k-mer dataset compression using Eulerian covers of de Bruijn graphs and BWT
RAIRO - Theoretical Informatics and Applications. 2025. V.59. 20 . DOI: 10.1051/ita/2025020 WOS Scopus РИНЦ OpenAlex

Поступила в редакцию:	14 февр. 2025 г.
Принята к публикации:	25 окт. 2025 г.
Опубликована в печати:	5 дек. 2025 г.
Опубликована online:	5 дек. 2025 г.

Web of science:	WOS:001631841900001
Scopus:	2-s2.0-105024074068
РИНЦ:	88088489
OpenAlex:	W7108715310

Пока нет цитирований