Smith-Waterman算法优化改进与Spark并行化研究

论文摘要

Smith-Waterman算法是1种精确度最高、广泛应用于文本搜索的生物学序列比对算法。在对Smith-Waterman算法深入研究的基础上,从减少计算任务量和降低计算复杂度两个方面对算法进行优化改进,将优化改进算法基于Spark平台进行算法并行化设计,并通过准确性测试、算法运行速度测试、算法速度比较测试、算法可扩展性测试等实验分析优化改进算法和并行化算法的性能。实验结果表明:优化改进和并行化后的算法在保证准确性的前提下,极大地提高了算法运行速度和可扩展性。

论文目录

• 1 SW算法研究与改进
•   1.1 SW算法
•   1.2 SW算法的优化改进
•     1.2.1 降低计算任务量
•       （1）利用式（1）和式（2）推导可得式（4）。
•       （2）利用式（1）和式（2）推导可得式（5）。
•       （3）同理,利用式（1）和式（2）推导可得式（7）。
•     1.2.2 简化计算复杂度
•     1.2.3 提出Opti-SW算法
•   1.3 Opti-SW算法的准确性和对比实验
•     1.3.1 Opti-SW算法准确度测试
•     1.3.2 Opti-SW算法速度测试
• 2 Opti-SW算法的并行化
•   2.1 并行化思路
•   2.2 并行化方案设计
•     Stage1 求解所有比对得分过程
•     Stage2 选取相似度高的序列过程
•     Stage3 求解并输出最优比对过程
•   2.3 SparkOSW算法相关实验
•     2.3.1 SparkOSW准确性测试
•     2.3.2 算法速度对比实验
•     2.3.3 并行化方案效益测试
•     2.3.4 SparkOSW算法可扩展性测试
•     2.3.5 查询序列长度与运行时间的关系测试
• 3 结论

文章来源

类型: 期刊论文

作者: 李雷孝,刘燕凤,高静

关键词: 基因序列比对,算法,优化改进,并行化

来源: 内蒙古农业大学学报(自然科学版) 2019年05期

年度: 2019

分类: 农业科技,基础科学,信息科技

专业: 生物学,计算机软件及计算机应用

单位: 内蒙古工业大学数据科学与应用学院,内蒙古农业大学计算机与信息工程学院,内蒙古自治区农牧业大数据研究与应用重点实验室

基金: 国家自然科学基金项目(61462070),内蒙古农业大学博士研究基金项目(BJ09-44)

分类号: Q811.4;TP301.6

DOI: 10.16853/j.cnki.1009-3575.2019.05.014

页码: 76-85

总页数: 10

文件大小: 1199K

下载量: 129