论文部分内容阅读
本文研究基于加强超立方体容错性的蛋白质互作网络模体发现算法。图论是以“图”作为研究对象，图是描述成对事物之间关系的数学模型。加强超立方体网络作为超立方体网络的一个变形，可以被抽象为一个图。随着网络规模的不断扩大，节点出现故障的概率是随之增大的，因此研究网络的容错性质就显得尤为重要。网络容错性的重要研究领域就是网络连通度和诊断度分析。连通度是反映大型复杂网络容错性能的重要指标之一，而对故障节点的诊断可以提高整个网络可靠性。图的容错性能越大，则信息可以在已出现故障节点的网络环境中进行传输的可能性越大。
为了更好地揭秘蛋白质互作网络的结构、功能以及进化设计原理和设计安全稳定的人造复杂网络，因此网络模体的概念应运而生。网络模体是具有统计意义的重复出现子图，是复杂网络的基本组成单元。网络模体发现算法涉及到子图同构与子图枚举两个计算难题，因此模体发现算法的时间复杂度与计算复杂度会随着蛋白质互作网络的规模增大而呈指数级增长。因此如何设计一个高效、可扩展性强以及占用存储空间少的模体发现算法具有重要的理论研究意义与应用意义。
首先，从网络容错性能分析，故障容错性能是反映复杂网络可靠性重要因素之一。限制连通度是复杂网络容错能力的衡量指标之一。本文通过证明(n,k)-维加强超立方体Qn,k的?1,2,3?-限制连通度来阐述复杂网络的容错性能方面的可靠性。
其次，从故障诊断性能角度来看，当节点发生故障时,对故障节点进行快速诊断、定位、修复、移除可以提高网络系统的鲁棒性和可靠性。本文结合(n,k)-维加强超立方体Qn,k的限制连通度证明了(n,k)-维加强超立方体Qn,k的g好邻居条件诊断度来研究复杂网络的故障诊断方面的可靠性。
最后，本文研究工作方向从特殊正则的拓扑图扩展到不规则大型复杂的蛋白质互作网络中，结合图论中连通度与诊断度的特性设计了一个高效、占用存储空间较少并且具有可扩展性的图论算法，用于蛋白质互作网络模体检测(Motif Detection Based on Balanced Sample and Graph Retrieve，简记为MDB-BSGR)。该算法采取图论的方法，结合图连通度特性，能够快速准确枚举出所有小规模蛋白质互作网络中的候选子图。对于检测大规模蛋白质互作网络模体，本文通过采用平衡方法来产生出候选子图。并且将所有候选子图存储在图检索数据结构中。实验结果表明，本文提出的MDB-BSGR算法不仅能全面识别所有3节点以及4节点的小规模蛋白质互作网络模体，还可以识别包含10个节点的大规模蛋白质互作网络模体。本文提出的基于加强超立方体容错性的蛋白质互作网络模体发现算法优于大多数现有的蛋白质互作网络模体发现算法。
为了更好地揭秘蛋白质互作网络的结构、功能以及进化设计原理和设计安全稳定的人造复杂网络，因此网络模体的概念应运而生。网络模体是具有统计意义的重复出现子图，是复杂网络的基本组成单元。网络模体发现算法涉及到子图同构与子图枚举两个计算难题，因此模体发现算法的时间复杂度与计算复杂度会随着蛋白质互作网络的规模增大而呈指数级增长。因此如何设计一个高效、可扩展性强以及占用存储空间少的模体发现算法具有重要的理论研究意义与应用意义。
首先，从网络容错性能分析，故障容错性能是反映复杂网络可靠性重要因素之一。限制连通度是复杂网络容错能力的衡量指标之一。本文通过证明(n,k)-维加强超立方体Qn,k的?1,2,3?-限制连通度来阐述复杂网络的容错性能方面的可靠性。
其次，从故障诊断性能角度来看，当节点发生故障时,对故障节点进行快速诊断、定位、修复、移除可以提高网络系统的鲁棒性和可靠性。本文结合(n,k)-维加强超立方体Qn,k的限制连通度证明了(n,k)-维加强超立方体Qn,k的g好邻居条件诊断度来研究复杂网络的故障诊断方面的可靠性。
最后，本文研究工作方向从特殊正则的拓扑图扩展到不规则大型复杂的蛋白质互作网络中，结合图论中连通度与诊断度的特性设计了一个高效、占用存储空间较少并且具有可扩展性的图论算法，用于蛋白质互作网络模体检测(Motif Detection Based on Balanced Sample and Graph Retrieve，简记为MDB-BSGR)。该算法采取图论的方法，结合图连通度特性，能够快速准确枚举出所有小规模蛋白质互作网络中的候选子图。对于检测大规模蛋白质互作网络模体，本文通过采用平衡方法来产生出候选子图。并且将所有候选子图存储在图检索数据结构中。实验结果表明，本文提出的MDB-BSGR算法不仅能全面识别所有3节点以及4节点的小规模蛋白质互作网络模体，还可以识别包含10个节点的大规模蛋白质互作网络模体。本文提出的基于加强超立方体容错性的蛋白质互作网络模体发现算法优于大多数现有的蛋白质互作网络模体发现算法。