Designing small universal k-mer hitting sets for improved analysis of high-throughput sequencing

Area of Science:

• Bioinformatics
• Computational Biology
• Data Science

Background:

• Deep sequencing generates vast amounts of data, necessitating efficient algorithms and data structures.
• Minimizers are a current paradigm for improving sequence analysis tasks like read overlap detection and sequence searching.
• Existing methods face challenges in scalability and efficiency with increasing data volumes.

Purpose of the Study:

• To introduce a novel paradigm, universal hitting sets (UHS), as an alternative to minimizers for sequence analysis.
• To develop and evaluate DOCKS, a heuristic algorithm for finding compact UHS.
• To demonstrate the practical improvements of UHS over minimizers in handling large genomic datasets.

Main Methods:

• Defined universal hitting sets (UHS) for k-mers and L-long sequences.
• Developed DOCKS, a two-phase heuristic algorithm to find compact UHS.
• Assessed the NP-hardness of a related problem to justify heuristic use.
• Applied DOCKS to real genomic data for performance evaluation.

Main Results:

• DOCKS effectively finds compact UHS, closely approximating theoretical lower bounds.
• UHS generated by DOCKS show significant improvements over minimizers in sequence analysis tasks.
• For the human genome, DOCKS required less than 30% of the 10-mers compared to minimizers.

Conclusions:

• Universal hitting sets offer a promising alternative to minimizers for efficient sequence analysis.
• The DOCKS heuristic provides a practical and effective method for generating compact UHS.
• This approach has the potential to significantly enhance the analysis of large-scale sequencing data.