найти и удалить общую подстроку с питоном

Question

Так у меня есть две последовательности праймера:

 
fiveprime = "GATTCGAAGTCCACTATC" 
threeprime = "TGAGTAGGACGGCACTATC" 

Что мне нужно сделать, когда у меня есть другая последовательность, мне нужно, чтобы проверить, если он содержит часть одного этих праймеров последовательности, и если это необходимо, мне нужно удалить соответствующую часть, оставляя несогласованную часть для дальнейшего анализа.

Например, моя последовательность: CACTATC AAAAAAA имеет часть пятипримаров в нем. Мне нужно найти эту общую подстроку, а затем удалить ее, оставив только AAAAA.

Проблема, с которой я столкнулся, - это когда у вас есть такая последовательность: CACTATC GAAG, где GAAG также находится в грунтовке, но не является частью последовательности праймеров, он все еще удаляется. Я попытался исправить это, убедившись, что найденная структура находится на левой стороне грунтовки и с threeprimer на правой стороне, так например:

С CACTATC Гаагом у нас есть 2 общие структуры CACTATC и Гааг теперь я могу сравнить CACTATC с конца fiveprime GATTCGAAGTC CACTATC и сказать, что это часть праймера, когда это совпадение, а затем удалить его. Поэтому, когда мы сравниваем GAAG с длиной последнего конца пятипринтера, он даст нам этот GATTCGAAGTCCAC TATC, который не соответствует, поэтому GAAG может продолжаться для дальнейшего анализа.

По какой-то причине мой скрипт ошибочно работает или работает неправильно. Есть ли другие решения этой проблемы или предложения?

def longestSubstringFinder(string1, string2): 
answer = "" 
len1, len2 = len(string1), len(string2) 
for i in range(len1): 
    match = "" 
    for j in range(len2): 
     if i + j < len1 and string1[i + j] == string2[j]: 
      match += string2[j] 
     else: 
      if len(match) > len(answer): answer = match 
      match = "" 
return answer 

def get_sequence(test, fiveprime, threeprime): 
    if test == fiveprime: 
     pass 
    elif test == threeprime: 
     pass 
    elif test in fiveprime: 
     pass 
    elif test in threeprime: 
     pass 

     # find out if there is a matching part between the primers and the found 
     # single stranded region, then calculates what part that is, and removes it 
     # from the single stranded region 
    else: 
     overlap = longestSubstringFinder(fiveprime, test) 
     l = len(overlap) 

     if fiveprime[-l:] == test[:l]: 
      check = test[l:] 
     else: 
      check = test 

     overlap2 = longestSubstringFinder(check, threeprime) 
     l = len(overlap2) 

     if threeprime[:l] == check[-l:]: 
      check2 = check[:-l] 
      structure.append(check2) 
     else: 
      structure.append(check) 

return structure 

Answer 1

Я думаю, что ваша проблема будет более приемлемой, если вы выберете подходящую структуру данных для представления данных, которые вы пытаетесь найти. Самый лучший, о котором я могу думать, - это trie.

Преимущество этой структуры состоит в том, что она позволяет вам представлять все возможные соответствия, заданные начальной последовательностью букв, поэтому, если у вас есть последовательность AABAB, она позволит обходить от начального А до А и В, но не обход от A до G или T. Это позволяет эффективно находить частичные совпадения, так как любая точка в trie соответствует совпадению этих букв.

Эта структура данных будет что-то вроде:

class Trie(object): 
    def __init__(self): 
     self.children = {} 

    def add_child(self, letter): 
     if letter in self.children: 
      return self.children[letter] 
     else: 
      child = Trie() 
      self.children[letter] = child 
      return child 

    def traverse(self, letter): 
     return self.children.get(letter, None) 

Вы можете населить это как так:

root = Trie() 
current_positions = [] 
for letter in letters: 
    current_positions = [ 
     position.add_child(letter) 
     for position in current_positions 
    ] 
    current_positions.append(root.add_child(letter)) 

После того, как все это установить, то вы должны быть способны пересекать эту структуру пока обход не вернет значение null. Это будет означать самое длинное совпадение тока. Инициализация букв рассматривает каждую букву как потенциальную начальную точку матча, и вы тоже.

Вы можете найти длинный подстрок следующим образом:

class TrieSearch(object): 
    def __init__(self, trie, starting_index): 
     self.trie = trie 
     self.starting_index = starting_index 
     self.ending_index = starting_index + 1 

    def update(self, letter): 
     """ This returns a boolean indicating 
      if the search can accept the letter """ 
     self.trie = self.trie.traverse(letter) 
     if self.trie is not None: 
      self.ending_index = self.ending_index + 1 
      return True 
     return False 

    def get_match(self, letters): 
     return letters[self.starting_index:self.ending_index] 

def find_matches(root, letters): 
    completed_matches = [] 
    current_matches = [] 

    for index, letter in enumerate(letters): 
     new_current = [] 

     for current in current_matches: 
      if current.update(letter): 
       new_current.append(current) 
      else: 
       completed_matches.append(current) 

     new_search_trie = root.traverse(letter) 
     if new_search_trie is not None: 
      new_current.append(TrieSearch(new_search_trie, index)) 

     current_matches = new_current 

    all_matches = completed_matches + current_matches 
    return [match.get_match(letters) for match in all_matches] 

Я положил все это вместе в a gist и когда Trie инициализируется со значениями threeprime и fiveprime и входные данные CACTATCAAAAAAA в результаты:

['CACTATC', 'ACTATC', 'CTATC', 'TATC', 'ATC', 'TC', 'CA', 'AA', 'AA', 'AA', 'AA', 'AA', 'AA', 'A'] 

Так как вы, без сомнения, имеет дело с массивными строками, вы можете рассмотреть некоторые из наиболее эффективных алгоритмов замещения вообще струнных , Aho-Corasick algorithm является расширением трехстороннего подхода, описанного здесь. Существует также Knuth-Morris-Pratt algorithm, который использует таблицы вместо trie. Оба эти алгоритма линейной сложности, которые будут существенным улучшением по сравнению с квадратичным подходом, который использует ваш подход longestSubstringFinder.

Answer 2

Проблема в том, что ваш longestSubstringFinder не работает. Вы проверяете if len(match) > len(answer): answer = matchтолько если условие if len(match) > len(answer): answer = match - False. Если цикл for j in range(len2): заканчивается без этого, вы просто отбрасываете match.

Исправить это просто: добавить for j in range(len2): после for j in range(len2): цикл.

def longestSubstringFinder(string1, string2): 
    answer = "" 
    len1, len2 = len(string1), len(string2) 
    for i in range(len1): 
     match = "" 
     for j in range(len2): 
      if i + j < len1 and string1[i + j] == string2[j]: 
       match += string2[j] 
      else: 
       if len(match) > len(answer): answer = match 
       match = "" 
     if len(match) > len(answer): answer = match # this was missing 
    return answer