構建進化樹的鄰接法的改進算法.pdf

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

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