Eulertigs: minimum plain text representation of k-mer sets without repetitions in linear time

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. 2012 ACM Subject Classification Applied computing → Computational biology; Theory of computation → Data compression; Theory of computation → Graph algorithms analysis; Theory of computation → Data structures design and analysis