面向复杂疾病基因组动态交互网络的k点连通稠密子图查询与挖掘技术

Complex disease refers to the disease caused by the interaction effect of multiple SNPs and changes over time. Genetic dynamic interaction network can effectively characterize the dynamic association between interaction of SNP pairs and complex disease. Moreover, the cohesive regions in the network are closely related to complex disease. Different from traditional cohesive subgraphs, k-vertex connected cohesive subgraphs are more suitable for characterizing cohesive regions related to complex disease because of the property of tight connectivity, clear hierarchy in the subgraph and free overlap between subgraphs. Challenged by the features of genetic dynamic interaction network, such as large scale, complex local structure, time-varying topological structure and so on, this study focuses on the k-vertex connected cohesive subgraph query and mining techniques for genetic dynamic interaction network of complex disease. The main contents of this research can be summarized as follows: (1) Aiming at the false positive problem caused by multiple tests, a lightweight permutation test technique based on flexible lower bound is proposed to realize accurate network construction; (2) Aiming at the weak timeliness problem in traditional network management, a storage and index technology based on time-subgraph hierarchical partition is proposed to realize network dynamic maintenance; (3) Aiming at the problem of neglecting vertex connectivity in traditional cohesive subgraphs, a subgraph query and mining technology based on vertex connectivity is proposed to realize efficient k-vertex connected cohesive subgraph discovery. These research results can provide a new perspective to the complex disease pathogenesis and accurate medicine. Therefore, this research is of high theoretical significance and practical application value.

复杂疾病由多个SNP位点交互作用导致并随时间演变。基因组动态交互网络能够有效刻画位点交互与复杂疾病的动态关联且网络中稠密区域与复杂疾病密切相关。与传统稠密子图不同，k点连通稠密子图紧密连通且支持重叠，更适于表征复杂疾病相关稠密区域。然而，网络规模庞大、位点角色多样、交互关系协同且局部结构易变等特征为数据管理和查询挖掘带来严峻挑战。课题围绕面向复杂疾病基因组动态交互网络的k点连通稠密子图查询与挖掘技术展开深入研究。主要内容概括为：(1)针对多重检验导致的假阳性问题，提出基于柔性下界的置换检验技术，实现网络精准构建；(2)针对传统网络管理时效性弱的问题，提出基于时间-子图层次划分的存储索引技术，实现网络动态维护；(3)针对传统稠密子图忽略点连通性的问题，提出基于顶点连通度的子图查询挖掘技术，实现连通性更强的k点连通稠密子图高效发现。研究成果对复杂疾病发病机理揭示和精准医疗等具有重要意义。

复杂疾病由多个SNP位点交互作用导致并随时间演变。面向复杂疾病基因组动态交互网络的k点连通稠密子图查询与挖掘技术课题主要研究了基因组动态交互网络的构建、管理以及k点连通稠密子图查询与挖掘。. 具体内容如下：（1）在交互网络构建方面，分别提出了基于随机分组的自我调节人工蜜蜂蜂群算法、渐进式筛选记忆算法以及基于空间分割的分布式进化框架来检测与复杂疾病相关的SNP-SNP交互作用，大量真实数据集上的实验验证了上述提出算法的高效性和有效性，确实发现了与复杂疾病相关的遗传位点交互，从而完成基因组动态交互网络的初步构建。在网络精细构建上，利用现有主流图嵌入算法来进行位点交互预测，实验结果表明采用随机游走的DeepWalk，可以在图规模较大时有效减少计算量且准确率最高。（2）在交互网络管理方面，提出了一种以子图为中心的分布式大规模图处理框架。利用该框架能够在兼顾CPU计算时间和IO通信时间的情况下完成稠密子图挖掘任务的分配和计算。（3）在稠密子图查询与挖掘方面，不仅研究了k点连通稠密子图同时还研究了基于k-核和k-捆稠密子图的算法。在单网络模型上，提出了自顶向下、自底向上和混合框架来发现k点连通分量。为加速计算，进一步提出了基于概率采样的近似计算算法。在双网络模型上，首先，提出一种k-连通捆子图发现算法。为了完善该方法，提出了在权重双网络模型上的影响力k-连通捆子图发现算法，大大提高了发现结果的可解释性。另外，提出了一种考虑正负交互的全局对比核子图发现算法用来发现与复杂疾病正负相关的位点集合。在时序网络模型上，提出了包含查询点的持续性稠密子图搜索算法以及考虑内外存转换的早期突发稠密子图发现算法。高血压基因交互网络中发现的稠密子图中包含与该疾病高度相关的基因位点。. 本课题提出的算法和技术不仅局限于基因交互网络分析，还可以扩展应用于人脑网络、知识图谱、社交网络等其它大图相关研究领域，具有重要的理论研究意义和广泛的实际应用价值。