匹配技術(shù)在多序列比對(duì)中的運(yùn)用范文

本站小編為你精心準(zhǔn)備了匹配技術(shù)在多序列比對(duì)中的運(yùn)用參考范文，愿這些范文能點(diǎn)燃您思維的火花，激發(fā)您的寫(xiě)作靈感。歡迎深入閱讀并收藏。

《信息系統(tǒng)工程雜志》2014年第十期

一、問(wèn)題提出

由于星比對(duì)算法平方級(jí)的時(shí)間復(fù)雜度無(wú)法滿足實(shí)際需要，文獻(xiàn)[6]對(duì)其進(jìn)行改進(jìn)，提出了基于關(guān)鍵字樹(shù)的DNA多序列星比對(duì)算法。其主要思想是依次將每個(gè)序列都分割成等長(zhǎng)的子串集合，為這個(gè)集合構(gòu)建一棵模式樹(shù)。除該序列的其他序列使用Aho-Corasick算法對(duì)該模式樹(shù)進(jìn)行模式匹配，并記錄所有模式串出現(xiàn)次數(shù)的總和。將出現(xiàn)次數(shù)總和值最大的序列定為中心序列，然后根據(jù)星比對(duì)算法中“一旦為空格，始終為空格”的思想，將其他序列與中心序列的未匹配部分進(jìn)行多序列比對(duì)。文獻(xiàn)[6]雖然將星比對(duì)算法的平方級(jí)時(shí)間復(fù)雜度降到了線級(jí)，但在選取中心序列時(shí)，模式串的出現(xiàn)次數(shù)沒(méi)有考慮是否為公共的模式串，使得選取的中心序列并非為最優(yōu)解。本文在文獻(xiàn)[6]的基礎(chǔ)上進(jìn)行改進(jìn)，建立一棵公共的模式樹(shù)，所有序列都使用Aho-Corasick算法對(duì)這棵公共的模式樹(shù)進(jìn)行模式匹配，并使用數(shù)組記錄搜索得到的模式號(hào)，通過(guò)對(duì)數(shù)組中的模式號(hào)的逐級(jí)篩選，最后剩下的序列所包含的公共的模式串為最多，增強(qiáng)了算法尋求最優(yōu)解的能力。實(shí)驗(yàn)表明改進(jìn)后的算法更能獲得最優(yōu)解。

二、模式樹(shù)模型

