李静[1]2003年在《基于动态规划进行双序列全局比对研究》文中研究表明序列比对分析是生物信息学研究中的一个基本内容。大多数序列比对软件以动态规划算法作为其空位插入的核心算法。然而，一个普遍的问题是目前常用的大部分序列比对算法虽能达到最优或近似最优的结果，但却均由于计算复杂度所导致的计算速度缓慢这一瓶颈而在应用上受到限制。虽然近年来由于算法自身的不断改进以及计算机科学的发展，其实现程序依靠计算机硬件和软件开发技术的提高得到了效率和精度上的改善，从而使现在应用广泛的序列比对或数据库搜索程序如Blast、FASTA、ClustalW等才获得了相对满意的计算效率，但是从理论基础和思想原理上改善序列比对算法以期降低计算复杂度，才是提高计算效率和精度的根本途径。目前随着各种基因组测序计划陆续完成，大量序列数据急剧增长，以序列比对为核心的数据分析任务对于高效率的序列比对算法的需求日益迫切。 基于段与段比对的概念，我们设计了一个用于核酸序列全局比对的新算法SAMIDP(Sequence Alignment based on Multiple stage Intelligent Dynamic Programming algorithm)，将多阶段动态规划决策算法用于两两序列比对并用VisualBASIC编程实现，结果发现该新算法在将计算复杂度减小到O(N)的同时，也能够获得较为理想的计算精度，预期将在序列全局比对中起重要作用。
崔鑫[2]2008年在《异构机群系统上序列比对并行处理研究》文中研究指明序列比对是生物信息学的核心研究内容之一,也是各种序列分析任务的基本方法。它研究序列之间的优化对应,即用一个距离函数或者相似分数来度量序列之间的相似性和非相似性。序列比对对研究分子结构与功能预测具有重要意义,因此其计算方法得到人们高度重视。在实际应用中,序列比对的规模很大,即使利用最快的串行比对算法也很耗时,因此需要设计高效的并行算法以快速求解这类问题。由于机群计算系统具有高性能和低成本的特点,所以在异构机群系统上研究序列比对算法的并行处理具有重要的现实意义。本文基于可分负载理论的最优原则,对于处理机节点具有不同的计算速度、通信延迟和存储容量的异构机群系统,考虑通信启动开销,提出一种双序列全局比对问题并行处理的最优分配策略,利用该策略确定出并行迭代次数和分配给各个从处理机的子序列长度。异构PC机群系统上的实验结果表明,与平均分配策略相比,本文提出的最优分配策略进行双序列全局比对并行处理所需的时间明显缩短,并获得良好的加速和可扩展性。多序列局部比对是另一个重要的序列比对问题。本文针对处理机节点具有不同的计算速度、通信延迟和存储容量的异构机群系统,考虑通信启动开销,给定处理机分配顺序,基于可分负载理论提出一种多序列局部比对问题并行处理的最优分配策略,给定了处理机最优分配顺序,给出并行求解多序列局部比对问题所需时间的数学规划模型。异构PC机群系统上的实验结果表明,本文提出的最优分配策略进行多序列局部比对并行处理所需的时间比按平均分配策略的算法所需时间短,并获得良好的加速和可扩展性。
何万双[3]2006年在《双序列比对算法研究》文中进行了进一步梳理生物信息学是一门综合利用生物学、计算机科学、数学等学科知识的新兴交叉学科,其主要任务是利用信息处理方法揭示海量生物学数据中蕴含的生物学意义、探索生命活动的奥秘。比对是生物信息学中一种基本的序列分析方法,对于发现核酸和蛋白质序列所蕴含的功能、结构和进化信息具有非常重要的意义。随着生物序列数据的激增,开发高效率的比对算法就显得非常迫切。本文研究了生物信息学中的双序列比对算法,主要研究内容和取得的成果如下:1.基于经典的Ukkonen快速序列比对算法,借鉴FA算法(Fast Alignment Algorithm)在计算得分矩阵时记录元素来源关系的存储方法,运用在矩阵中寻找Checkpoint点的Checkpoint技术,提出一种基于动态规划思想的较为实用的双序列全局比对算法。2.对几种经典的双序列比对算法进行了分析介绍,并将其中一些算法与本文提出的新算法进行了性能比较。3.在深入分析Blast算法的基础上,基于序列划分策略,提出并实现新的并行双序列比对算法,数值试验表明算法是高效的。4.以本文提出的双序列比对算法为基础,设计并实现了一个基于Windows操作系统的序列比对应用平台。本文的研究内容是序列比对算法,经试验表明,新算法计算效率较之传统算法有提高,在此算法基础上开发的应用软件可以为生物信息学的研究及实践提供一定支持。
唐玉荣[4]2004年在《生物信息学中的序列比对算法研究》文中研究表明序列比对是生物信息学中一种基本的信息处理方法，对于发现核酸和蛋白质序列上的功能、结构和进化的信息具有非常重要的意义。随着生物序列数据库中序列数据的激增，开发兼有高度生物敏感性和高效率的算法就显得非常迫切。本文研究了生物信息学中的双序列和多序列比对算法，主要研究内容和取得的成果如下： 1．在经典的Ukkonen快速序列比对算法基础上，借鉴FA算法(Fast Alignment Algorithm)在计算得分矩阵时记录元素来源关系的存储方法，运用在矩阵中寻找Checkpoint点的Checkpoint技术，研究了一种基于动态规划思想的较为实用的全局双序列比对算法。 2．根据目前双序列比对的研究现状，对几种经典的双序列比对算法进行了分析介绍，并且用C++语言编程实现了这些算法，为本文研究的基于动态规划的双序列比对算法创造了对比实验条件。 3．基于多序列比对研究现状的分析，提出一种基于遗传算法的多序列比对解决方法，设计并实现了序列比对问题的遗传编码，初始群体生成方式，适应度函数计算以及选择、交叉和变异叁种重要遗传操作的方式。 4．针对遗传算法容易陷入局部最优解的缺点，提出模拟退火算法与遗传算法相结合的思想，在遗传操作中加入退火操作，可明显提高多序列比对进化后期的收敛速度。 5．CLUSTAL程序是生物学界通用的多序列比对软件之一，随着同时进行比对的序列数据量的增加，其时间复杂度急剧增加，该程序无法满足大规模的序列数据比对。为进一步优化算法的运行时间，设计了基于Windows操作系统的、单机多处理器的CLUSTAL并行算法，并对CLUSTAL程序中的两两快速比对的核心算法进行了代码优化。 6．CLUSTAL程序的指导树构建采用Neighbor-joining邻位相连算法，该算法同时也是很多指导树生成专用软件的核心算法。针对其在指导树生成方面存在近似程度不高的问题，运用寻找主结点的思想，设计了Neighbor-ioining的改进算法。 7．以本文提出的序列比对算法为基础，设计并实现了一个基于Windows操作系统的中文序列比对系统及应用平台。其功能主要包括序列文件管理、序列比对算法选择、参数设置、比对结果输出和指导树查看等。 本文的研究内容是生物信息学中序列比对的改进与创新算法，经过实际测试，其生物敏感性和运算效率较之传统算法均有所提高，在此算法基础上开发的系统平台软件可以为生物信息学的研究及实践提供一定支持。
夏飞[5]2011年在《生物序列分析算法硬件加速器关键技术研究》文中提出生物序列分析是现代生命科学领域重要的基础性研究工作,由于该领域应用的广泛性、程序特征的复杂性以及海量数据特征对计算机性能提出越来越高的要求,迫切需要高性能计算的支持。现有的基于CPU和GPU的通用计算平台虽然能够提供很强的峰值计算能力,但是不能在运算粒度、存储调度、计算适应度方面主动拟合应用的特点,难以应对生物序列分析领域细粒度的位级操作和不规则的计算、存储需求,实际应用效率低。近年来,FPGA器件以其可编程特性、细粒度并行能力、丰富的计算资源、灵活的算法适应性、低硬件代价和高性能功耗比成为理想的定制计算平台。本文针对生物序列分析应用在通用计算平台上并行性能不高的问题,基于通用微处理器结合FPGA可重构算法加速器的异构体系结构,研究了该领域典型计算方法的细粒度并行化问题。以存储优化为核心,集中解决了可重构算法加速器设计中面临的若干技术难点,构建了面向序列分析应用的动态可重构原型系统,实现了对典型生物信息序列分析过程的定制计算,达到了提高特定应用性能和降低系统功耗的双重目标。本文取得的重要研究成果如下:1.针对不同领域动态规划算法的数据相关性和存储访问特征,基于FPGA平台提出了资源受限条件下的数据相关性转换、负载平衡的任务划分和存储调度策略,设计了并行计算结构,对典型算法实现细粒度并行。具体包括:针对回溯条件下序列比对过程存储需求膨胀的问题,提出了节省存储需求的细粒度并行算法,采用区域划分和计算策略解决了长序列比对面临的FPGA片内逻辑和存储资源受限问题;利用二维串行动态规划问题具有的固定数据依赖和矩阵反对角线元素不存在数据相关的特点,提出基于同构线性阵列对矩阵反对角线元素实现并行计算的方法和加速器结构模板;采用等值罚分和仿射罚分模型分别实现了无回溯、片内回溯和片外回溯叁种序列比对设计方案,比较全面地解决了序列比对应用的硬件加速问题。针对RNA二级结构预测领域叁维非串行动态规划算法中变化的数据相关距离、不规则计算和非连续存储问题,提出了一系列提高存储效率的优化措施:通过重组单元计算顺序提高数据局部性,通过数据重用减少片外存储访问开销,通过数据预取和缓存、同步点写回等措施隐藏片外访问延迟,实现计算和通信的平衡;利用反对角线元素计算量相等且不存在数据依赖的特点,提出了细粒度并行算法和基于主从多处理单元的加速器设计模板;利用列元素计算量之差只与列坐标相关的特点,采用“区域分割”和“按列轮转划分”的层次化任务分配策略实现处理单元间的负载均衡;基于加速器设计模版,在国际上首次实现了对Zuker、RNAalifold和CYK叁种典型算法的硬件加速,取得了10倍以上的加速效果。针对带假结RNA结构预测领域的四维动态规划算法中复杂数据相关性和存储带宽受限的问题,提出了“时空域重迭”的数据相关性分析方法;通过对访存请求的动态调度减少片外存储访问的随机性,降低了50%的存储带宽需求;采用基于多处理单元的异构线性阵列结构,实现了对四维动态规划矩阵的细粒度并行计算,相对于通用计算平台取得了3~5倍的加速效果。2.针对启发式序列数据库搜索算法中存在的种子检测效率不高的问题,提出一种不基于常规查询策略的并行多种子检测算法和基于线性结构的并行多种子搜索阵列;采用阵列分组和并行种子收集、组内种子合并和多种子并行扩展策略实现了无阻塞的数据库搜索,成功对BLAST数据库搜索算法实现硬件加速。3.针对基于HMM模型的随机搜索过程中紧耦合的数据相关导致矩阵元素无法并行计算的问题,提出粗细粒度混合的HMM模型并行计算方法,即对单个元素内部状态的计算实现细粒度并行,对“模型—序列”间的匹配过程实现粗粒度并行。与目前最好的硬件加速方案相比,单PE的计算性能提升了30%;与运行在通用计算平台上的搜索程序相比,可获得接近200倍的全局加速效果。4.以蛋白质结构预测为应用背景,提出了贝叶斯网络模型的细粒度并行方法和计算结构。针对模型的串行结构和不同处理阶段负载不匹配的问题,提出了多阶段混合流水处理策略和细粒度并行计算结构,采用关键流水段复制实现了流水线负载平衡;针对模型参数的共享访问竞争和地址间隔访问的特点,采用参数表分割、复制和传递策略提高参数访问效率,首次对基于贝叶斯统计和网络模型的蛋白质结构预测应用成功实现硬件加速。5.以大容量FPGA芯片和SDRAM存储器为基础设计了硬件算法加速器,与通用微处理器结合构建了基于异构体系结构的序列分析原型系统,并开发了序列分析应用程序集和FPGA配置文件库,采用FPGA动态全局重构技术实现了不同应用间的快速切换,提高了原型系统对应用程序的适应性,达到了对生物序列分析典型应用的整体加速效果。研究结果表明,本文提出的通用微处理器结合可重构FPGA算法加速器的异构计算平台对生物序列分析应用具有显着的加速效果,并能实现提高计算性能和降低系统功耗的双重目标。
李镍岚, 李其申, 张永[6]2007年在《一种基于动态规划的全局双序列比对优化算法》文中进行了进一步梳理序列比对是生物信息处理中非常重要的一类方法,基本的序列比对算法是基于动态规划思想提出的。本文提出了一种基于动态规划思想的全局双序列比对优化算法(Optimized Global Pairwise Sequence Alignment based on the idea of Dynamic Programming)OGP-SADP,在保持基本动态规划敏感性的前提下,GOPSA方法计算替换矩阵时只需存储当前相邻两列的元素,同时引用checkpoint技术以减少计算迭代次数,有效降低了时间复杂度和空间复杂度。
李聪[7]2015年在《基于OpenCL平台的DNA序列并行比对算法的研究》文中进行了进一步梳理信息时代已经来临,当前计算机环境更加复杂多样,所以我们需要将计算机的硬件潜能(如CPU、GPU、PSP)更充分地发挥出来。在计算科学中,存在的异构体系就恰好可以成为我们计算、分析各项研究任务的最优选择方式。传统的C或C++的编译目标一般都是CPU;NVIDIA的CUDA也只能针对NVIDIA的GPU而非CPU。搭建OpenCL平台就可以在混合架构的设备(hybrid device)上,调用GPU实现在异构环境下的并行加速算法。当前,并行比对算法也被应用在生物信息学领域,DNA序列比对是生物信息学最基本的研究内容,基于OpenCL平台的并行加速算法将会为DNA序列比对提供新的研究途径。因此,本文结合OpenCL的并行特点,重点对DNA序列比对算法进行相关研究。主要研究成果有:首先,本文介绍了OpenCL基础以及DNA序列比对的相关知识,分析了OpenCL在异构体系上的作用,阐述了在生物信息学研究中DNA序列比对的现实意义,并对DNA序列比对方法在国内外的发展状况作出研究和总结。其次,本文研究了基于动态规划的DNA序列比对算法,阐述了双序列比对的数学理论和计数规则,在JAVA虚拟机上模拟基于动态规划算法的Needleman-Wunsch算法和Smith-Waterman算法的串行设计,引入“双罚分”机制,实现了基于Smith-Waterman算法的异构并行设计,并面向OpenCL平台实现了DNA序列并行异构比对算法,通过实验数据给出了使用并行算法前后的比对图。最后,本文研究分析了面向OpenCL平台的GPU优化策略,针对GPU架构特点,提出了一种基于GPU结构优化的并行策略,加速实现Smith—Waterman算法,并通过实验结果比对分析相关性能。
刘帅[8]2007年在《基于自适应免疫遗传算法的多序列比对方法研究》文中研究说明序列比对是生物信息学中基本的信息处理方法,随着人类基因组计划的推进得到了广泛的重视和深入的研究,但是目前还没有一个最佳的多序列比对算法。近年来,遗传算法的卓越性能引起了人们的关注,并成功地被应用到各种领域的优化问题中。如何改善遗传算法的搜索能力和提高算法的收敛速度,使其更好地应用于实际问题的解决中,是各国学者一直探索的一个主要课题。免疫算法作为一种新近受到重视和发展的计算智能,与其他理论的融合还有很多潜力期待挖掘。免疫算法和遗传算法结合时,遗传算法的全局搜索能力及免疫算法的局部优化相配合,可大大提高搜索效率。本文通过对多序列比对算法的研究以及对遗传算法和免疫算法特点的分析,提出了基于自适应免疫遗传算法的多序列比对算法MSAAIGA(Multiple Sequence Alignment Based On Adaptive Immune Genetic Algorithm)。该算法将自适应遗传算法与免疫算法相结合,运用遗传算法实现多序列比对问题的遗传操作,该算法中生成初始群体时采用了星比对算法,这样可以充分利用序列自身的信息,要优于盲目的在序列中插入空位生成的初始群体,虽然在比对初期会增加时间开销,但是会大大提高比对后期的搜索效率。遗传算法是全局收敛的,但是遗传算法的交叉算子和变异算子却相对固定,在求解问题时,可变的灵活程度较小,这样易使遗传算法产生早熟现象,陷入局部极值。因此本文采用自适应遗传算法,在进化过程中根据种群的实际情况,动态调整交叉概率和变异概率。自适应遗传算法在保持群体多样性的同时,保证了遗传算法的收敛性,提高了算法的寻优能力。另外将免疫算法中的免疫算子应用于自适应遗传算法,在保留原算法优良特性的前提下,更加有效地抑制了优化过程中出现的退化现象。本文给出了算法的具体步骤,并结合实例证明了其全局收敛性,理论分析及实验结果证明了这种融合的有效性。
徐小俊[9]2011年在《群智能优化算法在多序列比对中的应用》文中研究说明序列比对是生物信息学中最基本的信息处理方法之一,对于研究核酸与蛋白质序列有着非同一般的意义。通过序列比对,可以发现核酸或者蛋白质序列中的相似性片段,然后根据生物科学中的生物进化理论,依据相似性片段数量的多少以及相似程度的高低推断出该序列属于哪个基因家族,或者说,这些序列之间有着怎样的进化关系。同时,还可以根据相似性片段推测出未知序列的功能和结构。此外,序列比对还可应用在医学领域,通过比对健康序列和病变序列,可以推测出哪些基因发生了病变,发生病变的位置,为疾病的治疗提供有效帮助。多序列比对是本文研究的主要内容,研究的主要目的是提高多序列比对的精度。首先介绍了多序列比对研究现状和相关算法的问题,尤其是对群智能算法的研究,比如遗传算法、粒子群算法、模拟退火算法解决序列比对问题的现状；其次首次将人工蜂群算法应用到多序列比对问题中;最后,又对粒子群算法和人工蜂群算法进行了改进,应用到多序列比对中,并通过仿真实验的方式,证明了这两种方法的有效性。具体如下：介绍了基本粒子群优化算法(Particle Swarm Optimization, PSO)模型以及几种最具代表性的惯性权重取值方法：随迭代次数线性降低的线性惯性权重、动态自适应的惯性权重取值方法等。惯性权重大,粒子群算法的全局搜索能力强,粒子主要的功能是探索新的解领域；惯性权重小,粒子群算法的局部搜索能力强,粒子的主要功能是开发当前最优解,提高解的精度。对这些理论有了深入了解和分析之后,提出新的惯性权重取值方法----分段取值惯性权重(subsection weight, SW),将算法运行过程分成两个部分,符部分采用不同的惯性策略。随后,根据生物学中鸟群觅食的特点,粒子除了一个自我学习能力和社会生存能力之外,还具有小范围内粒子之间的交流能力,叁者分别对应着个体最优位置、全局最优位置、群组最优位置。将引入的群组最优位置与Sw惯性取值方法融合在一起,提出SWGPSO算法。介绍了人工蜂群算法的相关知识,基本人工蜂群算法模型来源于蜂群的觅食行为,在这个模型中,雇佣蜂、跟随蜂和侦察蜂符自行使自己的职权,并和谐交流,从而达到搜索到最佳食物源的目的。首先尝试将人工蜂群算法应用到多序列比对问题中,并对其解决该问题的效果进行了比较分析,不仅证实了该算法可以用于求解多序列比对问题,而且其性能在某种意义上要优于其他的群智能算法。一般来说,单一的算法并不完美,总会有一些缺点,因此,我们又对基本人工蜂群算法进行改进,将模拟退火算法中的Metropolis接受准则引入到侦察蜂的随机搜索过程中,使得侦察蜂能够以一个较小概率接受较差的解,从而保持种群多样性,避免算法陷入局部最优,提出了ABC_SA算法。仿真实验结果表明ABC_SA算法所得到的序列比对结果比基本人工蜂群算法得到的更精确,也证明了ABC_SA算法解决多序列比对问题的有效性。
祝庆燕[10]2007年在《生物序列比对算法的研究与实现》文中指出生物信息学是利用现代计算技术来处理和研究生物数据的一门新型交叉学科。其中,序列比对是生物信息学中最基本的信息处理方法,对于发现核酸和蛋白质序列上的功能、结构和进化信息具有非常重要的意义。如何获得比对准确率更高、时间空间效率更好的序列比对算法是生物信息学研究的一个重要课题。本文研究了以动态规划算法为代表的全局比对算法和以Smith-Waterman算法、BLAST算法、FASTA算法为代表的局部比对算法。在对这些算法的设计思想进行研究、性能进行比较分析的基础上,提出了基于后缀树的双序列比对算法SPLSA。该算法分为叁个主要步骤—建立后缀树,寻找公共子串,连接公共子串。本算法建立带后缀链的后缀树,利用后缀链可以快速定位下一后缀内结点的优势在线性时间内完成后缀树的建立;另外,后缀树本身具有易于寻找公共子串的特性,利用此后缀树可以在线性时间内完成公共子串的寻找;而公共子串连接成匹配段的过程中采用了剪枝策略,降低了算法的运行时间;采用深度扩展和广度扩展相结合的方式提高了算法比对准确性。实验结果表明,SPLSA算法在运行时间上优于Smith-Waterman算法,在比对准确率上优于BLAST算法。本文研究了目前主流的多序列比算法—渐进多序列比对算法和迭代多序列比对算法,分析了这两类算法的优缺点及适用范围。研究并实现了ClustalW渐进多序列比对算法。在对上述算法研究的基础上,实现了一个生物序列比对系统。该系统中双序列比对采用SPLSA算法,多序列比对采用ClustalW算法。除此之外,该系统还提供了文件搜索、比对结果对齐显示、比对结果保存等附加功能。
参考文献：
[1]. 基于动态规划进行双序列全局比对研究[D]. 李静. 北京工业大学. 2003
[2]. 异构机群系统上序列比对并行处理研究[D]. 崔鑫. 广西大学. 2008
[3]. 双序列比对算法研究[D]. 何万双. 国防科学技术大学. 2006
[4]. 生物信息学中的序列比对算法研究[D]. 唐玉荣. 中国农业大学. 2004
[5]. 生物序列分析算法硬件加速器关键技术研究[D]. 夏飞. 国防科学技术大学. 2011
[6]. 一种基于动态规划的全局双序列比对优化算法[J]. 李镍岚, 李其申, 张永. 电脑知识与技术(学术交流). 2007
[7]. 基于OpenCL平台的DNA序列并行比对算法的研究[D]. 李聪. 黑龙江大学. 2015
[8]. 基于自适应免疫遗传算法的多序列比对方法研究[D]. 刘帅. 东北师范大学. 2007
[9]. 群智能优化算法在多序列比对中的应用[D]. 徐小俊. 陕西师范大学. 2011
[10]. 生物序列比对算法的研究与实现[D]. 祝庆燕. 哈尔滨工业大学. 2007
标签：生物学论文; 动态规划论文; 遗传算法论文; 生物信息学论文; 序列比对论文; 异构网络论文; 优化策略论文; 时间计算论文; dna序列论文; 算法论文;