第六章系統(tǒng)發(fā)生分析-文庫(kù)吧
2025-07-17 13:25 本頁(yè)面
【正文】 （ 2）分支約束方法 即根據(jù)一定的約束條件將搜索空間限制在一定范圍內(nèi)，產(chǎn)生可能的樹，然后擇優(yōu)。 （ 3）啟發(fā)式或經(jīng)驗(yàn)性方法 根據(jù)先驗(yàn)知識(shí)或一定的指導(dǎo)性規(guī)則壓縮搜索空間，提高計(jì)算速度。 第二節(jié) 基于距離的系統(tǒng)發(fā)生樹構(gòu)建方法 ?基本思路是： 給定一種序列之間距離的測(cè)度，在該距離測(cè)度下構(gòu)建一棵系統(tǒng)發(fā)生樹，使得該樹能夠最好地反映已知序列之間的距離。 10條核酸序列的距離矩陣 例，如果有三個(gè)物種，其兩兩距離如下： dab = dac = dbc = 通過求解方程，得到 如圖 。 最小二乘法 ? 目標(biāo)是構(gòu)造一棵樹 T，該樹的葉節(jié)點(diǎn)代表物種，用該樹預(yù)測(cè)物種之間的距離。通過優(yōu)化，使下式最小化： 這里， Dij為物種 i和 j的實(shí)際觀察距離（或序列之間的計(jì)算距離）， dij是物種 i和 j在系統(tǒng)發(fā)生樹 T 中的距離， Wij是與物種 i和 j相關(guān)的權(quán)值。 SSQ（ T）是樹 T所有預(yù)測(cè)值與實(shí)際觀察值偏差的累加和。權(quán)值 Wij一般為 1，或 Wij =1/ Dij2 ? ?? ??? ni ijijijij dDWTSSQ12)()(連鎖聚類方法 ?選擇距離最小的一對(duì)序列 ?將這兩個(gè)序列合二為一，形成一個(gè)新的對(duì)象（代表這兩個(gè)序列的祖先） ?重新計(jì)算這個(gè)新的對(duì)象與其它序列的距離。 單連鎖聚類 : d(x,u)=min(d(y,u),d(z,u)) 最大連鎖聚類： d(x,u)=max(d(y,u),d(z,u)) 平均連鎖聚類： d(x,u)=1/2(d(y,u)+d(z,u)) 其中 x代表 y和 z的合并 ， u代表任意其它對(duì)象 。 非加權(quán)分組平均法 （ Unweighted Pair Group Method with Arithmetic mean, UPGMA） ? 在平均連鎖聚類過程中，一個(gè)新類到其它類之間的距離就是簡(jiǎn)單的原距離平均值 。 如果類中分類單元個(gè)數(shù)不一樣，原距離矩陣中各個(gè)距離值對(duì)新距離計(jì)算的貢獻(xiàn)就不一樣，或者說是經(jīng)過“加權(quán)”的，稱這樣的聚類為加權(quán)分組平均。 ? 在非加權(quán)分組平均法中，在計(jì)算新分類到其它分類之間的平均距離時(shí)按照各分類中分類單元的數(shù)目進(jìn)行加權(quán)處理。 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)分別
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1