Research on Protein Complex Recognition Using Hidden Markov Model

doi:10.3778/j.issn.1673-9418.2007073

Abstract

Abstract:

The construction of dynamic protein networks and the recognition of protein complexes are the hot topics in the current research of bioinformatics. In view of the shortcomings of existing algorithms in solving the above problems, a protein complex recognition algorithm (HMM-PC) based on hidden Markov model is proposed. In this paper, the initial protein network is constructed based on the co-expression characteristics of proteins, and then the dynamic protein network is obtained by weighting the initial network with the information of shared function annotation, shared domain and connection strength. On this basis, considering the influence of the previous time protein network topology information on the current protein network topology information, the relationship between protein complex and network individuals is described based on HMM, and then the problem of protein complex recognition in dynamic protein networks is modeled as the problem of optimal state sequence discovery in HMM and the protein complex is identified by the Viterbi algorithm. Finally, theoretical analysis shows that the proposed algorithm has low complexity. The yeast protein network in DIP data set and MIPS data set is used as the test object. A large number of simulation results also show that HMM-PC algorithm has strong robustness, and its performance is better than the existing composite recognition algorithms in terms of recall, precision, F-measure and efficiency.

Key words: dynamic protein network, protein complex, hidden Markov model, state sequence, Viterbi algorithm

摘要：

动态蛋白质网络的构建和复合物识别问题是生物信息学领域目前研究的热点。针对现有的算法在解决前述问题上的不足，提出了一种基于隐马尔科夫模型的蛋白质复合物识别算法（HMM-PC）。首先基于蛋白质的基因共表达特性构建初始蛋白质网络，然后利用蛋白质的共享功能注释、共享结构域和连接强度等信息来对网络进行加权，得到动态蛋白质网络。在此基础上，考虑前一时刻蛋白质网络拓扑结构信息对当前时刻蛋白质网络拓扑结构信息的影响，采用隐马尔科夫模型描述蛋白质复合物与网络个体间的相互关系，进而将动态蛋白质网络中的复合物识别问题建模为隐马尔科夫模型中的最优状态序列发现问题，并采用维特比算法识别得到蛋白质复合物。最后通过理论分析证明了所提算法的复杂度较低。采用DIP数据集和MIPS数据集中的酵母蛋白质网络作为测试对象，大量的仿真实验结果也表明，HMM-PC算法的鲁棒性较强，在查全率、查准率、F-measure和效率等方面的性能都要优于现有的复合物识别算法。

关键词: 动态蛋白质网络, 蛋白质复合物, 隐马尔科夫模型, 状态序列, 维特比算法

