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

Question

我有一些字符串，

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

这些字符串部分重叠。如果你手动重叠它们，你会得到:

SGALWDVPSPV

我想要一种从重叠字符串列表到 python 中最终压缩字符串的方法。我觉得这一定是有人已经解决了的问题，并且正在努力避免重新发明轮子。我现在可以想象的方法要么是蛮力，要么涉及通过使用 biopython 和序列对齐器变得比我想要的更复杂。我有一些简单的短字符串，只想以简单的方式正确合并它们。

有没有人对在 python 中执行此操作的好方法有任何建议？谢谢!

Answer 1

这是一个快速排序的解决方案:

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

输出:

'SGALWDVPSPV'

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