这个问题来自 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值和相应数据查询效率。
这道题用哈希怎么解决??求解
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
3条回答 默认 最新
- 知常曰明 2015-05-29 08:21关注
- 1. 设C=0,T=1,G=2,A=3,则一个CTGA串可以转为一个四进制数字。一个k-mer可以转换为k位长的四进制数字。
- 2. 以这个k位的四进制数字作为hash值,生成hashmap,可以快速的搜索.
- 3. 100w个基因序列,每个序列100长度,则总共可以标记的位置有100w*100=1ww<2^32,因此一个32位整数可以存放一个位置信息。
- 4. 假设一个节点为一个位置信息+一个指针信息(8G,64位,8字节)(用链表保存下一个值)即4+8=12字节存放一个位置。因此总位置信息有100w个12字节=1200w个字节<12M
- 5. 1字节可以记录4位四进制数字。1个k长度可以存放于一个k/4(向上取整)的字节数中。
- 5.1. 每个序列都保存,有4^k种可能,即2^2k种可能。总共存放字节(k/4)*2^2k
- 5.2. 用稀疏矩阵保存此哈希表,即最大的可能种树为1ww种k/4字节+一个指针,总计((k/4)+8)*1ww<8G-12M
- 5.3. 用5.1的方法,可知k<14(51539607552)用5.2的方法,100位足够(需要2500000000字节)
- 6.时间复杂度O(1)
- 7.空间复杂度O(n)
- 8.搜索方法是二分查找+hash索引。因此复杂度(log(2,n))
解决 无用评论 打赏 举报