论文部分内容阅读
模体发现是在给定的序列集合中找到过表达的序列模式,对生物序列中定位有意义的序列片断起着非常重要的作用,比如在DNA序列中识别转录因子结合位点和在蛋白质序列中识别短的线性模体。转录因子控制着靶基因的转录起始和转录效率。基因上游与转录因子相结合的特定DNA序列称为转录因子结合位点,对它的精确定位有助于理解基因的表达调控机制。线性模体是蛋白质序列中具有特定功能的序列片断,负责着蛋白质交互的调节,对许多调控过程都起着重要的作用,比如信号传导、蛋白质运输和翻译后修饰。植入(l,d)模体发现(Planted(l,d)motif search,PMS)是模体发现领域中一个广为接受的问题模型,求解PMS是计算机科学和生物信息学中的挑战问题。模体是未知的,并以退化的形式出现在序列中,也即模体实例(模体的出现)并不是模体的一份精确拷贝,而是与模体在某些位置上存在着差异。相对于DNA启动子序列,蛋白质序列和染色质免疫共沉淀测序(Chromatin Immunoprecipitation-Sequencing,ChIP-seq)序列又分别从大字符集和大数据集方面对求解PMS带来了新的挑战。本论文针对不同类型生物序列数据集的特点以及现有算法的不足,提出新的模体发现算法,以进一步提高模体发现的时间性能和识别准确率。具体工作概括为以下四个部分:第一部分研究了DNA启动子序列中(l,d)模体发现的精确算法。针对现有识别(l,d)模体的精确算法存在的计算量大或存储空间高、难以识别微弱信号模体等问题,提出了一种新的基于模式驱动的精确算法PairMotif:分析和描述了如何由一对l-mer(长为l的字符串)生成候选模体;通过估计候选模体的数量,从输入序列集中选择参考序列,能有效地减少候选模体的数量;设计了两种过滤待扫描l-mer的规则,有助于加速模体验证。相对于之前的几个精确算法,PairMotif需要更少的存储空间,能够更快速地求解大多数PMS问题实例,而且能够在10个小时内求解其它算法难以求解的(27,9)问题实例。第二部分研究了DNA启动子序列中(l,d)模体发现的近似算法。鉴于现有的模体发现算法要么花费巨量的时间输出最优的结果,要么在短时间内完成计算但常常陷入局部最优,提出了一种新的基于模式驱动的近似算法PairMotif+:依据概率分析和统计的方法,从输入序列中获取了若干l-mer对,使得其中含有一个或多个模体实例对;设计了一种高准确率的近似求精l-mer对的策略,避免了大部分候选模体的验证。PairMotif+能够在普通PC机上于1小时内求解各种PMS问题实例,并且相对于主流的近似算法(MEME、AlignACE和VINE)具有更好的识别准确率。第三部分研究了大字符集(蛋白质序列)上的模体发现问题。针对现有的模体stem搜索算法存在的stem表示不精确、通配符冗余、搜索效率低等问题,进行了如下工作:建立了一种基于正则表达式的stem表示方式,使stem的表示更为精确;提出了一种生成候选stem的方法,使得stem中不含冗余的通配符;结合stem表示和stem生成方法,提出了一种高效的stem搜索算法StemFinder,比现有算法具有更高的搜索效率,并且输出了更少的能够覆盖所有(l,d)模体的stem。第四部分研究了大数据集(ChIP-seq数据集)上的模体发现问题。鉴于已有的模体发现算法难以高效地处理完整的ChIP-seq数据集,提出了一种新的基于词频统计的模体发现算法MCES:通过挖掘和合并出现频率较高的子串进行模体预测;为了处理更大的数据集,设计了挖掘子串的基于MapReduce的分布式方案。MCES能够高效且有效地处理含有数千至数百万条序列的数据集,比现有的(l,d)模体发现算法的执行速度要快得多;能够识别未知长度的模体,而且比同是基于词频统计的CisFinder算法具有更好的识别准确率。