面向顺式调控元件及模块识别的近似序列模式挖掘

随着新的高效实验技术（如DNA测序、基因芯片技术）的出现，各类生物数据急剧增长，生物学相关领域的研究者面临着"数据越来越丰富但知识越来越匮乏"的困境，迫切需要人们提出有效的方法和手段对已有的生物数据进行挖掘。另一方面，目前数据挖掘领域各基本方法的研究已日臻成熟，基于传统事务数据库的基本算法的研究已很难取得突破，需要新的研究动力给予刺激来推动数据挖掘自身的进展，面向生物数据的数据分析和知识获取给数据挖掘研究提出了许多新的机遇和挑战。在分子生物学领域，由于进化上的保守性各种功能相关的基本元件（如DNA序列上的顺式调控元件和模块、选择性剪切位点，SNP数据上的疾病关联等）均表现出"近似序列模式"的特性，本项目主要针对顺式调控元件和模块识别问题，对DNA序列上的"近似序列模式"进行挖掘，在帮助生物学家识别DNA序列中蕴含的基本元件或模块的同时进一步发展数据挖掘的概念和方法。

识别DNA序列上的转录因子识别位点（也称为motif）是理解基因转录调控的关键步骤。本项目面向DNA序列集上的motif识别及组合motif识别问题，研究相关的近似序列模式挖掘算法。取得了以下成果：1)扩展了频繁挖掘算法Apriori，给出了一种利用Apriori下封闭特性、快速挖掘DNA序列集中的近似频繁模式的算法Apriori-Motif，该算法是首个成功利用广度优先策略的motif识别方法，可以在未知motif长度的条件下快速挖掘出DNA序列集中蕴含的最大近似序列模式，即motif及相关位点；对Apriori-Motif方法进行扩展，使之可以用于识别DNA序列集中的组合motif。2）对广泛使用的模式穷举型motif挖掘算法Weeder进行改进，针对Weeder算法压缩搜索空间带来的不能精确性问题和时间复杂度会随着参数q急剧升高的问题，利用改进的suffix tree结构给出了一种精确的、快速发现DNA序列集中蕴含的motif及其相关位点的启发式近似序列模式发现算法SUTMAPSTA，并建立了相应的网络版应用工具。3）利用复杂网络(G, E)图模型，将DNA序列集上的motif识别问题转化为网络上的稠密子图发现问题，利用快速的复杂网络社区发现算法及贪心策略给出了一种快速、精准的motif识别算法，该方法在原核基因启动子数据集RegulonDB及小鼠12组胚肝干细胞转录因子全基因组ChIP-Seq数据集上取得了非常好的识别效果。4）针对现有motif发现方法对大规模全基因组转录因子识别位点深度测序数据集ChIP-Seq及ChIP-exo可扩展性差的问题，给出了一种基于取样策略及全数据集再发现的motif识别策略，给出了基于该策略的大规模ChIP数据集motif识别算法FMotifEnum，该算法在4组人类转录因子ChIP-Seq数据集、12组小鼠胚肝干细胞转录因子ChIP-Seq数据集及4组酵母和1组人的ChIP-exo数据集上取得了非常好的效果。5) 对TFBSgroup进行改进，给出了一种结合DAN序列保守性和蛋白/DNA结合Potential的、新的motif识别方法，初步实验取得了较好效果。6) 结合生物信息学和数据挖掘当前的研究热点，积极寻找新的研究增长点，给出了若干复杂网络社区发现、重叠社区发现算法，并在生物网络及社会网络分析中取得了较好的效果。