2015年“深圳杯”數學建模夏令營-B題：DNA序列的k-mer index 問題

感受總結：這是第1次參加數學建模，貌似往年建模都是給大2大3做的，但幾年我們大1的熱忱都很高，我也糊里胡涂地被數學學院的拉去組隊了，說來組隊也坑，不想多說，由于最后選了這個算法題，隊友連C語言都沒學，所以全部比賽從算法到論文全是我1人完成，整了4天加1個通宵，累得不行，最后弄出來的還是很爛。不過學到了經驗是真的，并且也讓我對哈希算法懂了1點，畢竟啥也沒干這4天1直就圍繞哈希在研究。

經驗：1、組隊我認為應當2個計算機專業、1個數學專業的就能夠了。

2、頁數1定要多，最少20頁吧，而且內容逼格1定要高。

3、在開始之前要多搜集相干資料，確保最初方向的準確性。

知識方面：1、主要是對哈希算法有了深入了解，知道了其索引原理并在這次比賽進行了簡單利用。

2、哈希在很多方面都有利用，比如破解密碼等，可以大大提高效力，這也是我們常說的字典技術。

還有好多就不說了，把我猥瑣的建模處女座獻出。

題目：

2015年“深圳杯”數學建模夏令營

B題：DNA序列的k-mer index 問題

這個問題來自 DNA序列的k-mer index問題。

給定1個DNA序列，這個系列只含有4個字母ATCG，如 S =“CTGTACTGTAT”。給定1個整數值k，從S的第1個位置開始，取1連續k個字母的短串，稱之為k-mer（如k= 5，則此短串為CTGTA）， 然后從S的第2個位置， 取另外一k-mer（如k= 5，則此短串為TGTAC），這樣直至S的末端，就得1個集合，包括全部k-mer。 如對序列S來講，所有5-mer為

｛CTGTA，TGTAC，GTACT，TACTG，ACTGT，TGTAT｝

通常這些k-mer需1種數據索引方法，可被后面的操作快速訪問。例如，對5-mer來講，當查詢CTGTA，通過這類數據索引方法，可返回其在DNA序列S中的位置為｛1，6｝。

問題

現在以文件情勢給定 100萬個 DNA序列，序列編號為1⑴000000，每一個基因序列長度為100 。

（1）要求對給定k， 給出并實現1種數據索引方法，可返回任意1個k-mer所在的DNA序列編號和相應序列中出現的位置。每次建立索引，只需支持1個k值便可，不需要支持全部k值。

（2）要求索引1旦建立，查詢速度盡可能快，所用內存盡可能小。

（3）給出建立索引所用的計算復雜度，和空間復雜度分析。

（4）給出使用索引查詢的計算復雜度，和空間復雜度分析。

（5）假定內存限制為8G，分析所設計索引方法所能支持的最大k值和相應數據查詢效力。

（6）按重要性由高到低排列，將根據以下幾點，來評價索引方法性能

?        索引查詢速度

?        索引內存使用

?        8G內存下，所能支持的k值范圍

?        建立索引時間

論文及附件下載地址：http://pan.baidu.com/s/1i37YHcL

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