基于动态图的PPI网络构建和复合物挖掘算法研究

doi:10.12263/DZXB.20200357

电子学报 ›› 2021, Vol. 49 ›› Issue (8): 1489-1497.DOI: 10.12263/DZXB.20200357

基于动态图的PPI网络构建和复合物挖掘算法研究

李鹏¹^,²^,³, 闵慧⁴, 罗爱静¹^,³

^1.中南大学湘雅三医院，湖南长沙 410013
^2.湖南中医药大学信息科学与工程学院，湖南长沙 410208
^3.医学信息研究湖南省普通高等学校重点实验室(中南大学)，湖南长沙 410006
^4.湖南信息职业技术学院软件学院，湖南长沙 410200

收稿日期:2020-04-13 修回日期:2020-08-27 出版日期:2021-08-25
- 作者简介:
- 李鹏男，1983年11月出生，湖南泸溪人.博士、讲师，中南大学公共卫生与预防医学博士后流动站在站博士后.主要研究方向为生物信息学、机器学习、中医药大数据. E-mail:lpchs617@csu.edu.cn
  闵慧女，1986年12月出生，湖南湘潭人.硕士、讲师，主要研究方向为生物信息学、网络优化. E-mail:mh1220@126.com
  罗爱静(通信作者) 女，1962年出生，湖南安乡人.博士、教授、博士生导师，主要研究方向为医药信息管理、卫生信息管理、医药信息检索. E-mail:805372510@qq.com
- 基金资助:
- 国家社会科学基金重点项目 (17AZD037); 国家重点研发计划 (2017YFC1703306); 湖南省卫生健康委科研项目 (202112072217); 湖南自然科学基金青年项目 (2019JJ50453); 湖南自然科学基金面上项目 (2018JJ2301); 湖南省科技厅重点项目 (2018JJ2301); 湖南省教育厅一般项目 (19C1318)

Research on PPI Network Construction and Complex Mining Algorithm Based on Dynamic Graph

LI Peng¹^,²^,³, MIN Hui⁴, LUO Ai-jing¹^,³

^1.The Third Xiangya Hospital of Central South University, Changsha, Hunan 410013, China
^2.School of Informatics, Hunan University of Chinese Medicine, Changsha, Hunan 410208, China
^3.Key Laboratory of Medical Information Research （CSU）, College of Hunan Province, Changsha, Hunan 410006, China
^4.Software Department, Hunan College of Information, Changsha, Hunan 410200, China

Received:2020-04-13 Revised:2020-08-27 Online:2021-08-25 Published:2021-08-25
- Supported by:
- Key Program of The National Social Science Fund of China (17AZD037); National Key Research and Development Program of China (2017YFC1703306); Research Program of Health Commission of Hunan Province (202112072217); Youth Project of Natural Science Foundation of Hunan Province (2019JJ50453); Natural Science Foundation Project of Hunan Province (2018JJ2301); Key Project of Hunan Science and Technology Department (2018JJ2301); General Program of Hunan Educational Committee (19C1318)

摘要/Abstract

摘要：

动态蛋白质网络的构建和复合物挖掘问题是目前研究的热点.针对现有的算法在解决前述问题上的不足，文中考虑了蛋白质的活性周期和连接强度，首先提出了一种基于动态图的蛋白质网络构建算法.然后基于密度聚类设计了一种在动态蛋白质网络上挖掘复合物的算法(PCMA).整个挖掘过程包含三个步骤：基于DBSCAN(Density-Based Spatial Clustering of Applications with Noise)算法的蛋白质复合物生成；基于合并增益的蛋白质复合物合并和基于归属度的复合物调整.在多个公开的生物数据集上进行了实验，实验结果表明，所提算法在查全率、查准率和F-measure方面的性能都要优于现有的算法，且对输入参数不敏感.在保证蛋白质复合物挖掘准确性的前提下，算法的时间复杂度处于一个合理的范围之内.

关键词: 动态蛋白质网络, 蛋白质复合物, 动态图, 密度聚类, 查全率, 查准率, 时间复杂度

Abstract:

Dynamic protein network construction and complex mining problem is a hot topic. In view of the shortcomings of existing algorithms in solving the above problems, a protein network construction algorithm based on dynamic graph is firstly proposed by considering the active period and the connection strength of proteins in this paper. Then, a protein complex mining algorithm(PCMA) on dynamic protein network is designed based on the density clustering. The whole mining process consists of three steps: the generation of protein complex based on DBSCAN(density-based spatial clustering of applications with noise) algorithm; the combination of protein complex based on the combination gain and the adjustment of protein complex based on the degree of membership. Experiments are carried out on several open biological datasets. The experimental results show that the performance of the proposed algorithm is better than that of the existing algorithms in terms of recall, precision and F-measure, and it is not sensitive to the input parameters. On the premise of ensuring the accuracy of protein complex mining, the time complexity of the proposed algorithm is in a reasonable range.

Key words: dynamic protein network, protein complex, dynamic graph, density clustering, recall, precision, time complexity

