Author Login Editor-in-Chief Peer Review Editor Work Office Work

Computer Engineering ›› 2007, Vol. 33 ›› Issue (01): 56-58. doi: 10.3969/j.issn.1000-3428.2007.01.019

• Software Technology and Database • Previous Articles     Next Articles

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

LI Yugang1, LIU Zhiyong2   

  1. (1. Department of Computer, Beijing University of Technology, Beijing 100080; 2. National Natural Science Foundation of China, Beijing 100083)
  • Received:1900-01-01 Revised:1900-01-01 Online:2007-01-05 Published:2007-01-05

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

李玉岗1,刘志勇2   

  1. (1. 北京理工大学计算机系,北京 100080;2. 国家自然科学基金委员会,北京 100083)

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

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

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