两个字符串最大公共连续子串列表

Question

两个字符串最大公共连续子串列表

algorithm

3

假设我们有两个字符串 "abcdefgh" 和 "abudesh"。我希望解决方案是一个列表 ["ab", "de", "h"]，即最大相同子字符串的列表，它们在两个字符串中都相同。这种情况是否有名称，并且解决它的好方法是什么？

编辑：我需要说明的是，顺序对结果没有影响，例如，如果我们有两个字符串 "abcdefg" 和 "defkabc"，则结果为 ["abc", "def"]。

答：这个问题被称为最长公共子序列问题。可以使用动态规划算法来解决此问题。

- Alem

你希望 O(n^2) 的时间复杂度吗？ - Ashish sah

@Ashishsah 嗯，我的字符串不多（只有大约6000个），所以任何解决方案在这种情况下都可以工作，可能是可以的。 - Alem

1

这个 Python 包声称可以使用后缀树在线性时间内解决此问题。我自己没有尝试过，可能还有更受欢迎的后缀树包。 - hilberts_drinking_problem

1

@Alem 正在处理，让我们看看我能否使用循环找到最优解。 - Ashish sah

1

玩一下Biopython吧。print( pairwise2.align.globalxx('abcdefgh', 'abudesh') )会输出

[Alignment(seqA='abc-defg-h', seqB='ab-ude--sh', score=5.0, start=0, end=10), Alignment(seqA='abcdefg-h', seqB='abude--sh', score=5.0, start=0, end=9), Alignment(seqA='abc-defgh', seqB='ab-ude-sh', score=5.0, start=0, end=9), Alignment(seqA='abcdefgh', seqB='abude-sh', score=5.0, start=0, end=8), Alignment(seqA='abc-defgh', seqB='ab-udes-h', score=5.0, start=0, end=9), Alignment(seqA='abcdefgh', seqB='abudes-h', score=5.0, start=0, end=8)]

。 - Stef

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Stef · Accepted Answer

使用:

Biopython的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组中的字母。