基于词频统计的DNA序列大数据集模体发现算法研究

摘要

在DNA序列中识别保守的模式，即模体发现，主要用于在DNA序列中定位转录因子结合位点，对研究基因的表达调控有着重要的意义。此外，高等真核生物中基因的表达往往会受到多个转录因子的共同调控，识别相应的转录因子结合位点可以抽象成结构模体发现。下一代基因测序技术(Next-Generation Sequencing，NGS)使得当前可以在基因组水平上定位转录因子结合位点，但是产生的DNA序列大数据集远大于传统的启动子序列数据集(小数据集)，为求解模体发现带来了新的挑战。 模体发现可以形式化地定义为quorum植入(l,d)模体搜索(quorum Planted(l,d)Motif Search,qPMS)问题。结构模体由存在可变长度间隔的多个(l,d)模体组成。相对于传统的小数据集，DNA序列大数据集中含有的模体出现较多，由于模体的出现之间较为相似，那么大数据集中出现频次较高的子串可能是模体的出现。基于此，本文开展了两个基于词频统计的模体发现算法的研究工作。 第一部分研究通过样本序列选择加速现有qPMS算法。首先，分析了输入序列的数量t和含有模体出现的序列占所有序列的比例q对qPMS算法时间性能的影响，发现一个大的t或一个小的q将造成更大的时间开销。那么，为提升现有qPMS算法的时间性能，可以从大的输入序列中选择一个对应小的t和大的q的样本序列集。在此基础上，提出了一个样本序列选择算法SamSelect，采用词频统计得到输入序列中出现频次较高的子串，再通过高频子串聚类得到样本序列集。模拟和真实数据上的实验结果均表明，SamSelect只需很短的时间便能选出样本序列集，且qPMS算法运行于样本序列集后能以快得多的速度找出植入的或真实的模体。 第二部分研究DNA序列大数据集结构模体发现算法。由于结构模体中单模体及其片段会在大数据集中多次出现，挖掘这些出现频次较高的子串，再利用结构模体模板处理高频子串可以高效且有效地搜索结构模体。在此基础上，提出了一种基于词频统计的结构模体发现算法SMS。算法首先根据各个单模体的l和d值自适应选取w和k值，并统计输入序列中所有w-mer的k失配计数；然后根据结构模体模板采用滑动窗口方法扫描输入序列获取峰值子串，期望峰值子串能够覆盖结构模体实例；最后通过峰值子串比对得到结构模体。在多组数据集上与现有算法进行了比较，结果表明SMS算法在保持识别准确率相近的前提下，能够更快地找到结构模体。

目录

第一个书签之前