DNA序列的k-mer index 问题

DNA序列的k-mer index 问题

给定一个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需一种数据索引方法，可被后面的操作快速访问。例如，对5-mer来说，当查询CTGTA，通过这种数据索引方法，可返回其在DNA序列S中的位置为｛1，6｝。
问题
现在以文件形式给定 100万个 DNA序列，序列编号为1-1000000，每个基因序列长度为100 。
（1）要求对给定k， 给出并实现一种数据索引方法，可返回任意一个k-mer所在的DNA序列编号和相应序列中出现的位置。每次建立索引，只需支持一个k值即可，不需要支持全部k值。
（2）要求索引一旦建立，查询速度尽量快，所用内存尽量小。
（3）给出建立索引所用的计算复杂度，和空间复杂度分析。
（4）给出使用索引查询的计算复杂度，和空间复杂度分析。
（5）假设内存限制为8G，分析所设计索引方法所能支持的最大k值和相应数据查询效率。
（6）按重要性由高到低排列，将依据以下几点，来评价索引方法性能。

1、首先采用命A=0,C=1,G=2,T=3. 就相当于4进制数字，然后采用karp-Rabin算法转换成唯一十进制数字。由于用此算法的哈希函数为：hash(value)=value*(4^(k-q-1));
value是该字符对应的值，k是kmer长度,q是此字符在字符串的位置范围在[0-(q-1)]。然后把一个kmer里面所有字符的hash值求和就行了。
2、那么很容易看出来，对于连续的下一个Kmer，就有推理公式了 hashNew=addValue+(hashOld-deleteValue*(4^(k-1)))*4; hashNew就是往右平移一个字符的kmer hash值，hashOld就是平移之前的值，addValue就是平移后右边多的一个字符，deleteValue就是平移后左边少的一个字符。这样整个hash表建立的时间复杂度约为O（m+k）,m是整个文本长度。
3、由于kmer长度如果过长，其hash值过大，会造成内存不够溢出的现象，所以kmer内部定死为10 。那么问题就来了，如何应对不同的kmer值。分三种情况。
第一种：q>10
这种可以将kmer以10为单位，将hash表中对应值取出，然后对结果进行分析，这边分析方法为建立两个数组一个二维数组unionName储存位置关系，一个一维数组unionScore,计数用。 思路就是首先第一轮初始化unionName[Name][Pos]全部赋值Pos 并初始化unionScore，然后再第二轮匹配如果unionName[Name][Pos-cycle]=Pos-1则将其赋值为当前Pos，cycle为当前循环次数。并将当前循环数存入unionScore[NAME]中。最后当unionScore[NAME]值也就是循环数为k-1，即我们需要的交集了。
第二种：q=10
直接求出hash值，取出相应的值即可。
第三种：q<10
可以用前缀种子+后缀种子交集产生。
前缀种子：在字符串后面补字符直到长度等于K，这个很容易看出来 最小是全补A，最大是全补T，然后将最小值到最大值之间的hash值即为所求。
后缀种子：后缀种子和前缀种子不同就是在字符串左边补齐字符。所以此时需要进行变换。只要对前置种子产生的值变化下就行了。(preValue-minValue)*(4^(K-q))+hash(p) 。其中preValue就是对应的前置种子的hash值，minValue就是前置种子中最小值也就是全补A的情况，hash（p）就是字符串长度为p时候的hash值。
交集就是先求后缀种子所有的值，再加上 前缀种子中起始位置在[0-(k-1)]中的值。

滚犊子，自己解决

20分就给你来个答案？想太多了吧追问的确

数学建模B题，参考http://www.madio.net/forum-1670-1.html