Parallel Methods for Finding k-Mismatch Shortest Unique Substrings Using GPU.

Area of Science:

• Computational Biology
• Bioinformatics
• Parallel Computing

Background:

• k-mismatch shortest unique substring (SUS) queries are crucial for analyzing biological sequences.
• Existing methods focus on sequential CPU computation, facing challenges with large datasets.
• Efficiently computing SUS for all positions in long strings remains a significant computational hurdle.

Purpose of the Study:

• To develop the first parallel algorithm for k-mismatch SUS queries.
• To leverage graphic processing unit (GPU) technology for accelerated SUS computation.
• To provide a practical and efficient tool for analyzing massive biological strings.

Main Methods:

• Designed a parallel algorithm utilizing the multi-threading capabilities of GPUs.
• Implemented and tested the algorithm on real-world DNA sequence data.
• Compared performance against state-of-the-art sequential CPU-based SUS query methods.

Main Results:

• Achieved speedups of at least 6x for exact (k=0) SUS queries on a GPU.
• Demonstrated speedups of at least 23x for approximate (k>0) SUS queries on DNA sequences.
• Maintained comparable memory usage to the most memory-efficient sequential CPU approaches.

Conclusions:

• The proposed GPU-based parallel approach offers significant performance improvements for k-mismatch SUS queries.
• This work presents the first practical solution for approximate SUS computation on large biological sequences.
• The GPU acceleration makes SUS analysis feasible for massive datasets where CPU methods are too slow.