rosalind解决方案修复:共享主题

Question

我知道对于rosalind挑战有解决方案，但我不希望它们破坏乐趣。我以为我找到了“找到一个共同的主题”的解决方案，但我的答案总是错的。

问题是在给定的表中找到最长的公共子字符串，该表由以">“开头的行和下一行组成序列，直到另一行以">”开头。下面是它的外观：

>Rosalind_1
GATTACA
>Rosalind_2
TAGACCA
>Rosalind_3
ATACA

有大约一百个dna片段，你要找到最长的公共子序列。以下是我的方法：

    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))

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

我的解决方案给出了答案，但它不是正确的，并且我找不到代码中的误导性部分。有人可以试着理解我的方法，并给我一个修复它的建议吗？

Answer 1

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

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

GATCAA

您的算法将首先找到GA作为公用子字符串，然后继续从第三个字符开始查找。但那样的话，你就会遗漏真正最长的公用子字符串ATCAA。

EDIT:显然你还需要和start一起重新初始化end。要么将其设置为start+1，使其始终像现在这样从两个字母的字符串开始查找，要么从到目前为止找到的最长匹配的长度开始，对代码进行优化。