algorithm - 两个字符串的最大公共(public)连接子串列表

Question

假设我们有两个字符串“abcdefgh”和“abudesh”。我希望解决方案是一个列表 ["ab"、"de"、"h"]。所以，我想要一个最大连接的子串列表，这些子串对于两个字符串都是相同的。这有名称吗？什么是解决它的好方法？

编辑:我需要说顺序并不重要，例如，如果我们有两个字符串“abcdefg”和“defkabc”，结果是 ["abc", "def"]。

Answer 1

使用:

• Biopython's pairwise2对齐两个序列；
• itertools.groupby对“最大连接子串”进行分组。

from Bio import pairwise2
from itertools import groupby

def maxConnectedSubstrings(strA, strB):
    alignment = pairwise2.align.globalxx(strA, strB)[0]
    grouped = groupby(zip(alignment.seqA, alignment.seqB), key=lambda p: p[0] == p[1])
    return [''.join(ca for ca,cb in g) for k,g in grouped if k]

print( maxConnectedSubstrings('abcdefgh', 'abudesh') )
# ['ab', 'de', 'h']

解释

首先，我们比对序列。 alignment = pairwise2.align.globalxx(strA, strB)[0] 的结果是:

alignment.seqA = 'abcdefgh'
alignment.seqB = 'abude-sh'

比对算法找到了在序列中添加 '-' 以比对它们的最佳方法。

然后，我们在 zip(alignment.seqA, alignment.seqB) 上使用 groupby。 zip(...) 是一对序列(来自 seqA 的字符，来自 seqB 的字符)。我们用键 lambda p: p[0] == p[1] 对这些对进行分组，结果如下:

grouped = groupby(zip(alignment.seqA, alignment.seqB), key=lambda p: p[0] == p[1])

grouped = [
    (True,  [('a', 'a'),
             ('b', 'b')]),
    (False, [('c', 'u')]),
    (True,  [('d', 'd'),
             ('e', 'e')]),
    (False, [('f', '-'),
             ('g', 's')]),
    (True,  [('h', 'h')])
]

最后，我们丢弃 False 组，并加入每个 True 组的字母。