DNA序列的k-mer index 问题5 s) F+ \& y; s/ @: p3 ^" C O Z
给定一个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为; \. {4 t s) k: U9 x
K* N7 `8 M7 `6 O; c) R9 d{CTGTA,TGTAC,GTACT,TACTG,ACTGT,TGTAT} 0 w3 H; e$ X" s z+ u6 `8 `1 k2 }通常这些k-mer需一种数据索引方法,可被后面的操作快速访问。例如,对5-mer来说,当查询CTGTA,通过这种数据索引方法,可返回其在DNA序列S中的位置为{1,6}。1 c1 s# [/ v. |' B& N
# Y6 c1 m9 Y. E5 N# U问题, K, I* K3 o% f9 W# d3 x6 D
8 z9 t' n/ c# y8 v. q4 k
现在以文件形式给定 100万个 DNA序列,序列编号为1-1000000,每个基因序列长度为100 。 1 `2 N1 T* S/ j " v; ]) B! {0 r3 j0 M1 y(1)要求对给定k, 给出并实现一种数据索引方法,可返回任意一个k-mer所在的DNA序列编号和相应序列中出现的位置。每次建立索引,只需支持一个k值即可,不需要支持全部k值。 # ~3 D4 H T' H* \3 j* U( C7 k1 J# T3 W$ I1 v- N
(2)要求索引一旦建立,查询速度尽量快,所用内存尽量小。 : F; n: x0 S# B; F) F. P ~# z$ ` |; k7 q! L" `" ~& a* U; c. N5 s(3)给出建立索引所用的计算复杂度,和空间复杂度分析。7 N+ }' R9 e! h4 ^! a
) q2 v% _8 Q9 P9 n. q3 V, b
(4)给出使用索引查询的计算复杂度,和空间复杂度分析。- O) F8 c' v* K