構(gòu)建進(jìn)化樹(shù)的鄰接法的改進(jìn)算法.pdf

1、構(gòu)建進(jìn)化樹(shù)就是從生物序列的信息推斷生物進(jìn)化歷史,"重塑"出系統(tǒng)進(jìn)化的(譜系)關(guān)系,并把進(jìn)化關(guān)系用樹(shù)的形式表示出來(lái)——樹(shù)的葉子結(jié)點(diǎn)表示各個(gè)生物序列,樹(shù)枝的長(zhǎng)度表示生物間的進(jìn)化距離.構(gòu)建進(jìn)化樹(shù)問(wèn)題是一個(gè)典型的NP完全問(wèn)題,當(dāng)序列的條數(shù)很大時(shí),沒(méi)有一種最優(yōu)算法能在適當(dāng)?shù)臅r(shí)間內(nèi)計(jì)算得到其精確解,因此,構(gòu)造能在適當(dāng)?shù)臅r(shí)間內(nèi)得到最優(yōu)近似解的算法就有很強(qiáng)的實(shí)際意義.對(duì)經(jīng)典算法鄰接法進(jìn)行研究后,提出了兩種改進(jìn)的算法.對(duì)于距離矩陣法而言,遺傳模型在進(jìn)化樹(shù)

2、構(gòu)建算法中非常重要.只有當(dāng)進(jìn)化模型選擇恰當(dāng)時(shí),序列進(jìn)化距離才會(huì)計(jì)算得精確,構(gòu)建的進(jìn)化樹(shù)才會(huì)準(zhǔn)確.但是鄰接法采用了Jukes-Cautor單參數(shù)模型,該模型沒(méi)有考慮到基因突變中轉(zhuǎn)換和顛換的不同概率,其模型比較粗糙.因此,在改進(jìn)算法Ⅰ中,采用了Kimura兩參數(shù)模型,根據(jù)此模型來(lái)計(jì)算序列的距離,從而改進(jìn)序列間距離;并采用新的校正距離R<,ij>=αM<,ij>+βd<,ij>,這樣算法的準(zhǔn)確性得到提高.改進(jìn)算法Ⅱ考慮到鄰接法的另外一個(gè)不足,