一、Smith-Waterman算法在脉动阵列上的实现及分析（论文文献综述）
田英轩[1]（2020）在《基于GPU加速的BWA-MEM核心算法研究》文中研究指明基因技术的进步,对医药研发、个体健康等诸多领域具有深远影响,因此也催生了大量重要相关技术,基因比对就是其中之一。作为基因工程技术与计算机技术的结合领域,基因比对技术的主要通过计算设备,将大量无序基因序列匹配到标准基因组上,为分析生物特征提供关键数据。这对研究生物个体、种族、群落的基因特性具有重要意义,对探索未知生物信息具有深远影响。本文以Illumina公司的基因测序解决方案为基本标准,以100bp-200bp长度的碱基序列为对象,基于BWA-MEM算法和GPU异构计算平台展开研究。随着检测技术的提升,个体基因数据规模上升,这使比对算法对时效性有了更高的要求。由于传统算法难以满足个人快速检测要求,制约了相关技术的进一步应用落地,因此本文提出基于GPU的并行化加速方案。制约比对速度的主要矛盾在两方面:CPU计算能力的局限性和BWA-MEM算法固有的冗余性。围绕这两点问题,本文通过分析GPU编程中涉及到的软硬件结构,提出算法优化逻辑及实现并行方案。通过CPU+GPU混合异构编程,在任务间及任务内两个角度,对算法进行并行加速,实现效率提升。完成异构编程的工作主要有两方面:首先,在inter task维度实现任务间并行。根据基因序列的一致性原则,通过提升并行处理的任务规模,减少CPU与GPU之间的访存次数,为保证各任务间合并访存,通过设计流处理方案和扁平化数据结构,实现不同计算资源对数据的合并存取操作。同时,在intratask维度实现任务内并行。任务内并行主要分为两部分:精确比对算法（exact match algorithm）以及非精确比对算法（inexact match algorithm）。精确比对算法的核心是SMEM算法,优化上一方面通过算法级优化降低算法复杂度,另一方面通过细粒度并行对提升实现效率。非精确比对算法的核心是S-W算法,通过异步启动的方式实现warp内算法并行,合理利用高速访存以提升算法性能。本文通过任务间+任务内的方式设计了 BWA-MEM算法的并行实现模型。一方面研究GPU设备上的异构编程,另一方面通过统一计算架构（CUDA）完成软件设计。通过硬件、软件资源的彼此兼顾,有效提升了算法的比对性能。最后通过实验验证并行加速效果显着。
张琦[2]（2020）在《基于脉动阵列的广义相关系数计算方法研究与设计》文中研究指明相关分析起源于统计学时期,发展到至今仍然是一个热门的研究方向,通常使用相关系数作为衡量两个随机变量或两路信号之间的关系强弱指标。在众多的相关系数之中,其中皮尔逊积矩相关系数、斯皮尔曼相关系数、肯德尔相关系数研究的最为完善和应用的最广,并且使用的场景也不同。理论研究表明,皮尔逊积矩相关系数对具有非线性变换或者脉冲噪声的数据异常的敏感,但是斯皮尔曼和肯德尔系数对非线性变换或者脉冲噪声的数据就很不敏感具有良好的稳健性,所以数据存在非线性变换或者脉冲噪声时可以考虑选用后面两种相关系数。研究人员发现这几种相关系数有着内在的联系,提出了广义相关系数来概括这三种相关系数,分别输入不同的数据就可以推导出不同的相关系数。随着大数据时代的到来,需要处理的数据也日益增多,给相关系数的计算带了巨大的挑战。而脉动阵列架构在各种对大数据的并行计算的专用运算处理器中受到广泛的应用。受上述几方面的影响,本文提出一种基于脉动阵列对广义相关系数部分计算统一实现的电路。并做了以下几个方面的工作。1、通过对脉动阵列架构计算与CPU、GPU计算进行比较,最终选择FPGA作为脉动阵列电路的实现工具,并且通过详细分析矩阵相乘的例子,说明了使用具有并行性和流水线性的脉动阵列架构来进行实现框架的重要性。2、根据广义相关系数表达式对三种相关系数的定义表达式等价变换成相同的结构,发现分子、分母在运算实现的过程上非常相似并且运算独立,可以进行并行实现。从而提出了一种广义相关系数部分运算的统一实现的电路,可以灵活的切换求解不同的相关系数。3、使用硬件编程语言在FPGA相关软件平台上搭建出基于脉动阵列的广义相关系数部分运算的电路,分别在三种相关系数模式下进行仿真实验。在实验中得出两点主要结论:一、本文提出的基于脉动阵列的相关系数专用计算电路具有灵活性、并行性、流水线性特点。二、能够快速计算出两组随机数据中局部数据的相关性。
周智[3]（2020）在《应用于基因测序的Smith-Waterman算法的研究及FPGA实现》文中指出基因测序是生物信息学领域中重要的基础性问题,主要是获取基因序列中的信息,进行基因测序的根本方法是基因序列比对。目前,基因序列比对在临床医学上有着十分重要的作用,分析人类基因信息,可为医生在诊断,治疗病人时,提供极大的参考,也可以为人们预防疾病提供帮助。随着新一代测序仪器与测序技术的快速发展,基因测序的成本大大降低,基因数据库中的碱基数量大幅度增加。进行基因序列比对需要分析的碱基数量出现了极大的增长,而现有的计算资源与序列比对算法的计算速度,已经难以匹配目前基因测序数据数量的增长速度,导致出现速度失配问题。针对这一问题,本文提出了一种基于CPU-FPGA的Smith-Waterman算法的硬件加速方案。本设计对Smith-Waterman算法的计算原理进行分析,根据该算法在碱基序列计算得分的过程中,反对角线上的数据互不依赖的特征,结合动态规划思想,在序列打分部分提出了并行循环计算方案。在回溯部分,使用两个BRAM阵列,使保存回溯路径和回溯可同时进行。本文基于CPU+FPGA的异构平台,采用Open CL标准,实现该算法的硬件加速,解决了序列比对的速度失配问题。在实现整个系统的过程中,通过PCIe将测试数据传输到FPGA中的DDR中,再通过AXI总线传输到该算法的FIFO中存储,根据指令读取数据,进行运算。该算法包括数据写入模块、控制模块、数据暂存模块、数据传输模块、初始值模块、PE阵列模块、分数暂存比较模块、回溯模块以及数据输出模块。在Xilinx的SDAccel开发环境下,使用C语言完成该系统的控制部分,用verilog语言实现该算法模块并完成仿真。使用matlab语言开发该算法的序列比对得分部分,以此验证序列比对得分硬件仿真结果的正确性。硬件仿真完成后,生成比特流文件,配置到FPGA中完成运算。实验结果表明,本设计使用CPU+FPGA的异构硬件平台,成功实现Smith-Waterman算法的硬件加速,得出了正确的最优局部序列对以及对应的最大得分,实现的速度为302.6 GCUPS,与实现该算法的其他方案对比,本设计提高了该算法的运算速度。
朱高昂[4]（2020）在《Smith Waterman基因测序算法的改进与硬件加速方法的研究》文中提出自本世纪以来,随着基因测序技术的快速发展,对个人进行基因测序的成本大幅度下降,从而导致基因测序的数据量飞速增长,使得当前对基因数据进行分析的速度已经无法和基因数据产出的速度相匹配,出现了失配现象,因此本文对基因测序中常用的Smith Waterman算法进行改进及对硬件加速进行研究。本文从该算法的研究背景和研究意义着手,概述了基因测序的基本原理。通过对Smith Waterman算法进行深入剖析,对其进行优化改进:首先根据该算法初始化矩阵的特性,从算法的原理上对其进行改进,减少了二维动态矩阵的打分步骤,从而降低了算法的复杂度;其次利用该算法的二维动态矩阵的反对角线上的元素之间没有依赖关系的特征,并结合脉动阵列的思想,使该算法可在硬件上实现并行化;然后通过矩阵的分块和删减策略对硬件系统进行优化以及缩减硬件系统的计算量,从而实现该算法的并行化改进;最后设计了符合并行化要求的FPGA测序平台。通过对改进前后的Smith Waterman算法进行仿真,结果证明经过本文改进后的算法对同等规模的基因序列的测序时间明显变短,提升了运算效率,因此本论文的算法改进方案可行。
王刚[5]（2019）在《基于SOPC的Smith-Waterman算法硬件加速器的设计与实现》文中进行了进一步梳理近年来,生物信息学在不断地发展并成为一门重要的学科,国内许多高校和科研院所都在大力发展这一方面的技术,使其有了突飞猛进的发展,并且以大数据为基础的精准医疗将成为我国“十三五”期间重点发展的科学领域,这样使得生物信息学领域更受关注。生物序列分析是现代生命科学领域中重要的基础性研究工作,而进行序列分析的根本就是序列比对。目前美国已经建立起100万人的基因数据库,预计我国的基因数据库将远超此量级,并且伴随着新一代测序技术的迅速发展,所需比对分析的序列数量出现了爆炸性增长的趋势,但在现如今的序列比对技术当中,已经难以找出匹配序列数量迅速增快的技术,随后引发了序列比对速度跟不上序列产生速度的问题。针对这一问题,本文开展了基于SOPC的Smith-Waterman基因序列比对算法硬件加速器的设计实现工作,该研究利用Smith-Waterman算法原理与脉动阵列思想相结合的方法,基于SOPC硬件系统实现算法的高速完成,解决了上述的速度失配问题,具有十分重要的工程应用价值。本文首先对基因数据处理流程进行分析,提取其关键步骤,通过对处理模型进行特征分析,得出其中序列比对环节耗时最严重的结论;随后制定Smith-Waterman算法的硬件实现方案,利用算法的结果矩阵反对角线的并行性,在电路上结合脉动阵列思想,提出了适用于SOPC硬件系统的并行处理方案;进而搭建SmithWaterman算法的硬件加速器,采用行为级建模算法的阵列控制器、处理单元阵列、序列补给、回溯等模块,并完成模块仿真;搭建Smith-Waterman算法的软件处理平台,使用C语言（MFC控件）开发出序列比对算法程序,以此平台来检验硬件加速器的仿真正确性;最后下板验证硬件加速器的实际加速效果,基于团队自主研发的SOPC硬件开发平台,利用其动态可重构的功能,实现不同算法类型之间的快速切换。实验结果表明,本设计中Smith-Waterman算法硬件化系统可以实现40×50bp规模的短序列比对,将算法硬件加速器与算法软件平台的运行时间和比对结果进行比较,可以发现二者比对结果吻合,并且完成一次序列比对硬件系统所需时间是软件程序的1/40,最终硬件加速器实现了Smith-Waterman算法的高速完成,达到了设计之初的目的。
徐逸卿[6]（2018）在《林木系统发育的计算技术优化研究》文中研究说明近年来,随着高通量测序技术的迅猛发展,生物数据的存储与管理的规模在不断扩大,各种类型的生物数据成爆炸式增长,逐渐形成了“序列-染色体-全基因组”的不同规模层次的基因数据,林木作为重要的研究对象,其基因学研究也跨入了大数据时代。为了充分存储、管理、挖掘这些海量数据中蕴含的生物信息,在对国内外的研究现状进行分析的基础上,本文利用生物信息学方法以及大数据技术对林木基因组学数据进行了深度挖掘,主要工作和创新如下:1.基于位置特征的序列比对算法及其在遗传功能特征预测中的应用在微观的分子层面,序列比对技术是基因同源性分析的基础,根据基因之间同源性可以获得物种之间的系统发育学关系。为了研究林木的系统发育学关系,本文首次提出一种改进的基于位置特征的序列比对算法——LB-BLAST,并利用该算法结合模式植物拟南芥的完整注释信息,通过同源性匹配原则,首次预测了簸箕柳基因组中相应的遗传功能特征。与传统的BLAST序列比对算法相比,LB-BLAST算法在保证精度的基础上,利用基因之间的位置信息对比对结果进行约束,显着降低了算法的时间复杂度。此外,本文还成功利用LB-BLAST分析了杨树和柳树在进化过程中染色体的断裂和融合现象,给未来的林木进化分析提供了重要的参考。2.林木基因组同源性分析算法及其在林木系统发育中的应用在染色体层面,针对林木基因组种间差异大,生物多样性强的特征,提出一种新的基因同源性分析作图算法,并结合LB-BLAST搭建基因同源性分析的在线平台——VGSC,首次以在线服务的形式对同源物种的基因进行比对,将林木基因组的共线性关系快速高效地转换为可视化的图形,包括点阵图、双重线性图、条状图和圆型图。该分析作图算法结合了矢量图形方向无关性、尺寸无关性的特点,为分析林木基因组的种间关系以及种内基因特征提供了快捷准确的表达基础。利用该方法对簸箕柳的WRKY基因家族进行了进化分析,发现柳树中的WRKY基因家族主要以片段复制的模式在染色体中扩增,只有少数的基因发生了串联复制,表明WRKY基因在簸箕柳中很少出现共表达或者抑制事件,而是分散在不同的染色体上起调控作用。同时,这为验证高等植物在进化过程中发生过两次大规模的染色体复制事件提供了佐证。同时,由于该方法数据结果表达的通用性和易编辑性,特别适用于对高通量测序结果的分析作图研究,因此自发表以来在藜麦、柳树、千惠谷等众多国内外关键性研究中起到了重要的支持作用。3.面向林木细胞器基因组的系统发育树生成方法在全基因组层面,利用植物细胞器基因组在系统发育学上的同源性高度一致的优势,设计了一套新的基于大数据的植物细胞器基因组数据抽取、清洗与可视化方法,并结合不同细胞器的特征设计并实现了面向不同细胞器基因组的系统发育树生成算法,其中:叶绿体基因组中的16S及23S核糖体RNA基因序列长度较长,存在明显的保守区与多变区,是构建叶绿体系统发育树的较好选择,提出了一种基于叶绿体16S或23S rRNA基因快速构建系统发育树的方法;线粒体基因组存在于大多数真核生物中,不但可以用于林木之间的系统发育结构,还可以用于与其他生物的比较基因组学研究,提出了线粒体ORF识别算法以及基于线粒体保守基因的系统发育树构建算法。最终,基于上述全新的方法本文构建了一套面向林木细胞器基因组的系统发育学分析平台,以研究林木之间及林木与其他物种之间的进化关系。综上所述,本文以林木系统发育学研究为目标,由微观到宏观构建了在三个层次提出了对现有林木系统发育学研究的计算优化方案,LB-BLAST首次利用引入序列位置的限制条件优化了微观序列比对,VGSC优化了物种种间和种内同源性分析作图方法,OGTree则第一次在宏观上综合利用大数据技术实现了林木系统进化分析的计算系统,并成功的将这些方法应用于林木基因组研究。
兰海东[7]（2018）在《混合异构架构上的生物大数据并行计算研究》文中提出本文主要的研究内容是生物大数据在多种高性能异构计算架构下的并行计算方法,主要解决了三方面的挑战:（ⅰ）在有限的内存空间中对大规模数据集执行计算的方法,（ⅱ）基于异构计算的多层级的算法并行化设计方法和（ⅲ）对不同架构计算设备的硬件抽象建模方法。在这三方面的研究中,抽象硬件模型是最重要的贡献,提供了一个良好的抽象硬件底层,将框架设计和具体硬件分离,简化了软件框架,可以使软件框架快速扩展覆盖多种硬件架构,并能够以简便抽象的方式控制内存布局。同时提供了一个简化的硬件视角,抽象出影响性能的关键因素,进而在此基础上设计效率更高的并行方法。由于高通量测序技术的快速进展,在过去的十年中,生物序列数据的数量出现了爆炸性增长。生物学家存在分析和理解这些数据的强烈需求,因为基因序列决定了蛋白质的生物结构以及功能。但是,生物数据的可用性并不随着数据库的膨胀而增加。事实上,目前生物数据库的数据量如此之大以至于传统的数据分析方法已不足以快速执行涉及多种数据类型的生命科学查询。另一方面,近年来的计算力增长主要体现在新兴体系结构上,如GPU,Xeon Phi和基于Alpha指令集的国产申威众核处理器上。新兴体系结构呈现如下两方面的趋势:异构化和众核化。其中异构化意味着系统中可能存在多种架构的芯片,每种芯片均为特定的任务设计以提升能效。众核化是由于处理器的顺序执行性能的提升遇到瓶颈,转而增加核心数目,提升并行计算能力。因此传统计算方法面临数据规模和架构变化两方面的挑战。在数据规模方面,本文提出了一种异步执行的方法,利用数据/任务的并行特性进行切分,通过分批处理其数据/任务子集,构建处理流水,从而实现了在少量内存占用的基础上,执行对大规模数据集的计算。异步执行方法具备良好的可扩展性,本文分别展示了将成对序列比对和多序列比对两类问题分别扩展到大规模数据集和计算集群上的方法,在同样的硬件设备上成功处理了其他生物序列计算工具无法处理的大数据集,并得到了比小数据集上更高的计算效率。在异构计算方面,本文展示了基于Xeon Phi与CUDA异构架构和Knights Landing众核同构架构的多层级并行优化方法。对硬件的架构特点进行了探索并建立了理论性能模型,在理论性能模型的指导下发展了对一大类动态规划算法适用的高效并行化方法。特别的,在Xeon Phi平台上我发现并定位了关键的性能瓶颈,并通过重构计算顺序、解构数据依赖提升数据访问的局部性,大幅提升了缓存命中率,达到了该平台上目前最高的性能,并接近理论计算峰值。在设备抽象模型方面,本文首先从执行层面的角度统一了 SIMD与SIMT两类编程模型,并在该模型基础上将所涉及计算设备划分为低延迟顺序处理器和高通量向量处理器两大类。我基于统一的抽象设备模型对应设计了一组C++类层级,通过分析抽象计算设备的共性和特性,最小化架构特定部分的代码,并对架构共性的工作流程进行了高度优化,充分利用了异构架构中不同处理器的异步执行性能,并根据设备的抽象模型为系统中的每个计算设备提供理论上最优的数据布局和统一的数据访问接口。同时,抽象的设备模型有助于不同架构之间的核心计算函数与并行方法互相借鉴,进而在多种架构上达到更好的性能。在上述三方面的贡献的共同作用下,本文中的方法已经支持CUDA、KNC、SSE、AVX2、AVX512等架构与指令集,,并在上述架构与指令集上均能够超过其他最先进方法的性能。同时能够扩展到更多节点快速搜索接近40GB的蛋白质数据库,并具备扩展到更大数据库的能力。因此,本文所述的工作成功地解决了传统计算机算法算法和软件架构面对大规模数据集和新兴计算机体系结构的挑战,其方法可以扩展到更多算法与体系结构上。
陈观君[8]（2017）在《Smith-Waterman算法硬件加速的研究与实现》文中研究说明21世纪以来,计算机科学推动传统学科向前发展并不断形成新的学科,其中生物信息学就是一典型的学科,它对生物信息进行收集、处理、分析和解释,随着生命科学和信息技术的迅猛发展,尤其是信息技术中半导体技术的飞速发展,大大提高了传统生物学对生物数据的收集、分析、处理速度。分析序列的相似性是生物信息学当中最基本的问题,而分析序列相似性的最基本的方法是序列比对,序列比对是为确定两个或多个序列之间的相似性乃至于同源性,而将它们按照一定的算法排列得到结果的一个过程。比如有双序列比对、多序列比对,上述两种比对内部又分为全局比对和局部比对,涉及的处理算法有针对全局比对的Needleman-Wunsch算法和针对局部比对的Smith-Waterman算法、BLAST算法等,而涉及的工具软件主要有BWA,Bowtie,SOAP等。因为下一代测序技术的长足进步,大大降低了这十几年以来人类全基因组的测序成本,较低的测序成本导致测序数据的大量快速积累,而现有的计算资源以及计算速度已经跟不上测序数据的积累速度,因此数据生成与数据处理发生了矛盾,两者产生了速度失配的问题。为此,本论文立足于该矛盾,主要讨论了SmithWaterman算法在硬件平台的实现和加速处理。本论文首先对BWA-MEM软件进行解构,提取Smith-Waterman算法在BWA-MEM软件出现的位置,对算法如何被软件使用进行挖掘分析;同时探讨硬件加速平台的比较与选择;根据选择出的硬件平台的特点,进行硬件加速实现的具体策略研究,最终目标是将Smith-Waterman算法在目标硬件平台实现加速的定性与定量研究,并得出结论。鉴于本课题与相关公司的合作性质,本文的研究成果将为该公司产品的定型以及后续研究提供一定的参考。
朱香元,李仁发,李肯立,胡忠望[9]（2015）在《基于异构系统的生物序列比对并行处理研究进展》文中研究说明序列比对工作属于生物信息学的基础性研究领域。由于它具有应用广泛、计算复杂以及海量数据等特点,加之现在高性能计算的兴起,使得近年来序列比对并行处理技术快速发展。首先介绍了序列比对领域高性能计算的新进展,接着从体系结构特征入手对其研究进行分类,并对每类方法的实现细节和性能进行分析比较,从中不难看出访存控制、同步、数据交互以及算法可扩展性等问题均为目前基于异构系统的序列比对并行处理研究的关键点。最后,对该领域的未来研究方向进行了展望。
王涛[10]（2015）在《计算生物学中的高性能计算（Ⅱ）—序列分析》文中认为序列分析是高性能计算应用的一个重要方向。随着高通量测序技术的发展,基因数据呈现爆炸性增长,对高性能计算的需求也更加迫切。介绍了高性能计算在序列分析中的应用和序列分析算法的并行实现,包括序列比对、检索、重测序、拼接等。
二、Smith-Waterman算法在脉动阵列上的实现及分析（论文开题报告）
（1）论文研究背景及目的
此处内容要求：
首先简单简介论文所研究问题的基本概念和背景，再而简单明了地指出论文所要研究解决的具体问题，并提出你的论文准备的观点或解决方法。
写法范例：
本文主要提出一款精简64位RISC处理器存储管理单元结构并详细分析其设计过程。在该MMU结构中,TLB采用叁个分离的TLB,TLB采用基于内容查找的相联存储器并行查找,支持粗粒度为64KB和细粒度为4KB两种页面大小,采用多级分层页表结构映射地址空间,并详细论述了四级页表转换过程,TLB结构组织等。该MMU结构将作为该处理器存储系统实现的一个重要组成部分。
（2）本文研究方法
调查法：该方法是有目的、有系统的搜集有关研究对象的具体信息。
观察法：用自己的感官和辅助工具直接观察研究对象从而得到有关信息。
实验法：通过主支变革、控制研究对象来发现与确认事物间的因果关系。
文献研究法：通过调查文献来获得资料，从而全面的、正确的了解掌握研究方法。
实证研究法：依据现有的科学理论和实践的需要提出设计。
定性分析法：对研究对象进行“质”的方面的研究，这个方法需要计算的数据较少。
定量分析法：通过具体的数字，使人们对研究对象的认识进一步精确化。
跨学科研究法：运用多学科的理论、方法和成果从整体上对某一课题进行研究。
功能分析法：这是社会科学用来分析社会现象的一种方法，从某一功能出发研究多个方面的影响。
模拟法：通过创设一个与原型相似的模型来间接研究原型某种特性的一种形容方法。
三、Smith-Waterman算法在脉动阵列上的实现及分析（论文提纲范文）
（1）基于GPU加速的BWA-MEM核心算法研究（论文提纲范文）
| 摘要 |
| ABSTRACT |
| 符号对照表 |
| 缩略语对照表 |
| 第一章 绪论 |
| 1.1 研究背景及选题意义 |
| 1.2 GPU与CUDA研究概述 |
| 1.2.1 硬件结构分析 |
| 1.2.2 CUDA软件模型分析 |
| 1.3 国内外研究现状 |
| 1.4 研究内容及章节安排 |
| 1.4.1 主要研究内容 |
| 1.4.2 章节安排 |
| 第二章 BWA-MEM算法模型 |
| 2.1 引言 |
| 2.2 数据准备 |
| 2.2.1 基因测序序列 |
| 2.2.2 参考基因序列及BWT压缩模型 |
| 2.3 碱基比对算法 |
| 2.3.1 基于后缀树算法的精确比对 |
| 2.3.2 基于Smith Waterman算法的非精准比对 |
| 2.4 各模块耗时统计 |
| 2.5 本章小结 |
| 第三章 任务间数据并行框架 |
| 3.1 引言 |
| 3.2 测序序列数据池设计 |
| 3.3 cudaStream流处理方案 |
| 3.4 数据结构扁平化设计 |
| 3.5 运算效果提升 |
| 3.6 本章小结 |
| 第四章 任务内算法级并行 |
| 4.1 引言 |
| 4.2 精确比对算法并行化 |
| 4.2.1 SMEM的算法级加速 |
| 4.2.2 细粒度并行加速 |
| 4.2.3 精确比对优化小结 |
| 4.3 非精确比对算法并行化 |
| 4.4 算法评估 |
| 4.4.1 实验环境 |
| 4.4.2 加速效果分析 |
| 4.4.3 S-W算法加速实验 |
| 4.5 本章小结 |
| 第五章 总结与展望 |
| 5.1 本文工作总结 |
| 5.2 未来工作展望 |
| 参考文献 |
| 致谢 |
| 作者简介 |
（2）基于脉动阵列的广义相关系数计算方法研究与设计（论文提纲范文）
| 摘要 |
| ABSTRACT |
| 第一章 绪论 |
| 1.1 课题研究的背景及意义 |
| 1.2 国内外研究现状 |
| 1.2.1 相关系数的研究现状 |
| 1.2.2 脉动阵列的研究现状 |
| 1.3 论文的主要研究内容 |
| 1.4 本章小结 |
| 第二章 广义相关系数概述 |
| 2.1 相关系数定义 |
| 2.2 相关系数的性质及应用场景 |
| 2.3 广义相关系数介绍 |
| 2.4 本章小结 |
| 第三章 脉动阵列概述 |
| 3.1 脉动阵列介绍 |
| 3.1.1 线形脉动阵列 |
| 3.1.2 矩形脉动阵列 |
| 3.2 脉动阵列特点及应用场景 |
| 3.3 FPGA介绍 |
| 3.3.1 并行计算 |
| 3.3.2 流水线计算 |
| 3.4 本章小结 |
| 第四章 基于脉动阵列的广义相关系数分析 |
| 4.1 广义相关系数定义表达式分析 |
| 4.2 脉动阵列电路的设计与分析 |
| 4.2.1 运算单元电路设计与分析 |
| 4.2.2 整体脉动阵列电路设计与分析 |
| 4.3 本章小结 |
| 第五章 脉动阵列电路的仿真实现 |
| 5.1 实验平台的介绍 |
| 5.2 实验设计 |
| 5.2.1 运算单元电路验证实验 |
| 5.2.2 整体脉动阵列电路验证实验 |
| 5.3 实验结论 |
| 5.4 本章小结 |
| 总结与展望 |
| 参考文献 |
| 攻读硕士学位期间发表论文 |
| 致谢 |
（3）应用于基因测序的Smith-Waterman算法的研究及FPGA实现（论文提纲范文）
| 摘要 |
| Abstract |
| 第1章 绪论 |
| 1.1 课题研究背景 |
| 1.2 课题研究目的和意义 |
| 1.3 课题国内外研究现状 |
| 1.4 课题主要工作和论文结构 |
| 第2章 生物信息计算研究 |
| 2.1 生物信息学 |
| 2.1.1 生物信息学分析 |
| 2.1.2 生物信息学数据库 |
| 2.1.3 人类基因组计划 |
| 2.2 基因序列比对 |
| 2.2.1 基因序列比对原理 |
| 2.2.2 全局序列比对算法介绍 |
| 2.2.3 局部序列比对算法分析 |
| 2.3 基因序列比对算法分析 |
| 2.4 本章小结 |
| 第3章 Smith-Waterman算法的研究与分析 |
| 3.1 算法实现原理研究 |
| 3.2 算法开发思路分析 |
| 3.3 本章小结 |
| 第4章 Smith-Waterman算法的硬件加速方案实现 |
| 4.1 算法硬件加速平台 |
| 4.2 算法硬件加速架构设计 |
| 4.3 算法硬件加速模块设计 |
| 4.4 算法硬件加速计算分析 |
| 4.5 本章小结 |
| 第5章 系统测试与数据分析 |
| 5.1 开发环境与辅助工具 |
| 5.2 硬件资源使用分析 |
| 5.3 测试结果 |
| 5.4 加速效果比对 |
| 5.5 本章小结 |
| 第6章 总结与展望 |
| 6.1 工作总结 |
| 6.2 不足与展望 |
| 参考文献 |
| 指导教师对研究生学位论文的学术评语 |
| 深圳大学研究生学位〈毕业〉论文答辩委员会决议书 |
| 致谢 |
| 攻读硕士学位期间的学术成果 |
（4）Smith Waterman基因测序算法的改进与硬件加速方法的研究（论文提纲范文）
| 摘要 |
| Abstract |
| 第1章 绪论 |
| 1.1 研究目的与意义 |
| 1.2 国内外的研究现状及发展趋势 |
| 1.3 本文主要研究内容 |
| 第2章 基因测序的原理及常用算法 |
| 2.1 基因测序原理 |
| 2.1.1 生物信息学 |
| 2.1.2 基因序列对比 |
| 2.2 基因测序算法 |
| 2.2.1 Needleman Wunsch算法 |
| 2.2.2 Fasta算法 |
| 2.2.3 Blast算法 |
| 2.3 Smith Waterman算法 |
| 2.4 本章小结 |
| 第3章 Smith Waterman基因测序算法的改进 |
| 3.1 Smith Waterman算法的改进 |
| 3.2 算法改进前后的对比 |
| 3.3 算法的并行化改进 |
| 3.3.1 计算特征分析 |
| 3.3.2 并行化实现原理 |
| 3.4 矩阵分块与删减策略 |
| 3.5 本章小结 |
| 第4章 算法的硬件仿真与分析 |
| 4.1 基因测序平台的选取 |
| 4.2 整体架构框图 |
| 4.3 主要模块设计 |
| 4.3.1 PE阵列控制模块设计 |
| 4.3.2 PE阵列模块设计 |
| 4.3.3 回溯模块设计 |
| 4.4 实验与分析 |
| 4.5 本章小结 |
| 结论 |
| 参考文献 |
| 攻读学位期间发表的学术成果 |
| 致谢 |
（5）基于SOPC的Smith-Waterman算法硬件加速器的设计与实现（论文提纲范文）
| 摘要 |
| abstract |
| 第一章 绪论 |
| 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.5 多序列比对 |
| 2.3 Smith-Waterman算法的并行化理论分析 |
| 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 算法软件实现测试 |
| 4.1.1 测试原理 |
| 4.1.2 测试结果分析 |
| 4.2 算法硬件实现测试 |
| 4.2.1 测试原理 |
| 4.2.2 测试结果分析 |
| 4.3 本章小结 |
| 第五章 总结与展望 |
| 5.1 工作总结 |
| 5.2 不足与展望 |
| 致谢 |
| 参考文献 |
| 攻读硕士学位期间取得的成果 |
（6）林木系统发育的计算技术优化研究（论文提纲范文）
| 摘要 |
| Abstract |
| 术语表 |
| 第一章 绪论 |
| 1.1 研究背景及意义 |
| 1.2 国内外研究现状 |
| 1.2.1 生物信息学研究 |
| 1.2.2 林木物种的系统发育基因组学研究 |
| 1.2.3 生物大数据研究 |
| 1.3 论文主要研究内容 |
| 1.4 论文章节结构安排 |
| 第二章 序列比对算法及其在林木遗传功能特征预测中的应用 |
| 2.1 基因与遗传功能特征的关系 |
| 2.2 基因编码区及RNA位置特征 |
| 2.2.1 CDS基因编码区及其位置特征 |
| 2.2.2 典型的RNA及其位置特征 |
| 2.3 基因序列比对的匹配技术 |
| 2.3.1 点阵法 |
| 2.3.2 Needleman-Wunsch和 Smith-Waterman算法 |
| 2.3.3 FASTA算法 |
| 2.3.4 BLAST算法 |
| 2.4 基于位置的基因序列比对算法LB-BLAST |
| 2.5 实验设计 |
| 2.5.1 柳树模体及其位置特征 |
| 2.5.2 预测实验的设计与实现 |
| 2.6 预测结果与分析 |
| 2.6.1 模体预测结果 |
| 2.6.2 预测算法分析 |
| 2.7 LB-BLAST在林木系统发育学中的应用 |
| 2.8 本章小结 |
| 第三章 基因组同源性作图分析方法及在林木系统发育中的应用 |
| 3.1 基因同源性分析研究背景 |
| 3.1.1 比较基因组学 |
| 3.1.2 同源序列 |
| 3.1.3 共线性的概念及特征 |
| 3.1.4 常用的共线性分析算法及工具 |
| 3.2 基因同源性分析作图方法与实现 |
| 3.2.1 同源性分析的数据准备 |
| 3.2.2 基因同源性作图分析方法 |
| 3.2.3 基因同源性作图分析在线平台 |
| 3.3 基因组系统发育学中的同源性作图在林木和作物中的应用 |
| 3.3.1 面向林木基因家族系统发育学的基因同源性分析 |
| 3.3.2 藜麦基因组共线性分析 |
| 3.4 本章小结 |
| 第四章 面向林木细胞器基因组的系统发育学大数据分析 |
| 4.1 系统发育学研究 |
| 4.1.1 研究背景及意义 |
| 4.1.2 高等植物的细胞器基因组 |
| 4.1.3 常见的系统发育学算法 |
| 4.1.4 常见的系统发育学分析软件 |
| 4.2 常用的生物数据库 |
| 4.2.1 核酸序列数据库 |
| 4.2.2 蛋白质序列数据库 |
| 4.2.3 蛋白质结构数据库 |
| 4.2.4 其他生物分子数据库 |
| 4.3 基于大数据的林木细胞器基因组系统发育学方法研究 |
| 4.3.1 研究背景 |
| 4.3.2 整体架构 |
| 4.3.3 面向植物细胞器基因组的大数据构建 |
| 4.3.4 面向植物色素体基因组的系统发育分析 |
| 4.3.5 面向生物线粒体基因组的系统发育分析 |
| 4.3.6 基于细胞器基因组的数据分析 |
| 4.4 本章小结 |
| 第五章 总结和展望 |
| 5.1 全文总结 |
| 5.2 展望 |
| 参考文献 |
| 攻读博士期间论文发表情况 |
| 攻读博士期间参与的科研项目 |
（7）混合异构架构上的生物大数据并行计算研究（论文提纲范文）
| 摘要 |
| ABSTRACT |
| 第1章 绪论 |
| 1.1 研究背景及意义 |
| 1.2 研究现状与挑战 |
| 1.3 本文研究内容与创新点 |
| 1.4 本文组织结构和章节安排 |
| 第2章 高性能生物序列分析并行计算方法 |
| 2.1 生物数据分析算法 |
| 2.1.1 Smith-Waterman算法 |
| 2.1.2 ClustalW算法 |
| 2.1.3 启发式算法 |
| 2.1.4 最佳映射算法 |
| 2.1.5 全映射算法 |
| 2.2 高性能计算机的体系结构 |
| 2.2.1 CPU核心与向量处理单元 |
| 2.2.2 支持CUDA的异构计算 |
| 2.2.3 Xeon Phi |
| 2.3 并行计算语言 |
| 2.3.1 POSIX线程与OpenMP |
| 2.3.2 消息传递接口(MPI) |
| 2.3.3 CUDA与OpenCL |
| 2.3.4 SIMD扩展指令集 |
| 2.4 小结 |
| 第3章 基于Xeon Phi异构集群的并行大规模生物数据库搜索计算方法 |
| 3.1 引言 |
| 3.2 生物数据库搜索算法 |
| 3.3 基于Xeon Phi架构的多层级并行计算方法 |
| 3.3.1 设备层并行计算 |
| 3.3.2 线程级并行计算 |
| 3.3.3 VPU级并行计算 |
| 3.3.4 多遍搜索算法 |
| 3.4 基于Xeon Phi计算集群的并行计算方法 |
| 3.5 性能测试 |
| 3.5.1 单节点性能测试 |
| 3.5.2 集群性能测试 |
| 3.6 本章小结 |
| 第4章 基于Xeon Phi异构集群的并行多序列比对计算方法 |
| 4.1 引言 |
| 4.2 多序列比对问题与算法 |
| 4.3 异构并行计算框架设计与算法并行化方法 |
| 4.3.1 异构计算框架设计 |
| 4.3.2 算法向量化并行计算方法 |
| 4.4 基于集群的多序列比对并行计算方法 |
| 4.5 性能测试 |
| 4.5.1 测试平台 |
| 4.5.2 处理中等大小的数据集的性能 |
| 4.5.3 处理大规模数据集的性能 |
| 4.6 本章小结 |
| 第5章 基于混合异构架构优化蛋白质序列数据库搜索 |
| 5.1 引言 |
| 5.2 抽象机器模型与性能建模 |
| 5.3 通用异步并行计算框架设计 |
| 5.3.1 数据库划分 |
| 5.3.2 类层级设计 |
| 5.3.3 基类设计 |
| 5.3.4 负载均衡 |
| 5.4 面向架构的性能优化方法 |
| 5.4.1 CPU架构 |
| 5.4.2 针对Xeon Phi处理器的优化 |
| 5.4.3 针对基于CUDA的GPU的优化 |
| 5.5 性能评估 |
| 5.5.1 同构平台测试 |
| 5.5.2 异构平台测试 |
| 5.5.3 数据库读取效率测试 |
| 5.6 本章小结 |
| 第6章 总结与展望 |
| 参考文献 |
| 致谢 |
| 攻读学位期间发表的学术论文目录 |
| 攻读学位期间参与的科研项目 |
| 攻读学位期间获得的学校奖励列表 |
| 外文论文 |
| 学位论文评阅及答辩情况表 |
（8）Smith-Waterman算法硬件加速的研究与实现（论文提纲范文）
| 摘要 |
| abstract |
| 第一章 绪论 |
| 1.1 研究背景 |
| 1.2 国内外研究现状 |
| 1.3 研究意义 |
| 1.4 论文主要工作和组织安排 |
| 第二章 生物信息计算 |
| 2.1 生物信息学介绍 |
| 2.1.1 简介 |
| 2.1.2 细胞、氨基酸和蛋白质 |
| 2.1.3 染色体和DNA |
| 2.1.4 基因表达遗传与变异 |
| 2.1.5 人类基因组计划 |
| 2.2 序列比对的基本方法 |
| 2.2.1 序列的相似性 |
| 2.2.2 全局比对和局部比对 |
| 2.2.3 双序列比对 |
| 2.2.4 多序列比对 |
| 2.3 DNA测序 |
| 2.3.1 NGS流程 |
| 2.3.2 测序花费 |
| 2.4 生物信息学计算工具 |
| 2.4.1 计算平台 |
| 2.4.2 数据库 |
| 2.4.3 软件工具 |
| 2.5 本章小结 |
| 第三章 算法提取与研究 |
| 3.1 BWA简介 |
| 3.2 BWT和FM-INDEX |
| 3.2.1 BWT |
| 3.2.2 FM-index |
| 3.3 BWA-MEM解构 |
| 3.3.1 SMEM seeding |
| 3.3.2 Seed extension |
| 3.3.3 结果输出 |
| 3.4 BWA-MEM分析 |
| 3.5 算法计算特征分析 |
| 3.6 算法硬件化分析 |
| 3.6.1 算法并行化 |
| 3.6.2 矩阵删减与分块策略 |
| 3.6.3 矩阵回溯策略 |
| 3.7 本章小结 |
| 第四章 算法加速方案设计 |
| 4.1 硬件平台 |
| 4.2 算法硬件核设计 |
| 4.2.1 整体框图 |
| 4.2.2 PE阵列控制器 |
| 4.2.3 序列对齐模块 |
| 4.2.4 参数生成模块 |
| 4.2.5 序列补给模块 |
| 4.2.6 PE阵列 |
| 4.2.7 回溯模块 |
| 4.3 本章小结 |
| 第五章 设计仿真与验证 |
| 5.1 仿真平台与验证工具 |
| 5.2 验证电路 |
| 5.3 系统关键模块验证 |
| 5.3.1 PE工作控制信号仿真验证 |
| 5.3.2 PE计算数据正确性仿真验证 |
| 5.3.3 回溯结果正确性仿真 |
| 5.4 系统功能验证 |
| 5.5 加速效果对比 |
| 5.6 本章小结 |
| 第六章 总结和展望 |
| 6.1 总结 |
| 6.2 不足与展望 |
| 致谢 |
| 参考文献 |
| 攻读硕士学位期间取得的成果 |
（10）计算生物学中的高性能计算（Ⅱ）—序列分析（论文提纲范文）
| 1 引言 |
| 2 序列分析 |
| 2.1 双序列比对 |
| 2.2 多序列比对 |
| 2.3 数据库检索 |
| 2.4 重测序 |
| 2.5 基因组组装 |
| 3 结束语 |
四、Smith-Waterman算法在脉动阵列上的实现及分析（论文参考文献）
- [1]基于GPU加速的BWA-MEM核心算法研究[D]. 田英轩. 西安电子科技大学, 2020(05)
- [2]基于脉动阵列的广义相关系数计算方法研究与设计[D]. 张琦. 广东工业大学, 2020(06)
- [3]应用于基因测序的Smith-Waterman算法的研究及FPGA实现[D]. 周智. 深圳大学, 2020(10)
- [4]Smith Waterman基因测序算法的改进与硬件加速方法的研究[D]. 朱高昂. 哈尔滨理工大学, 2020(02)
- [5]基于SOPC的Smith-Waterman算法硬件加速器的设计与实现[D]. 王刚. 电子科技大学, 2019(01)
- [6]林木系统发育的计算技术优化研究[D]. 徐逸卿. 东南大学, 2018(01)
- [7]混合异构架构上的生物大数据并行计算研究[D]. 兰海东. 山东大学, 2018(12)
- [8]Smith-Waterman算法硬件加速的研究与实现[D]. 陈观君. 电子科技大学, 2017(03)
- [9]基于异构系统的生物序列比对并行处理研究进展[J]. 朱香元,李仁发,李肯立,胡忠望. 计算机科学, 2015(S2)
- [10]计算生物学中的高性能计算（Ⅱ）—序列分析[J]. 王涛. 计算机工程与科学, 2015(01)