- 在线时间
- 0 小时
- 最后登录
- 2015-8-18
- 注册时间
- 2015-8-18
- 听众数
- 7
- 收听数
- 0
- 能力
- 0 分
- 体力
- 4 点
- 威望
- 0 点
- 阅读权限
- 10
- 积分
- 2
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 2
- 主题
- 1
- 精华
- 0
- 分享
- 0
- 好友
- 2
升级   40% 该用户从未签到
 |
DNA序列的k-mer index 问题) C: @4 [7 @& r9 @2 f. o8 t4 l
给定一个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为! e, _9 s% K" P+ \' H/ C* ^
. q8 N' q U- q& a{CTGTA,TGTAC,GTACT,TACTG,ACTGT,TGTAT}6 M3 w3 k! M) I( l) i H3 _1 U
4 O- p, [' x M: ?9 J4 ]! D/ U通常这些k-mer需一种数据索引方法,可被后面的操作快速访问。例如,对5-mer来说,当查询CTGTA,通过这种数据索引方法,可返回其在DNA序列S中的位置为{1,6}。
2 y: |, }7 K$ A, E9 A6 N0 f2 ~3 l, r; h2 g' L8 X
问题
8 }+ k/ r2 n( ]" O8 R2 m" `
; {4 k: b" a! c现在以文件形式给定 100万个 DNA序列,序列编号为1-1000000,每个基因序列长度为100 。
- T# F8 k9 `# m8 o. Y$ {+ |$ Q$ N1 _
(1)要求对给定k, 给出并实现一种数据索引方法,可返回任意一个k-mer所在的DNA序列编号和相应序列中出现的位置。每次建立索引,只需支持一个k值即可,不需要支持全部k值。
( x" k8 j u5 m% k5 W; x5 |8 D& q i
(2)要求索引一旦建立,查询速度尽量快,所用内存尽量小。. g9 U7 t3 x# F' |9 N+ R# a
$ u5 Y6 x# K" ?* S
(3)给出建立索引所用的计算复杂度,和空间复杂度分析。
! t. z2 m& \' z; p& c9 @, V8 U; x- H1 S5 s, e0 N/ E
(4)给出使用索引查询的计算复杂度,和空间复杂度分析。
4 J; j' t# `! V( e) C
4 C/ a: D4 J) U1 k2 t(5)假设内存限制为8G,分析所设计索引方法所能支持的最大k值和相应数据查询效率。+ G' ?. f0 Y4 x; i0 u- k
(6)按重要性由高到低排列,将依据以下几点,来评价索引方法性能
y6 L/ o% s, h5 `( \) s1 I& B, t+ `" K, v+ o8 u
希望好心人帮忙# c6 M+ n6 O; O. y5 h
|
zan
|