生物信息学相关论文范文文献,与生物序列比对算法综述相关论文查重免费

本论文是一篇生物信息学相关论文查重免费,关于生物序列比对算法综述相关硕士学位毕业论文范文。免费优秀的关于生物信息学及生物信息及序列方面论文范文资料,适合生物信息学论文写作的大学硕士及本科毕业论文开题报告范文和学术职称论文参考文献下载。

【摘 要】随着生物信息学的快速发展,序列比对算法成为研究的热点问题.本文介绍序列比对算法的概念及研究,并针对几种常用的序列比对算法进行比较.同时也简单说明序列比对算法的改进方向.

【关 键 词】生物信息学序列比对准确率时空效率

随着生命科学研究的兴起和计算机技术的飞速发展,生物信息学已成为自然科学的核心领域之一[1].基因序列比对是生物信息处理的最基本方法,对发现基因功能、比较基因、探究生物进化等具有非常重要的作用.

1序列比对算法概述

所谓序列比对[2],是指两个或多个序列按字母比较,尽可能确切地反映它们之间的相似和相异性,用于阐明序列之间的同源关系.通过序列比对,找出序列之间的相似性,发现与结构相联系的保守序列片段,以及检测新测定序列与数据库中已知结构和功能的序列之间的相似性关系,从而以足够的可信度确定新序列的结构和功能信息.

目前已知的序列比对方法很多.本文主要针对常用的算法,按照比对的序列数目进行相关介绍：

1.1双序列比对

根据算法结构的不同,将双序列比对算法分为三类[3]：动态规划的优化方法,启发式算法和大型数据库搜索设计的概率方法.

1.1.1动态规划的优化算法

Needleman-Wunsch算法是最早的序列比对算法,属于全局序列比对,在生物信息处理中应用广泛.Smith-Waterman算法是一种局部相似性的动态规划算法,在识别局部相似性时具有很高的灵敏度,是双序列比对算法中最基本的算法.

1.1.2启发式算法

1）FASTA算法

FASTA是双序列比对启发式算法,采用了改进的wilbllr和Lipmall算法以集中反映具有显著意义的比对结果.

它的基本思想是：一个能揭示出真实序列关系的比对至少包含一个两条序列都拥有的片段,把查询序列中的所有片段编成Hash表,然后在数据库搜索时查询这个Hash表,以检索出可能的匹配,这样命中的片段就能很快地被鉴定出来.

2）BLAST算法

BLAST算法可以兼顾搜寻的速度以及搜寻结果的精确度,它比FASTA速度更快.它的基本思想是：产生比FASTA更少而更有意义的增强点,以提高整个算法的速度.BLAST算法在不失敏感性的前提下大大提高了算法的效率.

3）BLAT算法

Blat算法最初用于人类基因组拼接和注释过程中的大规模数据比对任务上.其速度快、共线性输出结果简单易读,存在的局限性是对于特殊的任务需要选择合适的软件,如：用于远亲缘物种间的核酸序列比对时,比对精度就不够高；在重复搜索短小匹配片段的同时,会产生过多的没有生物学意义的序列比对碎片.

1.1.3大型数据库搜索设计的概率方法为基础的算法

MUMmer算法是一种基于后缀树数据结构的全基因组比对方法,利用后缀树的数据结构有效地将算法的时间和空间复杂度由（N3）降到了（N）.与BLAST算法相比,其后缀树法在速度上快得多,且能处理大量的插入和删除片段,能识别重复片段和单核酸多态性等多种全基因组序列中的复杂片段.

1.2多序列比对

多序列比对的常用算法有累进算法、隐马尔科夫模型、迭代比对法等.

累进方法是最常用的启发式多序列比对算法.其中的CLUSTAL算法是由Feng和Doolittle提出的,基于相似序列通常具有进化相关性这一假设的算法,它是多序列比对算法中使用最广泛的.

大学生如何写生物信息学毕业论文
播放:34055次 评论:7633人

隐马尔科夫模型是目前较先进的多序列比对方法,跟常规的方法相比,它可以发现序列久远的同源性.

迭代方法也基于一个能产生比对的算法,并通过迭代方式精细多序列比对,直到比对结果不再改进为止.这类算法不能提供获得优化比对结果的保证,但却具有鲁棒性和对序列个数不敏感等特性.

2序列比对算法比较

通过