假设我们有两个字符串“abcdefgh”和“abudesh”。我希望解决方案是一个列表 ["ab"、"de"、"h"]。所以,我想要一个最大连接的子串列表,这些子串对于两个字符串都是相同的。这有名称吗?什么是解决它的好方法?
编辑:我需要说顺序并不重要,例如,如果我们有两个字符串“abcdefg”和“defkabc”,结果是 ["abc", "def"]。
最佳答案
使用:
- 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 组的字母。
关于algorithm - 两个字符串的最大公共(public)连接子串列表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/70553816/