对于给定的条件，要在很多可能的树中找一棵最佳的树。在实际应用中，不可能穷尽搜索所有可能的树，必须按照一定的方法、一定的策略在较短的时间内得到比较好的结果。

6.3.1 最大简约法

最大简约法(Maximum Parsimony)最早是基于形态特征分类的需要而发展起来的，具体的算法有许多版本，其中有些已被广泛地用于分子进化研究中，根据离散特征数据构建系统发生树。最大简约法的目标是构造一棵反映分类单元之间最小变化的系统发生树。最大简约法利用的只是对简约分析能提供信息的特征，如在DNA序列数据中，利用的只是存在于核苷酸序列差异（至少有两种不同类型的核苷酸）的位点，这些位点称为简约信息位点（parsimony informative site）。具体来说，信息位点就是指能由位点产生的突变数目把一棵树与其它树区分开来的位点。如果对于某个位点，所有序列都有同样的字符，则这个位点称为不变位点(invariant)。显然不变位点是非信息位点（uninformative site）。如果一个位点是信息位点，那么它至少有两种不同的核苷酸，并且这些核苷酸至少出现两次。所有的简约法程序在开始时都将这条简单的规则应用于输入数据集。显然，表6.5中位点6 是非信息位点，该位点将被舍弃，在简约法分析中不再被考虑。但是，非信息位点对基于距离的方法中两两相似度的得分有贡献，仅这一点差别就可能使这两类方法产生的结果有很大的不同。

对于系统发生树最直观的代价计算就是沿着各个分支累加特征变化的数目，而所谓简约就是使代价最小。利用最大简约方法构建系统发生树，实际上是一个对给定分类单元所有可能的树进行比较的过程。针对某一个可能的树，首先对每个位点祖先序列的核苷酸组成做出推断，然后统计每个位点用来阐明差异的核苷酸最小替换数目。在整个树中，所有简约信息位点最小核苷酸替换数的总和称为树的长度或树的代价。通过比较所有可能的树，选择其中长度最小、代价最小的树作为最终的系统发生树，即最大简约树（maximum parsimony tree）。

假设图6.9是根据表6.5所建立的一棵系统发生树。对于位点1，由于甲、乙、丙都取“C”值，而丁、戊取“T”值，它们分别处于树的两边，因此，只需要在系统发生树“根节点”所连接的两条边上有一个变化（左分支T变为C，或者右分支C变为T），就能解释各个分类单元在该位点的数据。对于位点2，甲、乙取“A”值，而丙、丁、戊取“G”值，通过“节点2”可以将它们分开，因此，“节点2” 所连接的左分支上的一个变化（G变为A），就能解释各个分类单元在该位点的差异。位点3的情况与位点1相同，位点4的情况比前几个位点复杂，甲、乙、丙、丁、戊的取值方式为“G、 A、G、A、G”，需要在“节点1”和“节点3”所连接的边上分别设置一个变换。因此位点4需要两个变化。同样位点5需要两个变化。对于位点6，显然只需要一个变化，其变化点处于“节点3”所连接的分支。位点6属于非信息位点，在简约分析时可以不再考虑它。总的来说，对于图6.9所示的整个系统发生树，共需要8个变化。

对于表6.5中所列出的5个分类单元，还可以形成其它拓扑结构的系统发生树，这些树为解释表6.5中各个位点的数据，可能需要更多或者更少的变化。而最大简约法的目的就是要寻找一棵最小变化的系统发生树。

最大简约法的处理过程如下：

（1）针对待比较的物种，选择核酸或蛋白质序列。有些分子比其它分子的变化速率稳定，适合于进行进化分析，例如哺乳类的线粒体DNA、管家蛋白质等；

（2）比较各个序列，产生序列的多重比对，确定各个序列字符的相对位置；

（3）根据每个序列比对的位置（即多重序列比对的每一列），确定相应的系统发生树，该树用最少的进化动作产生序列的差异，最终生成完整的树。

