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

Question

我有一个Newick树是通过比较4-9bp长DNA序列的推定DNA调节基序的位置权重矩阵(PWM或PSSM)的相似性(欧几里德距离)而构建的.

这个树的交互式版本在iTol(这里)上,您可以自由使用 - 只需在设置参数后按"更新树":

我的具体目标是:如果它们与最近的父进化枝的平均距离是<X(ETE2 Python包),则将这些图案(提示/终端节点/叶子)折叠在一起.这在生物学上是有意义的,因为一些基因调控DNA基序可以彼此同源(旁系同源物或直向同源物).这种折叠可以通过上面链接的iTol GUI完成,例如,如果你选择X = 0.001,那么一些图案会折叠成三角形(图案族).

我的问题:任何人都可以提出一种算法,可以输出或帮助可视化X的哪个值适合"最大化折叠图案的生物或统计相关性"？理想情况下,当对X绘制时,树的某些属性会有一些明显的阶跃变化,这表明算法是一个合理的X.是否有任何已知的算法/脚本/包？也许代码会针对X的值绘制一些统计数据？我已经尝试绘制X与平均簇大小(matplotlib),但我没有看到明显的"步骤增加"来通知我使用X的值:

我的代码和数据:我的Python脚本的链接是[这里] [8],我已经对它进行了大量评论,它将为您生成树数据和上图(使用参数d_from,d_to和d_step来探索距离切割-offs,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 提到的树协调的方法。但标准树协调实际上会失败。

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

但就您而言，您想要解决的问题是“将这棵超级树分解为适当大小的同源子树”。这意味着您并不想像重复一样遭受损失。您需要一种对树进行评分的方法，以便揭示有多少同源子树合并到您的超级树中。因此，您可以尝试以下评分方法：

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

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

S1 - S2 / N

推论：

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

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