中图分类号:

TP391

李鹏, 闵慧, 罗爱静. 基于动态图的PPI网络构建和复合物挖掘算法研究[J]. 电子学报, 2021, 49(8): 1489-1497.

Peng LI, Hui MIN, Ai-jing LUO . Research on PPI Network Construction and Complex Mining Algorithm Based on Dynamic Graph[J]. Acta Electronica Sinica, 2021, 49(8): 1489-1497.

图/表 6

参考文献 18

1	LaranceM， LamondA I. Multidimensional proteomics for cell biology［J］. Nature Reviews Molecular Cell Biology， 2015， 16（5）： 269－280.
2	YangX， Coulombe-HuntingtonJ， KangS， et al. Widespread expansion of protein interaction capabilities by alternative splicing［J］. Cell， 2016， 164（4）： 805－817.
3	LeiX， WangF， WuF X， et al. Protein complex identification through Markov clustering with firefly algorithm on dynamic protein-protein interaction networks［J］. Information Sciences， 2016， 329： 303－316.
4	NepuszT， YuH， PaccanaroA. Detecting overlapping protein complexes in protein-protein interaction networks［J］. Nature Methods， 2012， 9（5）： 471－472.
5	李敏，王晓桐，罗慧敏，等. 随机游走技术在网络生物学中的研究进展［J］. 电子学报， 2018， 46（8）： 2035－2048.
	LiM， WangX T， LuoH M， et al. Progress on random walk and its application in network biology［J］. Acta Electronica Sinica， 2018， 46（8）： 2035－2048. （in Chinese）
6	张媛，贾克斌，张爱东. 基于多视图融合的蛋白质功能模块检测方法［J］. 电子学报， 2014， 42（12）： 2337－ 2344.
	ZhangY， JiaK B， ZhangA D. Consistent protein functional module detection from multi-view of biological data［J］. Acta Electronica Sinica， 2014， 42（12）： 2337－2344. （in Chinese）
7	HegeleA， KamburovA， GrossmannA， et al. Dynamic protein-protein interaction wiring of the human spliceosome［J］. Molecular Cell， 2012， 45（4）： 567－580.
8	TangX W， WangJ X， LiuB B， et al. A comparison of the functional modules identified from time course and static PPI network data［J］. BMC Bioinformatics， 2011， 12（1）： 339.1－339.15.
9	雷秀娟，高银，郭玲. 基于拓扑势加权的动态PPI网络复合物挖掘方法［J］. 电子学报， 2018， 46（1）： 145－151.
	LeiX J， GaoY， GuoL. Mining protein complexes based on topology potential weight in dynamic protein-protein interaction networks［J］. Acta Electronica Sinica， 2018， 46（1）： 145－151. （in Chinese）
10	ShenX， YiL， JiangX， et al. Neighbor affinity based algorithm for discovering temporal protein complex from dynamic PPI network［J］. Methods， 2016， 110： 90－96.
11	LeiX J， FangM， GuoL， et al. Protein complex detection based on flower pollination mechanism in multi-relation reconstructed dynamic protein networks［J］. BMC Bioinformatics， 2019， 20（3）： 63－74.
12	ElfwingS， UchibeE， DovaK. Sigmoid-weighted linear units for neural network function approximation in reinforcement learning［J］. Neural Networks， 2018， 107： 3－11.
13	ShenJ， HaoX， LiangZ， et al. Real-time superpixel segmentation by DBSCAN clustering algorithm［J］. IEEE Transactions on Image Processing， 2016， 25（12）： 5933－5942.
14	乔少杰，郭俊，韩楠，等. 大规模复杂网络社区并行发现算法［J］. 计算机学报， 2017， 40（3）： 687－700.
	QiaoS J， GuoJ， HanN， et al. Parallel algorithm for discovering communities in large-scale complex networks［J］. Chinese Journal of Computers， 2017， 40（3）： 687－700.（in Chinese）
15	LeiH， WenY， YouZ， et al. Protein-protein interactions prediction via multimodal deep polynomial network and regularized extreme learning machine［J］. IEEE Journal of Biomedical and Health Informatics， 2019， 23（3）： 1290－1303.
16	RuanP Y， HayashidaM， AkutsuT， et al. Improving prediction of heterodimeric protein complexes using combination with pairwise kernel［J］. BMC Bioinformatics， 2018， 19（1）： 73－84.
17	PellegriniM， BaglioniM， GeraciF. Protein complex prediction for large protein interaction networks with the Core&Peel method［J］. BMC Bioinformatics， 2016， 17（12）： 372.1－372.30.
18	LeiH， WenY， YouZ， et al. Protein-protein interactions prediction via multimodal deep polynomial network and regularized extreme learning machine［J］. IEEE Journal of Biomedical and Health Informatics， 2018， 23（3）： 1290－1303.

算法	Precision	Recall	F-measure
TC-PINS	0.5417	0.4702	0.5034
MCL-TP	0.6818	0.5683	0.5889
DPC-NADPIN	0.7919	0.5122	0.6221
IFPA	0.8051	0.6322	0.7081
PCMA	0.8605	0.8456	0.8530

