基于c程序的dna序列的k-mer_index数据查找

《基于c程序的dna序列的k-mer_index数据查找》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、论文题目：基于C程序的DNA序列的k-merindex数据查找姓名学院年级专业学号联系电话数学分析高等代数高等数学线性代数概率统计数学实验数学模型CET4CET6电气工程学院2013级电气工程及其自动化\918996\560电气工程学院2013级电气工程及其自动化\918885\578540电气工程学院2013级电气工程及其自动化\858989\55423基于C程序的DNA序列的k-merindex数据查找摘要DNA是生命体的基本遗传物质，其组成和序列变化创造了形形色色的生命世界。快速、准确

2、地获取生物体的遗传信息对于生命科学的研究具有重要意义[1]。现需要给定一种数据索引方法，利用一种查询算法查询百万条序列中是否存在相应的片段，如果存在，则输出相应片段所在的位置。针对问题一，运用karp-Rabin算法，在C程序环境下编写字符串匹配算法。具体做法是将碱基序列映射成四进制的数串，对给定的k，构造合适的哈希函数，将四进制数串内每个长度为k的子数串译为唯一的十进制数，按顺序放进索引数组（哈希表）。查找相同的字符串等价于判断相应的hash值是否相同。此法可以大大提高建立索引和查询的时间。针对问题二，对

3、不同k值经过大量多次的尝试，一般来说建立索引约10秒，查询约0.3秒（VisualC++6.0运行环境）。针对问题三和问题四，本算法使用for循环函数，先计算出建立索引与使用索引的算法中每一个语句的执行次数，然后再相加，最后依据去低阶项，去掉常数项，去掉高阶项的常参的原则得到时间复杂度。然后根据算法临时存储的空间大小来计算空间复杂度，观察有无临时存储大小以及临时存储大小与输入变量的关系。经分析，本算法在建立索引时的时间复杂度为O（n*m），空间复杂度为O（n）；在使用索引时的时间复杂度为O（n*m），空间复

4、杂度为O（1）。针对问题五，首先分析了整形数据最大值的限制，k最大只能取14。为了扩展k的最大值，我们提出将字符串分成几个不相交的完备的字串，其长度不超过14，分别比较每一个字串，然后对结果取交集。并给出了这种方法下所需要的内存与k的关系，得出理论上可以在8G的内存下支持所有k值的查找。关键词：DNA数据索引查询算法算法复杂度karp-Rabin哈希函数C程序字符串匹配23一、问题重述这个问题来自DNA序列的k-merindex问题。给定一个DNA序列，这个系列只含有4个字母ATCG，如S=“CTGTACT

5、GTAT”。给定一个整数值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中的

6、位置为｛1，6｝。问题现在以文件形式给定100万个DNA序列，序列编号为1-，每个基因序列长度为100。（1）要求对给定k，给出并实现一种数据索引方法，可返回任意一个k-mer所在的DNA序列编号和相应序列中出现的位置。每次建立索引，只需支持一个k值即可，不需要支持全部k值。（2）要求索引一旦建立，查询速度尽量快，所用内存尽量小。（3）给出建立索引所用的计算复杂度，和空间复杂度分析。（4）给出使用索引查询的计算复杂度，和空间复杂度分析。（5）假设内存限制为8G，分析所设计索引方法所能支持的最大k值和相应数据

7、查询效率。（6）按重要性由高到低排列，将依据以下几点，来评价索引方法性能•索引查询速度•索引内存使用•8G内存下，所能支持的k值范围•建立索引时间23二、问题分析针对问题一，要求对给定k，给出并实现一种数据索引方法，可返回任意一个k-mer所在的DNA序列编号和相应序列中出现的位置。以及每次建立索引，只需支持一个k值即可，不需要支持全部k值。首先利用C程序的中的fp文件读取函数将目标文件中的一亿个单字符数据读出，用于建立数据库，由于给定的是100万个DNA序列，每个基因序列长度为100。而C程序中静态数组的

8、范围限制远远小于100万，于是定义全局变量建立动态数组，动态分配储存空间，即建立行为100万，列为100的[×100]的动态数组，也就是索引的建立过程。采用karp-Rabin算法[2]，可令A=0,C=1,G=2,T=3，将碱基序列映射成一个四进制数串。对于给定的K，可以构造这样一个集合，即这个集合囊括了四进制数串中所有长度为K的子数串。构造相应的哈希函数，将每个四进制子数串转换成唯一的十进制数字。待查kmer