摘要
生物序列比对是生物信息学中最常见的问题之一,基于动态规划思想的Smith-Waterman算法是序列比对中最基本的算法.然而现有的并行Smith—Waterman算法都需要庞大的内存,且无法处理大规模的数据串,随着生物数据的急剧增长,这些并行算法对内存空间的需求已成为需要迫切解决的问题.由此提出一种并行生物序列比对算法,PSW—DC算法,该算法采用分而治之的方法把query序列划分为若干片段,并分配给相应的各个处理器,而后并行地按Smith—Waterman算法与目标(subiect)序列进行比对,再通过按一定规则的扩展过程求取序列的优化匹配.与其他并行算法相比,该算法有效地降低了内存空间的需求,并实现了对大规模数据串的并行处理.为实现该算法,给出了一种称作C&E的拓展规则及实现方法.且该方法已经在实际系统中得到实现.
出处
《中国科学（E辑）》
CSCD
北大核心
2004年第2期190-199,共10页
Science in China(Series E)
