選擇最優(yōu)樹——NP-complete?問題
（以下內(nèi)容都是基于Christopher P. Randle教授在研究組上交流時的課件整理而來。感謝Christopher。）
在介紹選擇最優(yōu)系統(tǒng)發(fā)育樹的三種方法之前，我們先引入一個例子，幫助理解這些方法解決的問題。
有一種職業(yè)叫旅行銷售員，銷售員要往返于各個城市，假設(shè)他需要去A、B、C、D、E 5個城市，怎么保證他能到達(dá)這5個城市，走過的路程又最短呢？
Is there general solution to such problems?
如果我們假設(shè)他需要去n個城市，所有可能的路線有(n-1)!/2種情況。
注：(n-1)!=(n-1)(n-2)(n-3)···1
旅行銷售員的問題是NP-hard或者NP-complete問題，每一條路線就是一個solution，每個solution都可以很快的進(jìn)行分析（這里就是計(jì)算每一條路線的長度），但是在沒有分析完所有的solution之前你永遠(yuǎn)不知道哪個solution是最好的（也就是說不計(jì)算完所有的路線長度進(jìn)行比較，你永遠(yuǎn)不知道哪個是最短的）。
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.
找到最優(yōu)樹也是一個NP-complete問題
Finding the best tree is also NP-Complete
這是因?yàn)?，隨著taxa（分類群）和character（性狀）的增加，可能的topologies（拓?fù)浣Y(jié)構(gòu)或者系統(tǒng)發(fā)育樹）的數(shù)目會是一個天文數(shù)字。
現(xiàn)在我們來看一下給定taxa的數(shù)目，可能的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的數(shù)目為
每個topology有2n-3個branches。其中，internal branches有n-3個，內(nèi)部的節(jié)點(diǎn)數(shù)為n-2。
假設(shè)共有r個性狀（如果使用DNA數(shù)據(jù)就是有r個位點(diǎn)），那么一個特定的假設(shè)拓?fù)浣Y(jié)構(gòu)就有[if !msEquation][endif]種不同的情況。
隨著taxa和character的增加，這就是一個天文數(shù)字。
最大簡約法的原理
（以下文字基本來自對《生物進(jìn)化》這本書中相關(guān)章節(jié)的總結(jié)，該書Douglas J. Futuyma著，葛頌等人翻譯。）
最大簡約法（Maximum Parsimony?）是系統(tǒng)發(fā)生分析中最簡單的方法之一。但是，先別高興的太早，這一個方法也存在著很大的弊端。
最大簡約法依據(jù)的是一個哲學(xué)原理，the Principle of Parsimony：
The simplest explanation is best until evidence against it is found。
翻譯下就是：最簡單的解釋就是最好的解釋，除非你找到反駁它的證據(jù)。
這個原理反映在系統(tǒng)發(fā)生重建上就是：
The phylogeny requiring the fewest character transformations maximizes homology. It is the simple explanation and should be preferred
即最接近真實(shí)系統(tǒng)發(fā)生的樹就是所要求的進(jìn)化改變數(shù)最少的那棵系統(tǒng)發(fā)生樹。
比如根據(jù)形態(tài)性狀推斷植物類群的系統(tǒng)發(fā)生關(guān)系時，我們更傾向于圖右面的topology，因?yàn)樗米钌俚淖兓涂梢缘玫接^察到的性狀分布（character?state?distribution），證據(jù)表明它確實(shí)更符合實(shí)際情況。
最大簡約法的弊端
我們提到這一方法存在弊端，那么是什么弊端呢？
我們先來說下進(jìn)行比較的不同物種間的性狀特征有系統(tǒng)發(fā)生信息和無系統(tǒng)發(fā)生信息的相似性。
這里用5個taxa（1、2、3、4、5）的DNA序列在5個位點(diǎn)上（(A)、(B)、(C)、(D)、(E)）的核苷酸替代來展示。圖中的所有信息，包括分支歷史和堿基替代，都是實(shí)際情況。
在(A)位點(diǎn)，最簡單的解釋是A是祖先狀態(tài)，而C是一個衍生狀態(tài)，在taxa1、2、3中是同源的，是它們形成一個進(jìn)化枝的證據(jù)。
在(B)位點(diǎn)同理，G是一個衍生狀態(tài)，在taxa1、2中同源，是它們形成一個進(jìn)化枝的證據(jù)。
在(C)位點(diǎn)，如果不知道進(jìn)化歷史，僅知道堿基狀態(tài)，我們無法確定1和2的親緣關(guān)系比其他taxa更近，我們也無法判斷2、3、4、5的親緣關(guān)系遠(yuǎn)近，因此無法分支，它是一個無信息的性狀。
在(D)位點(diǎn)，在1-3的祖先中，C被A替代，在taxon1中，A又被C替代，發(fā)生了非同源相似中的進(jìn)化逆轉(zhuǎn)。這種情況有誤導(dǎo)性，因?yàn)槿绻覀冎恢缐A基狀態(tài)，很可能得到1與4、5的親緣關(guān)系比2、3更近，和2、3具有共享衍征，親緣關(guān)系更近的結(jié)論。
在(E)位點(diǎn)，C被T替代這一事件在taxon1和taxon3中獨(dú)立發(fā)生，是非同源相似的另一種情況趨同進(jìn)化，也具有誤導(dǎo)性，讓我們誤以為1、3是近親。
如果依據(jù)最大簡約原則，在(D)和(E)位點(diǎn)發(fā)生的情況將會誤導(dǎo)我們得到錯誤的結(jié)論。
This is because homology requires fewer hypotheses of transformation than convergence or parallelism.
翻譯一下：這是因?yàn)榧僭O(shè)同源比假設(shè)出現(xiàn)趨同進(jìn)化和平行進(jìn)化需要的進(jìn)化改變（這里是堿基替換）更少，而最大簡約法就是選擇堿基替換最少的那種可能的系統(tǒng)發(fā)育關(guān)系。
這也被稱為Hennigs Auxilliary Principle:
In the absence of contrary data, assume homology.
在沒有其他反對證據(jù)的情況下，假設(shè)同源。
