Abstract
With early hardware limitations of the GPU (lack of synchronization primitives and limited memory caching mechanisms) making GPU-based computation inefficient, emerging DNA sequence technologies open up more opportunities for molecular biology. This paper presents the issues of parallel implementation of the longest overlap region problem on a multiprocessor GPU using the Compute Unified Device Architecture (CUDA) platform. Compared to standard CPU implementation, CUDA performance proves the method of longest overlap region recognition of noncoding DNA is an efficient approach to high-performance bioinformatics applications. The study shows that the efficiency is more than 15 times that of CPU serial implementation. We believe our method provides a cost-efficient solution to the bioinformatics community for solving the longest overlap region recognition problem and other related fields.
Introduction
For a long time, noncoding DNA was dismissed as "junk DNA." However, we now know these sequences play critical roles in gene regulation, RNA molecule production, and structural functions like centromeres. As DNA sequencing technology advances, the volume of data is growing exponentially, making traditional sequence alignment—the process of finding similarities and overlaps—a massive computational bottleneck.
The "Longest Overlap Region" problem is a specific type of sequence comparison. Finding these overlaps efficiently is essential for understanding functional genomics. Traditional CPU-based serial algorithms struggle to keep up with the scale of modern genomic databases, necessitating a shift toward high-performance parallel computing.
Methodology
The authors propose a hybrid approach that combines efficient string algorithms with the massive parallelism of GPUs. The core of the solution lies in parallelizing the DC3 (Difference Cover modulo 3) suffix array construction and Range Minimum Query (RMQ) algorithms.
Parallel Radix Sort
The primary bottleneck in the DC3 algorithm is sorting. The authors implemented a custom parallel Radix Sort on the GPU using CUDA. This involves dividing the DNA sequence into "chunks" that are processed simultaneously by thousands of GPU threads. The sorting process utilizes split, scan, and scatter operations to reorganize data efficiently across the GPU's architecture.
Algorithmic Pipeline
- Suffix Array Construction: Using the DC3 algorithm with linear time complexity $O(n)$.
- Longest Common Prefix (LCP) & RMQ: The algorithm calculates the LCP between adjacent suffixes, transforming the search into a Range Minimum Query problem.
- LCA Transformation: The RMQ problem is further converted into a Least Common Ancestor (LCA) problem using Cartesian trees and Euler tours, allowing for $O(1)$ query time after $O(n)$ preprocessing.
- Memory Optimization: "Tile optimization" partitions local data into the GPU's shared memory, significantly reducing global memory access latency.
Experimental Results
The researchers evaluated their method using noncoding DNA sequences from the NCBI Nucleotide database, including Homo sapiens (Chromosome Y) and Caenorhabditis elegans. Query sequences ranged from 512 to over 2 million bases.
Performance and Speedup
The results demonstrate a significant performance advantage for the GPU as the data size increases. The CUDA-based implementation achieved a maximum speedup of approximately 14.2x to 19x over the serial CPU version for the largest datasets, depending on the specific GPU configuration.
A key insight from the data is the "crossover point." For sequences smaller than roughly 65,536 bases, the CPU is actually faster due to the overhead of data transfer to the GPU. However, as the sequence length increases, the GPU's efficiency grows significantly, while CPU performance degrades linearly.
Conclusion
This study provides a cost-effective solution for bioinformatics labs by leveraging consumer-grade GPU hardware to achieve supercomputer-like performance for specific genomic tasks. While the RMQ algorithm can be memory-intensive, the parallelized DC3 approach offers a scalable path forward for processing massive noncoding DNA datasets. Future work may involve further memory management refinements to handle entire genomes in a single pass.
Summary updated