Indexing Arbitrary-Length k-Mers in Sequencing Reads

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Next-generation sequencing (NGS) generates vast amounts of data, necessitating efficient methods for analysis.
• Indexing and querying k-mers in sequencing reads are fundamental operations in bioinformatics.
• Existing data structures face challenges in balancing space usage and query speed.

Purpose of the Study:

• To introduce a novel, lightweight data structure for in-memory indexing and querying of NGS reads.
• To support the k-mer counting and locating interface established by Philippe et al.
• To provide a competitive alternative to current algorithms in terms of space and time efficiency.

Main Methods:

• Developed PgSA (pseudogenome suffix array), a data structure based on identifying overlapping reads.
• Implemented an indexing strategy optimized for main memory.
• Evaluated performance against existing algorithms for k-mer analysis.

Main Results:

• PgSA demonstrates competitive performance in space utilization and query times compared to existing solutions.
• The data structure efficiently handles large collections of NGS reads.
• Achieved performance metrics suitable for demanding bioinformatics tasks.

Conclusions:

• PgSA offers an efficient and lightweight solution for indexing and querying NGS data.
• The proposed data structure is well-suited for key applications such as variant calling, error correction, and RNA-seq analysis.
• This work contributes to advancing computational tools for genomic data processing.