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

題目：

不完整字符（Incomplete Characters）

?

Given: A partial character table C.

所給：一個有信息缺失的字符表C。

Return: The collection of all quartets that can be inferred from the splits corresponding to the underlying characters of C.

需得：從C中可以推斷出的所有“四重”劃分方式。

?

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

cat dog elephant ostrich mouse rabbit robot

01xxx00

x11xx00

111x00x

測試輸出

{elephant, dog} {rabbit, robot}

{cat, dog} {mouse, rabbit}

{mouse, rabbit} {cat, elephant}

{dog, elephant} {mouse, rabbit}

?

生物學(xué)背景

? ? ? ?測序技術(shù)的發(fā)展產(chǎn)生了大量數(shù)據(jù)，這些數(shù)據(jù)來自各種各樣的生物種群。設(shè)想一下，如果我們擁有全部生物的全部基因組信息，就可以構(gòu)建一個完整的系統(tǒng)發(fā)育樹。

? ? ? ?舉例來說，假設(shè)我們已知在很多物種中都存在的基因，根據(jù)某個物種是否有這個基因，我們可以創(chuàng)造一個特征，從而依據(jù)做出的字符表構(gòu)建出進(jìn)化樹。然而，現(xiàn)實(shí)情況是，很多物種的基因組都是未知的，我們有太多缺失的信息。

? ? ? ?因此，我們必須學(xué)會在現(xiàn)實(shí)世界進(jìn)行研究，即使只有部分分類單元的信息已知，也可以推斷出很多信息。我們可以將分類單元分為三類：擁有某性狀的，不擁有某性狀的，以及我們還不知道的。

?

?

數(shù)學(xué)背景

? ? ? ?集合S有n個分類單元組成，S的部分分割可以用A|B來表示，其中A和B是S的子集，且A和B之間沒有交集。與之前集合的分割所不同的是，A∪B可以不等于S，所以（A∪B）的補(bǔ)集對應(yīng)的就是S中未知特征的那些分類單元。

? ? ? ?在55 創(chuàng)建字符表中，我們了解到字符表是一個矩陣C，其中每一行的數(shù)組表示分類特征的狀態(tài)。也就是說， Ci,j表示第i個特征相對于第j個分類單元的狀態(tài)。在本題中，我們可以建立一個廣義的部分字符表，如果未知某分類單元是否存在一個特征，就用x來表示。

? ? ? ?為了簡化問題，本題中我們只考慮“四重（quartet）”的情況。“四重” 是一種部分分割A(yù)|B，且A和B中恰好各包含兩個元素。如果A?C且B?D（或者等價地A?D且B?C），我們就可以說一個 “四重”A|B是從一個部分分割的C|D推斷出來的。比如：{1,3}|{2,4}和{3,5}|{2,4}可以從{1,3,5}|{2,4}推斷出來。

?

思路

? ? ? ?為了達(dá)到“四重（quartet）”的要求，本題一直在進(jìn)行兩兩組合。具體方法并不難，可以參考下面代碼及其中的注釋。我相信應(yīng)該會有更簡練的寫法。

? ? ? ?我認(rèn)為本題的難度主要在兩方面。首先是讀懂題意，題目看著非常晦澀難懂，其實(shí)只是要根據(jù)每一行“0”和“1”的位置，將所給的物種分成兩組，再兩兩組合即可。第二個難點(diǎn)是刪除重復(fù)的結(jié)果，因?yàn)闇y試數(shù)據(jù)給的很簡單，很可能出現(xiàn)測試得到了正確的輸出，正式的數(shù)據(jù)卻過不了的情況，而因?yàn)槿狈Υ笠稽c(diǎn)的測試數(shù)據(jù)，難以快速想到重復(fù)數(shù)據(jù)上去，我就在這里卡了很久，無法突破，而一旦“窗戶紙”被捅破，也就沒有神秘的地方了。

?

代碼