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

題目：

創(chuàng)建字符表（Creating a Character Table）

Given: An unrooted binary tree T in Newick format for at most 200 species taxa.

所給：一個Newick格式的無根二叉樹T，最多可容納200個物種。

Return: A character table having the same splits as the edge splits of T. The columns of the character table should encode the taxa ordered lexicographically; the rows of the character table may be given in any order. Also, for any given character, the particular subset of taxa to which 1s are assigned is arbitrary.

需得：一個與T中結(jié)點對應(yīng)的字符表，列應(yīng)該以物種的字母順序排列，行則可以按任意順序給出。哪一類用1表示也可以任意指定。

?

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

(dog,((elephant,mouse),robot),cat);

測試輸出

00110

00111

?

生物學(xué)背景

? ? ? ?在分子生物學(xué)發(fā)展起來之前，構(gòu)建進化樹通常依賴對形狀特征進行比較。典型的例子是對恐龍盆骨化石的研究，化石是進化研究的重要一環(huán)，因為化石是已滅絕生物留下的唯一痕跡，幫助我們推測生物是如何一步一步進化至今。1887年，有科學(xué)家提出：通過骨盆形狀，可以將恐龍分為兩大類，分別為蜥龍目（Saurischia）和鳥龍目（Ornithischia），前者髖骨形狀類似爬行動物，后者則更接近鳥類。骨盆形狀作為單一的變量將所有恐龍劃分為兩類，且這種分類方法一直沿用至今。這其中包含的前提假設(shè)是：所有擁有某一個特征的分類單元都是從出現(xiàn)該特征的一個祖先進化而來，相反，任何不擁有該特征的分類單元都不從該祖先進化而來。

? ? ? ?本題中的字符表是一個矩陣C，其中每一行的數(shù)組表示分類特征的狀態(tài)。也就是說， Ci,j表示第i個特征相對于第j個分類單元的狀態(tài)。

思路

? ? ? ?本題由@AMWDF同學(xué)提供代碼，我用的思路和代碼都來自他，在此先表示感謝！

? ? ? ?本題的題干部分給了如下一些提示：給定一個包含n個分類單元的集合，該集合的任意一個子集S都可以看作是整個集合由于一個特征的差異被分裂（split）所得到，相應(yīng)的另一部分為Sc，我們可以用S|Sc來表示這種分裂結(jié)果；換句話說，這個特征可以用數(shù)組A來表示，A的長度為n，如果A[j]=1，則第j個分類單元屬于S，若A[j]=0，則第j個分類單元屬于Sc。同時，我們知道從一棵無根二叉樹上刪除一條邊會產(chǎn)生兩棵獨立的樹，每棵樹都是原始樹的子集，所以這種樹的分裂也可以用S∣Sc表示。如果一個特征太過于微小，它可能只使一個分類單元自己進入一類，即S或Sc中只有一個分類單元，相當(dāng)于樹的一個葉子結(jié)點，這種分裂在分類研究中無法給我們提供類群彼此間的關(guān)系。

? ? ? ?這道題我自己做了很久，用所給的示例數(shù)據(jù)可以得到結(jié)果，但下載了較大的數(shù)據(jù)后卻始終得不到正確答案。萬般無奈下，我在21年4月底發(fā)專欄求助，上周終于有好心人@AMWDF在答案通過后把代碼分享給了我。我已經(jīng)不想再拿起以前一團亂麻一樣的代碼了，所以這里不僅完全按照@AMWDF的思路，代碼也完全照搬（只改了一句，詳見注釋）。再次感謝@AMWDF大佬！

? ? ? ?首先，我們在48 Newick格式與進化樹已經(jīng)接觸過了這種表示進化樹的形式。一方面，我們可以用現(xiàn)成的包對Newick格式進行解析；另一方面，我們也可以不構(gòu)建進化樹直接得到結(jié)果，但需要理解符號的含義。

? ? ? ?首先我們要先讀懂題目，先看所給數(shù)據(jù)：(dog,((elephant,mouse),robot),cat)，可以畫成下面的樹：

? ? ? ?不難看出，我們有兩種分裂樹的方法（黃圈中的為一類，圈外為另一類）：

? ? ? ?為什么其他方法不行呢？從圖上很容易看出，其他分裂方法會產(chǎn)生一棵只有一個結(jié)點的樹，對分類研究沒什么意義。

? ? ? ?把這5個結(jié)點按照字母順序排列，得：'cat', 'dog', 'elephant', 'mouse', 'robot'。

? ? ? ?按圖中可以看出，字符表可以表示為：

'cat', 'dog', 'elephant', 'mouse', 'robot'

?0? ? ? ? 0? ? ? ? ? 1? ? ? ? ? ? ? ?1? ? ? ? ? 1

?0? ? ? ? 0? ? ? ? ? 1? ? ? ? ? ? ? ?1? ? ? ? ??0

? ? ? ?可以看到，我們得到了正確答案（順序不重要），至此題目已讀懂。

? ? ? ?接下來我們分析一下@AMWDF的代碼。

? ? ? ?代碼將所給的newick格式的樹讀入后，先做了兩件事：首先，把‘(’、‘)’、‘,’和種屬名分開儲存在列表newdata中；然后，把種屬名按字母順序排序后存入另一個列表character。做完準備工作后，就開始用循環(huán)構(gòu)建字符表。

? ? ? ?讀取newdata中的內(nèi)容，共有如下幾個情況：

1）‘(’。這之后將開啟一個新的分支，將出現(xiàn)一個新的類。用leftnum儲存此時所有類的數(shù)量，遇到左括號時該值加1。

2）‘,’。一個分支內(nèi)的結(jié)點，可以不作處理。

3）種屬名。是每個結(jié)點的內(nèi)容，用一個字典left來接收整理。對于@AMWDF的代碼我是這么理解的：

假設(shè)這棵樹就代表我們的進化樹，以藍圈框出的枝條為例，我們希望從最末端的分枝開始，逐步把每一層的分枝都取出來，這樣就可以讓取出來的和未取出來的分枝分屬不同的類，也就達到了目的。所以，我們不能一砍了之，不僅要能把末端的枝條砍下來，還要確保在砍下來的地方保留一個“殘影”，這樣，上一層的枝干結(jié)構(gòu)依然完整。這一段代碼里的循環(huán)做的工作就是保留“殘影”。

4）‘)’。樹的一個分支結(jié)束了。從上一個左括號到這個括號中的內(nèi)容就是一類，把這一支取出來，存在另外一個變量中，然后就可以砍掉這個分枝了。因為這一支的 “殘影”已經(jīng)被保留了，所以在上一層的分枝中依然能看到這一支。再按照character中排序后的名稱就可以構(gòu)建出字符表的一行。

代碼