Related Experiment Video
Updated: Aug 9, 2025

A Concoction Pipeline for Generating Molecular Operational Taxonomic Units (MOTUs) Among Riparian and Aquatic Beetles
Published on: July 11, 2025
Eulertigs: minimum plain text representation of k-mer sets without repetitions in linear time
Sebastian Schmidt1, Jarno N Alanko1,2
1Department of Computer Science, University of Helsinki, Helsinki, Finland.
Abstract:
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. Our algorithm first constructs the de Bruijn graph in linear time and then uses a Eulerian-cycle-based algorithm to compute the minimum representation, in time linear in the size of the output.
Related Concept Videos
Maxam-Gilbert Sequencing
Challenges of the Maxam-Gilbert Method
The...
Multi-species Conserved Sequences
Although the genome of each species varies greatly from each other, a few sequences are highly conserved. Such conserved...
¹H NMR Signal Multiplicity: Splitting Patterns
Karyotyping
Sanger Sequencing
Polymers: Molecular Weight Distribution

