Partial Substring Matching in Python

Question

Я заинтересован в создании программы, которая будет искать определенную строку (известную в дальнейшем как строку A) в большой библиотеке других строк. В принципе, если строка A существовала в библиотеке, она была бы отброшена, а существование другой строки было бы проверено внутри библиотеки. Затем программа предоставит мне окончательный список строк, которые не существовали как подстроки в большой библиотеке. Я смог создать программу, которая находит соответствия EXACT, но мне нужно добавить дополнительный модуль, который позволяет подстрочному поиску разрешать частичные совпадения. А именно, один или два из символов подстроки будут в порядке. Список строк A (которые являются перестановками a, t, g, c в 7-буквенной строке 4^7 разных) имеет трудности с очень разнообразными библиотеками.

Моя первоначальная мысль заключалась в том, чтобы использовать регулярное выражение и, возможно, алгоритм расстояния от хамминга, чтобы найти все эти частичные совпадения. В основном эта первая попытка позволяет мне поставить «?» или подстановочный знак во всех положениях строки A, о которой идет речь (1-7), но я могу попасть только в первую позицию. Подстановочный знак затем позволит мне искать частичные совпадения конкретной строки A, о которой идет речь. Если это неправильный подход к решению этой проблемы, я бы с радостью ее изменил. Я использовал fnmatch согласно предложению на другой вопрос, это то, что я до сих пор:

from Bio import SeqIO 
import fnmatch 
import random 
import itertools 

#Define a splitting string algorithm 
def split_by_n(seq,n): 
    while seq: 
     yield seq[:n] 
     seq = seq[n:] 

#Import all combinations/permutations from fasta fille, 4^7 
my_combinations = [] 
fasta_sequences = SeqIO.parse(open("Combinations/base_combinations_7.fasta"),'fasta') 
for fasta in fasta_sequences: 
    name, sequence = fasta.id, str(fasta.seq) 
    x = sequence.lower() 
    my_combinations.append(x) 

primer = "tgatgag" 
final = [] 

#List to make wildcard permutations 
wildCard = ['?'] 

i = list(split_by_n(primer, 1)) 

for letter in i: 
    wildCard.append(letter) 

del wildCard[1] 

final.append(''.join(wildCard)) 

#Search for wildcard permutation 
for entry in final: 
    filtered = fnmatch.filter(my_combinations, entry) 

Это мой желаемый результат:

праймер = «tgatgag»

['?', 'g', 'a', 't', 'g', 'a', 'g'] 
['t', '?', 'a', 't', 'g', 'a', 'g'] 
['t', 'g', '?', 't', 'g', 'a', 'g'] 
['t', 'g', 'a', '?', 'g', 'a', 'g'] 
['t', 'g', 'a', 't', '?', 'a', 'g'] 
['t', 'g', 'a', 't', 'g', '?', 'g'] 
['t', 'g', 'a', 't', 'g', 'a', '?'] 
['agatgag', 'tgatgag', 'cgatgag', 'ggatgag'] 
['taatgag', 'ttatgag', 'tcatgag', 'tgatgag'] 
['tgatgag', 'tgttgag', 'tgctgag', 'tggtgag'] 
['tgaagag', 'tgatgag', 'tgacgag', 'tgaggag'] 
['tgataag', 'tgattag', 'tgatcag', 'tgatgag'] 
['tgatgag', 'tgatgtg', 'tgatgcg', 'tgatggg'] 
['tgatgaa', 'tgatgat', 'tgatgac', 'tgatgag'] 

Answer 1

Вот пример решения для замены 2-х элементов:

primer = 'cattagc' 
bases = ['a','c','g','t'] 

# this is the generator for all possible index combinations 
p = itertools.permutations(range(len(primer)), 2) 
# this is the list of all possible base pair combinations 
c = list(itertools.combinations_with_replacement(bases, 2)) 

results = [] 
for i1, i2 in p: 
    for c1, c2 in c: 
     temp = list(primer) 
     temp[i1], temp[i2] = c1, c2 
     results.append(''.join(temp)) 

Это создаст все возможные замены для su выбирая любые два элемента исходного праймера.