生物信息學(xué)學(xué)習(xí)報(bào)告-文庫(kù)吧資料
2024-08-18 00:41本頁(yè)面
【正文】 的調(diào)和序列和每條輸入序列進(jìn)行兩兩比對(duì)得到比對(duì)結(jié)果。設(shè)想所有輸入序列都是從一個(gè)祖先序列進(jìn)化而來，我們要找的就是這個(gè)祖先序列。基于最大權(quán)值路徑算法的 DNA 多序列比對(duì)方法本算法用 de Bruijn graph[19]的形式表示輸入序列，將輸入序列的信息記錄在圖的邊上，定義邊的權(quán)值為經(jīng)過該邊的序列的條數(shù)，則邊的權(quán)值越大，說明此邊越有可能代表輸入序列的保守區(qū)域。上述方法各有其不同的優(yōu)點(diǎn)，但它們中的大多數(shù)對(duì)于大量輸入序列，其時(shí)空復(fù)雜度依然是實(shí)際應(yīng)用的一個(gè)瓶頸，至少都O(N2L2)其中 N 是序列條數(shù)，L 是序列平均長(zhǎng)度。其中，最有影響的多序列比對(duì)軟件包 SAGA(sequence alignment by genetic algorithm）基于遺傳算法構(gòu)建，共設(shè)計(jì)了 22 種不同的遺傳算子，采用動(dòng)態(tài)調(diào)度的策略控制 22 種遺傳算子的使用。迭代比對(duì)方法基于一個(gè)能產(chǎn)生比對(duì)的算法，并通過一系列的迭代方式改進(jìn)多序列比對(duì)，直到比對(duì)結(jié)果不再改善為止。但是，不同的添加順序會(huì)產(chǎn)生不同的比對(duì)結(jié)果，所以，確定合適的比對(duì)順序是漸進(jìn)比對(duì)方法的一個(gè)關(guān)鍵問題。具體介紹如下：精確比對(duì)方法精確比對(duì)方法完全基于動(dòng)態(tài)規(guī)劃算法，最為經(jīng)典的是多維 NeedlmanWunsch 算法，但其可行的計(jì)算維數(shù)為 3。它是SPS(sumofpairs scoring)意義下的 NP 完全問題。該算法把序列信息用 de Bruijn 圖的形式表示，并將輸入序列的信息記錄在圖的邊上，這樣，就將求調(diào)和序列的問題轉(zhuǎn)化為求圖的最大權(quán)值路徑問題，使多序列比對(duì)問題的時(shí)間復(fù)雜度降低到幾乎線性。實(shí) 驗(yàn) 報(bào) 告題 目 基于最大權(quán)值路徑算法的 DNA 多序列比對(duì)方法學(xué)習(xí)報(bào)告學(xué) 院： 軟件學(xué)院 系 計(jì)算機(jī) 專業(yè)班級(jí)： 軟件工程
電大資料相關(guān)推薦
鄂ICP備17016276號(hào)-1