LI Peng, LUO Aijing, MIN Hui, TAN Sunyi, GUO Huimin. Research on Protein Complex Recognition Using Hidden Markov Model[J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(10): 1980-1989.

李鹏, 罗爱静, 闵慧, 谭荪怡, 郭惠敏. 采用隐马尔科夫模型的蛋白质复合物识别研究[J]. 计算机科学与探索, 2021, 15(10): 1980-1989.

References

[1] SZKLARCZYK D, GABLE A L, LYON D, et al. STRING v11: protein-protein association networks with increased coverage, supporting functional discovery in genome-wide experimental datasets[J]. Nucleic Acids Research, 2018, 47(D1): D607-D613.
[2] GEORGE G, PARAMBATH S V, LOKAPPA S B, et al. Construction of Parkinson??s disease marker-based weighted protein-protein interaction network for prioritization of co-expressed genes[J]. GENE, 2019, 697: 67-77.
[3] BORGIA A, BORGIA M B, BUGGE K, et al. Extreme disorder in an ultrahigh-affinity protein complex[J]. Nature, 2018, 555(7694): 61-66.
[4] WANG R Q, WANG C X, SUN L Y, et al. A seed-extended algorithm for detecting protein complexes based on density and modularity with topological structure and GO annota-tions[J]. BMC Genomics, 2019, 20(1): 637-645.
[5] ELMSALLATI A, CLARK C, KALITA J. Global alignment of protein-protein interaction networks: a survey[J]. IEEE/ACM Transactions on Computational Biology and Bioin-formatics, 2016, 13(4): 689-705.
[6] ZHANG C, ZHENG W, FREDDOLINO P L, et al. MetaGO: predicting gene ontology of non-homologous proteins through low-resolution protein structure prediction and protein-protein network mapping[J]. Journal of Molecular Biology, 2018, 430(15): 2256-2265.
[7] LEI X J, GAO Y, GUO L. Mining protein complexes based on topology potential weight in dynamic protein-protein in-teraction networks[J]. Acta Electronica Sinica, 2018, 46(1): 145-151.
雷秀娟, 高银, 郭玲. 基于拓扑势加权的动态PPI网络复合物挖掘方法[J]. 电子学报, 2018, 46(1): 145-151.
[8] ZHAO X W, CHENG X D, LYU J W, et al. Identify protein complexes by integrating temporal function continue feature and ant colony clustering on dynamic PPI networks[J]. Jour-nal of Chinese Computer Systems, 2017, 38(6): 1311-1316.
赵学武, 程新党, 吕嘉伟, 等. 融合时序保持特征和蚁群聚类的动态PPI网络复合物识别[J]. 小型微型计算机系统, 2017, 38(6): 1311-1316.
[9] YI L. Dynamic protein complex recognition and conserva-tive complex evolution[D]. Wuhan: Central China Normal University, 2017.
易丽. 动态蛋白质复合物识别与保守复合物进化研究[D]. 武汉: 华中师范大学, 2017.
[10] ZHOU J. Dynamic and conservative protein complex recog-nition based on multi-component data integration[D]. Wuhan: Central China Normal University, 2018.
周锦. 基于多组学数据整合的动态与保守蛋白复合物挖掘研究[D]. 武汉: 华中师范大学, 2018.
[11] LEI X J, WANG F, WU F X, et al. Protein complex identifi-cation through Markov clustering with firefly algorithm on dynamic protein-protein interaction networks[J]. Information Sciences, 2016, 329: 303-316.
[12] DONG S L, WU Z G, SHI P, et al. Quantized control of Markov jump nonlinear systems based on fuzzy hidden Markov model[J]. IEEE Transactions on Cybernetics, 2019, 49(7): 2420-2430.
[13] WANG J X, PENG X Q, PENG W, et al. Dynamic protein interaction network construction and applications[J]. Pro-teomics, 2014, 14(4/5): 338-352.
[14] TU B P, KUDLICKI A, ROWICKA M, et al. Logic of the yeast metabolic cycle: temporal compartmentalization of cellular processes[J]. Science, 2005, 310(5751): 1152-1158.
[15] ZHAO B H, LI X Y, HU S, et al. Prediction of protein fun-ctions based on essential functional modules mining[J]. Acta Automatica Sinica, 2018, 44(1): 183-192.
赵碧海, 李学勇, 胡赛, 等. 基于关键功能模块挖掘的蛋白质功能预测[J]. 自动化学报, 2018, 44(1): 183-192.
[16] WANG J X, CAI Z, LI M. An improved method based on maximal clique for predicting interactions in protein intera-ction networks[C]//Proceedings of the 2008 International Conference on BioMedical Engineering and Informatics, Sanya, May 28-30, 2008. Washington: IEEE Computer Soc-iety, 2008: 62-66.
[17] YUAN C, ILLINDALA M S, KHALSA A S. Modified Viterbi algorithm based distribution system restoration strategy for grid resiliency[J]. IEEE Transactions on Power Delivery, 2017, 32(1): 310-319.
[18] LEI H J, WEN Y T, YOU Z H, et al. Protein-protein inter-actions prediction via multimodal deep polynomial network and regularized extreme learning machine[J]. IEEE Journal of Biomedical and Health Informatics, 2019, 23(3): 1290-1303.
[19] RUAN P Y, HAYASHIDA M, AKUTSU T, et al. Improving prediction of heterodimeric protein complexes using combi-nation with pairwise kernel[J]. BMC Bioinformatics, 2018, 19(1): 73-84.
[20] PELLEGRINI M, BAGLIONI M, GERACI F. Protein com-plex prediction for large protein interaction networks with the core & peel method[J]. BMC Bioinformatics, 2016, 17(12): 37-58.
[21] HAQUE R, PENKALE S, WAY A. TermFinder: log-likelihood comparison and phrase-based statistical machine translation models for bilingual terminology extraction[J]. Language Resources and Evaluation, 2018, 52(2): 365-400.