DNA最长公共子序列

Question

所以这是一个家庭作业问题，它使我很困惑。我曾多次尝试编写这段代码，但仍然一无所获。问题是在两个DNA链之间找到最长的公共子序列，并打印这个序列。这里有谁能帮我，也能让我知道该怎么做吗？我已经设置了窗口，并使用find函数查看字符串相等的位置，然后设置一个max函数以只显示最长的字符串。

def main():

s1 = input("Enter first strand: ")
s2 = input("Enter second strand: ")
window = 0
if len(s1) < len(s2):
    window = len(s1)
elif len(s1) > len(s2):
    window = len(s2)
else:
    window = len(s1)
for i in range(window, 1, -1):
    for j in range(0, i, 1):
     if s1.find(s1[i:i + window]) == s2.find(s2[i:i + window]):
        max = a[0][0]
        for i in range(len(a)):
            for j in range(len(a[i]):
                if (a[i][j] > max):
                    max = a[i][j]
                    print ("Common Subsequence: ", max)
     else:
        print ("No Common Sequence Found")

main()

Answer 1

假设给你等长的股(因为这是作业，我就让你把它调整为不等长的股)

from itertools import zip_longest, chain
def longestCommonSubstring(p1, p2):

    answer = [[0.0 for _ in range(len(p2)+1)] for _ in range(len(p1)+1)]

    for r, row in enumerate(answer[1:], 1):
        for c, _ in enumerate(row[1:], 1):
            if p1[r-1] == p2[c-1]:
                answer[r][c] = answer[r-1][c-1]+1
            else:
                answer[r][c] = 0.0

    return max(chain.from_iterable(matrix))/max(len(p1), len(p2))

希望这能有所帮助

编辑：实现find

def myFind(string, substring):
    for i in range(len(string) - len(substring)):
        if string[i] == substring[0]:
            if string[i:i+len(substring)] == substring:
                print substring, "found in", string, "at position", i

如果不想使用字符串比较：

def myFind(string, substring):
    for i in range(len(string) - len(substring)):
        if string[i] == substring[0]:
            found = True
            for j in range(len(substring)):
                if string[i+j] != substring[j]:
                    found = False
            if found:
                print substring, "found in", string, "at position", i