生物信息學(xué)學(xué)習(xí)報告(完整版)
【正文】 題，使多序列比對問題的時間復(fù)雜度降低到幾乎線性。迭代比對方法基于一個能產(chǎn)生比對的算法，并通過一系列的迭代方式改進(jìn)多序列比對，直到比對結(jié)果不再改善為止。設(shè)想所有輸入序列都是從一個祖先序列進(jìn)化而來，我們要找的就是這個祖先序列。sN)，其中：，為第 i 條序列的長度，則關(guān)于 S 的一個多序列比對可定義為一個矩陣。為了反映所有序列準(zhǔn)確對齊的比率，通常使用 CS(columnscore)值來計算。但是，此算法也有一些不足之處有待改進(jìn)：當(dāng)序列之間變異率較大時，比對結(jié)果較差；并且，算法本。同樣，對于比對結(jié)果 S′，CS值計算公式為基本上，SPS 值和 CS 值越高，說明比對結(jié)果越準(zhǔn)確，越能反映序列的生物特性。多序列比對結(jié)果的評判標(biāo)準(zhǔn)目標(biāo)函數(shù)用來評判序列比對結(jié)果的優(yōu)劣。最后，利用得到的調(diào)和序列和每條輸入序列進(jìn)行兩兩比對得到比對結(jié)果。其中，最有影響的多序列比對軟件包 SAGA(sequence alignment by genetic algorithm）基于遺傳算法構(gòu)建，共設(shè)計了 22 種不同的遺傳算子，采用動態(tài)調(diào)度的策略控制 22 種遺傳算子的使用。它是SPS(sumofpairs scoring)意義下的 NP 完全問題?；A(chǔ)知識多序列比對是生物信息學(xué)中挑戰(zhàn)性的問題之一，并在序列裝配、序列注釋、基因和蛋白質(zhì)的結(jié)構(gòu)和功能預(yù)測以及系統(tǒng)發(fā)育和進(jìn)化分析等方面應(yīng)用廣泛?；谶@種思想的方法很多，例如模擬退火、遺傳算法、隱馬爾可夫模型等。此過程不需要進(jìn)行多序列比對，并且使尋找調(diào)和序列問題的時間復(fù)雜度大為降低，幾乎是線性的。該矩陣有如下特性：1)2) 如果刪除空位“—”，則 的每一行 與對應(yīng)序列 相同；3) S′中不存在只由空位“?”組成的列。CS 值計算策略為：如果一列上的所有堿基都相等，則 ci=1；否則 ci=0。參考文獻(xiàn)[1] Batzoglou S. The many fa
電大資料相關(guān)推薦
鄂ICP備17016276號-1