基于特征压缩方法的图同构算法及其在网络模体发现中的应用

来源 :西安电子科技大学 | 被引量 : 0次 | 上传用户:yanrj
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
目前人类基因组研究已经从结构基因组时代进入到了功能基因组时代,也就是“后基因组时代”。研究发现人类基因组不是由孤立的基因和大量无用的“DAN片段”组成的,其本身是一个复杂的网络系统。因此,对生物复杂网络的研究就成了研究者关注的焦点。网络模体查找就是其中一个很有代表性的研究方向。网络模体是真实网络中出现频率明显高于随机网络中出现频率的子图。模体发现需要对各种子图类型计数,这一问题就需要图同构算法来解决。但是图同构问题仍然是一个NP难问题。本文提出了基于特征压缩方法的一种新的启发式的图同构算法FCGI (Feature Compression for Graph Isomorphism).首先,构造了四种特殊的图拓扑特征;然后利用特征压缩策略对这些特征进行流水操作,实现了对各种类型的同构图的唯一标记。这种方法大大地缩减了搜索的节点置换空间、降低了比较次数。实验用该算法对各种同构种类的图所对应的可能的邻接矩阵进行了归类,并且比较了特征压缩算法和层次分类算法的性能,结果证明该算法是一种非常精确有效的图同构算法。此外,我们将该算法用于酵母菌基因调控网络的模体发现,结果发现它成功的找到了已被理论和实验证明的具有重要意义的网络模体。
其他文献
随着信息技术的飞快发展,信息的安全问题正在成为研究的热点。目前关于计算机设备的信息安全研究还主要集中在软件层面,虽然达到了比较好的效果,但没有从本质上解决安全问题
学位
随着网络技术的迅速发展和互联网规模的不断扩大,互联网已经成为了全球最大、最广泛使用的信息库,有效检索这些海量信息以获得感兴趣的部分已经成为人们迫切需要的服务。在实
学位
近年来,复杂网络中社区结构的发现及社会关系知识的挖掘,已经成为数据挖掘领域的研究热点之一。电子邮件系统中的邮件通信网络是一种较简单的社会网络,其社区划分问题本质上
传统学术论文作为记录、传递、累积、创新、交流人类科技成果的载体和工具一直伴随着学术界的成长。但随着科学技术的迅速发展以及Internet的出现传统科技学术期刊的出版慢慢
无线传感器网络是由布置在检测区域内大量的廉价微型传感器节点组成,通过无线通信方式形成的一个多跳的自组织的网络系统。现已广泛应用于军事、环境监测和现代化农业等方面,
辩论是社会日常生活、工作中广泛存在的一种重要群体活动,基于Web的辩论支持系统是目前群体决策支持系统领域研究的重点。辩论支持系统以计算机为媒介,主要用来解决对抗性强
组合分类方法是机器学习领域逐渐发展起来的用于提高弱分类器准确性的有效方法,被认为是十几年来研究的最好的学习算法之一。大量的理论和实验研究表明:与单个分类模型相比,组
特征选择作为数据预处理的关键手段,是数据挖掘、模式识别和机器学习等领域的重要研究课题之一。它是指在原始数据中删除大量无关和冗余的特征,找到一组包含原始特征空间的全
20世纪以来,信息技术和网络技术快速发展,在各个方面影响着人们的生活,学习和工作。在教育领域,各种网络教学系统正在兴起,其中以提倡学习者为中心的自适应学习系统最为引人
随着无线网络技术的发展,基于无线网络的定位服务为其提供了更多的附加价值。在无线网络中基于信号到达时间或信号相位的定位技术需要专门的硬件支持,而信号强度数值在现有的