如果第一次閱讀本系列文檔請先移步閱讀【ROSALIND】【練Python，學(xué)生信】00 寫在前面 ?謝謝配合~

題目：

鑒定不連續(xù)的DNA模序（Finding a Spliced Motif）

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

所給：兩條不超過1kb長的DNA序列s和t，以FASTA格式給出。

Return: One collection of indices of s in which the symbols of t appear as a subsequence of s. If multiple solutions exist, you may return any one.

需得：t作為s的子序列，其中的元素在s上出現(xiàn)的位置，如果存在多個解，只需要給出任意一個。

?

測試數(shù)據(jù)

>Rosalind_14

ACGTACGTGACG

>Rosalind_18

GTA

測試輸出

3 8 10

?

生物學(xué)背景

????????人類的基因組中存在外顯子和內(nèi)含子，內(nèi)含子在mRNA加工成熟的過程中被剪切掉。因此一些模序在原始的DNA鏈上可能是不連續(xù)的，在成熟的mRNA上才連接在一起。這給我們從基因組上分析模序帶來了困難。

?

數(shù)學(xué)背景

????????子序列（subsequence）是包含在另一條序列中的序列，但與子串（substring）不同，子序列中的字符在包含它的序列中可以是不連續(xù)的，只需要順序保持不變即可。例如ACG 是TATGCTAAGATC的子序列，出現(xiàn)的位置是2, 5, 9，顯然位置可以不唯一。

?

思路

????????我用兩層循環(huán)解決這個問題，第一層將子序列中的字符一個個取出來，第二層與另一字符串中的字符挨個比較。一旦找到相同的，就存儲當(dāng)前位置，并跳出第二層循環(huán)，將子序列中下一個字符拿出來再按上述過程進(jìn)行比較。

?

代碼

def readfasta(lines):
??? """讀入fasta格式文件的函數(shù)"""
??? seq = []
??? index = []
??? seqplast = ""
??? numlines = 0
??? for i in lines:
??????? if '>' in i:
??????????? index.append(i.replace("\n", "").replace(">", ""))
??????????? seq.append(seqplast.replace("\n", ""))
??????????? seqplast = ""
??????????? numlines += 1
??????? else:
??????????? seqplast = seqplast + i.replace("\n", "")
??????????? numlines += 1
??????? if numlines == len(lines):
??????????? seq.append(seqplast.replace("\n", ""))
??? seq = seq[1:]
??? return index, seq

?

?

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

[index, seq] = readfasta(lines)
subseq = seq[1] # subseq存儲子序列
seq = seq[0]
i = 0
j = 0
n = '' # 用字符串的形式存儲位置
while i < len(subseq):
??? while j < len(seq):
??????? if subseq[i] == seq[j]: # 如果子序列中的這個字符在序列中
??????????? n = n + str(j + 1) + ' ' # 把當(dāng)前位置存儲在n中
??????????? j += 1
??????????? break # 不再比較子串這個字符是否與后續(xù)字符相同
??????? j += 1
??? i += 1

print(n)