Downloads provided by UsageCounts
handle: 2117/369035
Sequence alignment remains a fundamental problem with practical applications ranging from pattern recognition to computational biology. Traditional algorithms based on dynamic programming are hard to parallelize, require significant amounts of memory, and fail to scale for large inputs. This work presents eWFA-GPU, a GPU (graphics processing unit)-accelerated tool to compute the exact edit-distance sequence alignment based on the wavefront alignment algorithm (WFA). This approach exploits the similarities between the input sequences to accelerate the alignment process while requiring less memory than other algorithms. Our implementation takes full advantage of the massive parallel capabilities of modern GPUs to accelerate the alignment process. In addition, we propose a succinct representation of the alignment data that successfully reduces the overall amount of memory required, allowing the exploitation of the fast shared memory of a GPU. Our results show that our GPU implementation outperforms by 3- 9× the baseline edit-distance WFA implementation running on a 20 core machine. As a result, eWFA-GPU is up to 265 times faster than state-of-the-art CPU implementation, and up to 56 times faster than state-of-the-art GPU implementations.
:Informàtica::Aplicacions de la informàtica::Bioinformàtica [Àrees temàtiques de la UPC], compute unified device architecture (CUDA), Bioinformatics, pairwise sequence alignment, edit-distance, Edit-distance, Pairwise sequence alignment, Àrees temàtiques de la UPC::Informàtica::Aplicacions de la informàtica::Bioinformàtica, graphics processing unit (GPU), Compute unified device architecture (CUDA), Heuristic algorithms, Wavefront alignment algorithm (WFA), :Informàtica::Arquitectura de computadors::Arquitectures paral·leles [Àrees temàtiques de la UPC], Approximate string matching, Levenshtein distance, Genomics, Unitats de processament gràfic, 004, TK1-9971, Genòmica, Àrees temàtiques de la UPC::Informàtica::Arquitectura de computadors::Arquitectures paral·leles, Time complexity, Electrical engineering. Electronics. Nuclear engineering, High performance computing, Càlcul intensiu (Informàtica), Graphics processing units, Memory management
:Informàtica::Aplicacions de la informàtica::Bioinformàtica [Àrees temàtiques de la UPC], compute unified device architecture (CUDA), Bioinformatics, pairwise sequence alignment, edit-distance, Edit-distance, Pairwise sequence alignment, Àrees temàtiques de la UPC::Informàtica::Aplicacions de la informàtica::Bioinformàtica, graphics processing unit (GPU), Compute unified device architecture (CUDA), Heuristic algorithms, Wavefront alignment algorithm (WFA), :Informàtica::Arquitectura de computadors::Arquitectures paral·leles [Àrees temàtiques de la UPC], Approximate string matching, Levenshtein distance, Genomics, Unitats de processament gràfic, 004, TK1-9971, Genòmica, Àrees temàtiques de la UPC::Informàtica::Arquitectura de computadors::Arquitectures paral·leles, Time complexity, Electrical engineering. Electronics. Nuclear engineering, High performance computing, Càlcul intensiu (Informàtica), Graphics processing units, Memory management
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 9 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
| views | 59 | |
| downloads | 221 |

Views provided by UsageCounts
Downloads provided by UsageCounts