Introducing difference recurrence relations for faster semi-global alignment of long sequences.

Area of Science:

• Bioinformatics
• Computational Biology
• Genomics

Background:

• Single-molecule DNA sequencing now produces reads up to 1 Mb.
• Current alignment software uses SIMD for Smith-Waterman-Gotoh (SWG) but 16/32-bit integers limit SIMD efficiency with long reads.

Purpose of the Study:

• To develop a faster semi-global alignment algorithm for long DNA reads.
• To enable full utilization of modern processor SIMD capabilities.

Main Methods:

• Proposed a "difference recurrence relations" algorithm.
• Calculates and stores differences between adjacent DP matrix cells instead of full matrices.
• Utilizes 8-bit integer operations for enhanced SIMD performance.

Main Results:

• Achieved 2.1x speedup over state-of-the-art algorithms.
• Outputs identical results to the SWG algorithm.
• Developed the libgaba library for easy integration into alignment programs.

Conclusions:

• The novel algorithm and libgaba library accelerate long-read nucleotide analysis.
• Facilitates faster pairwise alignment stages in bioinformatics.
• The C library is publicly available for developers.