算法	Precision	Recall	F-measure
TC-PINS	0.5417	0.4702	0.5034
MCL-TP	0.6818	0.5683	0.5889
DPC-NADPIN	0.7919	0.5122	0.6221
IFPA	0.8051	0.6322	0.7081
PCMA	0.8605	0.8456	0.8530

算法	Precision	Recall	F-measure
TC-PINS	0.4998	0.5115	0.5056
MCL-TP	0.6639	0.5714	0.6142
DPC-NADPIN	0.7781	0.5236	0.6260
IFPA	0.7967	0.6880	0.7384
PCMA	0.8513	0.7451	0.7947

算法	Precision	Recall	F-measure
TC-PINS	0.4998	0.5115	0.5056
MCL-TP	0.6639	0.5714	0.6142
DPC-NADPIN	0.7781	0.5236	0.6260
IFPA	0.7967	0.6880	0.7384
PCMA	0.8513	0.7451	0.7947

蛋白质	功能
Origin recognition complex subunit 2	（1） stabilizes ORC3；（2） Binds histone H3 and H4 trimethylation marks H3K9me3， H3K20me3 and H4K27me3；（3） Stabilizes LRWD1；（4） Acts as component of the MCM2-7 complex.
DNA replication licensing factor MCM2	（1） Acts as component of the MCM2-7 complex；（2） Plays a role in terminally differentiated hair cells development of the cochlea and induces cells apoptosis.
CDC6 protein	（1） Involved in the initiation of DNA replication；（2） participates in checkpoint controls that ensure DNA replication is completed before mitosis is initiated.
Replication protein A3， 14kDa homo-log RPA14	（1） Acts as component of the MCM2-7 complex；（2） it plays an essential role both in DNA replication and the cellular response to DNA damage.
DNA replication licensing factor MCM5	（1） Acts as component of the MCM2-7 complex；（2） Interacts with MCMBP.
DNA replication licensing factor MCM7	（1） Acts as component of the MCM2-7 complex；（2） Once loaded onto DNA， double hexamers can slide on dsDNA in the absence of ATPase activity.
DBF4-related protein	（1） Regulatory subunit for CDC7；（2） involved in regulating the initiation of DNA replication during cell cycle.

基于动态图的PPI网络构建和复合物挖掘算法研究

Research on PPI Network Construction and Complex Mining Algorithm Based on Dynamic Graph

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 6

参考文献 18

相关文章 12

编辑推荐

Metrics

算法	DIP数据集	MIPS数据集
TC-PINS	8.5	7.75
MCL-TP	9.7	9.33
DPC-NADPIN	11.2	10.28
IFPA	12.8	10.93
PCMA	9.1	8.2

[1]	王宁远, 刘亮, 陈东, 刘欢, 郝时光. 低轨巨星座多品类业务流低复杂度分段路由方法[J]. 电子学报, 2021, 49(11): 2124-2132.
[2]	刘剑锋, 孙力帆, 普杰信, 何子述, 王燕玲. 基于刚性约束的双移动机器人协同定位[J]. 电子学报, 2020, 48(9): 1777-1785.
[3]	王治丹, 蒋建国, 齐美彬. 基于最大池图匹配的形变目标跟踪方法[J]. 电子学报, 2017, 45(3): 704-711.
[4]	丁琳琳, 李正道, 纪婉婷, 宋宝燕. 基于改进哈夫曼编码的大规模动态图可达查询方法[J]. 电子学报, 2017, 45(2): 359-367.
[5]	曹政才, 林诚然, 黄冉. 带等待时间约束并行机调度问题的Copula分布估计算法[J]. 电子学报, 2017, 45(12): 2949-2956.
[6]	梁常建, 李永明. 具有模糊时态的广义可能性线性时序逻辑的模型检测[J]. 电子学报, 2017, 45(12): 2971-2977.
[7]	李仲生, 李仁发, 蔡则苏, 赵乘麟. 稀疏表示下的非监督显著对象提取[J]. 电子学报, 2012, 40(6): 1097-1102.
[8]	钱鹏江;王士同;邓赵红;徐华. 基于最小包含球的大数据集快速谱聚类算法[J]. 电子学报, 2010, 38(9): 2035-2041.
[9]	裴继红, 卢宗庆, 谢维信. 基于图像梯度场序列的双向GDIM光流计算方法[J]. 电子学报, 2007, 35(7): 1301-1305.
[10]	牛夏牧;SCHMUCKER Martin;BUSCH Christoph. 基于时间轴上模板的动态图像数字水印处理技术[J]. 电子学报, 2004, 32(8): 1236-1238.
[11]	蒋廷耀;李庆华. 多播路由算法MPH的时间复杂度研究[J]. 电子学报, 2004, 32(10): 1706-1708.
[12]	吴湛击, 吴伟陵. 随机排序的优化算法[J]. 电子学报, 2000, 28(S1): 76-79.