生物信息学
维普资讯 doc.guandang.net
第 4期
张敏:生物序列比对算法研究现状与展望
从右下单元到左上单元回溯最佳路径 (由箭头表示 )路径中每个单元的评价值是根据前面各单元,的评价值决定的.最后,根据最佳路径从左上到右下给出两序列的比对结果.若箭头为对角线,则在比对后的序列中,个残基相对应 .箭头为水平方向,在 A序列的相应位置插入一个“一”若箭头为垂两若则 . 直方向,在 B序列的相应位置插入一个“一”比对结果可能不唯一,图 2中,列 A,则 .如序 B有三个最优
比对结果,每个比对结果有三个保守残基被对齐 (大写字符 ) . 和全局比对算法不同,序列局域比对所要寻找的是两条序列中相似性最大的子序列 .寻求局域比对可能会发现若干重要的保守区域 .m t— tma S i Wa r n算法是一个局域比对算法, h e它规定矩阵单元值为负者一律取 0加入这一项是为了确保计算中丢弃得分为负值的子序列的比较,,因为分值为负的比对丧失了比对的生物学意义 .在计算完矩阵后,找出矩阵的最大分值 .通过回溯法,从最大分值单元开始回溯到分值为 0的单元为止,确定局域比对路径,构建局部最优比对 . 2 2两序列比对的数据库相似性搜索 .两序列比对的一个主要目的是进行数据库相似性搜索,A T和 B A T是最常用的数据库搜索程 F SA LS序,采用局域比对方法 .均 F S A是第一个广泛使用的数据库相似性搜索程序 .是一种启发式算法,基本思想是:个 AT 这其一
能够揭示出真实的序列关系的比对至少包含一个两个序列都拥有的字 (由连续字符组成的子序列 )把, 查询序列中的所有字编成索引,后在数据库中查询这些索引字 . A T然 F S A程序并不研究每一个选中的
字,而是寻找包含若干个相邻的选中片段,将这些片段组合起来予以评价;然后,那些最有可能的匹配序列将会通过局域比对而被进一步评分,并对每一个检索到的比对提供一个统计学显著性的评估. B A T4是目前使用最广泛的数据库搜索算法,基本思想是:过产生数量较少,质量更好的 L_ S 其通但匹配片段来提高搜索速度,并把数据库搜索建立在严格的统计
学基础之上.算法描述如下:其首先是在 数据库中找出与查询序列相同的匹配字串 ( i)且这一局部字串中不含空位;个匹配字串选中后, ht,一以
此作为内核向两端延伸,以找出尽可能长的相似序列片段,即高分片段对 H P( i eu nep i )也 S hg sq ec a s; h r 设定一个统计显著性阀值 E,计显著性大于 E的 H P将被舍弃,下的 H P即为高质量的匹配片段统 S剩 S
对,由此在数据库中搜索出具有一定可信度的同源序列 .
3多序列比对 ( lpeain n )法 mut l l me t算 i g 从理论上来说,序列的动态规划比对算法可以推广到多序列比对中去,现已经证明:于 S两但基 P度量的多序列比对是一个 N P问题 .际上,了个数较少,列较短的比对问题外,序列比对基本上实除序多
都是采用启发式算法.文重点介绍目前国际上最具代表性的两类算法:本渐进比对和迭代比对算法. 3 1渐进比对 ( rgesv l n n )法 . P o rsieai me t算 g
渐进比对是最常用的多序列比对方法,基本思想是:比对的序列是进化相关的,此可以按着其要因序列的进化顺序,近至远将序列或子比对结果按双重比对 ( a— i ln e t算法逐步进行比对,由 p iws ai m n) r e g重复这一过程直到所有序列都加入为止 .类算法的主要优点是:单、速;点是:比对初期引进的这简快缺在空位插入错误无法在比对后期因加入其它序列而改正,于陷入局部最优解 .易
Cut l是一个使用最广的渐进比对程序, l r sa W其具体算法为:对所有序列进行两两比对,由①并
此计算出距离矩阵;②基于距离矩阵,利用 N方法构建指导树; J③依据指导树的分支顺序,由关系最近的两个序列开始进行比对,现在比对中的空位保持固定不变;出由近至远,步添加序列,到所有序列逐直 全部加入为止 . l t对于亲缘关系较近的序列比对效果较好, Cu a W sl但是对于分歧较大的序列,比对的准确率明显降低 . TCfe—o e是另一个有代表性的渐进比对算法 J它的主要特点是
将序列的两两局域及全局比对结 f, 果收集在一起,成一个扩展比对信息库 .利用扩展比对信息库中提取的信息取代替代矩阵进行渐近做再
比对,使得在每一步渐近比对过程中用到的是所有序列之间的关系信息,而不只是仅考虑当前要比对的 序列信息,而在一定程度上提高了比对准确率,其是对于存在大量空位插入的情况,果更为明显 .从尤效

生物序列比对算法研究现状与展望生物序列比对算法研究现状与展望隐藏>> 第25 卷 4 期第 2004 年 8 月 大连大学学报 J OURNAL OF DALIAN UNIVERSITY Vol. 25 ...
生物序列比对算法综述_生物学_自然科学_专业资料。生物序列比对算法综述 【摘要】 随着生物信息学的快速发展, 序列比对算法成为研究的热点问题。 本文介绍序列比对...
生物序列比对算法的研究现状文凤春 , 王邦菊 , 肖枝洪 ( 华中农业大学理学院,...杂度, 优缺点, 讨论了各自的使用范围, 并指出今后序列比对研 究的发展方向。...
生物序列比对算法的研究现状生物序列比对算法的研究现状隐藏>> 第8卷第1期 ... 优缺点 , 讨论 了各 自的使用范 围, 并指出今后序列比对研 究的发展方 ...
.cn 生物序列比对算法综述 作者:艾冬梅 赵清玉 张德坤 来源:《中国科技纵横》2013 年第 18 期 【摘要】 随着生物信息学的快速发展,序列比对算法成为研究的热点...
DOI:10.3969/j.issn.1001-8972.2011.09.021 生物序列比对算法的研究现状杨洁 刘海 湖南信息职业技术学院 410200摘要 本文综述了生物序列比对的基本思想和主 要...
多序列比对算法的研究进... 5页 1下载券 DNA测序技术的发展历史与... 7...\ \ 二 生物信 息学 中序 列比对技术和算 法研 究进展 ★ 李美满 (东...
基于图形硬件加速的生物序列比对算法研究_专业资料。生物序列比对是生物信息学的基础,是当今功能基因组学研究中最常用、最重要的研究方法之一。本文对各类序列比对...
燕 申请学位级别:硕士 专业:卫生统计学 指导教师:易东 20080501 第三军医大学硕士学位论文 生物序列比对算法研究于两研究背景 近年来,生物信息学获得了飞速的发展。...
多序列比对算法的研究进展_IT/计算机_专业资料。多...摘要: 多序列比对在阐明一组相关序列的重要生物学... 针对具体问题发展具体的多序列比对方 法目前已经被...
热门文档