Странное поведение библиотеки Python difflib для соответствия последовательности

Question

Я несколько озадачен странным поведением в difflib библиотека. Я пытаюсь найти перекрывающиеся последовательности в строках (на самом деле последовательности Fasta из задачи Розалинд), чтобы склеить их вместе. Код, адаптированный здесь, хорошо работает с меньшей длиной строки (для ясности, я построю здесь пример из общей подстроки 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 Страница документации привела меня к этому отрывку:

Автоматическая эвристика мусора: SequenceMatcher поддерживает эвристику, которая автоматически обрабатывает определенные элементы последовательности как нежелательные. Эвристика подсчитывает, сколько раз каждый отдельный элемент появляется в последовательности. Если дубликаты элемента (после первого) составляют более 1% последовательности, а длина последовательности составляет не менее 200 элементов, этот элемент помечается как "популярный" и рассматривается как нежелательный для соответствия последовательности. Эту эвристику можно отключить, установив аргумент autojunk в False при создании SequenceMatcher.

Поскольку последовательность содержит только ATCG они, конечно, более 1% последовательности из 200 символов и, следовательно, считаются ненужными. Изменение кода на

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

избавляется от этого поведения и позволяет сопоставлять подстроки без ограничений.
Я думал, что оставлю это здесь на SO, потому что я потратил часы, перебирая свой код, чтобы найти эту проблему.