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