对于一棵系统发生树T ，假设树中的节点集合用V(T)表示，树中边的集合用E(T)表示，以u_j、v_j分别表示节点u和v的第j个特征，则树T的代价为：

给定一棵有根的系统发生树，我们所关心的是：如何计算该树的最小变化？如何标定树的内部节点？假设以v_c代表v节点特征c的值，单特征（即每个分类单元所对应的序列仅含一个字符，作为单个特征的值）Fitch算法如下：首先，对于每个待分析的分类单元，分配一个叶节点v，其值v_c取对应分类单元的特征值。然后执行下面两步：

(1)   给每个节点v赋予一个特征值集合S_v：如果v是叶节点 ，则S_v ={v_c}；如果v是内部节点，并且u、w是其子节点，如果S_uÇS_w ¹φ（φ代表空集合），则S_v =S_uÇS_w；否则 S(v)=S_uÈS_w 。这个过程从叶节点开始，直至处理到根节点。如果用递归算法，则应该按后序遍历方式处理每个节点。

(2)    给定集合S_v，为每个内部节点v的特征c赋予值v_c。如果v有一个父节点u满足u_cÎS_v,则将u_c赋予v_c，否则，任取一个tÎS_v赋予v_c。这个过程的执行方向刚好与上一个过程相反，即从树根出发，直至叶节点为止，最后得到完全标定的树。应按前序遍历方式依次处理每个节点。

最后，树中变化的个数等于第一步计算得到空交集S_uÇS_w的个数。图6.10是对5条序列（每个序列仅含一个字符，作为分类单元的特征）执行过程（1）的结果，最小的总代价为3，图中节点标注“*”表明该节点的子节点交集S_uÇS_w为空。

上述算法对特征值之间变换的代价进行统一处理，不考虑其中的差别。其实，各种特征值之间变换的代价是不一样的，比如，DNA序列中碱基转换比颠换的可能性大，碱基的插入和删除比替换的可能性小，长插入和删除比短插入和删除少见。如果能给各种突变赋予相对概率值，则在简约算法中可将这些值转化为权值。不幸的是，我们不可能得到一组适用于所有（或大部分）数据集的基于概率的权值。确定一组普遍适用的相对概率的有许多困难，例如，一些序列（象非编码序列，特别是包含连续短重复片段的序列）比其它序列更容易插入和删除，不同的基因和物种有不同的替换偏好。所以，最佳的权值通常来自对实验数据集的分析。可获得的最佳实验数据集是实际分析过的数据集。例如，把每条序列进行多重序列比对，假如转换出现的频率是颠换的三倍，那么对同一个序列集的简约分析就可以给所有的转换替换赋权值1，给所有的颠换替换赋权值3。在建立数学模型时，应该区分这些差别。

令C_ij^c代表特征c的特征值从i变化为j的代价。将上述算法改进为求加权最大简约树，这就是比Fitch算法更一般化的Sankoff算法。该算法可以处理多个特征，并考虑不同特征值变换代价的差异。计算过程如下：

(1)   对于每个树节点v和特征值t，计算S_t^c(v)，它代表树根为v的子树在v_c=t的情况下的最小代价值。计算的顺序与Fitch算法中的第一步一样，后序遍历。对每个叶节点v：

对于每个内部节点v，设其两个子节点分别为u和w，则：

树根为r的最小总代价等于

这里，m为特征的个数。

(1)   根据第一步的计算，确定每个特征在内部节点上的最佳值:

对于根节点r，选择

对于其他节点v，假设其父节点为u，则

    前面的工作实际上是针对已知拓扑结构的系统发生树，确定其中的内部节点标记，即确定树的内部节点特征取值。这仅仅是解决问题的一个步骤，或者是后面的一个步骤。关键的问题是系统发生树的拓扑结构又是如何确定的呢？实际上，这是要在众多可能的拓扑结构中选择一棵与给定数据相一致的树，或代价最小的树。这是一个典型的搜索问题，而且，搜索空间非常大。分析10个分类单元，至少要考虑2百万棵树；如果分类单元再增加，恐怕即使最快的计算机也不能完成穷举搜索，即比较每一棵可能的树。目前已经研究出一些改进的算法，不用考虑所有可能的树就能够方便可靠地确定最简约树。

