Advantages and GPU implementation of high-performance indexed DNA search based on suffix arrays

Author

Encarnação, Gustavo ; Sebastiao, Nuno ; Roma, Nuno

Author_Institution

IST, INESC-ID, Tech. Univ. Lisbon, Lisbon, Portugal

fYear

2011

fDate

4-8 July 2011

Firstpage

49

Lastpage

55

Abstract

A comparative analysis of high-performance implementations of two state of the art index structures that are of particular interest in the field of bioinformatics applications to accelerate the alignment of DNA sequences is presented. The two indexes are based on suffix trees and suffix arrays and were implemented in two different platforms: a quad core CPU and a NVIDIA GeForce GTX 580 GPU, based on the newest Fermi architecture. Unlike what happens in conventional CPU implementations, the obtained experimental results reveal that GPU implementations clearly favor the suffix arrays, due to the achieved performance in terms of memory accesses. When compared with the CPU, the results demonstrate the possibility to achieve speedups as high as 85 when using the suffix array in the GPU, thus making it an adequate choice for high-performance bioinformatics applications.

Keywords

DNA; bioinformatics; computer graphic equipment; coprocessors; DNA sequence alignment; Fermi architecture; NVIDIA GeForce GTX 580 GPU; bioinformatics applications; high-performance indexed DNA search; index structures; memory accesses; quad core CPU; suffix arrays; suffix trees; Acceleration; Arrays; Bioinformatics; DNA; Graphics processing unit; Indexes; Instruction sets; Bioinformatics; GPGPU; Indexed Search;

fLanguage

English

Publisher

ieee

Conference_Titel

High Performance Computing and Simulation (HPCS), 2011 International Conference on

Conference_Location

Istanbul

Print_ISBN

978-1-61284-380-3

Type

conf

DOI

10.1109/HPCSim.2011.5999806

Filename

5999806