【ROSALIND】【练Python，学生信】38 求解最长公共子序列

如果第一次阅读本系列文档请先移步阅读【ROSALIND】【练Python，学生信】00 写在前面  谢谢配合~

题目：

寻找共有的经剪接模序（Finding a Shared Spliced Motif）

Given: Two DNA strings s and t (each having length at most 1 kbp) in FASTA format.

所给：两条长度不超过1kb的DNA序列s和t，以FASTA给出。

Return: A longest common subsequence of s and t. (If more than one solution exists, you may return any one.).

需得：s和t的最长公共子序列（如果不止一个，给出任一个即可）。

测试数据

>Rosalind_23

AACCTTGG

>Rosalind_64

ACACTGTGA

测试输出

AACTGG

背景

        在30 鉴定不连续的DNA模序中我们核酸剪接以及不连续模序的概念，为了找到两条序列间不连续的相同子序列，我们需要求解最长公共子序列。

思路

        这里的方法其实和24 求解最长递增子序列完全一样，代码也基本是从那道题复制过来的。求最长递增子序列的问题实质就是求所给序列和原先的连续递增序列的最长公共子序列。本题思路和代码不再作解释，详细请参考24 求解最长递增子序列。

代码

def LCSQ(s1, s2):
    """用动态规划求解最长公共子序列的函数"""
    m, n = len(s1), len(s2)
    dp = [[["", 0] for j in list(range(n + 1))] for i in list(range(m + 1))]
    for i in list(range(1, m + 1)):
        dp[i][0][0] = s1[i - 1]
    for j in list(range(1, n + 1)):
        dp[0][j][0] = s2[j - 1]

        for i in list(range(1, m + 1)):
            for j in list(range(1, n + 1)):
                if s1[i - 1] == s2[j - 1]:
                    dp[i][j] = ['↖', dp[i - 1][j - 1][1] + 1]
                elif dp[i][j - 1][1] > dp[i - 1][j][1]:
                    dp[i][j] = ['←', dp[i][j - 1][1]]
                else:
                    dp[i][j] = ['↑', dp[i - 1][j][1]]

        s3 = []
        i = m
        j = n
        while i > 0 and j > 0:
            if dp[i][j][0] == '↖':
                s3.append(dp[i][0][0])
                i -= 1
                j -= 1
            elif dp[i][j][0] == '←':
                j -= 1
            elif dp[i][j][0] == '↑':
                i -= 1
        s3 = s3[::-1]
        return s3


f = open('input.txt', 'r')
lines = f.readlines()
f.close()

[index, seq] = readfasta(lines)
seq1 = seq[0]
seq2 = seq[1]
res = []
res = LCSQ(seq1, seq2)
res = ''.join(res)
# print(res)
f = open('output.txt', 'w')
f.write(res)
f.close()