dna序列的k-mer问题

《dna序列的k-mer问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、DNA序列的k-merindex问题摘要在百万条DNA序列中查找的特定的是生物信息处理中一个非常基础且重要的问题。针对这一问题，本文提出了三种索引算法，并对每种算法进行复杂度的分析。最后利用模糊综合评价模型对索引算法的性能做出评价。针对问题一和问题二，本文采用三种编程策略：DNA序列的依次遍历策略、DNA序列整体纵向遍历策略、单条DNA整体遍历策略，并结合计算机MATLAB编程提出了三种算法,之后对每种算法上机测试，统计出算法各自的运行时间和占用的内存空间。结果显示，当处理对象为100万组DNA序列时，随着k值的变化，算法1耗时200秒到

2、300秒，占用300M左右的内存空间；算法2耗时1到6秒，占用250M左右的内存空间；算法3耗时0.9秒到1.5秒，需要800M左右的内存空间。由于算法1的运行时间太长，所以算法2和算法3是符合题意的。针对问题三和问题四，本文对算法2和算法3中建立索引和使用索引查询两方面进行了计算复杂度和空间复杂度的分析。分析结果表明，算法2中使用索引查询的计算复杂度和空间复杂度都小于算法3；由于算法3不需要建立索引库，所以它的建立索引的计算复杂度和空间复杂度都为零，使用索引查询的复杂度均与问题规模呈一次函数关系。针对问题五，本文取k从2到99之间的10

3、个值，统计了方案二和方案三在相应k值下的运行时间，以算法的运行时间评价其在相应k值处的数据查询效率。结果表明，算法2和算法3在给定8G的条件下，均支持所有的k值。算法3的整体运行时间低于算法2，因而算法3的索引效率更高。针对问题六，本文利用模糊综合评价模型来评价索引算法性能（以算法2为例）。首先利用层次分析模型（AHP），确定出题中所给的四个影响因素的权重分别为，模型的评语集为{优，良，差}，之后对其进行模糊综合评价，评价结果矢量，表明该算法的索引性能为优。综上所述，本文针对问题所提出的三种算法，上机测试结果表明，算法2和算法3的运行效率

4、非常高，占用内存很小，在8G内存下均支持所有k值，利用模糊综合评价模型对算法性能评价值为优，具有实际应用价值。关键词：计算复杂度空间复杂度层次分析模糊综合评价1问题重述给定一个DNA序列，这个序列只含有4个字母ATCG，如S=“CTGTACTGTAT”22。给定一个整数值k，从S的第一个位置开始，取一个连续k个字母的短串，称之为（如k=5,则此短串为CTGTA），然后从S的第二个位置，取另一个（如k=5，则此短串为TGTAC），这样直至S的末端，就得一个集合，包含全部。如对序列S来说，所有5-mer为：{CTGTA，TGTAC，GTACT

5、，TACTG，ACTGT，TGTAT}通常这些需要一种数据索引方法，可被后面的操作快速访问。例如，对于来说，当查询CTGTA时，通过这种数据索引方法，可返回其在DNA序列S中的位置。现在以文件形式给定100万个DNA序列，序列编号为1-1000000，每个基因序列长度为100。解答以下问题：1.要求对给定k，给出并实现一种数据索引方法，可返回任意一个所在的DNA序列编号和相应序列中出现的位置。每次建立索引，只需支持一个k值即可，不需要支持全部的k值。2.要求索引一旦建立，查询速度尽量快，所用内存尽量小。3.给出建立索引所用的计算复杂度，和

6、空间复杂度分析。4.给出使用索引查询的计算复杂度，和空间复杂度分析。5.假设内存限制为8G，分析所设计索引方法所能支持的最大k值和相应的数据查询效率。6.按照重要性由高到低排序，将依据以下几点，来评价索引方法性能l索引查询速度l索引内存使用l8G内存下，所能支持k值范围l建立索引时间1问题分析1.1问题一和问题二的分析题目的第一问和第二问要求设计数据索引算法，算法的目的是能够返回任意一个所在的DNA序列编号和在相应序列中出现的位置，要求索引一旦建立，查询速度尽量快，所用内存尽量小。对于这道题而言，可以选用多种编程语言进行代码的编写，编程语

7、言不同，执行起来的效率不同，查询速度也不一样，由于涉及到大型矩阵的处理，决定采用M语言编写程序。针对这一问题，本文提出了下面三种编程方案：第一种方案的想法很简单，它是按行遍历，每一行中逐个判断的索引方法。当给定一个之后，k值也随之确定，找出每一条DNA的所有长度为k的子串，组成一个集合，然后在其中搜索，找到相同的子串，把该位置记录到预先分配的位置矩阵里面，这样便完成了题目的要求。本题中问题的规模是100万，每条DNA的长度为100，按照此方案编写程序，核心语句需要执行将近一亿次，所以算法的执行效率不会很高。第二种方案采用MATLAB向量化

8、编程的思想，它是把100万组DNA序列作为一个整体，按列遍历的索引方法。在给定一个之后，将其复制成100万行1列的矩阵，把它与DNA序列的前k列作比较，如果某几行的DNA序列与给定的22序列一