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

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

0 голосов
/ 05 мая 2018

Я несколько озадачен странным поведением в библиотеке 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 с более длинными строками?

1 Ответ

0 голосов
/ 05 мая 2018

Я заметил, что такое поведение начинается, когда строка «ATCG» длиннее 200. Поиск этого числа на странице документации difflib привел меня к этому отрывку:

Автоматическая эвристика мусора: SequenceMatcher поддерживает эвристику, которая автоматически обрабатывает определенные элементы последовательности как ненужные. Эвристический подсчитывает, сколько раз каждый отдельный элемент появляется в последовательности. Если дубликаты элемента (после первого) составляют более 1% последовательность и последовательность длиной не менее 200 элементов, этот элемент помечен как «популярный» и рассматривается как мусор с целью последовательности соответствия. Эту эвристику можно отключить, установив автоханк аргумент 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, потому что я потратил часы, перебирая свой код, чтобы найти эту проблему.

...