生物网络中概率模体发现算法的研究

摘要

随着生物技术的发展，产生了大量的生物网络数据。如何从这些生物网络数据中发现一些具有生物功能的拓扑结构成为生物信息学的一个研究热点。大量实验表明，模体是这些生物网络中有生物功能的基本模块。目前模体的研究主要侧重于识别精确模体，事实上，由于目前的测量手段的不准确性或者实验方法的不完整性，这些已经得到的生物网络数据往往是有噪声的或者不完整的。另外，生命过程本身也是一个动态变化的过程，因此概率模体更能体现生命的动态变化过程和生物网络的功能意义。概率模体发现算法的主要瓶颈在于非树形子图的挖掘和在得分函数最大化的过程中得分函数值的计算。其中后者需要进行多图比对，并且需要建立在任意两个子图的两两最小错配的基础上。当要发现的概率模体规模增大的时候，计算任意两个子图的最小错配所需时间也急剧增长。
　　 因此，论文的主要工作如下：
　　 1.论文首先提出了一种基于划分的非树形子图搜索算法，与已有的非树形子图搜索算法相比，具有更高的时间效率。
　　 2.论文利用子图同构是子图最小错配的特殊化，求解子图同构比求解子图的最小错配更有效率这一优势，提出先利用同构来对子图分组，属于同一个同构组的任意两个子图其最小错配为零，之后再对不同构的子图进行最小错配的求解。这样在减少了求解任意两个子图最小错配时间的同时，也缩小了之后利用智能优化算法对得分函数求解的解空间。
　　 3.论文将一种基于模拟退火算法和遗传算法的混合算法应用于得分函数的求解过程，这与已有的只利用模拟退火算法进行求解相比，能以相对较快的收敛速度收敛到一个较优的解。
　　 4.论文将子图抽样方法应用于概率模体的识别，进一步提高了概率模体发现的效率。
　　 本文在大肠杆菌基因调控网络中进行了实验验证，实验结果表明上述提出的方法可以有效地提高概率模体发现的效率。