模式樹(shù)模型[7]描述如下：定義1：由模式串集合構(gòu)成的模式樹(shù)K是一棵有根樹(shù)，滿足：(1)K的每一條邊由1個(gè)字符標(biāo)記；(2)與同一節(jié)點(diǎn)相連的任意多條邊標(biāo)記的字符均不相同；(3)每個(gè)模式串都對(duì)應(yīng)著一個(gè)節(jié)點(diǎn)v，使得，其中是從根節(jié)點(diǎn)到節(jié)點(diǎn)v所經(jīng)過(guò)的邊的對(duì)應(yīng)字符的拼接；(4)K的每個(gè)葉節(jié)點(diǎn)v''''，存在模式串，使得。

三、算法描述

基于模式匹配的多序列比對(duì)算法仍然是以星比對(duì)為基礎(chǔ)的，分為尋找中心序列和兩兩比對(duì)兩個(gè)主要步驟。要尋找中心序列，設(shè)需要進(jìn)行比對(duì)的多個(gè)序列分別是。具體操作如下。步驟1：將每個(gè)序列等分成長(zhǎng)度為r的子序列構(gòu)成子序列集合L，（l取值，k取值）。將集合L中的所有子序列構(gòu)成一棵公共的模式樹(shù)T。步驟2：對(duì)于公共的模式樹(shù)T，每個(gè)序列利用Aho-Corasick算法搜索T，并記錄每個(gè)序列匹配的模式號(hào)和該模式在當(dāng)前序列中出現(xiàn)的位置，其中模式號(hào)表示模式樹(shù)中該模式的編號(hào)。這里使用一個(gè)多維數(shù)組進(jìn)行記錄，表示序列Pi搜索T時(shí)，匹配編號(hào)為Pos[j]的模式串在Pi中的位置為Pos[j,j]。步驟3：統(tǒng)計(jì)每個(gè)序列匹配的模式號(hào)，這里只考慮搜索T時(shí)通過(guò)非失效鏈接得到的模式號(hào)，并使用一個(gè)二維數(shù)組進(jìn)行統(tǒng)計(jì)。表示匹配成功的模式號(hào)，表示序列Pi匹配編號(hào)為的模式串的次數(shù)。步驟4：依次找出匹配次數(shù)最多的那個(gè)模式號(hào)，將沒(méi)有匹配該模式號(hào)的序列從查找中心序列的隊(duì)列中去除，最后剩下的序列將是中心序列Pc。步驟5：得到中心序列后，將Pc與依次進(jìn)行比對(duì)。由于在步驟(4)中已經(jīng)記錄了Pc和Pi匹配的子串位置，然后使用動(dòng)態(tài)規(guī)劃算法將Pc和Pi未匹配的子串進(jìn)行比對(duì)。并且記錄需要在Pc和Pi中插入空格的位置Sci和Si。步驟6：依次比對(duì)完P(guān)c和后，對(duì)所有需要插入空格的位置匯總，匯總后的位置記為Sc，分別比較Sc和Sci，在Si中加入新匯入的空格位置。分別根據(jù)Si中記錄的空格位置將空格插入到Pi中并輸出多序列比對(duì)的結(jié)果。

四、實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)將基于模式匹配的多序列比對(duì)算法和星比對(duì)算法、基于關(guān)鍵字樹(shù)的DNA多序列星比對(duì)算法進(jìn)行比較。實(shí)驗(yàn)PC的CPU為Pentium(R)Dual-CoreT42002.00GHz，內(nèi)存為2.00GB，操作系統(tǒng)為Windows7，運(yùn)行環(huán)境為VistualStudio2008。選取了兩組數(shù)據(jù)進(jìn)行測(cè)試，對(duì)每組測(cè)試數(shù)據(jù)都連續(xù)運(yùn)行程序20次，并從程序運(yùn)行時(shí)間和堿基對(duì)匹配情況兩個(gè)方面比較三種算法的期望時(shí)間復(fù)雜度和比對(duì)的效率。第一組實(shí)驗(yàn)通過(guò)對(duì)6種西藏部分地區(qū)豆科植物的根瘤菌多序列比對(duì)，完成DNA同源性分析。實(shí)驗(yàn)數(shù)據(jù)來(lái)自于NCBI上的核酸庫(kù)以及文獻(xiàn)[8]。序列的條數(shù)為6，序列的平均長(zhǎng)度為1428。該實(shí)驗(yàn)數(shù)據(jù)程序運(yùn)行時(shí)間如圖1所示。第二組實(shí)驗(yàn)通過(guò)對(duì)11個(gè)物種的β-球蛋白基因的第一個(gè)外顯子進(jìn)行多序列比對(duì)。實(shí)驗(yàn)數(shù)據(jù)來(lái)自于NCBI上的核酸庫(kù)以及文獻(xiàn)[9]，序列的條數(shù)為11，序列的平均長(zhǎng)度為92。該實(shí)驗(yàn)數(shù)據(jù)程序運(yùn)行時(shí)間如圖3所示。統(tǒng)計(jì)11個(gè)物種的β-球蛋白基因第一個(gè)外顯子的堿基對(duì)匹配情況如圖4所示。通過(guò)第一組實(shí)驗(yàn)結(jié)果可知，在運(yùn)行時(shí)間上本算法雖然略高于基于關(guān)鍵字樹(shù)的星比對(duì)算法，但其堿基對(duì)匹配數(shù)卻遠(yuǎn)高于基于關(guān)鍵字樹(shù)的星比對(duì)算法。因?yàn)楸舅惴ㄔ趯ふ抑行男蛄袝r(shí)采用的是逐級(jí)去掉希望最小的序列，最后剩下的序列所包含的公共的子串為最多，相對(duì)于基于關(guān)鍵字樹(shù)的星比對(duì)算法中直接將模式串出現(xiàn)次數(shù)最多的序列定為中心序列的方法，得到的結(jié)果則更接近最優(yōu)解。在第二組實(shí)驗(yàn)中，本算法的堿基對(duì)匹配數(shù)也高于基于關(guān)鍵字樹(shù)的星比對(duì)算法，與星比對(duì)算法更為接近。在運(yùn)行時(shí)間方面，由于本實(shí)驗(yàn)所選取的序列相似性很高，尋找中心序列時(shí)統(tǒng)計(jì)每個(gè)序列共有的模式號(hào)的個(gè)數(shù)接近k值，所以可以認(rèn)為尋找中心序列的運(yùn)行時(shí)間為O(n2k)。而基于關(guān)鍵字樹(shù)的星比對(duì)算法的尋找中心序列運(yùn)行時(shí)間為O(n2l)，k是待比較的序列所分割的段數(shù)，取值O(l/logl)，遠(yuǎn)小于l，所以O(shè)(n2k)也遠(yuǎn)小于O(n2l)。在建立好模式樹(shù)后，本算法和基于關(guān)鍵字樹(shù)的星比對(duì)算法一樣，將完全匹配的子串位置存儲(chǔ)下來(lái)。所以在其他序列與中心序列逐個(gè)進(jìn)行比對(duì)的過(guò)程中，對(duì)于完全匹配的子串就不需要再進(jìn)行比對(duì)。另外，其他序列與中心序列采用動(dòng)態(tài)規(guī)劃算法進(jìn)行比對(duì)，其運(yùn)行時(shí)間與比對(duì)的長(zhǎng)度呈平方關(guān)系。如果相似程度非常高的序列進(jìn)行比對(duì)，匹配的子串個(gè)數(shù)與k越接近，那么在每個(gè)序列與中心序列進(jìn)行比對(duì)的長(zhǎng)度就越短，花費(fèi)的時(shí)間也就越少。

五、結(jié)論

本文提出了一種新的生物序列比對(duì)算法——基于模式匹配的DNA多序列比對(duì)算法。此算法是在星比對(duì)算法和Aho-Corasick算法的基礎(chǔ)上，針對(duì)基于關(guān)鍵字樹(shù)的DNA多序列比對(duì)方法提出來(lái)的。由于此算法是對(duì)原始星比對(duì)算法的一種改進(jìn)，所以算法的實(shí)現(xiàn)仍然包括兩個(gè)步驟：尋找中心序列和序列兩兩比對(duì)。通過(guò)實(shí)驗(yàn)結(jié)果表明，新算法相對(duì)于基于關(guān)鍵字樹(shù)的DNA多序列比對(duì)算法的準(zhǔn)確率更高，相對(duì)于原始星比對(duì)算法的運(yùn)算速度更快。

作者：王櫻楊麗李錫輝單位：湖南信息職業(yè)技術(shù)學(xué)院計(jì)算機(jī)工程系