Вопрос динамического программирования подпоследовательности ДНК

Question

Я пытаюсь решить проблему ДНК, которая является более улучшенной (?) Версией проблемы LCS.В задаче есть строка, которая является строкой и полуподстрокой, которая позволяет части строки пропустить одну или ни одной буквы.Например, для строки "desktop" в ней есть полустрока {"destop", "dek", "stop", "skop","desk","top"}, у каждой из которых пропущена одна буква или ее нет.

Теперь мне даны две строки ДНК, состоящие из {a,t,g,c}.Я пытаюсь найти самую длинную полу-подстроку, LSS. И если существует более одной LSS, распечатайте ее в самом быстром порядке.

Например, две дн {attgcgtagcaatg, tctcaggtcgatagtgac} распечатывает "tctagcaatg"

и aaaattttcccc, cccgggggaatatca распечатывает "aattc"

Я пытаюсь использовать общий алгоритм LCS, но не могу решить его с помощью таблиц, хотя я решил его без пропущенной буквы. Любой совет?

Answer 1

Это вариант решения для динамического программирования для LCS, написанный на Python.

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

Обратите внимание, что это технически O(n^2).В худшем случае, когда обе строки имеют одинаковый символ, повторяются снова и снова.Поскольку вы получаете много чего-то похожего, «l» в позиции 42 в одной строке могло бы совпадать с позицией l в позиции 54 в другой ».Но на практике это будет O(n).

def find_subtree (text, max_skip=1):
    tree = {}
    tree_at_position = {}

    def subtree_from_position (position):
        if position not in tree_at_position:
            this_tree = {}
            if position < len(text):
                char = text[position]
                # Make sure that we've populated the further tree.
                subtree_from_position(position + 1)

                # If this char appeared later, include those possible matches.
                if char in tree:
                    for char2, subtree in tree[char].iteritems():
                        this_tree[char2] = subtree

                # And now update the new choices.
                for skip in range(max_skip + 1, 0, -1):
                    if position + skip < len(text):
                        this_tree[text[position + skip]] = subtree_from_position(position + skip)

                tree[char] = this_tree

            tree_at_position[position] = this_tree

        return tree_at_position[position]

    subtree_from_position(0)

    return tree


def find_longest_common_semistring (text1, text2):
    tree1 = find_subtree(text1)
    tree2 = find_subtree(text2)

    answered = {}
    def find_intersection (subtree1, subtree2):
        unique = (id(subtree1), id(subtree2))
        if unique not in answered:
            answer = {}
            for k, v in subtree1.iteritems():
                if k in subtree2:
                    answer[k] = find_intersection(v, subtree2[k])
            answered[unique] = answer
        return answered[unique]


    found_longest = {}
    def find_longest (tree):
        if id(tree) not in found_longest:
            best_candidate = ''
            for char, subtree in tree.iteritems():
                candidate = char + find_longest(subtree)
                if len(best_candidate) < len(candidate):
                    best_candidate = candidate
            found_longest[id(tree)] = best_candidate
        return found_longest[id(tree)]

    intersection_tree = find_intersection(tree1, tree2)
    return find_longest(intersection_tree)


print(find_longest_common_semistring("attgcgtagcaatg", "tctcaggtcgatagtgac"))

Answer 2

Пусть g(c, rs, rt) представляет самую длинную общую подстроку строк, S и T, заканчивающуюся на rs и rt, где rs и rt - ранжированные вхождения символа, c, в S и T соответственно, а K - количество допустимых пропусков.Затем мы можем сформировать рекурсию, которую мы обязаны выполнить для всех пар c в S и T.

Код JavaScript:

function f(S, T, K){
  // mapS maps a char to indexes of its occurrences in S
  // rsS maps the index in S to that char's rank (index) in mapS
  const [mapS, rsS] = mapString(S)
  const [mapT, rsT] = mapString(T)
  // h is used to memoize g
  const h = {}

  function g(c, rs, rt){
    if (rs < 0 || rt < 0)
      return 0
    
    if (h.hasOwnProperty([c, rs, rt]))
      return h[[c, rs, rt]]
      
    // (We are guaranteed to be on
    // a match in this state.)
    let best = [1, c]
    
    let idxS = mapS[c][rs]
    let idxT = mapT[c][rt]

    if (idxS == 0 || idxT == 0)
      return best

    for (let i=idxS-1; i>=Math.max(0, idxS - 1 - K); i--){
      for (let j=idxT-1; j>=Math.max(0, idxT - 1 - K); j--){
        if (S[i] == T[j]){
          const [len, str] = g(S[i], rsS[i], rsT[j])

          if (len + 1 >= best[0])
            best = [len + 1, str + c]
        }
      }
    }
  
    return h[[c, rs, rt]] = best
  }

  let best = [0, '']
  
  for (let c of Object.keys(mapS)){
    for (let i=0; i<(mapS[c]||[]).length; i++){
      for (let j=0; j<(mapT[c]||[]).length; j++){
        let [len, str] = g(c, i, j)
        
        if (len > best[0])
          best = [len, str]
      }
    }
  }
  
  return best
}

function mapString(s){
  let map = {}
  let rs = []
  
  for (let i=0; i<s.length; i++){
    if (!map[s[i]]){
      map[s[i]] = [i]
      rs.push(0)
    
    } else {
      map[s[i]].push(i)
      rs.push(map[s[i]].length - 1)
    }
  }
  
  return [map, rs]
}

console.log(f('attgcgtagcaatg', 'tctcaggtcgatagtgac', 1))

console.log(f('aaaattttcccc', 'cccgggggaatatca', 1))

console.log(f('abcade', 'axe', 1))