.png){kind=icon}
返回
Accelerating Edit-Distance Sequence Alignment on GPU Using the Wavefront Algorithm
.png){kind=icon}
OA
AI
DOI：10.1109/ACCESS.2022.3182714.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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 x 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.
Keyword:
Approximate string matching
compute unified device architecture (CUDA)
edit-distance
graphics processing unit (GPU)
Levenshtein distance
pairwise sequence alignment
wavefront alignment algorithm (WFA)
期刊
IF:
3.6
论文数:
9.8W
被引数:
29.4W
机构
引用论文
Characteristics of Indium Bump for Flip-Chip Bonding Used in Polymeric-Waveguide-Integrated Optical Interconnection Systems倒装芯片键合中用于聚合物波导集成光互连系统的铟凸点特性
PREAI
分享收藏Inflammatory and Vitamin Bio-Markers Of Iron Trafficking and Distribution In Transfusional Overload: Insights From Comparing Diamond Blackfan Anemia With Sickle Cell Disease and Thalassemia (MCSIO PILOT Study)输血过量中铁转运和分布的炎症及维生素生物标志物：比较先天性红细胞生成障碍性贫血与镰状细胞病和地中海贫血的见解（MCSIO 前瞻性研究）.png)
Blood
BloodIF0
PREAI
分享收藏
查看更多内容