理解小吝啬，Sankoff的算法

Question

小的简约问题： 在演化树中找到最简约的内部顶点标签。 输入：Tree 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，INF，INF〕，〔INF，INF，INF，0]，[9,7， 8，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)