基因网络中重要节点的挖掘研究论文PPT.ppt

安徽农业大学信息与计算机学院 安徽农业大学信息与计算机学院 基因网络中重要节点的挖掘研究 安徽农业大学信息与计算机学院 学生：肖翔月 指导教师：李绍稳 教授 2013年五月 目录 二 重要节点挖掘方法 三 基因网络中重要节点的挖掘 四 总结与展望 一 复杂网络理论 复杂网络研究历程 1 在最初的研究中，人们认为复杂网络中是由一些规则的元素所组成的 2 20世纪50年代末到90年代末，易于被人们接受的则是随机网络模型 3 随着研究的不断深入，科学家们提出了符合幂律分布的复杂网络，即无尺度网络 复杂网络定义：具有自组织、自相似、吸引子、小世界、无标度中 部分或全部性质的网络称为复杂网络 安徽农业大学信息与计算机学院 复杂网络特点 度分布，与该节点连接的其他节点的数目 称为度 1 小世界效应指的是尽管复杂网络的规模很大，因为其中包含很多的节点与连接，两个节点间总存在着相对较短的距离 2 强”抵抗性与“弱”抵抗性 3 节点的度按幂次定律分布.此时,认为该网络具有无尺度分布的特性.这也是近几年关于复杂网络的新的研究成果 4 1 2 3 4 复杂网络的研究意义 复杂网络的研究意义十分重大，一方面我们可以通过对其的研究更好的保护与发展，比说国家的安全网络，我们只有充分了解它的节点与节点间的关系，才能更好的控制，防止被破坏。又如人类的基因网络，大家都知道基因通常决定着遗传和某些疾病的产生，研究好基因网络，对一些疾病的治疗会起到帮助，也会对人类的发展产生深远的影响。另一方面，我们对复杂网络的研究也可以帮助攻击一些不好的网络，以达到摧毁的目的。 复杂网络 工程技术 社会 政治 医药 经济 管理 拟南芥花药基因网络的构建 拟南芥简介： 拟南芥是一种细长而直立的植物，羽状多叶，茎高度达40厘米 ，拟南芥的基 因组是目前已知植物基因组中最小的。每个单倍染色体组（n=5）的总长只有 7000万个碱基对 ，其被科学家誉为“植物中的果蝇” 。 根据上图在第一行有三个基因，每个基因对应一个文件名，把其做 为靶基因，下列文件的每一行都代表一个拟南芥花药基因，它们和 靶基因之间存在一定的关系，主要指标有表中的相关系数来确定， 取第三列系数为两者的相关系数，其阀值的设定为0.6，通过这些表 和数据可以构建拟南芥花药基因网络，每个拟南芥基因为一个节点 ，若两个基因之间的相关系数超过0.6，则在两个节点之间用边连接 起来，由此可以得到拟南芥基因组成的复杂网络 。 下图为pajek 网 络 分析软件对预测到得 6836 对调控关系基因对可视 化 的结果： 对图形优化后得出下图作为复杂网络进行分析，挖掘出重要节点并进行分析： 实验原图 重构图 三种方法的具体应用和分析： 一 度数法 一个节点的度，是指网络拓扑中与此节点连接的边的数量 ，实验中计算出每个节点的度，并根据大小得出重要节点（图中用黑体标出） 二 基于生成树的节点删除法的原理是评估节点失效后对整个复杂网络的影响，即破坏性等价于重要性，其基本思想是最重要的节点是去掉该节点以及相关联的链路后，使得图的生成树数目最小 算法为： begin 初始化图G的全顶点关联矩阵AC A：=AC-AC (the last row); Num_spn_tree:= det(AAT); FOR i:=1 TO vtsnum DO (主循环，计算各节点对应的生成树数目和重要性归一化结果） { B:= AC; FOR j:= 1 TO edgnum DO IF AC[i,j]!=0 THEN B:=B- AC (the_j the column); B:=B-B(the i-th row); B:=B-B(the last row); nst[i]:=det(BBT); r[i]:=1-nst[i]/ num_spn_tree; } End edgum代表图中边的数目，vtsnum代表图的顶点数目 实验结果如下： 根据归一化结果可得重要节点为： 5号23号28号30号35号49号80号88号92号93号97号103号 三 节点收缩法,它对节点的分析并不是通过删除，而是收缩某节点看整个网络是否可以更好的凝聚 算法为： 输入:H 输出:IMC 1)计算所有节点对之间的最短距离矩阵D=[dij]PPFloyd算法; 2)根据公式计算网络初始凝聚度; 3) FORi=1 tonPP主循环,评估所有节点重要度; { 计算节点vi收缩后所有节点对之间的最短距离矩阵D(i)=[d(i)st]; 根据公式计算节点vi收缩后网络的凝聚度； 根据公式计算IMC(vi); } 实验结果如下： 重要节点为：5号，23号,28号,35号,49号，80号，88