序列比对正文.docx

一 前言DNA蛋白质序列比对是生物信息学中的基本手段，深入了解比对算法的核心内容是学 习掌握生物信息学的必需内容。本专题通过 Perl程序分别实现动态规划算法与模糊匹配 的方式（即字符串相似度算法），处理比较多条序列，从而比较两种算法的区别和优劣。 进而通过实际操作（程序运行）了解动态规划算法与其它算法之间的区别，掌握动态规划 算法的特点和优势。二本论动态规划算法动态规划解决序列比对问题的基本思想：使用迭代法计算出两个序列的相似分值,并 存入一个得分矩阵中，根据得分矩阵 回溯寻找最优的比对序列.序列比对是动态规划的一个重要应用。序列比对问题通常是使用编辑操作(替换、插 入、删除一个要素等)进行序列转换。每次操作对应不同成本，目标是找到编辑序列的最 低成本。可以很自然地想到使用递归解决这个问题，序列 A到B的最优编辑通过以下措施 之一实现：插入B的第一个字符，对A和B的剩余序列进行最优比对；删去 A的第一个字 符，对A和B进行最优比对；用B的第一个字符替换A的第一个字符，对A的剩余序列和 B进行最优比对。局部比对可在矩阵中列表表示，单元 (i,j)表示A1.i到b1.j最优 比对的成本1。单元(i,j)的成本计算可通过累加相邻单元的操作成本并选择最优解实现。两条序列分别作为横坐标和纵坐标放置，组成一个路径矩阵，即得分矩阵，矩阵元素(i,j)值为比对的得分值。在得分矩阵中到达位置为 (i,j)的某一个元素有三种可能的路 径：通过位置i- 1,j- 1的对角方向，没有空位罚分：通过列j的垂直方向，通过行i的 水平方向，空位罚分的值 取决于插入空格的个数。序列比对序列同源(homology)指的是序列来自相同的祖先，意味着这些序列具有相同的进化历史，而序列的相似性 (similarity) 指的是两序列在某参数条件下的相像，它可以用相同残基的百分比或是其 他的方法来表示。列之间的相似度是可以量化的参数，列是否同源需要有进化事实的验 证，显著的相似性通常意味着同源是运用某种特定的数学模型或算法 ，找出两个或多个 序列之间的最大匹配碱基或残基数，比对算法的结果在很大程度上反映了序列之间的相 似性程度以及它们的生物学特征。动态规划序列比对算法动态规划算法比较序列相似度程序如下：open(INFILE,、生信比对算法应用专题比对序列.txt) or die "Can't生信比对算法应用专题比对序列.txt $!"open(OUTFILE, '>C:UsersAdministratorDesktop') or die "Can't open : $!" while(<INFILE>) if ( $_ = / SEQUENCE1:/ ) $_=s/ SEQUENCE1:和.0"字符用单元存放的数组是从1开始计数的单元中，开 始扫描！和"字符串"如果遇到字符串单元相同的时候权值相乘最后得到一个 /92"!./#.0"/92 即为匹 配度”根据/92的值进行冒泡排序"权值由大到小排列4。模糊匹配序列比对算法程序下面是采用模糊匹配方法对2个文本中的序列进行的相似度处理程序： #!/usr/bin/perl use strict;use Tie:File;my $count=0;tie my array ,'Tie:File'," 数据 1",memory=>0 ;何等数据绑定成数组的形式，给内存 为250MB控制程序的内存利用，维持稳定和性能open OUT1,"数据 2" or die "$!" ; /open IN,">./字符串相似的数据4txt" #将相似的数据导入到这个表中my ip=array;/my data=<OUT1> /for(my $i=0;$i<=$#ip;$i+)for (data) my $s2=$_; chomp($s2); chomp($ip$i);if (leng($ip$i,$s2)if (levenshtein($ip$i,$s2)/leng11($ip$i,$s2)<# 我查询的 80%勺相似度#print levenshtein($ip$i,$s2)."n"/print IN $ip$i.'和这个很相似.$s2."n" else print $i."n" print IN1 $i."n" close OUT1; close IN;sub levenshtein($)my A=split ®B);my ($i, $j, $cur, $next);for $i (0.$#A)$cur=$i+1;for $j (0.$#B) $next=min( $W$j+1+1, $cur+1,($A$i ne $B$j)+$W$j);$W$j=$cur;$cur=$next; $WB=$next;return $next;sub min($)if ($_0 < $_2) pop ®_; else shift ®_; return $_0 < $_1? $_0:$_1;sub leng #当2个数据进行模糊匹配的数据，用最长字符的数据底数相除/ my ($s1,$s2) = _;my $len1 = length $s1;my $len2 = length $s2;my $ss1=$len1>$len2?$len1:$len2;my $ss2=$len1<$len2?$len1:$len2;if ($ss2/$ss1> #只有最大字符和最小字符长度的比较大与80%勺时候才调用算法，这样可以提高速度 return ($s1,$s2) /sub leng11'/ my ($s1,$s2) = ®_;/my $len1 = length $s1;my $len2 = length $s2;return $len1>$len2?$len1:$len2 )动态规划算法与模糊匹配的比较进行序列的两两比对最直接的方法就是生成两条序列所有可能的比对，分别计算得分 函数，然后挑选一个得分最高或代价最小的比对作为最终结果。但是两条序列可能的比对 数非常多，是序列长度的指数函数，随着序列长度的增长，计算量呈指数增长。模糊匹配 采用文本方式的处理，来进行字符串相似度的匹配做法，速度会很慢。可能有 100左右各 字符需要半个小时去处理，而实际中，生物信息中的数据字符是大量而冗长的。从算法时 间复杂性的角度来看，这种比对方法显然不合适。而动态规划寻优策略就是针对寻求最佳 序列比对这一问题提出的。/ 通过实际编程运行可知，动态规划算法在时间效率上的优势是模糊匹配无法比拟的。 它把一个问题分解成计算量合理的子问题，并使用这些这些子问题的结果来计算最终答 案。动态规划算法无疑是生物信息学的基本算法之一。 三结论 /序列比较是生物信息学中最基本、最重要的操作，通过序列比较可以发现生物序列中 的功能、结构和进化的信息。序列比较的根本任务是：通过比较生物分子序列，发现它们 的相似性，找出序列之间共同区域，同时辨别序列之间的差异。在分子生物学中，DNA 或蛋白质的相似性是多方面的，可能是核酸或氨基酸序列的相似，可能是结构的相似，也 可能是功能的相似。一个普遍的规律是序列决定结构，结构决定功能。研究序列相似性的 目的之一是通过相似的额序列得到相似的结构或相似的功能一个目的是通过序列的相似性，判别序列之间的同源性，推测序列之间的进化关系。而针对生物信息，量大、字符串 长、更新快等特点，以及结合动态规划算法高效率寻优的特点，动态规划算法无疑是生物信息学中序列比对最重要经典的算法参考文献1 张敏.生物序列比对算法研究现状与展望.J大连大学学报，2004,25(4):75- 78.2 Huang X, Miller 2efficien t, linear 2sp acelocal siilarity algorithm J . A dv A pp l Math, 1991,2: 337.3 钟诚，陈国良.PRAM和LARPBS模型上的近似用匹配并行算法J.软件学报,2004,15(2):159 169./4 向永红等.P用的最大匹配算法UXVP计算机工程与科学.5 孙啸，陆祖宏，谢建明.生物信息学基础，清华大学出版社,2005,3(82).