一种基于同配性的重叠蛋白质复合体检测算法

doi:10.11896/j.issn.1002-137X.2019.02.045

Abstract

Abstract: Protein complexes play significant roles in biological processes.The detection of protein complexes from available protein-protein interaction (PPI) networks is one of the most challenging tasks in the post-genome era.Seed expansion method is an effective clustering technique for overlapping protein complexes detection from PPI networks.However,existing methods are usually faced with two problems.One is that they only consider link density between direct neighbors of nodes in a network in the step of seed selection,which is not enough to indicate the importance of nodes in local subgraphs consisting of their neighborhoods.The other is that candidate nodes are assumed to be independent from each other,ignoring the impact of candidate nodes’ order on clustering in the process of cluster extension.To solve the problems,this paper proposed an overlapping protein complexes detection algorithm based on assortativity,which considers 2-order neighborhood of nodes in the process of seed selection,and multiple candidate nodes are added into clusters based on assortativity in networks in the process of cluster expansion.In order to evaluate overlapping results,a new evaluation index named F-overlap was presented.Experiment results on PPI networks show that the proposed algorithm can effectively identify overlapping protein complexes.

Key words: Assortativity, Complexes detection, Protein-protein interaction network, Seed expansion method

CLC Number:

TP181

WANG Jie, LIANG Ji-ye, ZHAO Xing-wang, ZHENG Wen-ping. Overlapping Protein Complexes Detection Algorithm Based on Assortativity in PPI Networks[J].Computer Science, 2019, 46(2): 294-300.

References

