理解小简约，Sankoff算法

Question

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

我指的是这篇文章底部的图片。我只是简单地尝试遵循提供的示例。我知道第一步是标记四个叶子A，C，T，G(因为我们被提供了这个输入)，我们通过在每个叶子的数组中将适当的一个字符设置为0，并将字符的其余字母表设置为无穷大来实现这一点。

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

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

当我画出它时，似乎根的A/14，T/9，10/G，15/c是这样计算的:对于A/14，我们取四个可能值中的最小值。第一个值是左右孩子是A的情况(9+7+2(0) = 16)，第二个值是左右孩子是T的情况(7+2+2(3) = 14)，第三个值是左右孩子是G的情况(8+2+2(4) = 18)，第四个值是左右孩子是C的情况(9+8+2(9) = 35)。这四个值中的最小值是min(16，14，18，35) = 14，这意味着如果根是A，那么左右两边的孩子都是T。

如果我继续这样做，我会得到与书中的根相同的值(14，9，10，15)，其中最小值是9，表示根是T(它的两个子元素也是T)。

然而，这是正确的逻辑吗？我觉得可以有更多的组合，而不仅仅是探索根的每个字符四个值。我尤其感到奇怪的是，我只考虑了四种情况，即孩子必须是相同的角色(A和A，T和T，G和G，C和C)。

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

谢谢。

​

如果难以读取，后序中的顶点数组为0，inf，0，9，7，8，9，inf，0，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)