Rosalind 033 Finding a Shared Spliced Motif

题目背景：

上述问题的解决方法是使用动态规划来找出两个DNA字符串的最长公共子序列（LCS）。

https://rosalind.info/problems/lcsq/

很经典的动态规划问题了。直接给出解题步骤：

1. 初始化矩阵：创建一个大小为 (len(s) + 1) x (len(t) + 1) 的矩阵。将第一行和第一列的元素初始化为零。这些代表了一个字符串与空字符串的LCS，其长度为零

2.?填充矩阵：对于矩阵中的每个元素 (i, j)（不包括第一行和第一列），检查字符 s[i-1] 和 t[j-1] 是否相等。

• 如果相等，该单元格的值为左上角对角线单元格 (i-1, j-1) 的值加1。
• 如果不相等，取其正上方 (i-1, j) 或左侧 (i, j-1) 单元格中的最大值。

下面上图来解释这个动态的过程：

3.?回溯找出LCS：从矩阵的右下角单元格 (len(s), len(t)) 开始回溯以重构LCS。

• 如果 s[i-1] 等于 t[j-1]，则该字符是LCS的一部分。向左上对角线移动，并将此字符添加到LCS中。
• 如果不相等，向值较高的方向移动（向上或向左）。如果两者相等，可以选择任一方向。

4.?重构LCS：在回溯过程中收集的字符（逆序排列）形成了LCS。

题目要求：

给定输入：给定两个最大长度为1kbp的DNA字符串s和t（以FASTA格式表示）。

输出：s和t的一个最长公共子序列。如果存在多个解决方案，你可以返回任何一个。

代码：

from method import fasta

namelist,valuelist = fasta("")

s = valuelist[0]
t = valuelist[1]

def lcs(s, t):
    # 创建一个动态规划矩阵
    dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
    # 填充矩阵
    for i in range(1, len(s) + 1):
        for j in range(1, len(t) + 1):
            if s[i - 1] == t[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    # 回溯找出LCS
    i, j = len(s), len(t)
    lcs = []
    while i > 0 and j > 0:
        if s[i - 1] == t[j - 1]:
            lcs.append(s[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1
        else:
            j -= 1
    # LCS是逆序构建的
    return ''.join(reversed(lcs))
print(lcs(s, t))