资源描述：
《关于DNA序列k-merindex问题的改进Hash_函数多线程算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、关于DNA序列^-merindex问题的改进Hash函数多线程算法摘要本文通过字符吊匹配的形式解决了DNA序列的Jt-merindex问题。最简单的方法是字典树，然而这种用空间换时间的算法只能适用于较小的ko我们尝试了KMP算法，这是一种利用需要匹配的DNA序列自身的特点进行查找的算法，其占用内存大约为100MB,单次查找的吋间复杂度为0(壮)(其屮厶为DNA序列长度，N为数据规模)，但是这种算法在用于多次查找时，时间复杂度过高。所以我们釆取了Hash算法，利用4进制数，对固定的k,将长度为k的子序列进行分类，以此建立索引。这种方法对较小的k是适用的，但
2、是对较人的k,由于数值太人导致存储量过人、计算速度太慢，此时可采用按人素数取模的方法来分类。而这乂有可能使许多不同的数放在同一•类屮，所以我们还需要利用另一个大素数将同一类中的数作进一步分离。经过对给定数据的测试，最多只需要用3个大素数就可以对这组DNA序列进行完全分离。经过改进的Hash算法查询搜索的计算复杂度为0(1),查询搜索的时间基本上远小T1ms,建立索引的计算复杂度为0(NL),建立索引的时间平均为8So空间复杂度为0(NL),实际占用内存1GB左右。然后我们分别采用随机生成的DNA模拟数据、将原始DNA序列错位排列两种方法来检验Hash算法
3、的实用性，发现建立索引的时间最大仍不超过12s,所以改进后的Hash算法是一种高效实用的算法。鉴于Hash算法对原始DNA序列使用的内存远低于8GB,采取多线程的方法可以加快建立索引的速度，建立索引的时间降低到原来的2/3左右，占用的内存则增加到原来的2倍左右。同样采用随机牛成的DNA模拟数据和将原始DNA序列错位排列两种方法检验多线程Hash算法，结果表明多线程Hash算法在存储空间不超过8GB的条件下可以冇效地减少建立索引的时间。最后，以DNA序列长度和数据规模作为控制变量进行测试，发现对更大规模的DNA序列，改进后的Hash算法仍然适用。关键词:k
4、-merindex;Hash函数;素数；分类；多线程木文得到国家基础科学人才培养皋金的资助，项目号J1103105一、问题的重述与分析这个问题来自DNA序列的k-merindex问题。给定一个DNA序列，这个系列只含有4个字母ATCG，如S=“CTGTACTGTAT”。给定一个整数值从S的第一个位置开始，取一连续k个字母的短串，称Z为肛mer(如k=5,则此短串为CTGTA),然后从S的第二个位置，取另一^-mer(如k=5,则此短串为TGTAC),这样直至S的末端，就得一个集合，包含全部^-mero对上述序列S来说，所有5-mer为{CTGTA,TGT
5、AC,GTACT,TACTG,ACTGT,TGTAT}通常这些^-mer需一种数据索引方法，可被后面的操作快速访问。例如，对5-mer來说，当查询CTGTA,通过这种数据索引方法，口J返回其在DNA序列S中的位置为{1,6}o^-merindex问题木质上就是一个字符串匹配问题，对于字符串匹配问题一般采用KMP算法[1]和Hash函数[4]来解决。二、符号定义与说明B[i],B(i):DNA片段B的第i个字母B[i.・j],B(i..j):DNA片段B的第i个字母到第j个字母这j・i+l个字母组成的子串Num(B[i]):用数字表示B串的第i个字母，A代
6、表0,T代表1,C代表2,G代表3。三、KMP算法假设给定的DNA片段为B(B是一个长度为k的片段)，将B放在每个DNA的每一位上进行比较，这样一定能找出所有完全匹配上的位置，但是这样做的查询速度明显非常慢。判断片段B是否可以在DNA序列A的第i个位置完全匹配上需要先比较B的第1个字母B⑴与A的第i个字母A⑴是否相同，若相同则比较B⑵与B(i+1),””，一旦不相同可直接判定为匹配失败，如果可以完全匹配上，则会一一直比较到B(k)与A(i+k・l),即需要进行k次计算。给定了100力个DNA序列，口每个序列长度为100,则每个DNA序列有go-£+1=1
7、01-£个位置可以进行匹配，最坏情况下每个位置需要进行k次计算，则对于1个DNA序列就要进行k(101-k)次计算，100万个DNA序烈一共进行了106k(101-k)次计算，当k=50的时候大约要进行25x1(/次计算，按照普通计算机大约1秒1亿次的运算能力，一次查询就需要25s左右的时间，这是不能接受的。当然这是最坏情况下的吋间，比如A=”AAAAAAAAAT”，B=”AAAAT”。给定的数据远好于最坏情况，所以时间不会达到25s,但是我们可以试图优化这个方法。这个方法效率低下的一个原因是检测完一个DNA序列，最坏情况下需要k（101-Jt）次计算，
8、使用KMP算法来匹配可以使这个计算次数降低为与100+R同数量级，即时间复杂度为
