構(gòu)建進化樹的方法主要分為
- 距離矩陣法（含 UPGMA瓮具、ME石咬、NJ等）
- 最大簡約法（MP）
- 極大似然法（ML）
- 貝葉斯法（Bayesian）
基于距離的進化樹構(gòu)建方法
常用的距離法構(gòu)建系統(tǒng)樹：
- 不加權(quán)算術(shù)平均對方法（Unweighted Pair-Group Method using Arithmetic average, UPGMA）
- 最小進化距離法（Mnimal Evolution Method）
- 鄰接法（Neighbor-Joining Method, NJ）
這一系列方法主要考量參數(shù)是：
- 如何計算距離帜矾，節(jié)點間的距離毙籽；cluster之間的距離构韵；校正的距離
- 如何聚類绑咱？
UPGMA 法
本質(zhì)上是“自下而上”或者說“聚合”的層次聚類（hclust）法悴晰，且距離的計算采用“平均距離法”慢睡。一般繪制熱圖，常見的表達模式聚類方法也是 hclust铡溪，往往默認(rèn)“最長距離法”漂辐。兩者只是cluster之間距離的計算方式不同。當(dāng)所有分支的突變率相同棕硫，UPGMA效果較好髓涯。
最小進化法（ME）
尋找某一進化樹的拓?fù)浣Y(jié)構(gòu)，使得全樹枝長總和最短哈扮。邏輯上需要對每一個拓?fù)浣Y(jié)構(gòu)進行評估纬纪，當(dāng)序列增加時蚓再，計算量暴增。
這個與后續(xù)提到的最大簡約法（MP）的最大區(qū)別是：（1）ME法直接基于一個距離矩陣包各，計算的是最終進化樹枝長總和最姓觥；（2）MP法直接基于序列问畅，計算的最終是在當(dāng)前拓?fù)浣Y(jié)構(gòu)下娃属，所有序列需要發(fā)生突變的位點的總和最少。
鄰接法（NJ）
與UPGMA幾乎相反护姆，UPGMA約等于層次聚類的聚合法膳犹；而NJ法從拓?fù)浣Y(jié)構(gòu)的變化上來看，與層次聚類的分離法比較像签则。當(dāng)然還是有比較大的區(qū)別须床。層次聚類的分離實現(xiàn)考量的是分離后兩個cluster的內(nèi)部距離總和最小。NJ法考量的是分離出來的兩個leaf node的校正距離最小渐裂。這一校正距離綜合考量了每個leaf node以及cluster的距離豺旬。在距離計算上的實現(xiàn)，邏輯上比層次聚類的分離法要簡單一些柒凉。簡單實現(xiàn)了一下族阅，似乎還是跟UPGMA法類似，NJ法計算邏輯其實還是跟層次聚類的聚合法比較像膝捞。最大的區(qū)別坦刀，仍然是距離的計算。但是蔬咬，在不少資料中翻閱鲤遥，圖示上似乎不是這個畫法。
簡單摘菜已報道文稿的NJ法實現(xiàn)邏輯林艘，代碼就不擺了盖奈。寫完之后，感覺跟寫TBtools的熱圖聚類邏輯類似狐援，效率上還是不太行钢坦。估計還是要想想辦法重構(gòu)代碼。感興趣的朋友也可以參考Nei老爺子的論文（同樣重磅的還有他的NG86算法啥酱，計算dnds的....可以說是目前最常用方法之一）爹凹。簡單來說，就是都挺準(zhǔn)镶殷，但又容易實現(xiàn)禾酱，且很快，著實大神級別。
百度的時候發(fā)現(xiàn)國內(nèi)有不少關(guān)于NJ法的小改進宇植，當(dāng)然都是很多年前得封。我猛然發(fā)現(xiàn)，對于經(jīng)典算法的實現(xiàn)闡述指郁，新的算法改進論文寫得更清晰忙上。當(dāng)然可能是 typeset 的問題。畢竟現(xiàn)在的印刷和公式編輯都比以前方便得多闲坎。
（注：dlk 應(yīng)是筆誤疫粥，應(yīng)為 dik）
最大簡約法
距離法的主要特點是距離實質(zhì)是序列兩兩之間的距離，在進化樹構(gòu)建的構(gòu)建的過程中腰懂，邏輯上不存在距離重新計算梗逮，直接導(dǎo)入一個距離矩陣即可建樹。最大簡約法考量的距離具體到每條序列的每個位點绣溜。拓?fù)浣Y(jié)果改變時慷彤，序列兩兩間兩位點的所需的突變次數(shù)同樣變化。最大簡約法遍歷所有拓?fù)浣Y(jié)構(gòu)怖喻，并尋求全局位點突變次數(shù)最小的一個底哗。
極大似然法
Emmm，突然不想寫了锚沸。極大似然法確實沒時間捋明白跋选，還沒做過代碼實現(xiàn)。大體認(rèn)知哗蜈，拿著進化模型來看不同拓?fù)浣Y(jié)構(gòu)（進化樹）出現(xiàn)的可能性前标。可能性越大也就越準(zhǔn)確距潘。當(dāng)然炼列，這里的問題就還是哪個模型合適，這個還是要算一算的绽昼。拿錯模型的話....
ML法跟MP法邏輯上都是要遍歷所有樹唯鸭，當(dāng)然，一般情況下....還是用 UPGMA 或者 NJ 建個樹硅确，作為起始樹，然后改吧改吧明肮，看看結(jié)果是不是更優(yōu)菱农，直到似乎找不到更優(yōu)，就認(rèn)為當(dāng)前最優(yōu)柿估。于是循未，出現(xiàn)局部最優(yōu)，邏輯合理。
貝葉斯法
至今未用過.... 明明是干一個事情的妖，一定要把方法搞得越復(fù)雜越好绣檬，參數(shù)越多，模型就流弊嫂粟。當(dāng)我們把固定參數(shù)變成分布娇未，ML就變成bayesian....
寫在最后
Emmm.... 今天，就水一文星虹。昨天海邊玩累了零抬，今天干活也沒力氣，只能準(zhǔn)備準(zhǔn)備課件宽涌。
