用于序列匹配器的 Python difflib 库的奇怪行为

Question

我对 difflib 库中的一个奇怪行为感到有些困惑。我尝试在字符串中找到重叠序列（实际上是来自 Rosalind 任务的 Fasta 序列）以将它们粘合在一起。代码 adapted from here 适用于较小长度的字符串（为了清楚起见，我在这里构建了一个来自公共子字符串 a 的示例）：

import difflib

def glue(seq1, seq2):     
    s = difflib.SequenceMatcher(None, seq1, seq2)
    start1, start2, overlap = s.find_longest_match(0, len(seq1), 0, len(seq2)) 
    if start1 + overlap == len(seq1) and start2 == 0:
        return seq1 + seq2[overlap:]
    #no overlap found, return -1
    return -1


a = "ABCDEFG"
s1 = "XXX" + a
s2 = a + "YYY"

print(glue(s1, s2))

输出

XXXABCDEFGYYY

但是当字符串较长时，difflib 不再找到匹配项。

a = "AGGTGTGCCTGTGTCTATACATCGTACGCGGGAAGGTCCAAGTTAACATGGGGTACTGTAATGCACACGTACGCGGGAAGGTCCAAGTTAACTACGAAACGCGAGCCCATCTTTGCCGGTGTTAACTTGCTGTCAGGTGTTTGGCAAGGATCTTTGTTTGCCGGTGTTAACTTGCTGTCAGGTGTTTGGCCGGTGTTAACTTGCTGTCAGATGCGCGCCACGGCCAAATTCTAGGCACGCCAAATTCTAGGCACTTTAAGTGGTTCGATGATCCACGATGGTAAGCCAGCCGTACTTGC"

s1 = "XXX" + a
s2 = a + "YYY"

print(glue(s1, s2))

输出

-1

为什么会发生这种情况，如何将 difflib 用于更长的字符串？

Answer 1

我注意到，当 "ATCG" 字符串的长度超过 200 时，这种行为就开始了。在 difflib 文档页面上寻找这个数字让我看到了这段话：

Automatic junk heuristic: SequenceMatcher supports a heuristic that automatically treats certain sequence items as junk. The heuristic counts how many times each individual item appears in the sequence. If an item’s duplicates (after the first one) account for more than 1% of the sequence and the sequence is at least 200 items long, this item is marked as “popular” and is treated as junk for the purpose of sequence matching. This heuristic can be turned off by setting the autojunk argument to False when creating the SequenceMatcher.

由于序列只包含 ATCG，它们当然超过 200 个字符序列的 1%，因此被认为是垃圾。将代码更改为

import difflib

def glue(seq1, seq2):     
    s = difflib.SequenceMatcher(None, seq1, seq2, autojunk = False)
    start1, start2, overlap = s.find_longest_match(0, len(seq1), 0, len(seq2)) 
    if start1 + overlap == len(seq1) and start2 == 0:
        return seq1 + seq2[overlap:]
    return -1

摆脱这种行为并允许不受限制地进行子字符串匹配。
我想我把它留在这里，因为我浪费了几个小时来梳理我的代码来找到这个问题。

用于序列匹配器的 Python difflib 库的奇怪行为

Strange behaviour of Python difflib library for sequence matcher

python

biopython

difflib

rosalind