摘要
随着生物序列数据库中序列数据的激增,开发兼有高度生物敏感性和高效率的算法显得极为迫切.通过对生物序列比对问题中Needleman-Wunsch算法和Smith-Waterman算法深入分析,提出了Smith-Waterman算法的改进算法,并通过实验验证该算法,对改进前后的运行性能进行比较分析.实验证明,改进后的算法实现了双序列局部最优解个数的优化,有效降低了生物序列比对算法时间与空间的复杂性,提高序列比对的得分率和准确率.
With the surge in sequence data of biological sequence database, developing a algorithm which has the high biology sensitivity and efficiency is very urgent. Based on the deep analysis on the Needleman-Wunsch and Smith-Waterman Algorithm of bio-sequence alignment, the author enhances the Smith-Waterman algorithm as well as proves its accuracy through a series of experiments in this paper. Comparing between the Smith-Waterman algorithm and the improved one, the author analyzes the performance of the two algorithms. Experimental results show that the newly improved algorithm can optimize the number of local optimal solutions for pairwise sequence, reduce the complexity in time and space of bio-sequence alignment algorithms, and increase the scores and accuracy of sequence alignments.
出处
《计算机系统应用》
2015年第9期112-117,共6页
Computer Systems & Applications
基金
河南省高等学校重点科研项目(15A520083)
河南省2014年基础与前沿技术研究计划(142300410428
142300410391)
河南中医学院苗圃工程项目(MP2013-74)
河南省教育厅2011年自然科学研究项目(2011A520027)
2014年度河南省教育厅科学技术研究重点项目(14A520070)
关键词
生物信息学
双序列比对
算法
bioinformatics
pairwise sequence alignment
algorithm
