Locating Motifs Despite Introns

In “Finding a Shared Motif”, we discussed searching through a database containing multiple genetic strings to find a longest common substring of these strings, which served as a motif shared by the two strings. However, as we saw in “RNA Splicing”, coding regions of DNA are often interspersed by introns that do not code for proteins.

We therefore need to locate shared motifs that are separated across exons, which means that the motifs are not required to be contiguous. To model this situation, we need to enlist subsequences.

Problem

A string uu is a common subsequence of strings ss and tt if the symbols of uu appear in order as a subsequence of both ss and tt. For example, “ACTG” is a common subsequence of “AACCTTGG“ and “ACACTGTGA”.
Analogously to the definition of longest common substring, uu is a longest common subsequence of ss and tt if there does not exist a longer common subsequence of the two strings. Continuing our above example, “ACCTTG” is a longest common subsequence of “AACCTTGG” and “ACACTGTGA”, as is “AACTGG”.
Given: Two DNA strings ss and tt (each having length at most 1 kbp) in FASTA format.
Return: A longest common subsequence of ss and tt. (If more than one solution exists, you may return any one.)

Sample Dataset

Rosalind_23
AACCTTGG
>Rosalind_64
ACACTGTGA

Sample Output

AACTGG

Solution

本题让求最长公共子序列，然后输出一条（可能大于等于 1 ）最优解。
语雀内容
下面代码是是用动态规划后使用回溯算法得到 所有最优解 ```python from typing import List class Solution: def longestCommonSubsequence(self, text1: str, text2: str) -> int: m, n = len(text1), len(text2)

  1.     # 1. 填写 dp 表格
  2.     dp = [[0] * (n + 1) for _ in range(m + 1)]
  3.     for i in range(1, m + 1):
  4.         for j in range(1, n + 1):
  5.             if text1[i-1] == text2[j-1]:
  6.                 dp[i][j] = dp[i-1][j-1] + 1
  7.             else:
  8.                 dp[i][j] = max(dp[i-1][j], dp[i][j-1])
  9.     # 2. 回溯路径输出
  10.     path = []
  11.     res = []
  12.     def backtrace(i: int, j: int) -> None:
  13.         if dp[i][j] == 0:  # 结束
  14.             res.append("".join(reversed(path)))
  15.             return
  16.         if text1[i-1] == text2[j-1]:
  17.             path.append(text1[i-1])
  18.             backtrace(i - 1, j - 1)
  19.             path.pop()
  20.         else:
  21.             if dp[i][j] == dp[i-1][j]:
  22.                 backtrace(i - 1, j)
  23.             if dp[i][j] == dp[i][j-1]:
  24.                 backtrace(i, j - 1)
  25.     backtrace(m, n)
  26.     return res

seqs = “””

Rosalind_23 AACCTTGG Rosalind_64 ACACTGTGA “”” import re s, t = (seq.replace(‘\n’, ‘’) for seq in re.split(r’>.*’, seqs) if seq.replace(‘\n’, ‘’)) # 第一个是 \n

for subseq in Solution().longestCommonSubsequence(s, t): print(subseq) # AACTGG

  1. 输出结果：

AACTTG ACCTTG AACTTG ACCTTG AACTGG ACCTGG

  1. 上面回溯时间复杂度太高，当遇到输入字符串太长时，等一千年后再出结果。因此只需要得到一条最佳路径即可。
  2. ```python
  3. from typing import List
  4. class Solution:
  5.     def longestCommonSubsequence(self, text1: str, text2: str) -> int:
  6.         m, n = len(text1), len(text2)
  7.         # 1. 填写 dp 表格
  8.         dp = [[0] * (n + 1) for _ in range(m + 1)]
  9.         for i in range(1, m + 1):
  10.             for j in range(1, n + 1):
  11.                 if text1[i-1] == text2[j-1]:
  12.                     dp[i][j] = dp[i-1][j-1] + 1
  13.                 else:
  14.                     dp[i][j] = max(dp[i-1][j], dp[i][j-1])
  15.         # 2. 回溯路径输出
  16.         path = []
  17.         res = []
  18.         def backtrace(i: int, j: int) -> bool:
  19.             if dp[i][j] == 0:  # 结束
  20.                 res.append("".join(reversed(path)))
  21.                 return True  # 一次就好
  22.             if text1[i-1] == text2[j-1]:
  23.                 path.append(text1[i-1])
  24.                 if backtrace(i - 1, j - 1): return True  # 找到一个最优解停止递归
  25.                 path.pop()
  26.             else:
  27.                 if dp[i][j] == dp[i-1][j]:
  28.                     if backtrace(i - 1, j): return True  # 找到一个最优解停止递归
  29.                 if dp[i][j] == dp[i][j-1]:
  30.                     if backtrace(i, j - 1): return True  # 找到一个最优解停止递归
  31.         backtrace(m, n)
  32.         return res
  34. seqs = """
  35. >Rosalind_23
  36. AACCTTGG
  37. >Rosalind_64
  38. ACACTGTGA
  39. """
  40. import re
  41. s, t = (seq.replace('\n', '') for seq in re.split(r'>.*', seqs) if seq.replace('\n', ''))  # 第一个是 `\n`
  43. for subseq in Solution().longestCommonSubsequence(s, t):
  44.     print(subseq)  # AACTGG