2026-07-23T17:37:45Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17036 2024-03-06T10:58:35Z ddc:004 open_access

Eulertigs: Minimum Plain Text Representation of k-mer Sets Without Repetitions in Linear Time Schmidt, Sebastian Alanko, Jarno N. Spectrum preserving string sets Eulerian cycle Suffix tree Bidirected arc-centric de Bruijn graph k-mer based methods A fundamental operation in computational genomics is to reduce the input sequences to their constituent k-mers. For maximum performance of downstream applications it is important to store the k-mers in small space, while keeping the representation easy and efficient to use (i.e. without k-mer repetitions and in plain text). Recently, heuristics were presented to compute a near-minimum such representation. We present an algorithm to compute a minimum representation in optimal (linear) time and use it to evaluate the existing heuristics. For that, we present a formalisation of arc-centric bidirected de Bruijn graphs and carefully prove that it accurately models the k-mer spectrum of the input. Our algorithm first constructs the de Bruijn graph in linear time in the length of the input strings (for a fixed-size alphabet). Then it uses a Eulerian-cycle-based algorithm to compute the minimum representation, in time linear in the size of the output. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sebastian Schmidt and Jarno N. Alanko 2022 Is Part Of LIPIcs, Volume 242, 22nd International Workshop on Algorithms in Bioinformatics (WABI 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WABI.2022.2 urn:nbn:de:0030-drops-170361 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2022.2 eng https://creativecommons.org/licenses/by/4.0/legalcode