选择最优树——NP-complete 问题
（以下内容都是基于Christopher P. Randle教授在研究组上交流时的课件整理而来。感谢Christopher。）
在介绍选择最优系统发育树的三种方法之前，我们先引入一个例子，帮助理解这些方法解决的问题。
有一种职业叫旅行销售员，销售员要往返于各个城市，假设他需要去A、B、C、D、E 5个城市，怎么保证他能到达这5个城市，走过的路程又最短呢？
Is there general solution to such problems?
如果我们假设他需要去n个城市，所有可能的路线有(n-1)!/2种情况。
注：(n-1)!=(n-1)(n-2)(n-3)···1
旅行销售员的问题是NP-hard或者NP-complete问题，每一条路线就是一个solution，每个solution都可以很快的进行分析（这里就是计算每一条路线的长度），但是在没有分析完所有的solution之前你永远不知道哪个solution是最好的（也就是说不计算完所有的路线长度进行比较，你永远不知道哪个是最短的）。
The travelling salesman problem is likely in a class of problems which are NP(NonPolynmial time)*-hard or NP-complete. Each solution can be assessed quickly. However, no algorithm is guaranteed to obtain the optimal solution without assessing all solutions.
找到最优树也是一个NP-complete问题
Finding the best tree is also NP-Complete
这是因为，随着taxa（分类群）和character（性状）的增加，可能的topologies（拓扑结构或者系统发育树）的数目会是一个天文数字。
现在我们来看一下给定taxa的数目，可能的topologies有多少。
如果有4个taxa，那么会有3种可能的unrooted topologies，每个topology有5个branches。
如果有5个taxa呢？
在4个taxa的情况下，在3个可能的unrooted topology的5个branches上都能增加一个branch，那就是3的5次方，共15种可能的unrooted topologies，每个topology有7个branches。
假如有n个taxa，那么可能的unrooted topologies的数目为
每个topology有2n-3个branches。其中，internal branches有n-3个，内部的节点数为n-2。
假设共有r个性状（如果使用DNA数据就是有r个位点），那么一个特定的假设拓扑结构就有[if !msEquation][endif]种不同的情况。
随着taxa和character的增加，这就是一个天文数字。
最大简约法的原理
（以下文字基本来自对《生物进化》这本书中相关章节的总结，该书Douglas J. Futuyma著，葛颂等人翻译。）
最大简约法（Maximum Parsimony ）是系统发生分析中最简单的方法之一。但是，先别高兴的太早，这一个方法也存在着很大的弊端。
最大简约法依据的是一个哲学原理，the Principle of Parsimony：
The simplest explanation is best until evidence against it is found。
翻译下就是：最简单的解释就是最好的解释，除非你找到反驳它的证据。
这个原理反映在系统发生重建上就是：
The phylogeny requiring the fewest character transformations maximizes homology. It is the simple explanation and should be preferred
即最接近真实系统发生的树就是所要求的进化改变数最少的那棵系统发生树。
比如根据形态性状推断植物类群的系统发生关系时，我们更倾向于图右面的topology，因为它用最少的变化就可以得到观察到的性状分布（character state distribution），证据表明它确实更符合实际情况。
最大简约法的弊端
我们提到这一方法存在弊端，那么是什么弊端呢？
我们先来说下进行比较的不同物种间的性状特征有系统发生信息和无系统发生信息的相似性。
这里用5个taxa（1、2、3、4、5）的DNA序列在5个位点上（(A)、(B)、(C)、(D)、(E)）的核苷酸替代来展示。图中的所有信息，包括分支历史和碱基替代，都是实际情况。
在(A)位点，最简单的解释是A是祖先状态，而C是一个衍生状态，在taxa1、2、3中是同源的，是它们形成一个进化枝的证据。
在(B)位点同理，G是一个衍生状态，在taxa1、2中同源，是它们形成一个进化枝的证据。
在(C)位点，如果不知道进化历史，仅知道碱基状态，我们无法确定1和2的亲缘关系比其他taxa更近，我们也无法判断2、3、4、5的亲缘关系远近，因此无法分支，它是一个无信息的性状。
在(D)位点，在1-3的祖先中，C被A替代，在taxon1中，A又被C替代，发生了非同源相似中的进化逆转。这种情况有误导性，因为如果我们只知道碱基状态，很可能得到1与4、5的亲缘关系比2、3更近，和2、3具有共享衍征，亲缘关系更近的结论。
在(E)位点，C被T替代这一事件在taxon1和taxon3中独立发生，是非同源相似的另一种情况趋同进化，也具有误导性，让我们误以为1、3是近亲。
如果依据最大简约原则，在(D)和(E)位点发生的情况将会误导我们得到错误的结论。
This is because homology requires fewer hypotheses of transformation than convergence or parallelism.
翻译一下：这是因为假设同源比假设出现趋同进化和平行进化需要的进化改变（这里是碱基替换）更少，而最大简约法就是选择碱基替换最少的那种可能的系统发育关系。
这也被称为Hennigs Auxilliary Principle:
In the absence of contrary data, assume homology.
在没有其他反对证据的情况下，假设同源。
