基于SOPC的Smith-Waterman算法硬件加速器的设计与实现

摘要

近年来，生物信息学在不断地发展并成为一门重要的学科，国内许多高校和科研院所都在大力发展这一方面的技术，使其有了突飞猛进的发展，并且以大数据为基础的精准医疗将成为我国“十三五”期间重点发展的科学领域，这样使得生物信息学领域更受关注。 生物序列分析是现代生命科学领域中重要的基础性研究工作，而进行序列分析的根本就是序列比对。目前美国已经建立起100万人的基因数据库，预计我国的基因数据库将远超此量级，并且伴随着新一代测序技术的迅速发展，所需比对分析的序列数量出现了爆炸性增长的趋势，但在现如今的序列比对技术当中，已经难以找出匹配序列数量迅速增快的技术，随后引发了序列比对速度跟不上序列产生速度的问题。针对这一问题，本文开展了基于SOPC的Smith-Waterman基因序列比对算法硬件加速器的设计实现工作，该研究利用Smith-Waterman算法原理与脉动阵列思想相结合的方法，基于SOPC硬件系统实现算法的高速完成，解决了上述的速度失配问题，具有十分重要的工程应用价值。 本文首先对基因数据处理流程进行分析，提取其关键步骤，通过对处理模型进行特征分析，得出其中序列比对环节耗时最严重的结论；随后制定Smith-Waterman算法的硬件实现方案，利用算法的结果矩阵反对角线的并行性，在电路上结合脉动阵列思想，提出了适用于SOPC硬件系统的并行处理方案；进而搭建Smith-Waterman算法的硬件加速器，采用行为级建模算法的阵列控制器、处理单元阵列、序列补给、回溯等模块，并完成模块仿真；搭建Smith-Waterman算法的软件处理平台，使用C语言（MFC控件）开发出序列比对算法程序，以此平台来检验硬件加速器的仿真正确性；最后下板验证硬件加速器的实际加速效果，基于团队自主研发的SOPC硬件开发平台，利用其动态可重构的功能，实现不同算法类型之间的快速切换。 实验结果表明，本设计中Smith-Waterman算法硬件化系统可以实现40×50bp规模的短序列比对，将算法硬件加速器与算法软件平台的运行时间和比对结果进行比较，可以发现二者比对结果吻合，并且完成一次序列比对硬件系统所需时间是软件程序的1/40，最终硬件加速器实现了Smith-Waterman算法的高速完成，达到了设计之初的目的。

目录

声明

第一章 绪论

1.1 课题研究的来源及背景

1.2 课题研究的目的及意义

1.3 课题国内外研究现状

1.4 主要工作和文章结构

第二章 生物信息计算及并行化研究

2.1 生物信息学

2.1.1 生物信息学简介

2.1.2 生物的遗传和变异

2.1.3 人类基因组计划

2.2 序列比对

2.2.1 序列比对基本原理

2.2.2 动态规划算法基本原理

2.2.3 Needleman-Wunsch全局比对算法介绍

2.2.4 Smith-Waterman局部比对算法介绍

2.2.4 多序列比对

2.3.1 算法计算特征分析

2.3.2 算法并行化实现原理

2.3.3 辅助矩阵分块与删减原理

2.4 序列比对算法复杂度分析

2.5 本章小结

第三章 Smith-Waterman算法并行化实现

3.1 SOPC系统介绍

3.1.1 SOPC芯片架构介绍

3.1.2 SOPC硬件系统介绍

3.1.3 SOPC系统特点介绍

3.2 Smith-Waterman算法的软件实现

3.2.1 算法软件开发思路分析

3.2.2 算法软件程序设计实现

3.2.3 算法软件界面设计实现

3.3 Smith-Waterman算法的硬件实现

3.3.1 算法硬件加速器架构分析

3.3.2 算法硬件加速器模块分析

3.3.3 算法硬件加速器分块计算分析

3.4 本章小节

第四章 系统测试与比对结果分析

4.1.1 测试原理

4.1.2 测试结果分析

4.2.1 测试原理

4.2.2 测试结果分析

4.3 本章小结

第五章 总结与展望

5.1 工作总结

5.2 不足与展望

致谢

参考文献

攻读硕士学位期间取得的成果