2 sungaochao sungaochao 于 2015.05.29 15:25 提问

这道题用哈希怎么解决??求解

这个问题来自 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值和相应数据查询效率。

3个回答

gamefinity
gamefinity   Rxr 2015.05.29 16: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))
gamefinity
gamefinity 回复qian言wan语: 不是有代码了嘛。您就行行好,这东东别让我写了,写一遍得死多少脑细胞啊。@caozhy提供的网页里有源代码,去抄一遍交差吧
2 年多之前 回复
sungaochao
sungaochao 用c语言怎么写啊
2 年多之前 回复
caozhy
caozhy   Ds   Rxr 2015.05.29 18:26
sungaochao
sungaochao   2015.05.30 15:05

能给写个c代码吗??
谢谢

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!