生物信息学中基于启发式的多序列比对算法

序列比对是生物信息学中一项重要的基础性研究课程,其基本任务之一就是进行多重序列比对,但是如何优化多重序列比对算法目前生物信息学面临的一个核心课题,本文介绍了多重序列比对研究所涉及的基本问题,对当前多重序列比对启发式算法的几种经典算法进行描述,并对多重序列比对算法的前景进行了展望。     

针对基因选择性剪接的多序列比对算法研究

为对真核基因的选择性剪接形式进行准确、快速、有效的研究 ,提出了一种启发式多序列比对算法。该算法借助引导树启发序列之间的两两段对段比对 ,通过建立序列相似性估计模型 ,给出了一种由序列间相同词数估计序列相似程度的方法。利用这种方法构造引导树 ,大大缩短了其构造时间。通过采用序列间的段对段比对 ,克服了间隙罚分问题 ,更准确地反映了真核基因的选择性剪接形式。引导树构造方法的改进和快速局部比对算法的采用 ,使得算法运行速度大大高于一般算法。该算法为真核基因的选择性剪接研究提供了一种新的有效途径     

基于遗传算法和蚁群算法的多重序列比对

多重序列比对问题是复杂性较高的困难问题.基于蚁群算法的多重序列比对方法能够在合理的时间内找到得分接近参考比对的多序列比对解.但是,随着序列的加长,蚁群算法对于长序列的比对效果并不是很理想.本文提出一种基于遗传算法和蚁群算法的多重序列比对方法.该方法利用遗传算法对长序列分段,利用蚁群算法对分段后的序列进行求解,然后直接将各段的结果进行拼接即可.     

基于序列划分的压缩序列模式挖掘算法

研究了静态数据库当中挖掘压缩序列模式的问题,提出了一个压缩序列模式挖掘算法.该算法通过对闭序列模式全集进行划分处理,降低了序列的比对空间,并结合δ-dominant序列检测机制,有效的挖掘出了压缩序列模式集.实验表明,该算法具有较好的运行效率.     

生物信息学中的双序列比对算法

生物信息学是生物技术的核心,序列比较是生物信息学中最基本、最重要的操作,通过序列比较可以发现生物序列中的功能、结构和进化的信息,序列比较的基本操作是比对。描述了常用的各类双序列比对算法,并结合实例进行了详细的解释,最后指出了序列比对算法目前存在的问题。     

基于动态规划的序列比对的并行算法研究

针对序列比对算法进行了深入地研究,分析比较了两序列和多序列、局部和全局、渐进和迭代的序列比对算法.利用动态规划序列比对算法内在的并行性,提出了自适应的动态规划序列比对的并行策略.该策略在计算初期和计算末期采用较小的高度和宽度值使得大部分处理器参与计算,在计算中期采用较大的高度和宽度值降低处理器间的通信开销;运用上述自适应的动态规划序列比对的并行策略,提出了一种基于动态规划的序列比对的并行算法,将读入的比对序列负载均衡地分布至不同的计算结点.基于集群系统和MPI环境的实验数据及分析表明,该算法在给定进程数量的条件下,其执行时间随序列长度的增长而急剧上升;在给定序列长度的条件下,其执行时间随并行进程数量的增大而大幅减小;充分反映出该算法较好地发挥了序列比对问题的内在并行性,有效地降低了序列比对算法的时间复杂度.     

生物序列比对算法分析与比较

序列比对是生物信息学的一个非常重要的操作．它可以预测生物序列的功能、结构和进化过程等．文中首先介绍双序列比对的基本算法;接着分析和比较多序列比对的四个常用模型和三类算法以及并行比对算法;最后,给出一些研究问题．     

基于知识表达系统的序列比对研究

序列比对是生物信息学中基本的信息处理方法,对于发现生物序列中的功能、结构和进化信息具有重要的意义。该文对典型的双序列比对算法以及多序列比对算法进行了描述和评价;针对目前序列比对算法普遍存在的不足,提出了一种新的思想--基于知识表达系统的序列比对研究,应用知识表达系统对序列比对相似性发现进行定义及其处理。     

BLAST序列比对脱机移植研究

BLAST序列比对算法是NCBI综合性生物信息平台整合的众多重要功能之一。研究建立BLAST算法的脱机环境移植,可使生物信息学研究人员在构建自己专有序列数据库的同时,对DNA序列进行脱机环境比对,以期更高的序列数据安全性,避免联网状态下造成的数据丢失和泄露等严重问题。通过研究BLAST序列比对过程中涉及的标准数据格式与调用细节,实现了脱机环境下的BLAST序列比对,为建立安全序列比对提供了一种可行参考。     

