1、2015山東科技大學數學建模競賽承 諾 書我們仔細閱讀了山東科技大學數學建模競賽的競賽規則.我們完全明白，在競賽開始后參賽隊員不能以任何方式（包括電話、電子郵件、網上咨詢等）與隊外的任何人研究、討論與賽題有關的問題。我們知道，抄襲別人的成果是違反競賽規則的, 如果引用別人的成果或其他公開的資料（包括網上查到的資料），必須按照規定的參考文獻的表述方式在正文引用處和參考文獻中明確列出。我們鄭重承諾，嚴格遵守競賽規則，以保證競賽的公正、公平性。如有違反競賽規則的行為，我們將受到嚴肅處理。我們參賽選擇的題號是（從A/B/C中選擇一項填寫）：我們的參賽序號為：所屬學院（請填寫完整的全名）：參賽隊員 (打

2、印并簽名) ：1. 2. 3. 日期：年月日基于Hash表在大量DNA序列中快速索引查找k-mer的算法摘要：為了解決在大量DNA數據中快速查找到k-mer所在位置，我們基于Hash算法思想建立適合此題的快速索引方法（桶式定址法），利用四進制轉十進制的方式（）取得關鍵碼值建立哈希表進行索引查詢，8G內存限制下在codeblocks集成開發環境中，借助C語言進行編寫使k支持114。針對問題將依次進行下列敘述：對建立索引的算法進行敘述和沖突分析；對建立索引算法的計算復雜度和空間復雜度進行分析；對索引查詢進行敘述及性能分析；分析整套算法程序在不同k值下內存占用及極限分析。總結分析整套索引算法性能，對

3、算法進行缺陷分析及改進方案。關鍵詞：索引算法、Hash表、k-mer快速索引、數據結構一、問題重述1.1背景 給定一個DNA序列，這個系列只含有4個字母ATCG，如 S =“CTGTACTGTAT”。給定一個整數值k，從S的第一個位置開始，取一連續k個字母的短串，稱之為k-mer（如k= 5，則此短串為CTGTA）， 然后從S的第二個位置， 取另一k-mer（如k= 5，則此短串為TGTAC），這樣直至S的末端，就得一個集合，包含全部k-mer 。 如對序列S來說，所有5-mer為CTGTA，TGTAC，GTACT，TACTG，ACTGT，TGTAT通常這些k-mer需一種數據索引方法，可被后

4、面的操作快速訪問。例如，對5-mer來說，當查詢CTGTA，通過這種數據索引方法，可返回其在DNA序列S中的位置為1，6。1.2問題現在以文件形式給定 100萬個 DNA序列，序列編號為1-1000000，每個基因序列長度為100 。（1）要求對給定k， 給出并實現一種數據索引方法，可返回任意一個k-mer所在的DNA序列編號和相應序列中出現的位置。每次建立索引，只需支持一個k值即可，不需要支持全部k值。（2）要求索引一旦建立，查詢速度盡量快，所用內存盡量小。（3）給出建立索引所用的計算復雜度，和空間復雜度分析。 （4）給出使用索引查詢的計算復雜度，和空間復雜度分析。（5）假設內存限制為8G，

5、分析所設計索引方法所能支持的最大k值和相應數據查詢效率。（6）按重要性由高到低排列，將依據以下幾點，來評價索引方法性能 · 索引查詢速度· 索引內存使用· 8G內存下，所能支持的k值范圍· 建立索引時間二、問題分析在生物技術快速發展的今天，人類分析人類自身編碼的需求也越來越高，人們利用計算機來處理分析大量DNA序列，k-mer快速查找也是處理大量數據的問題，所以必須依賴數據結構原理，建立模型構造算法，從而利用有限的資源解決復雜問題。針對問題一：按照給定k值，將所有數據按題目要求分組，求出每組數據的關鍵碼值，并將關鍵碼值與此組k-mer所在位置建立對應關系

6、并存儲到表中，從而建立哈希表。針對問題二：將要查找的k-mer序列求出其關鍵碼值，直接輸出其關鍵碼值在表中對應位置信息，大大加快了索引查詢速度。針對問題三：詳見四-（二）-2，3。針對問題四：詳見四-（三）-2，3。針對問題五：根據k值大小動態分配內存建立哈希表，最終實現k支持114的范圍，因為直接關鍵碼值尋址輸出，所以索引查詢速度非常快。針對問題六：按照重要性首先考慮索引查詢速度，其次動態內存分配盡量減少索引對內存的消耗，在8G內存限制下，使k值支持114，最后優化添加計數器記錄已經存在地址的k-mer個數，倘若達到所有k-mer種類數，則停止建立索引，索引成功建立。三、符號說明符號符號說明

7、H(x)關鍵碼值生成函數，其中x代表一個k-mer代表A，T，C，G中的任意一個與相對應的四進制數k一個k-mer的長度M內存空間占用（單位：GB）四、算法設計思路及性能分析（代碼見附錄一）(一) 哈希表設計：1、k-mer關鍵碼值生成函數H(x)由于DNA序列由4個字母排列而成，所以每個k-mer都是一個四進制數，H(x)函數根據這個特征將四進制數轉為十進制數作為哈希表關鍵碼值。x= “CTGTA”如上圖為每個字母代表的四進制數字，例如一個5-mer “CTGTA” 可以表示為四進制數21310，其十進制表示為628，628即為5-mer “CTGTA”在哈希表中的關鍵碼值。關鍵碼值計算的一

