【ROSALIND】【練Python，學(xué)生信】38 求解最長(zhǎng)公共子序列
如果第一次閱讀本系列文檔請(qǐng)先移步閱讀【ROSALIND】【練Python，學(xué)生信】00 寫(xiě)在前面 ?謝謝配合~
題目：
尋找共有的經(jīng)剪接模序（Finding a Shared Spliced Motif）
Given: Two DNA strings s and t (each having length at most 1 kbp) in FASTA format.
所給：兩條長(zhǎng)度不超過(guò)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的最長(zhǎng)公共子序列（如果不止一個(gè)，給出任一個(gè)即可）。
?
測(cè)試數(shù)據(jù)
>Rosalind_23
AACCTTGG
>Rosalind_64
ACACTGTGA
測(cè)試輸出
AACTGG
?
背景
????????在30 鑒定不連續(xù)的DNA模序中我們核酸剪接以及不連續(xù)模序的概念，為了找到兩條序列間不連續(xù)的相同子序列，我們需要求解最長(zhǎng)公共子序列。
?
思路
????????這里的方法其實(shí)和24 求解最長(zhǎng)遞增子序列完全一樣，代碼也基本是從那道題復(fù)制過(guò)來(lái)的。求最長(zhǎng)遞增子序列的問(wèn)題實(shí)質(zhì)就是求所給序列和原先的連續(xù)遞增序列的最長(zhǎng)公共子序列。本題思路和代碼不再作解釋，詳細(xì)請(qǐng)參考24 求解最長(zhǎng)遞增子序列。
?
代碼
def LCSQ(s1, s2):
??? """用動(dòng)態(tài)規(guī)劃求解最長(zhǎng)公共子序列的函數(shù)"""
??? 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()
?