6.3.2 快速搜索策略

对于庞大的搜索空间，采用许多快速搜索策略可以大大提高搜索效率。分支约束（Branch and Bound，B&B）技术是其中的一类。分支约束是在一个复杂的空间中进行搜索的通用技术，搜索空间以从一个分层树的根节点至叶节点的一系列路径表示。如果搜索树是单调的，在搜索树中每个节点的代价不比其任何祖先节点低，即等于或者高于祖先节点的代价，则分支约束算法奏效。分支约束保证能够找到最优解，但是在最坏的情况下，该算法的时间复杂度与穷尽搜索相近。

分支约束最简单的算法形式是按照一定的顺序遍历搜索树，保存到目前为止到达叶节点路径的最小的代价，并作为代价的上限，记为B。在后续搜索过程中，如果到达搜索树的某个节点，并且到达该节点路径的代价大于B，则不再搜索以该节点为树根的子树，搜索树在此节点处不再继续扩展，因为即使搜索该节点的子树，也不会得到比B更好的结果。上述行为称为搜索树在某个节点剪枝。在开始搜索之前，可以根据期望值，或根据其他线索设定初始的上限值B。

考虑这样一棵搜索树，以搜索树的节点代表相应的系统发生树。在搜索树的第k层上的节点代表具有k个叶节点、对应于前k个分类单元的所有可能的系统发生树，第k层上的节点的子节点将代表在上述系统发生树中加入第k+1个分类单元而形成的新系统发生树。搜索树的树根代表空系统发生树。由于在一棵系统发生树上增加一个新节点不会减小简约代价，所以搜索树满足单调条件，分支约束技术可以帮助我们对搜索树进行剪枝，从而压缩搜索空间，提高搜索效率。

具体利用分支约束法发现最简约树包括两个基本的步骤。第一步是为最简约树的代价确定一个上限B，其值可以取随机选择的任何一棵描述被研究分类单元之间关系的树的代价，但是如果用近似最简约的树来建立上限，这个方法将更有效。第二步是树的生长过程，即在描述部分分类单元之间关系的树中每次增加一个分支。如果增加一个分支后的代价大于B，那么当剩下的分类单元加入后，总的代价必定变得更大。也就是说，最简约树不可能是包含上述特定分支模式的树，因为已经找到了一棵更简约的树（即用于确定B的那棵树）。在分析过程中，如果发现比建立初始上限的树替换数更少的树，B的值将随之修正，这样，对余下的数据集的分析将更为有效。

和穷举搜索一样，分支约束法保证在分析完成时没有遗漏更简约的树，它还有比穷举搜索快几个数量级的优点，能够用于分析多达20个分类单元。但是，对于更多的分类单元，分支约束法还是存在计算效率问题，还需要其它的更有效的快速搜索方法, 如启发式方法(heuristic method)。启发式算法包括贪婪算法、模拟退火算法等。这类算法不一定总能找到最简约的树，得到的往往是一个局部最优结果，但是接近于全局最优结果。

许多搜索最简约树的启发式方法都基于同样的假设：最简约树应该和次简约树有相似的拓扑结构。这些算法首先构造一棵初始树，从它开始寻找更简约的树。同分支约束法一样，如果初始树很接近于最简约树，启发式搜索会更有效。启发式方法并不逐个分支地构建所有可能的树，而是通过子树分支交换(branch swapping)，把它们嫁接到该步分析中找到的最好的那棵树的其它位置上，从而产生一棵拓扑结构和初始树相似的树。第一轮分析中，由初始树产生出上百棵新树，其中所有比初始树代价小的新树都在第二轮分析中被剪枝和嫁接。不断重复这个过程，直到某一轮通过剪枝和嫁接无法产生与前一轮相同或代价更小的树。