【ROSALIND】【练Python，学生信】55 创建字符表

如果第一次阅读本系列文档请先移步阅读【ROSALIND】【练Python，学生信】00 写在前面  谢谢配合~

题目：

创建字符表（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中结点对应的字符表，列应该以物种的字母顺序排列，行则可以按任意顺序给出。哪一类用1表示也可以任意指定。

测试数据

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

测试输出

00110

00111

生物学背景

       在分子生物学发展起来之前，构建进化树通常依赖对形状特征进行比较。典型的例子是对恐龙盆骨化石的研究，化石是进化研究的重要一环，因为化石是已灭绝生物留下的唯一痕迹，帮助我们推测生物是如何一步一步进化至今。1887年，有科学家提出：通过骨盆形状，可以将恐龙分为两大类，分别为蜥龙目（Saurischia）和鸟龙目（Ornithischia），前者髋骨形状类似爬行动物，后者则更接近鸟类。骨盆形状作为单一的变量将所有恐龙划分为两类，且这种分类方法一直沿用至今。这其中包含的前提假设是：所有拥有某一个特征的分类单元都是从出现该特征的一个祖先进化而来，相反，任何不拥有该特征的分类单元都不从该祖先进化而来。

       本题中的字符表是一个矩阵C，其中每一行的数组表示分类特征的状态。也就是说， Ci,j表示第i个特征相对于第j个分类单元的状态。

思路

       本题由@AMWDF同学提供代码，我用的思路和代码都来自他，在此先表示感谢！

       本题的题干部分给了如下一些提示：给定一个包含n个分类单元的集合，该集合的任意一个子集S都可以看作是整个集合由于一个特征的差异被分裂（split）所得到，相应的另一部分为Sc，我们可以用S|Sc来表示这种分裂结果；换句话说，这个特征可以用数组A来表示，A的长度为n，如果A[j]=1，则第j个分类单元属于S，若A[j]=0，则第j个分类单元属于Sc。同时，我们知道从一棵无根二叉树上删除一条边会产生两棵独立的树，每棵树都是原始树的子集，所以这种树的分裂也可以用S∣Sc表示。如果一个特征太过于微小，它可能只使一个分类单元自己进入一类，即S或Sc中只有一个分类单元，相当于树的一个叶子结点，这种分裂在分类研究中无法给我们提供类群彼此间的关系。

       这道题我自己做了很久，用所给的示例数据可以得到结果，但下载了较大的数据后却始终得不到正确答案。万般无奈下，我在21年4月底发专栏求助，上周终于有好心人@AMWDF在答案通过后把代码分享给了我。我已经不想再拿起以前一团乱麻一样的代码了，所以这里不仅完全按照@AMWDF的思路，代码也完全照搬（只改了一句，详见注释）。再次感谢@AMWDF大佬！

       首先，我们在48 Newick格式与进化树已经接触过了这种表示进化树的形式。一方面，我们可以用现成的包对Newick格式进行解析；另一方面，我们也可以不构建进化树直接得到结果，但需要理解符号的含义。

       首先我们要先读懂题目，先看所给数据：(dog,((elephant,mouse),robot),cat)，可以画成下面的树：

       不难看出，我们有两种分裂树的方法（黄圈中的为一类，圈外为另一类）：

       为什么其他方法不行呢？从图上很容易看出，其他分裂方法会产生一棵只有一个结点的树，对分类研究没什么意义。

       把这5个结点按照字母顺序排列，得：'cat', 'dog', 'elephant', 'mouse', 'robot'。

       按图中可以看出，字符表可以表示为：

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

 0        0          1               1          1

 0        0          1               1          0

       可以看到，我们得到了正确答案（顺序不重要），至此题目已读懂。

       接下来我们分析一下@AMWDF的代码。

       代码将所给的newick格式的树读入后，先做了两件事：首先，把‘(’、‘)’、‘,’和种属名分开储存在列表newdata中；然后，把种属名按字母顺序排序后存入另一个列表character。做完准备工作后，就开始用循环构建字符表。

       读取newdata中的内容，共有如下几个情况：

1）‘(’。这之后将开启一个新的分支，将出现一个新的类。用leftnum储存此时所有类的数量，遇到左括号时该值加1。

2）‘,’。一个分支内的结点，可以不作处理。

3）种属名。是每个结点的内容，用一个字典left来接收整理。对于@AMWDF的代码我是这么理解的：

假设这棵树就代表我们的进化树，以蓝圈框出的枝条为例，我们希望从最末端的分枝开始，逐步把每一层的分枝都取出来，这样就可以让取出来的和未取出来的分枝分属不同的类，也就达到了目的。所以，我们不能一砍了之，不仅要能把末端的枝条砍下来，还要确保在砍下来的地方保留一个“残影”，这样，上一层的枝干结构依然完整。这一段代码里的循环做的工作就是保留“残影”。

4）‘)’。树的一个分支结束了。从上一个左括号到这个括号中的内容就是一类，把这一支取出来，存在另外一个变量中，然后就可以砍掉这个分枝了。因为这一支的 “残影”已经被保留了，所以在上一层的分枝中依然能看到这一支。再按照character中排序后的名称就可以构建出字符表的一行。

代码