决定折叠这棵树的截止点的算法？

Question

我有一个Newick树，它是通过比较假定的DNA调控基序（PWMs或PSSMs）的位置权重矩阵（PWMs或PSSMs）的相似性（欧几里德距离）来构建的，这些模体是4-9bp长的DNA序列。在

iTol（here）上有一个交互式的树，您可以自由地使用它-只需在设置参数后按“更新树”：

我的具体目标：如果到最近父类的平均距离是<；X（ETE2 Python package），则将这些motif（tips/terminal nodes/leaves）折叠在一起。这在生物学上很有趣，因为一些基因调控的DNA基序可能彼此同源（副同源或同源）。这种折叠可以通过上面链接的iTol GUI来完成，例如，如果选择X=0.001，那么一些motif就会折叠成三角形（motif族）。在

我的问题：有人能提出一种算法来输出或帮助可视化哪个X值适合“最大化折叠模体的生物学或统计相关性”？理想的情况下，当与X作图时，树的某些属性会有一些明显的阶跃变化，这对算法来说是一个合理的X。有没有已知的算法/脚本/包？也许代码会根据X的值绘制一些统计数据？我尝试过绘制X与平均簇大小（matplotlib）的对比，但我没有看到明显的“步长增加”来通知我要使用哪个X值：

我的代码和数据：到Python脚本的链接是[here][8]，我对它进行了大量注释，它将为您生成上面的树数据和绘图（使用参数d_from、d_to和d_step来探索距离截止值X）。如果您有easy install和Python，则需要通过简单地执行以下两个bash命令来安装ete2：

apt-get install python-setuptools python-numpy python-qt4 python-scipy python-mysqldb python-lxml

easy_install -U ete2

Answer 1

您可以尝试使用类似于@Jeff提到的tree reconction的方法。但标准的树和解实际上会失败。在

协调首先需要在目标树中添加表示进化特征“损失”的分支。然后指出进化特征发生“重复”的节点。损失和重复的加权和提供了一个可优化的成本函数。在

但是在你的例子中，你想要解决的问题是“把这棵超级树分解成大小合适的，正交的子树”。这意味着你不会真的想要像复制一样多地获得损失。你想要一种给树评分的方法，这样它就可以显示出有多少正交子树被合并到你的超级树中。因此，您可以尝试这种评分方法：

1. 取一棵超级树，计算重复物种的数量，S1。在
2. 折叠所有的末梢叶，并计算新的重复物种的数量，S2。在
3. S1和S2之间的差异揭示了超级树中大约有多少个子树。在
4. 纠正由不同大小的超级树除以超级树N中所代表的独特物种的数量所引起的任何偏差

如果我们把这个分数称为“子树因子”，那么它等于：

S1-S2/N

推论：

• 如果S1-S2=S1，那么这意味着你的超级树中大约有一个真正的子树，所有的多个物种的出现都是由于最近的副词。

• 如果S1-S2=0，那么这意味着你的超级树中有大约S1的真子树。

Answer 2

我想我需要了解更多，然后才能给出具体的建议。但也许这会有帮助。我假设每个终端节点是一个序列，每个内部节点是一个PSSM。在

X的计算是特定于应用程序的。例如，如果你想折叠超平行对数，你得到的X和你想要折叠所有同系物时得到的X是不一样的。在

因为基因是通过复制和物种形成不断产生的，所以没有一个X值可以通过进化关系来区分序列。因此，我不认为你会找到一个满意的代理来确定序列之间的进化关系，只看集群统计。在

一种更严格的方法是从每个调控基序的基因中构建一个基因树，并将其与物种树相协调。那里有软件和附加的启发式算法来识别正射测井仪。在

如果你这样做，你的树的内部节点将被推断出的进化事件（例如，复制，物种形成）修饰。然后，您可以在树上查找不关心的类的折叠节点。在