论文部分内容阅读
随着后基因组时代的到来,生物组学研究深入发展,大量的生物网络数据涌现,有效地解析和分析这些网络数据是当前生物信息学的研究重点。网络模体是网络中一种有着不同局部结构特征的模块,在生物网络中具有重要的作用。大量算法被研究出来用于网络模体发现,由于网络模体发现计算非常复杂,抽样算法被用来减少网络模体发现的计算量,但是抽样算法不可避免的抽样误差影响抽样结果的正确性,是抽样网络模体发现中不可忽视的问题。本文致力于研究具有低抽样误差的网络模体发现算法。为了降低抽样误差,针对现有抽样网络模体发现算法在计算子图比例时采取同构子图简单计数的方法,本文提出了一种基于子图扩展和子图支持度的网络模体发现抽样算法——SE&SSV(Sampling Network Motif Detection Algorithm Basedon Subgraph Extending and Subgraph Support Value)算法。该算法采用子图扩展的方法进行同构判断,在扩展的过程中计算出一个衡量子图同构概率的子图支持度值(Subgraph Support Value, SSV),将子图支持度(SSV)用到子图浓度的计算当中,可以考虑到更多的网络拓扑信息。实验结果表明该算法具有较低的抽样误差和较高的稳定性。由于现有抽样网络模体发现算法中子图样本的选取通常采用简单随机抽样方法,而在相同样本容量情况下,分层抽样方法通常比简单随机抽样具有更小的抽样误差,更高的抽样精度。因此,本文提出一种基于节点度序列分布特征的网络模体发现分层抽样算法——SRand_ESU(Stratified Sampling Network MotifDetection Algorithm Based on Vertices Degree Sequence)算法。该算法将输入网络的节点度序列特征作为抽样分层的指标,根据不同的度序列分布特征选择合理的分层模型,可以有效降低抽样误差提高抽样精度。实验结果表明,该算法取得的子图样本节点度分布与输入网络节点度分布更加一致,并且能取得较好的抽样精度和稳定性。