论文部分内容阅读
大量的高通量实验产生了PB级的生物组学数据,这些组学数据包含了海量的生物分子作用信息。如何从这些组学数据中挖掘出有价值的信息是计算生物学的一个重大挑战。为了研究生物分子间的调控机制,常用的研究方法是将生物分子间的作用关系抽象为一个网络图,然后通过基于图论的数据挖掘方法,从生物分子作用网络中挖掘出生物分子间的调控机制。模体结构是一种被认为包含潜在生物分子调控机制的子图结构,在共调控网络中挖掘共调控网络模体,对研究共调控网络中的生物分子调控机制有重大的意义。相比于蛋白质作用网络、基因调控网络等单一分子类型的调控网络,共调控网络规模更大、节点类型更多。现有的模体发现算法难以高效的处理该类型网络图,所以需要设计一种更加高效的共调控网络模体发现算法。本文的主要研究工作如下:1)为了提升共调控网络模体发现算法的效率,本文将G-trie结构应用于共调控网络模体发现算法,把多种共调控网络模体类型存储于一棵前缀树结构中,通过重用查找过程,提升了子图统计的效率。并通过多线程技术,实现了该算法的并行,进一步提升了共调控网络模体发现算法的效率。为了发现更大规模的共调控网络模体类型,本文设计了一种采样生成候选子图的方法,通过该方法本文最多能发现8个节点的共调控网络模体类型。另外,本文根据共调控网络模体结构在共调控网络中的实例,发现了共调控网络模体的团簇性特征。2)通过采样生成候选子图的方法虽然能查找较大规模的模体类型,但难以查找共调控网络中全部的模体类型。查找共调控网络中全部的模体类型是一个NP难问题,计算量会随着模体规模的增加呈指数增长。为此,本文设计一个基于MapReduce计算模型的共调控网络模体发现算法。该算法解决了以往模体发现算法中迭代依赖问题,以及难以通过MapReduce计算模型精确统计网络图中每个子图出现频率的问题,并且通过多线程并行的方法解决了MapReduce计算模型CPU利用率不足的问题。基于MapReduce计算模型的共调控网络模体发现算法实现了对计算机资源的融合与高效利用,并极大限度的缩短了在共调控网络中查找全部模体类型的时间。