Implementation and performance analysis of efficient index structures for DNA search algorithms in parallel platforms

摘要

Because of the large datasets that are usually involved in deoxyribonucleic acid (DNA) sequence alignment,rnthe use of optimal local alignment algorithms (e.g., Smith–Waterman) is often unfeasible in practicalrnapplications. As such, more efficient solutions that rely on indexed search procedures are often preferredrnto significantly reduce the time to obtain such alignments. Some data structures that are usually adopted tornbuild such indexes are suffix trees, suffix arrays, and the hash tables of q-mers.rnThis paper presents a comparative analysis of highly optimized parallel implementations of index-basedrnsearch algorithms using these three distinct data structures, considering two different parallel platforms: arnhomogeneous multi-core central processing unit (CPU) and a NVidia Fermi graphics processing unit (GPU).rnContrasting to what happens with CPU implementations, the obtained experimental results reveal that GPUrnimplementations clearly favor the suffix arrays, because of the achieved performance in terms of memoryrnaccesses. Furthermore, the results also reveal that both the suffix trees and suffix arrays outperform the hashrntables of q-mers when dealing with the largest datasets.rnWhen compared with a quad-core CPU, the results demonstrate the possibility to achieve speedups asrnhigh as 65 with the GPU when considering a suffix-array index, thus making it an adequate choice forrnhigh-performance bioinfomatics applications.