DNA序列的k-mer index问题建模

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

1、队伍信息表队伍基本情况介绍（数学基础，编程基础，队伍基本分工）三名队员均具备数学分析、高等代数、概率论与数理统计、数值分析、常微分方程、离散数学、数学建模、运筹学等课程的数学基础；会使用字处理软件“word”、电子表格“excel”、matlab软件、lingo软件、SAS软件等；具备c语言、Java编程基础。队长负责整理综合所有人就建模题目一起讨论的结果，在建模过程中及时收集整合队员的创新性想法，进行整体分析，统筹建模大局，列出建模步骤，给自己和两名队员分配任务，把握建模进度。一名队员主要负责计算机的运用

2、，应用字处理软件“word”，电子表格“excel”，matlab软件、lingo软件等进行模型的相关制图，并用Java编写程序且运行得出结果。另一名队员具有较好的论文写作能力，按照严格的格式要求，综合三个人的思路和个人建模任务完成的成果，清楚地叙述摘要内容，有条理地的把建立模型、设计算法、求解模型等步骤写在论文中，从而完成本数学建模的论文。DNA序列的k-merindex问题摘要DNA序列片段索引在基础生物学研究和在众多的应用领域，如诊断，生物技术，法医生物学，生物系统学中，有着极其重要的应用价值。本文利

3、用Java软件、Rabin-Karp算法和哈希算法，建立了DNA序列数据索引的数学模型及算法，解决了基因序列数据索引的问题。在保证调用100万条DNA序列完整性、准确性和连续性的同时，设计出查询速度尽量快，所用内存尽量小的数据索引方法，并给出建立索引和使用索引所用的计算复杂度和空间复杂度分析。针对问题1，由于100万条DNA序列数据量庞大，所以本文先将原始数据的字符串reads表示成二进制（A=00，C=01，G=10，T=11），通过编写Java程序读取。再将二进制采用Rabin-Karp算法转化成唯一十

4、进制数字存入哈希表。通过此算法的哈希函数，对给定一个确定的k值，将每条DNA序列分成100-k+1个长度为k的k-mer短序列，把一个k-mer里面所有字符的hash值求和。也就是将一个字符串（模式串）转化成为能够快速进行比较的哈希值。任意给定一个k-mer短序列，将对应的十进制数哈希值在100万条DNA序列中进行索引，返回该短序列所在DNA序列编号和相应序列出现的位置。针对问题2，由顺序算法优化成二分法，将k-mer的所有序列哈希值按照升序排列，对给定的k-mer哈希值x，从第一个DNA序列的中间位置开始

5、比较，如果当前位置等于x，则查找到其中一个并记录下来位置信息，再继续查找；如果x小于当前位置值，则在数列的前半段位置查找；如果x大于当前位置值，则在数列的后半段位置查找；直到找出该条DNA序列全部所求位置信息。再进行第二条、第三条直至100万条DNA序列结束。针对问题3，得出建立索引计算复杂度为。空间复杂度为=。针对问题4，得出使用索引查询的时间复杂度是：。空间复杂度为。针对问题5，通过Java程序的反复运行，得出8G内存下所涉及索引方法所能支持的最大k值为67。在索引程序中使用了hash算法（hash表在

6、JDK中的一个实现就是HashMap）来缓存一些数据，从而提高系统的运行速度。Java使用了有向图的方式进行内存管理，尽管可以消除引用循环的问题，但是效率较低。针对问题6，通过模糊综合评价法对索引方法性能进行评价，并对所建立的模型和求解方法的优缺点给出客观分析。最后，对所建立模型进行实际应用的推广。关键词：数据索引；Java软件；二进制；Rabin-Karp算法；哈希算法；二分法；时空复杂度；Proid索引优化；模糊综合评价法。一、问题的重述与分析1.1问题背景生物信息学是20世纪80年代末，随着人类基因组

7、计划的不断发展，基因序列和蛋白质数据的急速增加，以及信息理论和计算机技术的不断发展而逐渐形成的。在过去的十几年中人类对生物信息学，特别是DNA和人类基因序列的研究取得了长足的发展。海量DNA序列的测试完成和发布使人们可以利用计算机技术对包括DNA、RNA和蛋白质等生物序列进行分析，为生物学家提供更多有价值的信息。而DNA序列库的庞大使得它在运用时遇到困难，本文致力于通过建立DNA序列索引的办法，更快更省空间的完成对目标k-mer序列的查找以及相关首位置的返回工作。 1.2问题提出给定一个DNA序列，这个序列

8、只含有4个字母ATCG，如S=“CTGTACTCTAT”。给定一个整数值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}.通常这些