【ROSALIND】【练Python，学生信】60 同一基因中的共存模序

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

题目：

在基因中搜寻不相交的模序（Finding Disjoint Motifs in a Gene）

Given: A text DNA string s of length at most 10 kbp, followed by a collection of n (n≤10) DNA strings of length at most 10 bp acting as patterns.

所给：一条DNA序列s，长度不超过10kb。一组长度不超过10bp的DNA短序列，数目n不超过10。

Return: An n×n matrix M for which Mj,k=1 if the jth and kth pattern strings can be interwoven into s and Mj,k=0 otherwise.

需得：一个n×n的矩阵M，如果第j个和第k个短序列可以“融合”成s，则Mj,k=1，否则Mj,k=0。

测试数据

GACCACGGTT

ACAG

GT

CCG

测试输出

0 0 1

0 1 0

1 0 0

生物学背景

        在之前的题目中，我们已经了解了模序（motif）的概念。模序并不一定单独存在，在同一个位置可能存在多个模序。在本题中，我们的目的是定位两个“不相交（disjoint）”的模序。

        何为 “不相交”？举例来说，两个序列"ACAG" 和"CCG"可以融合（interweave）成序列"GACCACGGTT"。但不能融合为” GACCACAAAAGGTT"因为其中插入了4个“A”。同理，尽管"ACACG"是ACAG 和CCG的最短公共超序列（详见49 求解最短公共超序列），但却不是由它们融合而来的，因为字符出现了重合，不满足“不相交”。

思路

        我解决本题的思路是：把两个序列所有能融合成的序列枚举出来，然后在长DNA序列中查找，能找到就说明可以融合。

        因此，本题的关键代码是createstraing函数，在这个函数中，我用递归的方法，生成两个序列的所有融合序列，为了保存这个序列集合，我在函数外定义了一个列表res，相当于一个全局变量，这样createstraing函数运行完后，我可以在函数外使用res中储存的序列。

        随后，我就可以把res中的序列依次拿出来，用python定义的find函数在长DNA序列中进行查找。用循环实现短序列的两两融合比较，就可以完成题目要求。

代码