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