如何在python中合并重叠字符串？

Question

我有一些绳子

['SGALWDV', 'GALWDVP', 'ALWDVPS', 'LWDVPSP', 'WDVPSPV']

这些字符串部分重叠。如果您手动重叠它们，您将得到：

^{pr2}$

我想要一种从重叠字符串列表到python中最终压缩字符串的方法。我觉得这一定是一个问题，有人已经解决了，并试图避免重蹈覆辙。我现在能想到的方法要么是蛮力，要么是使用生物塞隆和序列比对器变得比我想要的更复杂。我只想用简单的方式把它们合并起来。在

有人对用python实现这一点的好方法有什么建议吗？谢谢！在

Answer 1

我提出的解决方案有一个更具挑战性的测试列表：

#strFrag = ['SGALWDV', 'GALWDVP', 'ALWDVPS', 'LWDVPSP', 'WDVPSPV']
strFrag = ['ALWDVPS', 'SGALWDV', 'LWDVPSP', 'WDVPSPV', 'GALWDVP', 'LWDVPSP', 'ALWDVPS']

for repeat in range(0, len(strFrag)-1):
    bestMatch = [2, '', ''] #overlap score (minimum value 3), otherStr index, assembled str portion
    for otherStr in strFrag[1:]:
        for x in range(0,len(otherStr)):
            if otherStr[x:] == strFrag[0][:len(otherStr[x:])]:
                if len(otherStr)-x > bestMatch[0]:
                    bestMatch = [len(otherStr)-x, strFrag.index(otherStr), otherStr[:x]+strFrag[0]]
            if otherStr[:-x] == strFrag[0][-len(otherStr[x:]):]:
                if x > bestMatch[0]:
                    bestMatch = [x, strFrag.index(otherStr), strFrag[0]+otherStr[-x:]]
    if bestMatch[0] > 2:
        strFrag[0] = bestMatch[2]
        strFrag = strFrag[:bestMatch[1]]+strFrag[bestMatch[1]+1:]

print(strFrag)       
print(strFrag[0])

基本上，代码将每个字符串/片段与列表中的第一个进行比较，并找到最佳匹配（大部分重叠）。它逐步合并列表，合并最佳匹配项并删除单个字符串。代码假定字符串/片段之间没有无法填充的间隙（否则答案可能不会导致尽可能长的汇编）。可以通过将起始字符串/片段随机化来解决）。还假设不存在反向补码（contig assembly的错误假设），这将导致无意义/不匹配的字符串/片段。我已经包含了一种限制最小匹配要求（更改bestMatch[0]值）以防止错误匹配的方法。最后一个假设是所有匹配都是精确的。在装配序列时允许不匹配的灵活性使得问题变得相当复杂。我可以提供一个解决方案，组装错配应要求。在