第六章系統(tǒng)發(fā)生分析-文庫吧資料
2024-08-14 13:25本頁面
【正文】 u滿足 uc?Sv,則將 uc賦予 vc， 否則任取一個(gè) t?Sv賦予 vc。如果用遞歸算法，則應(yīng)該按后序遍歷方式處理每個(gè)節(jié)點(diǎn)。然后執(zhí)行下面兩步： (1) 給每個(gè)節(jié)點(diǎn) v賦予一個(gè)集合 Sv： 如果 v是葉節(jié)點(diǎn) ，則Sv ={vc}； 如果 v是內(nèi)部節(jié)點(diǎn)，并且 u、 w是其子節(jié)點(diǎn)，如果 Su?Sw ??， 則 Sv =Su?Sw； 否則 S(v)=Su?Sw 。有些分子比其它分子變化慢 ， 適合于進(jìn)行距離分析 ，例如哺乳類的線粒體 DNA、 管家蛋白質(zhì)等； （ 2） 比較各個(gè)序列 ， 產(chǎn)生序列的多重比對(duì) ， 確定各個(gè)序列符號(hào)的相對(duì)位置； （ 3） 根據(jù)每個(gè)序列比對(duì)的位置 （ 即多重對(duì)比排列的每一列 ） ， 確定相應(yīng)的系統(tǒng)發(fā)生樹 ， 該樹用最少的進(jìn)化動(dòng)作產(chǎn)生序列的差異 ， 最終生成完整的樹 。 對(duì)于系統(tǒng)發(fā)生樹最直觀的代價(jià)計(jì)算就是沿著各個(gè)分支累加特征變化的數(shù)目。 最大簡(jiǎn)約法 目標(biāo)： 構(gòu)造一棵反映分類單元之間最小變化的系統(tǒng)發(fā)生樹。 ?輸入一般為 n m的特征矩陣 M ?在構(gòu)建系統(tǒng)發(fā)生樹假設(shè)特征是相互獨(dú)立的，即一個(gè)特征的變化不影響另一個(gè)特征。 對(duì)于節(jié)點(diǎn) i， 到其它節(jié)點(diǎn)的距離 ui 按下式進(jìn)行估算： ui = ?k?i(Dik/(n2)) 這里 Dik是分類 i和分類 k之間的距離 選擇 Dijuiuj最小的一對(duì)節(jié)點(diǎn) i 和節(jié)點(diǎn) j 進(jìn)行歸并 ? 算法如下： （ 1）初始化（與 UPGMA一樣） （ 2）循環(huán) 對(duì)于所有的分類單元 i，計(jì)算 ui = ?k?I (Dik/(n2))； 選擇一對(duì)分類單元 i 和 j ，使 Dijuiuj最?。? 將 i和 j歸并為新的類 (ij)，在樹中添加一個(gè)新的節(jié)點(diǎn)，代表新生成的分類，計(jì)算從 i和 j到新節(jié)點(diǎn)的分支長(zhǎng)度； di,(ij） = 1/2Di,j +1/2(uiuj), dj,(ij） = 1/2Di,j +1/2(ujui) 計(jì)算新類與其它類的距離； D(ij） ,k = 1/2(Di,k + Dj,k Di,j) 刪除聚類 i和 j，添加新類 (ij)； 如果有兩個(gè)以上的分類存在，則繼續(xù)執(zhí)行循環(huán)；否則用長(zhǎng)度為 Di,j的分支連接剩余的兩個(gè)類 。 ? 重復(fù)上一次循環(huán) , 直到只剩一個(gè)類為止。 ? 重建時(shí)將距離最小的兩個(gè)葉節(jié)點(diǎn)連接起來，合并這兩個(gè)葉節(jié)點(diǎn)所代表的分類，形成一個(gè)新的分類。 UPGMA算法的執(zhí)行過程如下： (1) 初始化：使每個(gè)物種自成一類 ， 如果有 n個(gè)物種 ， 則開始時(shí)共有 n個(gè)類 ， 每個(gè)類的大小為 1， 分別用 n個(gè)葉節(jié)點(diǎn)代表每個(gè)類； (2)執(zhí)行下列循環(huán)： l 尋找具有最小距離 Dij的兩個(gè)類 i、 j； 建立一個(gè)新的聚類 （ ij) l 連接 i和 j形成新節(jié)點(diǎn) (ij)， 生長(zhǎng)兩個(gè)新的分支 ， 將 i 和 j 連接到(ij)， 分支的長(zhǎng)度為 Dij/2； l 計(jì)算新分類到其它類的距離 其中 ni、 nj、 (ni+nj)分別為 i類 、 j類 、 (ij)類的元素個(gè)數(shù)； l 在距離矩陣中刪除與類 i和類 j相應(yīng)的行和列 ， 為類 (
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1