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

Question

我有一些绳子

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

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

^{pr2}$

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

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

Answer 1

要确定两个字符串a和b的重叠，可以检查b的前缀是否是a的后缀。然后，您可以在一个简单的循环中使用该检查，聚合结果并根据重叠对列表中的下一个字符串进行切片。在

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

def overlap(a, b):
    return max(i for i in range(len(b)+1) if a.endswith(b[:i]))

res = lst[0]
for s in lst[1:]:
    o = overlap(res, s)
    res += s[o:]
print(res) # SGALWDVPSPV

或使用reduce：

^{pr2}$

这可能不是超高效的，复杂度大约为O（nk），n是列表中的字符串数，k是每个字符串的平均长度。只需测试b的假定重叠的最后一个字符是否是a的最后一个字符，从而减少生成器表达式中字符串切片和函数调用的数量，从而提高效率：

def overlap(a, b):
    return max(i for i in range(len(b)) if b[i-1] == a[-1] and a.endswith(b[:i]))

Answer 2

下面是一个快速排序解决方案：

s = ['SGALWDV', 'GALWDVP', 'ALWDVPS', 'LWDVPSP', 'WDVPSPV']
new_s = sorted(s, key=lambda x:s[0].index(x[0]))
a = new_s[0]
b = new_s[-1]
final_s = a[:a.index(b[0])]+b

输出：

^{pr2}$

此程序按每个元素第一个字符的索引值对s进行排序，试图找到最大化第一个元素与所需输出之间重叠距离的字符串。在

Answer 3

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

#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]值）以防止错误匹配的方法。最后一个假设是所有匹配都是精确的。在装配序列时允许不匹配的灵活性使得问题变得相当复杂。我可以提供一个解决方案，组装错配应要求。在