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

Area of Science:

• Computational Genomics
• Bioinformatics
• Algorithm Design

Background:

• Representing k-mers (DNA subsequences) efficiently is vital for computational genomics applications.
• Current methods often use heuristics, leading to near-minimum but not optimal space representations.
• The need exists for space-efficient, easily usable k-mer representations without repetitions.

Purpose of the Study:

• To develop an algorithm for computing a minimum k-mer representation.
• To achieve this minimum representation in optimal linear time.
• To evaluate existing heuristic methods using the new optimal algorithm.

Main Methods:

• Construction of the de Bruijn graph in linear time.
• Application of a Eulerian-cycle-based algorithm to find the minimum representation.
• Analysis of algorithm complexity in relation to input size and output size.

Main Results:

• An algorithm is presented that computes a minimum k-mer representation.
• The algorithm achieves optimal time complexity, linear in the input size.
• The study provides a benchmark for evaluating heuristic k-mer representation methods.

Conclusions:

• The developed algorithm offers a theoretically optimal solution for minimum k-mer representation.
• This advancement can enhance the performance of downstream computational genomics applications.
• The findings provide a new standard for assessing the efficiency of k-mer storage techniques.