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

Parallel Optimization of the Smith-Waterman Algorithm Based on HPM Model

作　　者：李玉岗[1] 刘志勇[2] 

机构地区：[1]北京理工大学计算机系,北京100080 [2]国家自然科学基金委员会,北京100083

出　　处：《计算机工程》2007年第1期56-58,共3页Computer Engineering

基　　金：国家自然科学基金资助项目(60372040;60373044;60503060)

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

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

分 类 号：TP311.52[自动化与计算机技术—计算机软件与理论]