文档介绍：关于 DNA 序列 k-mer index 问题的改进 Hash 函数多线程算法
黄恒意 1 许仁杰 1 张艺辉 1
指导教师:数模教练组 1,2
1 复旦大学数学科学学院,上海 200433
2 上海市现代应用数学重点实验室,上海 200433
摘 要
本文通过字符串匹配的形式解决了 DNA 序列的 k-mer index 问题。最简单的方法是字典树,然而这种用空间换时间的算法只能适用于较小的 k。我们尝试了 KMP 算法,这是一种利用需要匹配的 DNA 序列自身的特点进
行查找的算法,其占用内存大约为 100MB,单次查找的时间复杂度为 O(NL) (其中 L 为 DNA 序列长度,N 为数据规模),但是这种算法在用于多次查找时,时间复杂度过高。
所以我们采取了 Hash 算法,利用 4 进制数,对固定的 k,将长度为 k 的子序列进行分类,以此建立索引。这种方法对较小的 k 是适用的,但是对较大的 k, 由于数值太大导致存储量过大、计算速度太慢,此时可采用按大素数取模的方法来分类。而这又有可能使许多不同的数放在同一类中,所以我们还需要利用另一个大素数将同一类中的数作进一步分离。经过对给定数据的测试,最多只需要用 3 个大素数就可以对这组 DNA 序列进行完全分离。经过改进的 Hash 算法查询搜索的计算复杂度为 O(1),查询搜索的时间基本上远小于 1 ms,建立索引的计算复杂度为 O(NL),建立索引的时间平均为 8 s。空间复杂度为 O(NL),实际占用内存 1GB 左右。然后我们分别采用随机生成的 DNA 模拟数据、将原始 DNA 序列错位排列两种方法来检验 Hash 算法的实用性,发现建立索引的时间最大仍不超过 12 s,所以改进后的 Hash 算法是一种高效实用的算法。
鉴于 Hash 算法对原始 DNA 序列使用的内存远低于 8GB,采取多线程的方法可以加快建立索引的速度,建立索引的时间降低到原来的 2/3 左右,占用的内存则增加到原来的 2 倍左右。同样采用随机生成的 DNA 模拟数据和将原始 DNA 序列错位排列两种方法检验多线程 Hash 算法,结果表明多线程 Hash 算法在存储空间不超过 8GB 的条件下可以有效地减少建立索引的时间。
最后,以 DNA 序列长度和数据规模作为控制变量进行测试,发现对更大规模的 DNA 序列,改进后的 Hash 算法仍然适用。
关键词:k-mer index;Hash 函数;素数;分类;多线程
本文得到国家基础科学人才培养基金的资助,项目号 J1103105
一、问题的重述与分析
这个问题来自 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}。
k-mer index 问题本质上就是一个字符串匹配问题,对于字符串匹配问题一般采用 KMP 算法[1]和 Hash 函数[4]来解决。
二、符号定义与说明
B[i],B(i): DNA 片段 B 的第 i 个字母
B[i..j],B(i..j):DNA 片段 B 的第 i 个字母到第 j 个字母这 j-i+1 个字母组成的子串
Num(B[i]): 用数字表示 B 串的第 i 个字母,A 代表 0,T 代表 1,C 代表
2,G 代表 3。
三、 KMP 算法
假设给定的 DNA 片段为 B(B 是一个长度为 k 的片段),将 B 放在每个 DNA 的每一位上进行比较,这样一定能找出所有完全匹配上的位置,但是这样做的查询速度明显非常慢。
判断片段 B 是否可以在 DNA 序列 A 的第 i 个位置完全匹配上需要先比较 B 的第 1 个字母 B(1)与 A 的第 i 个字母 A(i)是否相同,若相同则比较 B(2)与 B(i+1),„„,一旦不相同可直接判定为匹配失败,如果可以完全匹配上,则会一直比较到 B(k)与 A(i+k-1),即需要进行 k 次计算。
给定了 100 万个 DNA