多粒度时空事件序列相似度算法研究

现有研究集中于不带有时间空间信息或带有固定时间空间信息的活动序列相似度计算,没有从不同层次来度量用户行为序列的相似性,为了实现对用户行为多粒度多视角的动态认知,提出一种基于序列比对算法Needleman-Wunsch的多粒度时空序列比对算法（multi-granular spatiotemporal sequences alignment,MGSSA）,扩展了NW算法的得分函数以结合时间、空间信息,通过粒度调控实现了从不同的粒度来计算时空事件序列的相似度.实验证明,多粒度时空序列比对算法MGSSA是有效且可行的.      

基于高分片段对的双序列比对分治算法SPDCA

针对传统双序列比对算法的高时空复杂性,在动态规划比对算法的基础上,引入了片段对和分治思想,提出了一个新型的基于高分片段对的分治算法.模拟结果表明:该算法在降低了双序列比对算法的时空需求的同时,还能发现双序列之间微弱的相似关系,可适用于序列数据库相似性的搜索.     

生物DNA序列比对算法研究

基于典型CLUSTALW序列比对算法,研究一种局部优化的多序列比对算法,用减少序列比对过程中总评分的方法来达到优化算法的目的,并对基因库中的序列进行了测试．     

mRNA序列与蛋白序列对比

生物序列的对比是计算生物学中的一个基本问题．目前已有许多算法对DNA序列或蛋白序列之间进行对比,多是对同种生物序列进行对比．为得到mRNA序列和蛋白序列之间的对比,采用动态规划算法,提供了寻求mRNA序列和蛋白序列的局部对比和全局对比,解决了核酸与氨基酸之间的对比问题．算法的时间复杂度为O(nm)．     

基于动态算法的序列分析

为了获得2009年新型甲型H1N1流感病毒与2008流感病毒的基因序列及氨基酸序列的一致性，以便对一个基因家族的生物学特征有一个简明扼要的了解，针对目前流行的新型甲型H1N1流感病毒的基因序列及其所编码的氨基酸序列，采用动态规划算法对其一级序列进行序列相似度分析，获得了2009年新型甲型H1N1流感病毒的NA和M基因片段以及2008年猪源性甲型H1N1流感病毒的相应基因片段同源性高、在有些位点发生了基因突变增添和突变缺失等重要基因信息。为此次新型甲型H1N1流感病毒的研究提供了依据。     

布尔逻辑DNA序列比对系统的软件平台设计

针对目前基于动态规划的DNA序列全局比对算法时间复杂度较高,设计了一个DNA序列全局比对系统。该系统用FPGA进行序列的比对,并配备一个软件平台存储数据、发送命令以及发送和接收数据。测试数据表明,该系统的DNA序列比对时间在序列相似度较低情况下,为Needleman的42%;在序列相似度较高的情况下,为Needleman的6%。     

一种新的视频质量评价中帧对齐算法

在全参考或者部分参考的视频质量评价算法中,由于视频序列在传输过程中总会存在丢帧、跳帧、停滞等现象,因此在视频质量评价之前进行的帧对齐处理是非常重要的步骤.提出了一种新的帧对齐算法,该方法在国际电信联盟(ITU)的ITU-T J.244和J.247的基础上,对源视频和劣化视频序列进行预处理和相关特征参数的提取,并采用类似滑动窗口的原理对二者进行相似度的运算,根据运算结果可判断是否达到帧对齐.结果表明,该方法可以明显甄别出视频序列相应帧的对齐情况,算法简单、实时性较好,具有一定的实用价值.     

相似序列Alignment快速算法及其应用

本文综述近期得到的由相似核苷酸序列给出Ａｌｉｇｎｍ ｅｎｔ的快速算法，以及此算法在若干应用问题中得到的新结果．     

双语句子对齐系统中多层次分段对齐方法研究

分段对齐在双语句子对齐的过程中发挥着重要的作用,文章提出了一种新的基于锚点句对的分段对齐方法,并把它和传统的基于回车符的分段对齐方法相结合,形成了一种多层次的分段对齐方法.     

用互关联后继树模型实现一个局部相似性比对算法

对基因数据库的一种常见操作是找到与待查询序列相似的序列.目前常使用的是BLAST算法,但是这种启发式算法有时会漏解.如果使用精确匹配算法,例如Smith-Waterman(S-W)算法,计算代价又会太大.OASIS算法是一种高效并且精确的生物序列局部相似性比对算法,而且互关联后继树模型的空间效率很高,因此使用互关联后继树实现了OASIS,并命名为OASISirst算法,其比对结果和OASIS一样按照得分降序排列,并且当目标序列和查询序列均较长时,时间优势明显.