python实现动态规划算法寻找最优匹配子串问题

Question

如题，譬如现在有一串字符串s1=“agtcgtaatgc”,想将另一个字符串s2="cgaa"比对到s1上，可以看到s2并非完全比对到s1上面，其中是有一个错配的。现在我要实现的就是寻找s2比对到s1上面的错配最少的位点。请多多指教，谢谢！

Answer 1

把较低的mismatch用字典保存一下，就好了。如：
def match(s1,s2):

length = len(s2)
result = ""
resultMissmatchCount=length
seqdict={}
for index,s in enumerate(s1[:-length]):
    missmatch = 0
    for j,k in zip(s1[index:index+length],s2): #[（s1[0],s2[0]),(s1[1],s2[1]),...]
        if j!=k:
            missmatch += 1
    if missmatch <= resultMissmatchCount: 
        seqdict[missmatch]=s1[index:index+length] 
        resultMissmatchCount = missmatch
minkey=min(seqdict.keys())
result = seqdict[minkey]
return result

Answer 2

算法什么的水平有限.. 用最好理解的方式写了一下。
这个记得时在刷题的时候看到的类似的，不过题目要求的时找出匹配的字段。
想象s2是一个窗口，在s1上从左向右滑动，每次滑动一个格子，计算现在字段的有多少错配点位。最后找出最小的一个。
我这么写这能找出最后一个。当然 <=改成<就是第一个了。

def match(s1,s2):
    length = len(s2)
    result = ""
    resultMissmatchCount=length
    for index,s in enumerate(s1[:-length]):
        missmatch = 0
        for j,k in zip(s1[index:index+length],s2):
            if j!=k:
                missmatch += 1
        if missmatch <= resultMissmatchCount:
            resultMissmatchCount = missmatch
            print s1[index:index+length]
            result = s1[index:index+length]
    return result

Answer 3

python3
difflib

import difflib

s1='agtcgtaatgc'
s2="cgaa"
mch=difflib.SequenceMatcher(a=s1,b=s2)
m=mch.find_longest_match(0,len(s1),0,len(s2))
print(s1[m.a:m.a+m.size],s2[m.b:m.b+m.size])
#cg cg

---

import numpy as np
s1='agtcgtaatgc'
s2="cgaa"
a = np.fromstring(s1,'S1')==np.fromstring(s2,'S1').reshape(-1,1)
i = max(range(len(s1)), key= a.trace)
print(s1[i:i+len(s2)])
#'cgta'