關(guān)于DNA序列的k—mer index問題的討論

摘 要 本文研究了DNA序列的k-mer index 問題，通過對(duì)大量基因組數(shù)據(jù)的考察，我們改進(jìn)了由暴力算法延伸的Donald Knuth的算法，即KMP算法，在原來的算法上我們嵌入了一個(gè)循環(huán)算法，并且使用java設(shè)計(jì)出算法程序來達(dá)到快速檢索的目的，并將數(shù)據(jù)以數(shù)組形式存儲(chǔ)，再將數(shù)組在二維坐標(biāo)系里投影，再利用信息熵的計(jì)算將問題簡(jiǎn)化成關(guān)于K值和fm的函數(shù)問題。

關(guān)鍵詞 k-mer k-mer 計(jì)數(shù) 頻次統(tǒng)計(jì) 逆向遍歷

主要原因是 k-長(zhǎng) DNA 子序列關(guān)鍵字不能完全存放在內(nèi)存中，運(yùn)行的大部分時(shí)間用在頻繁的內(nèi)外存交換上。所以，我們以算法將結(jié)果用二維數(shù)組存儲(chǔ)于內(nèi)存中就可以達(dá)到加快查詢結(jié)果以及存儲(chǔ)內(nèi)存的節(jié)省問題。

定義：函數(shù)（[…]） = （[]）

其中，[]， […]。稱（[…]）為[…]的關(guān)鍵字，由經(jīng)映射成的關(guān)鍵字多重集記為。

然后將數(shù)據(jù)映射到二維空間上，形成二維數(shù)組，其坐標(biāo)表示如下：

我們還可以利用KPM模式匹配的算法來處理序列拼接中的重復(fù)序列屏蔽問題。核心思想就是通過失效函數(shù)得到在當(dāng)前位置匹配失效后，下一次開始進(jìn)行匹配的位置，充分利了序列的已知信息，減少了無謂的序列比對(duì)，使得算法達(dá)到了線性時(shí)間復(fù)雜度。大大減少了所需CPU時(shí)間。經(jīng)試驗(yàn)驗(yàn)證該算法對(duì)重復(fù)序列的屏蔽具有線性時(shí)間復(fù)雜度。

具體的失效鏈接值以及KPM匹配算法實(shí)現(xiàn)過程如下：

索引的計(jì)算復(fù)雜度和空間復(fù)雜度分析如下：

KMP的算法流程：

我們發(fā)現(xiàn)如果某個(gè)字符匹配成功，模式串首字符的位置保持不動(dòng)，僅僅是 ++、 ++；如果匹配失配，不變（即不回溯），模式串會(huì)跳過匹配過的next []個(gè)字符。整個(gè)算法最壞的情況是，當(dāng)模式串首字符位于的位置時(shí)才匹配成功，算法結(jié)束。

因此可知整個(gè)算法的計(jì)算量

（ + / ∣∣ + / ∣∣2…+ / ∣）

由于 ≤ ，且 ≥ 2，所以整個(gè)算法的時(shí)間復(fù)雜度為 （），所以，如果文本串的長(zhǎng)度為，模式串的長(zhǎng)度為，那么匹配過程的計(jì)算復(fù)雜度為（），算上計(jì)算next的（）時(shí)間，KMP的整體計(jì)算復(fù)雜度為（ + ）。

參考文獻(xiàn)：

[1]朱赟.Snort 入侵檢測(cè)系統(tǒng)的警報(bào)日志分析[D].上海：上海交通大學(xué)，2007.

[2]胡鵬.入侵檢測(cè)系統(tǒng)中高效模式匹配算法的研究[D].上海：上海大學(xué)，2006.

[3]劉威，郭淵博，黃鵬.基于 Bloom filter 的多模式匹配引擎[J].電子學(xué)報(bào)，2010.

[4]劉紅梅，劉國(guó)慶.基于K-mer組分信息的系統(tǒng)發(fā)生樹構(gòu)建方法[J].2013.

（張琴單位：吉林建筑大學(xué)基礎(chǔ)科學(xué)部；朱穎莉單位：長(zhǎng)春市第二實(shí)驗(yàn)中學(xué)）