面向生物网络的并行关联搜索算法研究

发布时间：2020-06-09 12:43

【摘要】：随着生物医疗大数据的不断增长,用户对生物医疗大数据的搜索需求也随之增长,但是具体生物蕴含的特定语义使得传统的搜索引擎失效,无法为医疗大数据提供搜索支持。国家863项目“生物大数据表述索引、搜索与存储访问关键技术研发”就是为解决这个问题。该项目的核心是构建在由生物语义关系构建的生物网络中进行多关键字关联搜索的算法。生物网络中的关联搜索算法大多是以网络的最小斯坦纳树问题(SPN问题)作为算法基础进行设计,但是SPN问题本身时间复杂度很高,在大规模生物网络中不再适用。为此,本课题借用Spark计算框架,设计了针对生物网络的基于中心点的并行关联搜索算法(PAS-CN算法),并进行了实验验证。多关键字的关联搜索试图在生物网络中搜索到多关键字彼此之间的关联关系,从而找到可用于辅助医疗诊断的相关知识。生物网络是基于生物实体的关系而构建的,因此构建基于生物网络的最小斯坦纳树,就可以探索出这组关键字之间的关联关系。SPN问题是NP-hard问题,所以只能用近似算法求解。本课题利用生物网络的无标度特性对生物网络进行层次聚类,从而实现网络划分。并以此为基础设计了并行关联搜索算法,大大降低了时间复杂度,并且通过引入网络中心点成功控制了斯坦纳树的规模。本课题中对生物网络做了大量的预处理作为算法的基础条件,其中包含了层次聚类、网络划分、子网络中心点选取、最低公共祖先矩阵构建。本课题设计的基于中心点的并行关联搜索算法(PAS-CN算法)主要包含了3个部分:子网络划分、并行斯坦纳搜索和局部斯坦纳树合并。其中子网络划分和局部斯坦纳树合并部分都是Spark平台串行计算完成,并行斯坦纳搜索部分在Spark集群中并行计算求解。实验表明PAS-CN算法在运算时间和斯坦纳树规模的控制上都取得了很大的提升。
【图文】：

哈尔滨工业大学工程硕士学位论文的，几乎没有什么差别。最小距离和最大距离将两个样个簇之间的距离，由于是由两个样本点决定的，，所以稳些离群点和错误数据的影响，从而导致聚类的效果不好虑着两种做法。离考虑了所有的样本点之间的距离，全面反映了两个簇具有很高的稳定性和极强的代表性。有时候为了避免离点的影响，可以对一些过大过小的距离进行删除，求取为两个簇之间的距离。平均距离还有一个很好的变种，为两个簇之间的距离，这个方式可以有效避免离群点和

从而得到一组不同方案的网络划分结果。此处以如图 2-2 为例，介绍对树状图进行分割的算法。如图2-2 所示，它是一个有 30 个节点的层次聚类的结果树状图，其中每层链接成一组聚类簇。此处我们设立簇距 ， 表示树状图相邻两次分割之后对应的层次的簇个数的差。用簇距控制分割，可以相对在各种不同级别完成对网络的子网络划分。层次聚类树状图分割算法描述如下：（1）从根节点开始，初始化层次 ，记录当前簇个数 m=1。（2）查看当前层次的簇的数目 k，如果 k≥m+ ,则进行分割
【学位授予单位】：哈尔滨工业大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5;TP391.3

【相似文献】

相关期刊论文 前10条

1 郭昌;傅明骏;;生物网络在生物功能分析中的应用[J];高师理科学刊;2018年03期

2 TRAFFIC;PEXELS;;野生物网络非法交易新趋势和问题[J];人与自然;2017年08期

3 梅娟;王正祥;石贵阳;李炜疆;;复杂生物网络分析的图聚类方法研究进展[J];食品与生物技术学报;2008年05期

4 肖巧玲;;初次尝试生物网络教学[J];中小学信息技术教育;2003年03期

5 赵琳琳;赵亚莉;张牧歌;李文龙;;一款轻量级的复杂生物网络图形化分析软件的设计与实现[J];智能计算机与应用;2018年02期

6 周凤妹;;设计合理高效的生物网络课[J];中国信息技术教育;2011年18期

7 丁永生,任立红;一种基于免疫突现计算的生物网络结构的设计[J];控制与决策;2003年02期

8 张文波;吴晶;;生物网络型社会组织[J];办公自动化;2015年11期

9 张航;昝乡镇;刘志伟;;生物网络模体识别算法概述[J];科协论坛(下半月);2010年02期

10 丁永生;;计算智能的新框架:生物网络结构[J];智能系统学报;2007年02期

相关会议论文 前10条

1 古华光;;生物网络的时空动力学行为的实验和数学模型研究[A];The 5th 全国动力学与控制青年学者研讨会论文摘要集[C];2011年

2 徐佳;雷明莉;王博;李婧;;生物网络与疾病关键肽段/蛋白质的鉴定[A];“农业健康与环境”组学大数据整合生物信息学研讨会论文集[C];2017年

3 刘曾荣;;动力学与控制在生物系统中应用的几个例子[A];中国力学学会学术大会'2009论文摘要集[C];2009年

4 张嗣瀛;;网络生物学及其一些进展(报告提纲)[A];第四届全国网络科学学术论坛暨研究生暑期学校论文集[C];2008年

5 徐筱杰;古江勇;陈丽蓉;;药用天然产物的网络药理学研究[A];中国化学会第28届学术年会第14分会场摘要集[C];2012年

6 高蕾;高鲁彬;郭进利;;生物网络研究进展述评[A];第五届全国复杂网络学术会议论文（摘要）汇集[C];2009年

7 杨卓琴;管亭亭;陆启韶;;多时间尺度的复杂网络的动力学问题研究[A];第四届全国动力学与控制青年学者研讨会论文摘要集[C];2010年

8 李永;方锦清;毕桥;刘强;;和谐统一的混合网络中的相称性系数转变[A];第三届全国复杂动态网络学术论坛论文集[C];2006年

9 来鲁华;;基于系统的药物设计[A];中国化学会第30届学术年会摘要集-第二十五分会：化学信息学与化学计量学[C];2016年

10 陈慧平;陈慧选;;多重分形谱在非线性网络中的应用[A];2006全国复杂网络学术会议论文集[C];2006年

相关重要报纸文章 前3条

1 记者 周颖;网络靶标 可阐释中药方剂作用机理[N];中国中医药报;2010年

2 赵晓涛;哲学角度谈安全[N];网络世界;2008年

3 本报记者 杨丰源;大数据治病时代已来临[N];贵阳日报;2016年

相关博士学位论文 前10条

1 姜sバ

本文编号：2704707