摘要： 用于生物序列联配的Smith Waterman算法在生物信息学中有着重要的意义，但是，算法需要的空间复杂度和时间复杂度都是 O(mn)，极大地限制了算法的应用。该文从并行计算模型HPM出发，从通信、存储两方面对Smith Waterman算法进行分析，提出了针对CoSMPs系统的分层的分块行流水并行算法，并通过计算不同规模的长序列进行验证，实验结果与理论分析一致。

关键词: 生物序列联配, 动态规划, HPM模型

Abstract: The Smith_waterman algorithm, used for the pair-wise biological sequence alignment, is one the most important method in bioinformatics. However, its time and space complexity are both O(mn), prevents it from being used for large sequences. Here, based on the parallel computational model, the HPM model, the parallelism and the locality of the algorithm is investigated and the hierarchical block pipeline parallel method is presented. Experiments of aligning sequences of different scale, are designed and the results are consistent with the theoretical conclusion.

Key words: Pair-wise biological sequence alignment, Dynamic programming, HPM model