python - 罗莎琳德溶液固定: shared motifs

Question

我知道罗莎琳德挑战有解决方案，但我不希望它们破坏乐趣。我以为我找到了“寻找共享主题”的解决方案，但我的答案始终是错误的。

问题是在给定的工作表中找到最长的公共(public)子字符串，该工作表由以“>”开头的行和下一行组成，直到另一行以“>”开头的行组成一个序列。它是这样的:

>Rosalind_1
GATTACA
>Rosalind_2
TAGACCA
>Rosalind_3
ATACA

大约有一百个 DNA 片段，您需要找到最长的公共(public)子序列。这是我的方法:

    rosa = open("rosalind_lcsm.txt","r")
    oku = rosa.readlines()
    strs=[]
    for line in oku:
        if line.startswith(">"):
            strs.append("kiko")
        else:
            strs.append(line)
    rosa.close()
    strs = strs[1:]
    joint = "".join(strs)
    joint_s = joint.split("kiko")

    theOne = joint_s[0]
    rest = joint_s[1:]

    start=0
    end=1
    matches=[]

    while end < len(theOne):
        end+=1
        while all(theOne[start:end] in seq for seq in rest):
            end+=1
        else:
            matches.append(theOne[start:end-1])
            end+=1
        start=end-1
    print(max(matches, key=len))

我的策略是:读取文件，将其拆分为序列，选择第一个序列并将其公共(public)部分与其余部分进行比较。我正在检查至少 2 个匹配项，因为序列是由 ATGC 组成的，并且肯定会发生 1 个匹配项。它从一个字符开始，并不断将其扩展 1 个字符，直到匹配中断。然后它获取最后一个匹配位并附加到列表中。然后从停止的地方重新开始。

我的解决方案给出了答案，但它不是正确的答案，而且我无法发现代码中的误导部分。有人可以尝试理解我的方法并给我修复它的建议吗？

Answer 1

我不会说Python，但我认为你通过执行start=end-1跳过了可能的匹配。您可能需要执行 start=start+1。

例如，假设您有以下字符串:

GATCAAGAGCAATCAA

您的算法将首先查找 GA 作为公共(public)子串，然后从第三个字符继续查找。但这样你就错过了真正的最长公共(public)子串，ATCAA。

编辑:显然，您还需要与start一起重新初始化end。您可以将其设置为 start+1 以始终像您所做的那样从两个字母的字符串开始查找，或者您可以通过从找到的最长匹配的长度开始来优化代码到目前为止。