论文部分内容阅读
本文主要研究的是立方体图的可靠性及其在蛋白质相互作用网络中的应用。立方体图是由节点和边组成的几何结构,任何网络可被抽象为一个立方体图。随着网络规模的增大,在网络中将不可避免的出现故障节点,那么如何快速、准确地诊断故障节点并将其修复或替换成为立方体图可靠性中的重要部分,另外立方体图的容错性也是衡量立方体图可靠性的一项重要指标。此外作为生物体内所有蛋白质间的相互作用组成的蛋白质相互作用网络,在该网络中对功能模块进行检测为理解生命现象的一个突破口,同时也是检测失效功能模块进而维护蛋白质相互作用网络的可靠性的基础。本文结合立方体图可靠性研究的一些方法和思路研究了蛋白质互作网络中的功能模块检测问题。
首先,本文从容错性能方面分析了立方体图的可靠性,外连通度为刻画立方体图容错能力的重要指标,外连通度保证了立方体图不连通后的每个分支中节点的数目是不平凡的,本文研究了加强超立方体的{1,2,3}-外连通度。同时运用公共邻居的证明过程也为蛋白质互作网络中功能模块的检测算法的设计提供了思路。
然后,本文从故障诊断性能方面分析了立方体图的可靠性,在立方体图中节点发生故障时,我们需要快速准确地诊断出故障节点,然后将故障节点修复或者将其替换为无故障节点。(t,k)-诊断是一种悲观诊断策略,它指的是在故障节点数目不大于t的前提条件下,每次迭代至少可以诊断出的故障节点数目为k个,在下次迭代前对已诊断出的故障节点修复或者更换为无故障节点。这样可以保证立方体图的可靠性,这种诊断策略是一种较高效的方法。本文研究了在PMC(Preparata,Metze和Chien)模型下洗牌立方体的(t,k)-诊断算法和(t,k)-诊断度。另外,(t,k)-诊断策略以及算法也可进一步用于未来蛋白质相互作用网络中失效功能模块的检测。
最后,本文结合立方体图可靠性研究的一些方法和思路提出了一种新的功能模块检测算法,首先利用立方体图的概念将蛋白质相互作用网络抽象为一个无向图,然后基于证明外连通度使用的公共邻居思想给出了基于公共邻居的解的表示方法,在此基础上我们提出了一个基于改进的粒子群算法和多目标优化的功能模块检测方法(Multi-Objective Particle Swarm Optimization-Functional Modules Detection,简称MOPSO-FMD)。其中采用KKM(Kernel K-Means)和RC(Ratio Cut)作为目标函数,使其最小化。粒子群优化算法的创新之处在于改变了粒子的运动策略。最后在真实蛋白质相互作用网络做了算法对比实验,实验结果表明提出的算法不仅有明显的性能优势,而且能够更加准确、有效地检测功能模块。这也为未来检测失效功能模块进而维护蛋白质相互作用的可靠性奠定了基础。
首先,本文从容错性能方面分析了立方体图的可靠性,外连通度为刻画立方体图容错能力的重要指标,外连通度保证了立方体图不连通后的每个分支中节点的数目是不平凡的,本文研究了加强超立方体的{1,2,3}-外连通度。同时运用公共邻居的证明过程也为蛋白质互作网络中功能模块的检测算法的设计提供了思路。
然后,本文从故障诊断性能方面分析了立方体图的可靠性,在立方体图中节点发生故障时,我们需要快速准确地诊断出故障节点,然后将故障节点修复或者将其替换为无故障节点。(t,k)-诊断是一种悲观诊断策略,它指的是在故障节点数目不大于t的前提条件下,每次迭代至少可以诊断出的故障节点数目为k个,在下次迭代前对已诊断出的故障节点修复或者更换为无故障节点。这样可以保证立方体图的可靠性,这种诊断策略是一种较高效的方法。本文研究了在PMC(Preparata,Metze和Chien)模型下洗牌立方体的(t,k)-诊断算法和(t,k)-诊断度。另外,(t,k)-诊断策略以及算法也可进一步用于未来蛋白质相互作用网络中失效功能模块的检测。
最后,本文结合立方体图可靠性研究的一些方法和思路提出了一种新的功能模块检测算法,首先利用立方体图的概念将蛋白质相互作用网络抽象为一个无向图,然后基于证明外连通度使用的公共邻居思想给出了基于公共邻居的解的表示方法,在此基础上我们提出了一个基于改进的粒子群算法和多目标优化的功能模块检测方法(Multi-Objective Particle Swarm Optimization-Functional Modules Detection,简称MOPSO-FMD)。其中采用KKM(Kernel K-Means)和RC(Ratio Cut)作为目标函数,使其最小化。粒子群优化算法的创新之处在于改变了粒子的运动策略。最后在真实蛋白质相互作用网络做了算法对比实验,实验结果表明提出的算法不仅有明显的性能优势,而且能够更加准确、有效地检测功能模块。这也为未来检测失效功能模块进而维护蛋白质相互作用的可靠性奠定了基础。