编辑距离,重叠,组装算法和python程序解读.pptx

edit distance hamming距离是两个相等长度的字符串之间的距离。它只是等于将一个字符串转换为另一个字符串所需的替换数。你会排队你的字符串，x和y，通过比较每个位置。 在每种情况下，你发现对应的字符不匹配，你会添加1到计数器。 然后结束时，你只是报告那个数。 编辑距离定义为将一个字符串转换为另一个字符串所需的替换或插入或删除的最小数量。question:hammingDistance和这两个字符串的editDistance之间的关系。 它们是平等的，还是其中一个大于另一个，还是大于或等于另一个？ 例如： x: ACG Y: TCG hammingDistance和 editDistance相等，都为1然而 x: ACTGC Y: ATGCA editDistance为2，hammingDistance为4结论：X和Y之间的editDistance将总是小于或等于X和Y之间的hammingDistance 下限是editDistance必须至少与X和Y的长度之间的绝对差异一样大。如果我们知道这两个字符串的前缀之间的编辑距离帮助我们很多。例如： X : ACTG Y : A编辑距离至少为3 两个字符串之间的编辑距离可以计算为三个事物的最小值，即三个项。 def editDistRecursive(a,b): if len(a)==0: return len(b) if len(b)==0: return len(a) delt =1 if a[-1]!=b[-1]else 0 return min(editDistRecursive(a[:-1],b[:-1])+delt, editDistRecursive(a[:-1],b)+1, editDistRecursive(a,b[:-1])+1) 所以如果以后我们做相同的精确调用，我们调用具有相同参数的函数，那么我们可以记住答案是什么。 而不是再次运行该函数，这可能需要很多时间。下面为效率更好的算法： def editDistance(x,y): D=[] for i in range(len(x)+1): D.append([0]*(len(y)+1))  for i in range(len(x)+1): D[i][0]=i for i in range(len(y)+1): D[0][i]=i  for i in range(1,len(x)+1): for j in range(1,len(y)+1): distBor=D[i][j-1]+1 distVor=D[i-1][j]+1 if x[i-1]==y[i-1]: distDiag=D[i-1][j-1] else: distDiag=D[i-1][j-1]+1 D[i][j]=min(distBor,distVor,distDiag) return D[-1][-1] 近似匹配 近似匹配是一种允许误差的串匹配。这种误差的度量一般用编辑距离，记为k。衡量编辑距离的操作包括插入、删除、替换。问题的输入是文本T，模式P和编辑距离k，输出是匹配数或匹配位置。常用的方法包括动态规划、自动机、位并行和过滤算法。近似匹配也属于Non-standard Stringology问题。它最常见的应用背景来源于生物信息学。问题定义上，近似匹配中的k可以对模式中的任何字符的编辑操作进行计数。例如，给定文本T的子串T’= ……aacct……，P = aaacc，从P到T’要经过两次替换操作，因此k= 2。 A new solution to approximate matching 这是因为我们不知道提前在T内发生P的时间，因此每个偏移在这里是同样可能的，因此通过用全部0填充第一行，我们不偏向于任何特定偏移，其中P 可能发生在T.如果这一点现在不明显，它可能会在算法的描述后变得更清楚。 运用编辑距离相同的思想填写下面矩阵： 我们是如何得到这个2在底行？ 这样的方法的一个大问题是，他们可以很慢。因此，我们必须解决这个