基于K-mer相似性算法的DNA探针设计系统

作     者：崔晓飞 

作者单位：哈尔滨工业大学 

学位级别：硕士

导师姓名：王亚东

授予年度：2016年

学科分类：0710[理学-生物学] 07[理学] 071007[理学-遗传学] 

主      题：DNA芯片 探针设计 全局比对 K-mer相似性算法 

摘      要：随着基因组数据的增长、DNA寡核苷酸合成与芯片技术的进步,寡核苷酸微阵列成为了最广泛使用的高通量分子工具之一。DNA微阵列的检测精度在很大程度上取决于DNA探针设计的好坏,因此,如何设计出具有高特异性、灵敏性以及一致性的探针十分关键。此外,如何提高DNA探针设计效率,在DNA序列数据激增的今天同样重要。本文通过分析DNA探针设计中序列比对问题的特性,提出了针对DNA探针设计的全局比对算法——K-mer相似性算法。该算法能够得到与动态规划算法Needleman-Wunsch同样的结果,但是速度达到前者的60多倍。设计并实现了基于K-mer相似性算法的DNA探针设计系统,为用户提供快速的、高质量的DNA探针设计服务。本文通过分析当前DNA探针设计软件所考虑的影响DNA探针特异性、灵敏性、一致性的因素,综合使用了低复杂度区域过滤、最大连续匹配长度过滤、探针与非目标序列最大相似性限定、DNA探针GC含量过滤、熔解温度Tm值过滤以及自由能?G过滤,以便保证所设计的DNA探针具有高特异性、灵敏性与一致性。除此之外,本系统不仅可以为每个基因序列设计特异探针,而且可以为不存在特异探针的序列设计组探针。在文章最后,我们对DNA探针设计系统进行了测试。首先,分别对DNA探针设计系统的主要模块进行了功能测试,测试结果表明,系统的各个子模块表现良好,基本达到设计要求。然后,对系统的核心算法进行了测试,并与DNA探针设计系统中常用算法进行了比较,结果表明,本系统所采用的算法在保证准确性的同时,具有较高的效率。最后,对系统的总体性能进行了测试,与现存DNA探针设计软件相比,本系统在满足高精度的情况下具有很不错的性能表现,是进行DNA探针设计的良好选择。