【ROSALIND】【练Python，学生信】30 鉴定不连续的DNA模序

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

题目：

鉴定不连续的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上出现的位置，如果存在多个解，只需要给出任意一个。

测试数据

>Rosalind_14

ACGTACGTGACG

>Rosalind_18

GTA

测试输出

3 8 10

生物学背景

        人类的基因组中存在外显子和内含子，内含子在mRNA加工成熟的过程中被剪切掉。因此一些模序在原始的DNA链上可能是不连续的，在成熟的mRNA上才连接在一起。这给我们从基因组上分析模序带来了困难。

数学背景

        子序列（subsequence）是包含在另一条序列中的序列，但与子串（substring）不同，子序列中的字符在包含它的序列中可以是不连续的，只需要顺序保持不变即可。例如ACG 是TATGCTAAGATC的子序列，出现的位置是2, 5, 9，显然位置可以不唯一。

思路

        我用两层循环解决这个问题，第一层将子序列中的字符一个个取出来，第二层与另一字符串中的字符挨个比较。一旦找到相同的，就存储当前位置，并跳出第二层循环，将子序列中下一个字符拿出来再按上述过程进行比较。

代码

def readfasta(lines):
    """读入fasta格式文件的函数"""
    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) + ' ' # 把当前位置存储在n中
            j += 1
            break # 不再比较子串这个字符是否与后续字符相同
        j += 1
    i += 1

print(n)