基因序列比对Myers算法的FPGA实现
发布时间：2022-01-17 18:16
上个世纪末到21世纪初,随着人类的基因组计划和各类基因工程的深入实施,生物信息数据正以指数级的速度增加。这些生物信息将影响着药学、医学、农业和环保等方面的研究与发展,还有助于人们提高生活质量。其民用的一种主要技术是基因测序。基因测序作为一种新型基因检测技术,能够从血液或唾液中提取基因全序列,对这些基因全序列进行测定,从而分析出基因数据中携带疾病的可能性,进而提出科学的指导,以使其得到正确地治疗。在应用价值上,基因测序速度的加快,能够更快地找出疾病,这样能获得充足的时间用于治疗阶段,最终提高癌症治愈率和出生儿缺陷,可提高人类健康水平。通过分析各个序列比对的计算原理和速度,本文提出Myers算法作为基因测序中的全局序列比对算法,并在FPGA平台上实现进行加速,从而加速基因测序速度。通过对Myers算法中的PE模块电路进行分析,对关键电路进行优化,减少电路延时,使得整个系统的时钟频率得以提升,用来提高系统的计算量。系统测试结果表明,本系统运行于基于KCU1500实验平台的时钟频率可以达到181MHz,且每秒可以处理7032万对基因序列,为在CPU平台上运行速度的56倍。本文主要的研究内容和完...
【文章来源】：深圳大学广东省
【文章页数】：57 页
【学位级别】：硕士
【部分图文】：
KCU1500实验平台该实验平台只需要插入带有PCIe接口的电脑上即可使用，无需额外的电路辅助
基因序列比对Myers算法的FPGA实现33图5-4C代码随机产生测试的数据图5-4中的第一行数据是待检测基因序列的结构数据，所以第一个Byte的最高位是1。第二个Byte是表示待检测基因序列的长度，接着的四个Byte是待检测基因序列中文件的位置，按照顺序增加。剩下的数据是待检测基因序列，每两位代表基因序列的一个碱基。第二行数据是候选基因序列的结构数据，所以第一个Byte的最高位为0，ID号与待检测基因序列的一样，即0x01。第二个Byte是染色体编号，这不影响计算和验证结果，这里设定为固定值0x01。接着的四个Byte是基因库的位置，这个信息也不会影响结果，所以用来计数每个待检测基因序列的候选基因序列的个数。后面的基因序列为候选基因序列，与待检测基因序列一样，每两位表示一个碱基，但其长度比待检测基因序列的长度多两个，这是为了防止基因进行了突变，出现‘-’空位，而导致计算出来的结果会有差别。后面几行的数据信息跟前面的信息一样，只是运算到下一个待检测基因序列，ID号就会增加，用来标志为不同的待检测基因序列。从图5-4中还可以得知，第1条待检测基因序列有1条候选基因序列；第2条待检测基因序列同样有1条候选基因序列；第3条待检测基因序列有4条候选基因序列；第4、5条待检测基因序列都有6条候选基因序列。这可以得出PC端产生的数据具有随机性。经过Myers算法计算，PC端得出对应序列比对的得分结果如图5-5所示。
基因序列比对Myers算法的FPGA实现34图5-5随机产生数据的Myers算法结果从图5-5中得知，由于这些数据是随机产生的，因此相似度并不高，导致计算的结果得分值较高，而基因测序中两条相似度较高的基因序列比对的得分会较低。在Vivado软件上，使用PC端产生的数据，对Myers模块进行仿真，截取PEArray模块仿真的结果如图5-6所示。从图中得出，虽然输入的数据并没有全部连续，即有些连续，有些不连续，但可以看到结果的输出时序与数据的输入时序一样，即Val_o信号跟Val_i信号的波形一样，相当于数据进行若干个时钟计算后，计算的结果还是一个时钟接着一个时钟依次输出的。图5-6仿真结果输入的数据不连续是因为读取到待检测基因序列时，需要花费一个时钟周期，而此时因为没有对应的候选基因序列，所以该时钟周期没有参与计算。但在基因测序中，由于一条待检测基因序列至少有几万条候选基因序列，甚至高达几十万条基因序列，所以相对于几万个时钟和几十万个时钟来说，花费的这个时钟基本可以忽略。因此这个系统的计算等同于每个时钟可以计算一对基因序列对，即计算出一条待检测基因序列和一条候选基因序列的比对结果。为了验证数据的正确性，对仿真的得分结果进行放大，如图5-7所示。其中当val_o信号为1时，此刻的输出得分才有效，反之是一个随机数，没有实际意义。
【参考文献】：
期刊论文
[1]基于FPGA实现快速矩阵求逆算法[J]. 张繁,何明亮. 通信技术. 2020(02)
[2]基于高通量测序技术研究黄栌根际土壤微生物多样性[J]. 周江鸿,夏菲,车少臣,葛雨萱,周肖红. 园林科技. 2019(03)
[3]基于高通量测序技术研究黄栌根际土壤微生物多样性[J]. 周江鸿,夏菲,车少臣,葛雨萱,周肖红. 园林科技. 2019 (03)
[4]基于动态规划的双序列比对算法构件设计与实现[J]. 石海鹤,周卫星. 计算机研究与发展. 2019(09)
[5]面向嵌入式FPGA的高性能卷积神经网络加速器设计[J]. 曾成龙,刘强. 计算机辅助设计与图形学学报. 2019(09)
[6]高通量基因测序技术在胎儿性染色体非整倍体检测中的应用[J]. 蔡海英,许华英,熊卿圆. 中国现代药物应用. 2019(15)
[7]产前筛查及无创基因测序技术在胎儿出生缺陷中的诊断效果及对妊娠结局的影响研究[J]. 王新玲,尹璐,段雅. 中国优生与遗传杂志. 2019(07)
[8]Smith-Waterman算法优化改进与Spark并行化研究[J]. 李雷孝,刘燕凤,高静. 内蒙古农业大学学报(自然科学版). 2019(05)
[9]高通量基因测序技术检测外周血循环肿瘤DNA基因突变在非小细胞肺癌中的应用[J]. 吕爽,李卉,巴雅力格,孙岩岩,呼群. 现代肿瘤医学. 2019(13)
[10]Needleman-Wunsch算法的改进[J]. 张玉虎,周正. 火力与指挥控制. 2019(05)
博士论文
[1]生物信息学中多序列比对等算法的研究[D]. 张敏.大连理工大学 2005
[2]生物信息学中的序列比对算法研究[D]. 唐玉荣.中国农业大学 2004
硕士论文
[1]高通量测序数据集的短读序列比对算法研究[D]. 孙继鹏.西安电子科技大学 2019
[2]基于SOPC的Smith-Waterman算法硬件加速器的设计与实现[D]. 王刚.电子科技大学 2019
[3]双序列比对Needleman-Wunsch算法研究[D]. 姜鲜桃.内蒙古农业大学 2017
[4]Smith-Waterman算法硬件加速的研究与实现[D]. 陈观君.电子科技大学 2017
[5]双序列比对Needleman-Wunsch算法的分布式并行优化研究[D]. 冯百龙.内蒙古农业大学 2015
[6]生物序列比较算法的研究[D]. 郭晓冬.杭州电子科技大学 2012
本文编号：3595207
【文章来源】：深圳大学广东省
【文章页数】：57 页
【学位级别】：硕士
【部分图文】：
KCU1500实验平台该实验平台只需要插入带有PCIe接口的电脑上即可使用，无需额外的电路辅助
基因序列比对Myers算法的FPGA实现33图5-4C代码随机产生测试的数据图5-4中的第一行数据是待检测基因序列的结构数据，所以第一个Byte的最高位是1。第二个Byte是表示待检测基因序列的长度，接着的四个Byte是待检测基因序列中文件的位置，按照顺序增加。剩下的数据是待检测基因序列，每两位代表基因序列的一个碱基。第二行数据是候选基因序列的结构数据，所以第一个Byte的最高位为0，ID号与待检测基因序列的一样，即0x01。第二个Byte是染色体编号，这不影响计算和验证结果，这里设定为固定值0x01。接着的四个Byte是基因库的位置，这个信息也不会影响结果，所以用来计数每个待检测基因序列的候选基因序列的个数。后面的基因序列为候选基因序列，与待检测基因序列一样，每两位表示一个碱基，但其长度比待检测基因序列的长度多两个，这是为了防止基因进行了突变，出现‘-’空位，而导致计算出来的结果会有差别。后面几行的数据信息跟前面的信息一样，只是运算到下一个待检测基因序列，ID号就会增加，用来标志为不同的待检测基因序列。从图5-4中还可以得知，第1条待检测基因序列有1条候选基因序列；第2条待检测基因序列同样有1条候选基因序列；第3条待检测基因序列有4条候选基因序列；第4、5条待检测基因序列都有6条候选基因序列。这可以得出PC端产生的数据具有随机性。经过Myers算法计算，PC端得出对应序列比对的得分结果如图5-5所示。
基因序列比对Myers算法的FPGA实现34图5-5随机产生数据的Myers算法结果从图5-5中得知，由于这些数据是随机产生的，因此相似度并不高，导致计算的结果得分值较高，而基因测序中两条相似度较高的基因序列比对的得分会较低。在Vivado软件上，使用PC端产生的数据，对Myers模块进行仿真，截取PEArray模块仿真的结果如图5-6所示。从图中得出，虽然输入的数据并没有全部连续，即有些连续，有些不连续，但可以看到结果的输出时序与数据的输入时序一样，即Val_o信号跟Val_i信号的波形一样，相当于数据进行若干个时钟计算后，计算的结果还是一个时钟接着一个时钟依次输出的。图5-6仿真结果输入的数据不连续是因为读取到待检测基因序列时，需要花费一个时钟周期，而此时因为没有对应的候选基因序列，所以该时钟周期没有参与计算。但在基因测序中，由于一条待检测基因序列至少有几万条候选基因序列，甚至高达几十万条基因序列，所以相对于几万个时钟和几十万个时钟来说，花费的这个时钟基本可以忽略。因此这个系统的计算等同于每个时钟可以计算一对基因序列对，即计算出一条待检测基因序列和一条候选基因序列的比对结果。为了验证数据的正确性，对仿真的得分结果进行放大，如图5-7所示。其中当val_o信号为1时，此刻的输出得分才有效，反之是一个随机数，没有实际意义。
【参考文献】：
期刊论文
[1]基于FPGA实现快速矩阵求逆算法[J]. 张繁,何明亮. 通信技术. 2020(02)
[2]基于高通量测序技术研究黄栌根际土壤微生物多样性[J]. 周江鸿,夏菲,车少臣,葛雨萱,周肖红. 园林科技. 2019(03)
[3]基于高通量测序技术研究黄栌根际土壤微生物多样性[J]. 周江鸿,夏菲,车少臣,葛雨萱,周肖红. 园林科技. 2019 (03)
[4]基于动态规划的双序列比对算法构件设计与实现[J]. 石海鹤,周卫星. 计算机研究与发展. 2019(09)
[5]面向嵌入式FPGA的高性能卷积神经网络加速器设计[J]. 曾成龙,刘强. 计算机辅助设计与图形学学报. 2019(09)
[6]高通量基因测序技术在胎儿性染色体非整倍体检测中的应用[J]. 蔡海英,许华英,熊卿圆. 中国现代药物应用. 2019(15)
[7]产前筛查及无创基因测序技术在胎儿出生缺陷中的诊断效果及对妊娠结局的影响研究[J]. 王新玲,尹璐,段雅. 中国优生与遗传杂志. 2019(07)
[8]Smith-Waterman算法优化改进与Spark并行化研究[J]. 李雷孝,刘燕凤,高静. 内蒙古农业大学学报(自然科学版). 2019(05)
[9]高通量基因测序技术检测外周血循环肿瘤DNA基因突变在非小细胞肺癌中的应用[J]. 吕爽,李卉,巴雅力格,孙岩岩,呼群. 现代肿瘤医学. 2019(13)
[10]Needleman-Wunsch算法的改进[J]. 张玉虎,周正. 火力与指挥控制. 2019(05)
博士论文
[1]生物信息学中多序列比对等算法的研究[D]. 张敏.大连理工大学 2005
[2]生物信息学中的序列比对算法研究[D]. 唐玉荣.中国农业大学 2004
硕士论文
[1]高通量测序数据集的短读序列比对算法研究[D]. 孙继鹏.西安电子科技大学 2019
[2]基于SOPC的Smith-Waterman算法硬件加速器的设计与实现[D]. 王刚.电子科技大学 2019
[3]双序列比对Needleman-Wunsch算法研究[D]. 姜鲜桃.内蒙古农业大学 2017
[4]Smith-Waterman算法硬件加速的研究与实现[D]. 陈观君.电子科技大学 2017
[5]双序列比对Needleman-Wunsch算法的分布式并行优化研究[D]. 冯百龙.内蒙古农业大学 2015
[6]生物序列比较算法的研究[D]. 郭晓冬.杭州电子科技大学 2012
本文编号：3595207
本文链接：https://www.wllwen.com/kejilunwen/dianzigongchenglunwen/3595207.html
