【ROSALIND】【练Python，学生信】71 根据有信息缺失的字符表做推断

如果第一次阅读本系列文档请先移步阅读【ROSALIND】【练Python，学生信】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中可以推断出的所有“四重”划分方式。

测试数据

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}

生物学背景

       测序技术的发展产生了大量数据，这些数据来自各种各样的生物种群。设想一下，如果我们拥有全部生物的全部基因组信息，就可以构建一个完整的系统发育树。

       举例来说，假设我们已知在很多物种中都存在的基因，根据某个物种是否有这个基因，我们可以创造一个特征，从而依据做出的字符表构建出进化树。然而，现实情况是，很多物种的基因组都是未知的，我们有太多缺失的信息。

       因此，我们必须学会在现实世界进行研究，即使只有部分分类单元的信息已知，也可以推断出很多信息。我们可以将分类单元分为三类：拥有某性状的，不拥有某性状的，以及我们还不知道的。

数学背景

       集合S有n个分类单元组成，S的部分分割可以用A|B来表示，其中A和B是S的子集，且A和B之间没有交集。与之前集合的分割所不同的是，A∪B可以不等于S，所以（A∪B）的补集对应的就是S中未知特征的那些分类单元。

       在55 创建字符表中，我们了解到字符表是一个矩阵C，其中每一行的数组表示分类特征的状态。也就是说， Ci,j表示第i个特征相对于第j个分类单元的状态。在本题中，我们可以建立一个广义的部分字符表，如果未知某分类单元是否存在一个特征，就用x来表示。

       为了简化问题，本题中我们只考虑“四重（quartet）”的情况。“四重” 是一种部分分割A|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}推断出来。

思路

       为了达到“四重（quartet）”的要求，本题一直在进行两两组合。具体方法并不难，可以参考下面代码及其中的注释。我相信应该会有更简练的写法。

       我认为本题的难度主要在两方面。首先是读懂题意，题目看着非常晦涩难懂，其实只是要根据每一行“0”和“1”的位置，将所给的物种分成两组，再两两组合即可。第二个难点是删除重复的结果，因为测试数据给的很简单，很可能出现测试得到了正确的输出，正式的数据却过不了的情况，而因为缺乏大一点的测试数据，难以快速想到重复数据上去，我就在这里卡了很久，无法突破，而一旦“窗户纸”被捅破，也就没有神秘的地方了。

代码