INSC期刊 | 关于Smith-Waterman算法并行实现的综述

背景知识

史密斯-沃特曼算法（Smith-Waterman Algorithm）是生物信息领域程序中常用的一种用于寻找两条序列间最优子序列的算法。该算法通过动态规划的方式实现比对，具有二次时间复杂度，耗时较长，为了解决这一问题，许多并行计算技术被应用于加速该算法，主要包括：向量级并行、线程级并行、进程级并行和异构并行等。

文章亮点

2021年9月6日，Interdisciplinary Sciences: Computational Life Sciences杂志在线发表了最新文章 “A Review of Parallel Implementations for the Smith–Waterman Algorithm” （ 点击文末 “阅读原文”）。

本文对现有的并行Smith-Waterman算法进行了整理和归纳，分析了各种并行实现的特点。具体来说，向量级并行可分为序列内并行和序列间并行两种并行方式，区别在于：前者主要针对单对序列比对进行加速，而后者则侧重于多对序列比对加速。线程级并行可以充分利用CPU的计算资源，提高CPU利用效率；而进程级并行可以调用多个平台的计算资源；异构并行可以利用多种计算设备，更加充分提高比对速度。我们在综述了Smith-Waterman算法的各种并行实现技术的基础上，结合常用的序列比对软件进行了分析，更加直观地展示了各种并行实现的优缺点。该综述可以为相关研究人员在比对算法选择以及新软件研发等方面提供技术原理的借鉴和支持。

期刊简介