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

題目：

模式匹配初探（Introduction to Pattern Matching）

Given: A list of at most 100 DNA strings of length at most 100 bp, none of which is a prefix of another.

所給：一個列表，其中包含最多100條DNA序列，每條不超過100bp，相互不為前綴。

Return: The adjacency list corresponding to the trie T for these patterns, in the following format. If T has n nodes, first label the root with 1 and then label the remaining nodes with the integers 2 through n in any order you like. Each edge of the adjacency list of T will be encoded by a triple containing the integer representing the edge's parent node, followed by the integer representing the edge's child node, and finally the symbol labeling the edge..

需得：與這些DNA序列組成的Trie樹T對應(yīng)的鄰接表。格式如下：如果T有n個結(jié)點，首先將根結(jié)點標(biāo)記為1，然后把其他結(jié)點用從2到n的整數(shù)標(biāo)記，順序任意；T的鄰接表中每行代表一個邊，有三個內(nèi)容，第一個是正整數(shù)，是該邊父結(jié)點的標(biāo)記，第二個正整數(shù)是該邊子結(jié)點的標(biāo)記，最后是代表這條邊的符號。

?

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

ATAGA

ATC

GAT

測試輸出

1 2 A

2 3 T

3 4 A

4 5 G

5 6 A

3 7 C

1 8 G

8 9 A

9 10 T

?

生物學(xué)背景

? ? ? ?在09 確定DNA子序列出現(xiàn)的位置中，我們學(xué)習(xí)了模序（motif）的概念及如何定位模序。在實際操作中，我們通常需要從一個很長的序列中搜索一組模序。比如，從一個完整基因組中搜索幾個基因。為了更好地解決這個問題，需要引入模式匹配的概念，即從一個字符串中搜索一組子串。為了簡單起見，開始時我們只要求精確匹配。

? ? ? ?09 確定DNA子序列出現(xiàn)的位置中采用“滑動窗口”算法來掃描待找的子串，這個方法需要反復(fù)掃描序列，耗時長。我們希望有方法單次遍歷序列就解決問題，Tire樹（字典樹）這種數(shù)據(jù)結(jié)構(gòu)可以幫助我們實現(xiàn)目標(biāo)。

?

Python背景

? ? ? ?Trie樹是一種前綴樹，常用來儲存字符串，我們以具體例子來介紹一下Trie樹。

? ? ? ?上圖示包含'apple'， 'apropos'， 'banana'， 'bandana'和'orange'的Trie樹，從根節(jié)點到葉子結(jié)點形成的每個路徑就是一個單詞。由圖可知，Trie樹是有根樹，從根結(jié)點開始，每個單詞第一個獨有的字符形成一個邊（edge），連接根和一個新的頂點（vertex）。隨后再看第二個字符，每個單詞獨有的字符又形成新的邊，連接父結(jié)點和一個新的頂點……這個過程不停迭代，就形成了整棵樹。沿著Trie中從根到葉的任何路徑，每條邊的符號將拼出集合中每個唯一的字符串（注意：只有集合中沒有字符串是另一個字符串的前綴時這句話才成立）。

? ? ? ?我們可以通過定義一個類來實現(xiàn)Trie樹，Python中類用class關(guān)鍵字來標(biāo)記，可以定義每個實例共有的屬性和方法。

?

思路

? ? ? ?本題中Trie樹的實現(xiàn)參考了網(wǎng)絡(luò)上的相關(guān)博文，具體可閱讀下面這篇博文：https://blog.csdn.net/annilingmo/article/details/80879910。

? ? ? ?本題核心代碼可分為兩部分：Trie樹類的定義和遍歷。

? ? ? ?首先來看Trie樹的定義。因為題目中已經(jīng)明確說了所給的每條序列都相互不為前綴，所以這里其實使問題更簡化了，我們只需在__init__中初始化類時定義根節(jié)點即可。我在這里給根結(jié)點中添加了一個元素‘vertex’，記錄根結(jié)點的編號，以便后續(xù)操作。在insert函數(shù)中，每次向Trie樹中插入一條序列，這里用全局變量num記錄結(jié)點數(shù)。

? ? ? ?Trie樹構(gòu)建完成后，問題就變成了如何把其中的內(nèi)容讀出來。我這里寫了tradic函數(shù)實現(xiàn)這個功能。觀察Trie樹的結(jié)構(gòu)不難發(fā)現(xiàn)，這是一個多層嵌套的字典，每個結(jié)點的編號都是鍵名為‘vertex’的字典元素的值；而每個邊代表的符號都是一個鍵，值是這個邊下面的路徑內(nèi)容形成的字典。利用這種規(guī)律，就可以輕松寫出問題所需的鄰接表。

? ? ? ?詳細解釋已寫入代碼注釋，在此不再贅述。

P.S. 本題“solution”區(qū)下面有很多更好的寫法。

?

代碼