[1]SPIRIN V,MIRNY L A.Protein complexes and functional mo- dules in molecular networks [J].Proceedings of the National Academy of Sciences,2003,100(21):12123-12128.
[2]JI J Z,LIU Z J,LIU H X,et al.An overview of research on functional module detection for protein-protein interaction networks [J].Acta Automatica Sinica,2014,40(4):577-593.(in Chinese)
冀俊忠,刘志军,刘红欣,等.蛋白质相互作用网络功能模块检测的研究综述[J].自动化学报,2014,40(4):577-593.
[3]BRUN C,HERRMANN C,GUENOCHE A.Clustering proteins from interaction networks for the prediction of cellular functions [J].Bmc Bioinformatics,2004,5(1):95.
[4]YU L,GAO L,SUN P G.Research on algorithms for complexes and functional modules prediction in protein-protein interaction networks [J].Chinese Journal of Computers,2011,34(7):1239-1251.(in Chinese)
鱼亮,高琳,孙鹏岗.蛋白质网络中复合体和功能模块预测算法研究[J].计算机学报,2011,34(7):1239-1251.
[5]LI X L,WU M,KWOH C K,et al.Computational approaches for detecting protein complexes from protein interaction networks:A survey [J].Bmc Genomics,2010,11(1):S3.
[6]REN J,WANG J X,LI M.Identifying protein complexes based on local fitness method [C]∥ Proceedings of IEEE International Conference on Bioinformatics and Biomedicine.Piscataway,NJ:IEEE,2012:205-210.
[7]OUGHTRED R,CHATR-ARYAMONTRI A,BREITKREUTZ B J,et al.BioGRID:A resource for studying biological interactions in yeast [J].Cold Spring Harbor Protocols,2016,2016(1):080754.
[8]KESKIN O,TUNCBAG N,GURSOY A.Predicting protein- protein interactions from the molecular to the proteome level [J].Chemical Reviews,2016,116(8):4884.
[9]ASUR S,UCAR D,PARTHASARATHY S.An ensemble framework for clustering protein-protein interaction networks [J].Bioinformatics,2007,23(13):29-40.
[10]NEPUSZ T,YU H,PACCANARO A.Detecting overlapping protein complexes in protein-protein interaction networks [J].Nature Methods,2012,9(5):471-472.
[11]BHOWMICK S S,SEAH B S.Clustering and summarizing protein-protein interaction networks:A survey [J].IEEE Transactions on Knowledge and Data Engineering,2016,28(3):638-658.
[12]SHIH Y K,PARTHASARATHY S.Identifying functional mo- dules in interaction networks through overlapping Markov clustering [J].Bioinformatics,2012,28(18):473-479.
[13]WANG J,LIANG J Y,ZHENG W P.A graph clustering me- thod for detecting protein complexes [J].Journal of Computer Research and Development,2015,52(8):1784-1793.(in Chinese)
王杰,梁吉业,郑文萍.一种面向蛋白质复合体检测的图聚类方法[J].计算机研究与发展,2015,52(8):1784-1793.
[14]ADAMCSEK B,PALLA G,FARKAS I J,et al.CFinder:Locating cliques and overlapping modules in biological networks [J].Bioinformatics,2006,22(8):1021-1023.
[15]LIU G M,WONG L,CHUA H N.Complex discovery from weighted PPI networks [J].Bioinformatics,2009,25(15):1891-1897.
[16]BADER G D,HOGUE C W V.An automated method for fin- ding molecular complexes in large protein interaction networks [J].Bmc Bioinformatics,2003,4(1):2.
[17]ALTAF-UL-AMIN M,SHINBO Y,MIHARA K,et al.Deve- lopment and implementation of an algorithm for detection of protein complexes in large interaction networks [J].Bmc Bioinformatics,2006,7(1):207.
[18]WANG J,ZHENG W P,QIAN Y H,et al.A seed expansion graph clustering method for protein complexes detection in protein interaction networks [J].Molecules,2017,22(12):2179.
[19]LI M,CHEN J E,WANG J X,et al.Modifying the DPClus algorithm for identifying protein complexes based on new topological structures [J].Bmc Bioinformatics,2008,9(1):398.
[20]GAVIN A C,ALOY P,GRANDI P,et al.Proteome survey reveals modularity of the yeast cell machinery [J].Nature,2006,440(7084):631-636.
[21]LEUNG H C M,XIANG Q,YIU S M,et al.Predicting protein complexes from PPI data:A core-attachment approach [J].Journal of Computational Biology,2009,16(2):133-144.
[22]KOUHSAR M,ZARE-MIRAKABAD F,JAMALI Y.WCO- ACH:Protein complex prediction in weighted PPI networks [J].Genes and Genetic Systems,2015,90(5):317-324.
[23]NEWMAN M E J.Assortative mixing in networks [J].Physical Review Letters,2002,89(20):208701.
[24]NOLDUS R,VAN M P.Assortativity in complex networks [J].Journal of Complex Networks,2015,3(4):507-542.
[25]KUNEGIS J.Konect:The koblenz network collection [C]∥ Proceedings of the 22nd International Conference on World Wide Web.New York:ACM,2013:1343-1350.
[26]CHERRY J M,HONG E L,AMUNDSEN C,et al.Saccharomyces genome database:The genomics resource of budding yeast [J].Nucleic Acids Research,2011,40(1):700-705.
[27]LEE A J T,LIN M C,HSU C M.Mining dense overlapping subgraphs in weighted protein-protein interaction networks[J].Bio-Systems,2011,103(3):392-399.
[28]WHANG J J,GLEICH D F,DHILLON I S.Overlapping community detection using neighborhood-inflated seed expansion [J].IEEE Transactions on Knowledge and Data Engineering,2016,28(5):1272-1284.
[29]LUO J W,QI Y.Identification of essential proteins based on a new combination of local interaction density and protein complexes [J].Plos One,2015,10(6):0131418.
[30]QIN C,SUN Y Q,DONG Y D.A new method for identifying essential proteins based on network topology properties and protein complexes [J].Plos One,2016,11(8):0161042.
[31]TRAJANOVSKI S,MARTIN-HERNANDEZ J,WINTERBA- CH W,et al.Robustness envelopes of networks [J].Journal of Complex Networks,2013,1(1):44-62.
[32]CAO B W,LUO J W,LIANG C,et al.Moepga:A novel method to detect protein complexes in yeast protein-protein interaction networks based on multiobjective evolutionary programming genetic algorithm [J].Computational Biology and Chemistry,2015,58:173-181.
[33]GAVIN A C,BOSCHE M,KRAUSE R,et al.Functional orga- nization of the yeast proteome by systematic analysis of protein complexes [J].Nature,2002,415(6868):141-147.
[34]KROGAN N J,CAGNEY G,YU H,et al.Global landscape of protein complexes in the yeast Saccharomyces cerevisiae[J].Nature,2006,440(7084):637-643.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 0

No Suggested Reading articles found!

Overlapping Protein Complexes Detection Algorithm Based on Assortativity in PPI Networks

PDF (PC)

Abstract

Cite this article

share this article

References

Related Articles 4

Metrics

Comments

Recommended 0

[1]	TANG Jia-qi, WU Jing-li, LIAO Yuan-xiu, WANG Jin-yan. Prediction of Protein Functions Based on Bi-weighted Vote [J]. Computer Science, 2019, 46(4): 222-227.
[2]	ZHANG Yue-yang and LIU Wei. Link Prediction in Uncertain Protein-Protein Interaction Network [J]. Computer Science, 2014, 41(Z11): 399-402.
[3]	ZHAO Bi-hai,XIONG Hui-jun,NI Wen-yin,LIU Zhi-bing and HU Sai. Improved Weighted-network Based Algorithm for Predicting Protein Complexes [J]. Computer Science, 2014, 41(6): 231-234.
[4]	. PPI Networks Clustering Model and Algorithm Combining with the Principle of Artificial Fish School [J]. Computer Science, 2012, 39(7): 205-209.