多叉進(jìn)化樹構(gòu)建方法的研究與實(shí)現(xiàn)

多叉進(jìn)化樹構(gòu)建方法的研究與實(shí)現(xiàn)分子系統(tǒng)發(fā)育分析是生物信息學(xué)中的重要研究領(lǐng)域,它的主要研究手段是從一組同源的DNA或蛋白質(zhì)序列出發(fā),計(jì)算各個(gè)序列之間的進(jìn)化距離,從而得到反映物種進(jìn)化關(guān)系的進(jìn)化樹。進(jìn)化樹通常是一棵二叉樹:樹的葉結(jié)點(diǎn),代表了某個(gè)具體序列;樹的拓?fù)浣Y(jié)構(gòu)表現(xiàn)了各物種之間的親緣關(guān)系遠(yuǎn)近;樹的分枝長度刻畫了進(jìn)化距離的大小。構(gòu)建進(jìn)化樹的方法主要分為三類,即距離矩陣法、最簡約方法和極大似然法。其中,距離矩陣法以結(jié)構(gòu)簡單、具有良好的理論基礎(chǔ)等特點(diǎn)獲得了廣泛的應(yīng)用。但是,研究指出一些基于距離矩陣的建樹方法在某些情況下會產(chǎn)生拓?fù)浣Y(jié)構(gòu)不惟一的進(jìn)化樹結(jié)果,即進(jìn)化樹的具體拓?fù)浣Y(jié)構(gòu)會根據(jù)同源序列輸入算法的順序不同而發(fā)生變化。不加權(quán)算術(shù)平均組對法(UnweightedPair-GroupMethodusingArithmeticaverages,以下簡稱UPGMA)是一種比較常見的距離矩陣法,該方法也存在上述問題。雖然該方法被設(shè)計(jì)為針對同一組序列數(shù)據(jù)產(chǎn)生惟一的進(jìn)化樹結(jié)果,但是可以證明在算法迭代過程中,如果距離矩陣中出現(xiàn)最小元素不惟一的情況,則算法產(chǎn)生的進(jìn)化樹拓?fù)浣Y(jié)構(gòu)是隨著序列輸入順序的不同而變化的。這一現(xiàn)象為系統(tǒng)發(fā)育分析結(jié)果的解釋帶來了困難——在多個(gè)進(jìn)化樹結(jié)果中,顯然只能有一棵進(jìn)化樹反映了真實(shí)的物種進(jìn)化關(guān)系,但是在出現(xiàn)多個(gè)結(jié)果時(shí)UPGMA并不能判斷哪一棵樹的拓?fù)浣Y(jié)構(gòu)是正確的。并且大多數(shù)流行的分子系統(tǒng)發(fā)育分析軟件并沒有處理UPGMA產(chǎn)生的進(jìn)化樹不惟一的問題。通常僅根據(jù)算法實(shí)現(xiàn)方式的不同,給出了其中一種拓?fù)浣Y(jié)構(gòu)。針對以上問題,本文詳細(xì)分析了UPGMA產(chǎn)生不惟一結(jié)果的原因,在此基礎(chǔ)上提出并實(shí)現(xiàn)了UPGMA的一種改進(jìn)算法,即不加權(quán)算術(shù)平均組群方法(UnweightedMulti-GroupMethodusingArithmeticaverages,以下簡稱UMGMA)。UMGMA是UPGMA的一種擴(kuò)展,而UPGMA可以看作UMGMA的一個(gè)特例。在迭代計(jì)算過程中,UPGMA總是選取距離矩陣中最小的元素對應(yīng)的一對序列生成新的分類群單元。而UMGMA則通過引入距離容差參數(shù)τ,將所有小于τ的元素對應(yīng)的序列作為生成新分類群單元的基礎(chǔ)。該方法在一次迭代中可以產(chǎn)生多個(gè)新的分類群單元,因此其進(jìn)化樹結(jié)果可能是多叉樹。在UPGMA結(jié)果不惟一的情況下,各種可能的二叉樹結(jié)果在UMGMA中被綜合構(gòu)建成一棵惟一的多叉樹,從而解決了惟一性的問題;而在UPGMA結(jié)果惟一的情況下,取距離容差參數(shù)τ等于零,UMGMA得到的結(jié)果將與UPGMA的結(jié)果完全一致?；趯?shí)際數(shù)據(jù)的進(jìn)化樹構(gòu)建實(shí)驗(yàn)表明,UMGMA不僅能夠產(chǎn)生結(jié)果惟一的進(jìn)化樹,而且通過選擇不同的容差參數(shù)τ,還能產(chǎn)生不同層次的進(jìn)化樹。這意味著在大規(guī)模系統(tǒng)發(fā)育分析中,UMGMA可以通過調(diào)整τ的值,不斷突出進(jìn)化樹的整體脈絡(luò)。本文的課題研究工作中還實(shí)現(xiàn)了一種包含完整UMGMA算法實(shí)現(xiàn)以及傳統(tǒng)UPGMA方法實(shí)現(xiàn)的分子發(fā)育分析軟件——Multi-Tree。該軟件是一個(gè)基于Microsoft.Netframework2.0平臺構(gòu)建的客戶端應(yīng)用,其中使用WebService完成多序列比對功能,并提供一套基本的分子進(jìn)化分析流程,包括:多序列比對結(jié)果編輯、距離矩陣計(jì)算以及多種方法構(gòu)建進(jìn)化樹,并以多種風(fēng)格顯示進(jìn)化樹。Multi-Tree軟件系統(tǒng)有別于大多數(shù)傳統(tǒng)的分子發(fā)育分析工具軟件包,它具有友好的富