關于DNA序列的k—mer index問題的討論

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

關鍵詞 k-mer k-mer 計數 頻次統計 逆向遍歷

主要原因是 k-長 DNA 子序列關鍵字不能完全存放在內存中，運行的大部分時間用在頻繁的內外存交換上。所以，我們以算法將結果用二維數組存儲于內存中就可以達到加快查詢結果以及存儲內存的節省問題。

定義：函數（[…]） = （[]）

其中，[]， […]。稱（[…]）為[…]的關鍵字，由經映射成的關鍵字多重集記為。

然后將數據映射到二維空間上，形成二維數組，其坐標表示如下：

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

具體的失效鏈接值以及KPM匹配算法實現過程如下：

索引的計算復雜度和空間復雜度分析如下：

KMP的算法流程：

我們發現如果某個字符匹配成功，模式串首字符的位置保持不動，僅僅是 ++、 ++；如果匹配失配，不變（即不回溯），模式串會跳過匹配過的next []個字符。……