| 基于Smith-Waterman算法的并行分而治之生物序列比对算法 |
| |
| 作者姓名： | 张法 乔香珍 刘志勇 |
| |
| 作者单位： | 1. 中国科学院计算技术研究所,北京,100080
2. 国家自然科学基金委员会,北京,100085 |
| |
| 摘 要： | 生物序列比对是生物信息学中最常见的问题之一, 基于动态规划思想的Smith-Waterman算法是序列比对中最基本的算法. 然而现有的并行Smith-Waterman算法都需要庞大的内存, 且无法处理大规模的数据串, 随着生物数据的急剧增长, 这些并行算法对内存空间的需求已成为需要迫切解决的问题. 由此提出一种并行生物序列比对算法, PSW-DC算法, 该算法采用分而治之的方法把query序列划分为若干片段, 并分配给相应的各个处理器, 而后并行地按Smith-Waterman算法与目标(subject)序列进行比对, 再通过按一定规则的扩展过程求取序列的优化匹配. 与其他并行算法相比, 该算法有效地降低了内存空间的需求, 并实现了对大规模数据串的并行处理. 为实现该算法, 给出了一种称作C&;E的拓展规则及实现方法. 且该方法已经在实际系统中得到实现.
|
| 关 键 词： | 动态规划 分而治之 并行处理 内存空间 生物序列比对 |
| 收稿时间： | 2002-10-08 |
| 修稿时间： | 2003-08-01 |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《中国科学(E辑)》浏览原始摘要信息 |
|
点击此处可从《中国科学(E辑)》下载全文 |
|