8、般公式為:（1）2、哈希表結構將k-mer通過公式（1）轉換為十進制的關鍵碼值存入哈希表中的關鍵碼值一列，并將關鍵碼值與此k-mer所在位置建立對應關系，從而便于索引尋址。這里采用的方法是：桶定址法。桶：一片足夠大的存儲空間。桶定址：為表中的每個地址關聯一個桶。如果桶已經滿了，可以使用開放定址法來處理。如圖。3、沖突處理方法開放地址法有一個公式：Hi=(H(key)+di) MOD m i=1,2,.,k(k<=m-1）其中，m為哈希表的表長。di 是產生沖突的時候的增量序列。如果di值可能為1,2,3,.m-1，稱線性探測再散列。如果di取1，則每次沖突之后，向后移動1個位置.如果di

9、取值可能為1,-1,4,-4,9,-9,16,-16,.k*k,-k*k(k<=m/2）稱二次探測再散列。(二) 建立索引的算法、計算復雜度及空間復雜度分析1、 算法分析hash表初始化時，根據用戶輸入的k值， 計算出存儲哈希表需要的空間，利用內存動態分配函數動態分配內存，k-mer所在行數為100 0000以內所以我們采用int型（占用4字節）存儲，而其在行的第幾個位置數在100以內，我們則采用char（占用1字節）型存儲，充分減少空間損耗。哈希表初始化代碼：求關鍵碼值如上敘述采用四進制轉十進制數作為關鍵碼值存入哈希表用于位置索引。求關鍵碼值代碼：建立哈希表過程中先將傳入的長度為100

10、的字符串分成每k個字符一段的串，每分好一個就求一個關鍵碼值存儲哈希表，為了提高建立索引的速度，每個關鍵碼值只對應一個位置信息，也就是說索引查詢時只返回k-mer的一個位置信息。倘若每個關鍵碼值都有其對應的位置信息了，就退出索引建立，索引建立完成。建立哈希表代碼：2、計算復雜度分析不考慮8G空間限制，k在150的范圍內每條DNA序列分段的循環不斷增加，計算復雜度也隨之增加，而50100范圍內循環則又開始減少。根據，建立索引的計算復雜度為3、空間復雜度分析邏輯上哈希表空間占用計算公式：（每條索引信息邏輯空間占用為5Byte）k值建立索引后空間占用（GB）10.00000002 20.0000000

11、7 30.00000030 40.00000119 50.00000477 60.00001907 70.00007629 80.00030518 90.00122070 100.00488281 110.01953125 120.07812500 130.31250000 141.25000000 155.00000000 1620.00000000 由以上圖表可以清晰的看到，索引建立的內存消耗隨著k的增長冪指數增長，與k-mer排列組合種類數（）相對應，所以減少每條索引數據的存儲空間，可大大增加k的取值范圍，k-mer所在行數為100 0000以內所以我們采用int型（占用4字節）存儲，而

12、其在行的第幾個位置數在100以內，我們則采用char（占用1字節）型存儲，盡可能的縮小了每條索引數據的存儲空間，最終使k支持114。但由上表可以看出，邏輯上k=15也能支持，但設備資源有限，未能實際測試。k=14時，索引建立實際內存消耗為1313924KB=1.2530555GB，與邏輯分析基本一致。如下圖：(三) 索引查詢的算法、計算復雜度及空間復雜度分析1、算法分析索引查詢需要將要查找的k-mer的關鍵碼值求出來，然后直接從哈希表中輸出對應關鍵碼值的位置信息，求關鍵碼值的函數同建立索引過程的函數，不再重復給出。索引查詢代碼如下：2、計算復雜度分析索引查詢的過程中只有求關鍵碼值時需要進行計算

13、，其計算復雜度為：3、空間復雜度分析索引查詢過程用到只一個存關鍵碼值的中間變量，根據（臨時占用存儲空間大小的量度）可知，索引查詢過程中空間復雜度為：(四) 整套索引算法程序在不同k值下內存占用及極限分析k值k-mer種類數建立索引耗時（秒）索引查詢耗時（秒）1400216003640042560.0010510240.0010640960.00807163840.0310865536006801010485768.29011419430433.5580121677721636.0830136710886439.31601426843545643.9470測量上表耗時數

14、據設備參數：CPU：Intel 酷睿i3 3110M2.4GHz雙核心/四線程內存（RAM）：DDR3 1600MHz 8G硬盤：500G 5400轉比對以上兩折線圖不難發現建立索引耗時與k-mer種類數目變化趨勢并不是一致的，原因有兩點，第一點建立索引用事在9秒前幾乎為零因為此算法在確認所有種類k-mer都有對應位置后索引就建立完成不管是否將所有數據都遍歷過，9秒前k-mer種類較少，所以沒有檢索所有數據就已經完成了索引建立；第二點建立索引耗時并沒有跟著k-mer種類指數上升而是放緩，原因是k-mer種類太多，將所有數據都遍歷結束后，有的k-mer也沒有找到與其匹配的位置，所以耗時基本就是遍歷所有數據的時間。(五) 缺陷分析及改進方案1、 缺陷分析建立索引過程中會有一個k-mer與多個位置對應，由于hash表存儲限制發生了沖突，只能返回k-mer的一個位置信息，不能將k-me