数学建模社区-数学中国
标题:
2015深圳杯b题，求教
[打印本页]
作者:
丸子的建模
时间:
2015-5-17 17:09
标题:
2015深圳杯b题，求教
给定一个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为
7 Q5 n$ [; i' v. i
s# }1 x7 ?' S$ L, R4 h9 l
｛CTGTA，TGTAC，GTACT，TACTG，ACTGT，TGTAT｝
! |, g! d7 {' b1 v3 J# _
- M+ T! x5 _( h; P: Z
通常这些k-mer需一种数据索引方法，可被后面的操作快速访问。例如，对5-mer来说，当查询CTGTA，通过这种数据索引方法，可返回其在DNA序列S中的位置为｛1，6｝。
% H, ]" N# o# o8 r1 k
2 q; d# z" u5 h r8 x
问题
1 }& `) j& W% q7 o1 m1 `4 o
% m. Y: x1 R, D6 a
现在以文件形式给定 100万个 DNA序列，序列编号为1-1000000，每个基因序列长度为100 。
: R, T0 r: G5 ~6 a3 H' f. a! X
0 v2 r8 m" @8 d8 e& L
（1）要求对给定k， 给出并实现一种数据索引方法，可返回任意一个k-mer所在的DNA序列编号和相应序列中出现的位置。每次建立索引，只需支持一个k值即可，不需要支持全部k值。
4 X$ F }+ I5 p$ f7 I2 L! O! S, `
& M) Y" A2 V# B3 I. |
（2）要求索引一旦建立，查询速度尽量快，所用内存尽量小。
3 I) l( l" `3 M4 G
2 P- H% R1 ~* R: a
（3）给出建立索引所用的计算复杂度，和空间复杂度分析。
9 x% c& n1 d& m/ [) H- x- S% X
8 J( `+ G- E% n% c- s/ S0 v! L+ |, Z
（4）给出使用索引查询的计算复杂度，和空间复杂度分析。
! }+ t0 X* B' F4 R) O# ^
* D8 K4 C" e" u" k) c5 s
（5）假设内存限制为8G，分析所设计索引方法所能支持的最大k值和相应数据查询效率。
& R" K* B' |1 A$ a) g
（6）按重要性由高到低排列，将依据以下几点，来评价索引方法性能
. B/ s T8 S$ @! f6 I' W
给我有关程序和代码，如果可以帮忙建个数学模型，谢谢
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5