algorithm - 了解 Small Parsimony，Sankoff 算法

Question

小简约问题:在进化树中找到内部顶点的最简约标签。输入:树 T，每片叶子都标有 m 个字符串。输出:最小化简约分数的树 T 内部顶点的标记。

我指的是这篇文章底部的图片。我只是想按照提供的示例进行操作。我知道第一步是标记四片树叶 A、C、T、G(因为我们提供了这个输入)，我们通过将适当的一个字符设置为 0 并将其余字符设置为无穷大来实现在每个叶子的数组中。

图中的下一步，我们分析两个不是根的内部节点。我也理解这个过程。例如，在左侧内部节点中，我们得到数组 A/9、T/7、G/8、C/9。这四个值中的每一个都被计算为左 child (A) 和右 child (C)，加上分数罚分。比如A/9就是0+0(左子0分+A->A的penalty)加上0+9(右子0分+C->A的penalty)。

然而，令我感到困惑的是根是如何计算的。这与考虑具有无穷大值的叶子是不同的情况(这样添加一个小惩罚没有区别，甚至不考虑无穷大分数)。

我画出来的时候好像根的A/14,T/9,10/G,15/c是这样计算的:对于A/14，我们取四个可能值中的最小值。第一个值是左右 child 都是A的情况(9+7+2(0) = 16)，第二个值是左右 child 都是T的情况(7+2+2(3) = 14) ), 第三个值是左右 child 都是G的情况(8+2+2(4) = 18), 第四个值是左右 child 都是C的情况(9+8+2(9) = 35).这四个值中的最小值是 min(16, 14, 18, 35) = 14，这意味着如果根是 A，则左右 child 都是 T。

如果我以这种方式继续，我会得到与书上相同的根值 (14, 9, 10, 15)，其中最小值为 9，表明根是 T(并且它的两个子节点也是T).

但是，这是正确的逻辑吗？我觉得可以有更多的组合，而不是仅仅探索根的每个字符的四个值。我特别奇怪，我只考虑 child 必须是同一个角色的四种情况(A和A，T和T，G和G，C和C)。

所以我的问题是，这在这个问题中起作用只是巧合吗？如果是正确的，为什么我不需要考虑两个 child 性格不同的情况呢？如果它不正确，那么在这个例子中计算根的正确方法是什么(我更喜欢看到与这个特定问题相关的数字，因为我仍然在试图找出复杂的方程式时睁大眼睛)。

谢谢。

为了不方便阅读，后序顶点数组为[0, inf, inf, inf], [inf, inf, inf, 0], [9, 7, 8, 9], [inf , 0, inf, inf], [inf, inf, 0, inf], [7, 2, 2, 8], [14, 9, 10, 15]

Answer 1

好吧，这个答案有点晚了，但我还是会插话的。

是的，您的解决方案恰好有效只是一个巧合。要计算树的内部节点 A 的值，您应该考虑左分支中从 A 到 {A,C,T,G} 的最小成本，加上从 A 到 {A,C 的最小成本,T,G}在右分支。

所以对于根节点，要计算A的值:

LEFT            RIGHT

0 3 4 9         0 3 4 9
9 7 8 9         7 2 2 8
-------        ---------
9 10 12 18      7 5 6 17     min = 9+5 = 14 (A)

然后对 {C,T,G} 重复此过程以获得其他值。

 LEFT            RIGHT

3 0 2 4         3 0 2 4
9 7 8 9         7 2 2 8 
-------        ---------
12 7 10 13      10 2 4 12    min = 7+2 = 9  (T)

4 2 0 4         4 2 0 4
9 7 8 9         7 2 2 8
-------        ---------
13 9 8 13       11 4 2 12    min = 8+2 = 10 (G)

9 4 4 0         9 4 4 0
9 7 8 9         7 2 2 8
-------        ---------
18 11 12 9      16 6 6 8     min = 9+6 = 15 (C)