Algorithm 版 (精华区)

发信人: ssos (存在与虚无), 信区: Algorithm
标  题: 生物信息学笔记（一）
发信站: 哈工大紫丁香 (2001年06月08日18:49:23 星期五), 站内信件

我记的不全，欢迎各位指正和补充！
提要
1 序列比对(sequence alignment)
2 最短超串(shortest superstring problem)
2 DDP
参考书
1 M. S. Waterman,Introduction to computational Biology:
 maps,sequences,genomes,1995
2 D.Gausfield,Algorithms on strings,trees and sequences:
 compter science and computational biology
3 D. S. Hochbaum,Approximation algorithms for NP-hard problems,
 1998
§1 序列比对
一、编辑距离
a=a1a2...an,b=b1b2...bm,通过插入-得到两个串a*1a*2...a*l,b*1b*2...b*l.
定义d(x,y),x,y是单个字母或-，满足通常度量的性质：正定性、对称性和三角不等式.
             l
D(a,b)=min SIGMA d(a*i,b*i)
            i=1
D(a,b)可通过动态规划求，算法时间O(mn)
二、相似度
定义s(x,y)：
       >0 ,x=y
s(x,y)
       <0, x<>y
s(x,-)=s(-,x)=-delta,delta>0
             l
S(a,b)=max SIGMA s(a*i,b*i)
            i=1
注：编辑距离与相似度有密切联系，但相似度较通用。在局部比对时，
只能用相似度。
举一个例子，S1=pqraxabcstvq,S2=xyaxbacsll,令s(x,x)=2,
s(x,y)=-2,x<>y,s(x,-)=-1.则alpha=axabcs与beta=axbacs是最优对，相似度为8。
如这时用编辑距离，求其最小值，解只能是单个字母的子串。
三、模式识别
给定a=a1a2...an,b=b1b2...bm,n<<m，求b的子序列bk bk+1 ... bl,1<=k<=l<=m,
使S(a,bk bk+1 ... bk+l)最大。
直接法时间O(nm^3)，动态规划时间O(nm)。
四、局部比对
求H(a,b)=max{0,S(ai...aj,bk...bl)|1<=i<=j<=n,1<=k<=l<=m}.
五、成串重复
求R(a,b)=max{0,S(as...at,bu...bm b^l b1...bv)|1<=s<=t<=n,
 1<u<=m,1<=v<m,l>=0}.

--

   
<<社会契约论>>是一本好书,应当多读几遍
风味的肘子味道不错,我还想再吃它      

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.230.220]