基于HPM模型的Smith-Waterman算法并行优化

摘要：

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

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

所属期刊栏目：33

分类号：TP311.52(计算技术、计算机技术)

资助基金：国家自然科学基金60372040;60373044;60503060

在线出版日期：2007-03-05（万方平台首次上网日期，不代表论文的发表时间）

页数：共3页

页码：56-58