如果第一次閱讀本系列文檔請先移步閱讀【ROSALIND】【練Python，學(xué)生信】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短序列，數(shù)目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。

?

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

GACCACGGTT

ACAG

GT

CCG

測試輸出

0 0 1

0 1 0

1 0 0

?

生物學(xué)背景

? ? ? ? 在之前的題目中，我們已經(jīng)了解了模序（motif）的概念。模序并不一定單獨存在，在同一個位置可能存在多個模序。在本題中，我們的目的是定位兩個“不相交（disjoint）”的模序。

? ? ? ??何為 “不相交”？舉例來說，兩個序列"ACAG" 和"CCG"可以融合（interweave）成序列"GACCACGGTT"。但不能融合為” GACCACAAAAGGTT"因為其中插入了4個“A”。同理，盡管"ACACG"是ACAG 和CCG的最短公共超序列（詳見49 求解最短公共超序列），但卻不是由它們?nèi)诤隙鴣淼?，因為字符出現(xiàn)了重合，不滿足“不相交”。

?

思路

? ? ? ??我解決本題的思路是：把兩個序列所有能融合成的序列枚舉出來，然后在長DNA序列中查找，能找到就說明可以融合。

? ? ? ??因此，本題的關(guān)鍵代碼是createstraing函數(shù)，在這個函數(shù)中，我用遞歸的方法，生成兩個序列的所有融合序列，為了保存這個序列集合，我在函數(shù)外定義了一個列表res，相當于一個全局變量，這樣createstraing函數(shù)運行完后，我可以在函數(shù)外使用res中儲存的序列。

? ? ? ??隨后，我就可以把res中的序列依次拿出來，用python定義的find函數(shù)在長DNA序列中進行查找。用循環(huán)實現(xiàn)短序列的兩兩融合比較，就可以完成題目要求。

代碼