从原始字符串返回两个不匹配的序列

Question

我正在寻找一些代码来返回原始字符串中有两个不匹配的所有序列，以便找到与我输入的原始序列相似的部分蛋白质序列。例如，在LELFLKEF中搜索LKLD应该返回： 列尔夫 LKEF公司 LFLK公司 我已经研究了各种python方法来实现这一点，但是我似乎没有做任何工作。你知道吗

Search for string allowing for one mismatch in any location of the string

String regex two mismatches Python

Ambiguous substring with mismatches

Answer 1

一种简单的方法是遍历序列，并为查询“LKLD”到主题序列“LELFLKEF”的每个对齐计算hamming distance。链接的wikipedia文章中有一个汉明距离计算的示例实现。一旦你知道你的代码会做如下事情：

# hamming distance
d = lambda s1, s2: sum(e1 != e2 for e1, e2 in zip(s1, s2))

subject = 'LELFLKEF'
query = 'LKLD'
for i in range(len(subject)-len(query)+1):
    aligned_subject = subject[i:i+len(query)]
    if d(aligned_subject, query) == 2:
         print(aligned_subject)

输出：

LELF
LFLK
LKEF

请注意，这是一个有点幼稚的解决方案，有很大的优化空间，但它适用于简单的情况和相当小的字符串。生成列表的压缩版本：

s='LELFLKEF'
q='LKLD'
d= lambda s1, s2: sum(e1 != e2 for e1, e2 in zip(s1, s2))
[s[i:i+len(q)] for i in range(len(s)-len(q)+1) if d(s[i:i+len(q)],q) == 2]

for循环遍历两个字符串的所有可能的无上限对齐：

0
LELFLKEF
||||
LKLD
 1
LELFLKEF
 ||||
 LKLD
  2
LELFLKEF
  ||||
  LKLD
   3
LELFLKEF
   ||||
   LKLD
    4
LELFLKEF
    ||||
    LKLD

对于alignment of biological sequences问题也有许多实现，因此您可能还想探索一些更复杂的技术来处理诸如间隙对齐和more complicated modeling of substitutions之类的问题