DNA序列的K-mer index问题

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

1、数学建模论文题目：DNA序列的k-merindex问题分析队长姓名：陈智添学院：数学与信息学院联系方法：18826252948队员姓名：方宇靖学院：数学与信息学院联系方法：18826252970队员姓名：张航学院：数学与信息学院联系方法：1598914858515承诺书我们仔细阅读了华南农业大学数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资

2、料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：参赛队员(打印并签名)：1.2.3.2015年____月____日15评阅记录评阅人评分备注成绩：_____________名次：____________获奖等级：____________选拔结果：____________15DNA序列的k-merindex问题分析摘

3、要随生物学与计算机学科的不断发展扩大，DNA序列的k-mer频数统计是生物信息处理过程中的一个基础问题。本文在查阅大量相关文献后，反复运用二维数组进行数据处理，结合哈希算法，我们对固定的k值进行索引的构建后，进行k-mer的查找，并对复杂度进行计算以及对模型进行了评价。针对索引建立的问题，对于固定的k值，用二维数组储存100万行包含100个碱基的DNA序列的信息，把二维数组中的每个元素转化为四进制的序列数后，通过Dev-cpp运算分割出每行所有的k-mer，利用哈希算法把k-mer转化为十进制重新储存到二维数组中

4、，直到100万行碱基序列全部转换成十进制的k-mer储存到二维数组中，实现索引。针对索引使用的问题，建立需搜索的k-mer字符串与十进制数之间的关系，用计算机自动实现，输入要搜索的k-mer字符串，程序自动转换成十进制数到二维数组中，使二维数组返回该十进制数所在的位置，即返回该k-mer在100万行DNA序列中的位置，实现索引的使用。针对数据索引的复杂度分析问题，我们针对建立索引、索引查询，计算出算法的时间复杂度及空间复杂度，从而得出建立索引，索引查询的时间复杂度。通过运算，索引建立时的时间复杂度T（n）=O（n

5、），空间复杂度为O（n）；索引使用时的时间复杂度T（n）=O（n），空间复杂度O（1）。针对索引方法性能的评价，我们从索引查询速度、内存使用、K值范围、索引时间四个方面进行综合评价。我们通过算法输出建立索引所需时间，索引查询所需时间、索引所占用内存。从量化的角度客观评价算法性能。从多次对k值进行试验检索后发现，随着k值的增大，建立索引的时间逐渐增长，由k值为1时的19.87秒逐渐升为为k值为16的199秒；而索引使用的时间基本保持在1秒以内，所占内存保持在320m到380m之间，索引的建立、使用都比较快，占用空间

6、不大。运用二维数组储存、读取DNA序列，简洁直观，结合哈希算法的运用，提升了运算的效率，实现高效快捷操作，并且准确地实现了在大型数据库中快速访问指定碱基片段的目的，查找速度快，效率高，输出界面简洁，为生物科学与计算机科学的发展提供基础。关键词：k-merindex，二维数组，哈希算法，DNA序列15目录摘要i1问题重述12问题分析12.1数据索引建立与使用的分析12.2数据索引的复杂度分析12.3数据索引的评价23模型假设24模型建立与求解24.1建立索引的准备24.2索引的建立34.2.1理论准备34.2.2流

7、程图34.2.3建立索引44.2.3.1读取文本文档44.2.3.2转化整数数组54.2.3.3分割碱基序列64.3索引的使用64.4复杂度74.4.1建立索引所用的计算复杂度，和空间复杂度分析74.4.1.1建立索引时的时间复杂度分析74.4.1.2建立索引时的空间复杂度分析84.4.2使用索引查询时的复杂度分析84.4.2.1索引查询时的时间复杂度分析84.4.2.2索引查询时的空间复杂度分析96K值的最大取值分析97索引的性能评价9参考文献11附录12151问题重述给定一个DNA序列，这个系列只含有4个字母

8、ATCG，S=“CTGTACTGTAT”。给定一个整数值k，从S的第一个位置开始，取一连续k个字母的短串，称之为k-mer（如k=5，则此短串为CTGTA），然后从S的第二个位置，取另一k-mer（如k=5，则此短串为TGTAC），这样直至S的末端，就得一个集合，包含全部k-mer。如对序列S来说，所有5-mer为｛CTGTA，TGTAC，GTACT，TACTG，ACTG