Premium
Solving longest common subsequence and related problems on graphical processing units
Author(s) -
Deorowicz Sebastian
Publication year - 2010
Publication title -
software: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.437
H-Index - 70
eISSN - 1097-024X
pISSN - 0038-0644
DOI - 10.1002/spe.976
Subject(s) - longest common subsequence problem , computer science , subsequence , sequence (biology) , longest increasing subsequence , general purpose computing on graphics processing units , similarity (geometry) , field (mathematics) , edit distance , parallel processing , cuda , parallel computing , algorithm , theoretical computer science , graphics , computer graphics (images) , artificial intelligence , mathematics , image (mathematics) , mathematical analysis , biology , pure mathematics , bounded function , genetics
Modern graphical processing units (GPUs) offer much more computational power than modern central processing units. Therefore, it is natural that GPUs are applied not only for their original purposes, but also for general processing (GPGPU). In the field of sequence processing, one of the most important problems is the measuring of sequence similarity. There are many sequence similarity measures, e.g. edit distance, longest common subsequence length, and their derivatives. We examine the possibility of speeding up the algorithms computing some of them. We chose three measures useful in different situations. The experimental results show that the GPU versions of the examined algorithms are faster than their serial counterparts by a factor between 4 and 65. Copyright © 2010 John Wiley & Sons, Ltd.