Mining functional subgraphs from cancer protein-protein interaction networks

BMC Systems Biology - Tập 6 - Trang 1-14 - 2012
Ru Shen1,2, Nalin CW Goonesekere3, Chittibabu Guda1,4
1Department of Genetics, Cell Biology, and Anatomy, University of Nebraska Medical Center, Omaha, USA
2Department of Computer Science, State University of New York at Albany, Albany, USA
3Department of Chemistry and Biochemistry, University of Northern Iowa, Cedar Falls, USA
4Bioinformatics and Systems Biology Core Facility, University of Nebraska Medical Center, Omaha, USA

Tóm tắt

Protein-protein interaction (PPI) networks carry vital information about proteins' functions. Analysis of PPI networks associated with specific disease systems including cancer helps us in the understanding of the complex biology of diseases. Specifically, identification of similar and frequently occurring patterns (network motifs) across PPI networks will provide useful clues to better understand the biology of the diseases. In this study, we developed a novel pattern-mining algorithm that detects cancer associated functional subgraphs occurring in multiple cancer PPI networks. We constructed nine cancer PPI networks using differentially expressed genes from the Oncomine dataset. From these networks we discovered frequent patterns that occur in all networks and at different size levels. Patterns are abstracted subgraphs with their nodes replaced by node cluster IDs. By using effective canonical labeling and adopting weighted adjacency matrices, we are able to perform graph isomorphism test in polynomial running time. We use a bottom-up pattern growth approach to search for patterns, which allows us to effectively reduce the search space as pattern sizes grow. Validation of the frequent common patterns using GO semantic similarity showed that the discovered subgraphs scored consistently higher than the randomly generated subgraphs at each size level. We further investigated the cancer relevance of a select set of subgraphs using literature-based evidences. Frequent common patterns exist in cancer PPI networks, which can be found through effective pattern mining algorithms. We believe that this work would allow us to identify functionally relevant and coherent subgraphs in cancer networks, which can be advanced to experimental validation to further our understanding of the complex biology of cancer.

Tài liệu tham khảo

Badger GD, Hogue CW: An automated method for finding molecular complexes in large protein interaction networks. BMC Bioinformatics. 2003, 4: 2-10.1186/1471-2105-4-2.

Kelley BP, Yuan B, Lewitter F: Pathblast: a tool for alignment of protein interaction networks. Nucleic Acids Res. 2004, 32: W83-88. 10.1093/nar/gkh411.

Cook DJ, Holder LB: Mining graph data. 2007, John Wiley & Sons, Inc.

Borgwardt KM, Kriegel HP: Graph kernels for disease outcome prediction from protein-protein interaction networks. Pacific Symposium on Biocomputing. 2007, 4-15.

Bunke H, Shearer K: A graph distance metric based on the maximal common subgraph. Pattern Recognition Lett. 1998, 19: 255-259. 10.1016/S0167-8655(97)00179-7.

Fernandez ML, Valiente G: A graph distance metric combining maximum common subgraph and minimum common supergraph. Pattern Recognition Lett. 2001, 22: 753-758. 10.1016/S0167-8655(01)00017-4.

Sanfeliu A, Fu KS: A distance measure between attributed relational graphs for pattern recognition. IEEE Transactions on Systems, Man, and Cybernetics. 1983, 13: 353-363.

Li Z, Zhang S, Wang Y, Zhang XS, Chen L: Alignment of protein interaction networks by integer quadratic programming. Bioinformatics. 2007, 23: 1631-1639. 10.1093/bioinformatics/btm156.

Zaslavskiy M, Bach F, Vert JP: Global alignment of protein-protein interaction networks by graph matching methods. Bioinformatics. 2009, 25: i259-1267. 10.1093/bioinformatics/btp196.

Haussler D: Convolutional kernels on discrete structures. Technical Report. 1999, Computer Science Department, UC Santa Cruz

Gartner T, Flach P, Wrobel S: On graph kernels: Hardness results and efficient alternatives. Proc Annual Conf Computational Learning Theory. 2003, 129-143.

Kuramochi M, Karypis G: An efficient algorithm for discovering frequent subgraphs. Technical Report. 2002, University of Minnesota, Department of Computer Science, 2-26.

Yan X, Han J: Graph-based substructure pattern mining. Proceedings of 2002 International Conference on Data Mining. 2002, 721-724.

Ketkar NS, Holder LB, Cook DJ: Subdue: Compression-based frequent pattern discovery in graph data. OSDM. 2005

Lloyd SP: Least square quantization in pcm. IEEE Transactions on Information Theory. 1982, 28: 129-137. 10.1109/TIT.1982.1056489.

Goldberg AV: Finding a maximum density subgraph. Technical Report. 1984, University of California, Berkeley, CA

Ng AY, Jordan MI, Weiss Y: On spectral clustering: Analysis and an algorithm. Proceedings of Advances in Neural Information Processing Systems. 2001, 849-856.

King AD, Przulj N, Jurisica I: Protein complex prediction via cost-based clustering. Bioinformatics. 2004, 20: 3013-3020. 10.1093/bioinformatics/bth351.

Jiang P, Singh M: Spici: a fast clustering algorithm for large biological networks. Bioinformatics. 2010, 26: 1105-1111. 10.1093/bioinformatics/btq078.

Le TV, Kulikowski CA, Muchnik IB: Coring method for clustering a graph. Proceedings of ICPR. 2008

Rhodes DR, Yu J, Shanker K: Oncomine: A cancer microarray database and integrated data-mining platform. Neoplasia. 2004, 6: 1-6.

Guda C, King BR, Pal LR, Guda P: A Top-Down Approach to Infer and Compare Domain-Domain Interactions across Eight Model Organisms. PLoS ONE. 2009, 4: e5096-10.1371/journal.pone.0005096.

Kerrien S, Aranda B, Breuza L: The IntAct molecular interaction database in 2012. Nucleic Acids Res. 2012, 40: D841-D846. 10.1093/nar/gkr1088.

Chatr-aryamontri A, Ceol A, Palazzi LM: MINT: the Molecular INTeraction database. Nucleic Acids Res. 2006, 35: D572-D574. 10.1093/nar/gkl1094.

Prasad TSK, Goel R, Kandasamy K: Human Protein Reference Database - 2009 Update. Nucleic Acids Res. 2009, 37: D767-772. 10.1093/nar/gkn892.

Xenarios I, Rice DW, Salwinski L: DIP: the Database of Interacting Proteins. Nucleic Acids Res. 2000, 28: 289-291. 10.1093/nar/28.1.289.

Bader GD: Design and use of the Biomolecular Interaction Network Database (BIND) for storing and analyzing protein-protein interaction data. PhD thesis. 2003, Graduate Department of Biochemistry, University of Toronto

Altschul SF, Gish W, Miller W, Myers EW, Lipman DJ: Basic local alignment search tool. J Mol Biol. 1990, 215: 403-410.

Hartke SG, Radcliffe AJ: Mckay's canonical graph labeling algorithm. Contemporary Mathematics book series. 2009, 479: 99-111.

Page L, Brin S, Motwani R, Winograd T: The pagerank citation ranking: Bringing order to the web. Proceedings of the 7th International World Wide Web Conference. 1998, 161-172.

Shannon P, Markiel A, Ozier O: Cytoscape: a software environment for integrated models of biomolecular interaction networks. Genome Res. 2003, 13: 2498-2504. 10.1101/gr.1239303.

Guda P, Chittur SV, Guda C: Comparative Analysis of Protein-Protein Interactions in Cancer-Associated Genes. Genomics, Proteomics, Bioinformatics. 2009, 7: 25-36. 10.1016/S1672-0229(08)60030-3.

Brown KR, Jurisica I: Online predicted human interaction database. Bioinformatics. 2005, 21: 2076-2082. 10.1093/bioinformatics/bti273.

Wang JZ, Du Z, Payattakool R, Yu PS, Chen CF: A new method to measure the semantic similarity of GO terms. Bioinformatics. 2007, 23: 1274-1281. 10.1093/bioinformatics/btm087.

Schlossmacher GA, Stevens A, White A: Glucocorticoid receptor mediated apoptosis: mechanisms of resistance in cancer cells. J Endocrinol. 2011, 211: 17-25. 10.1530/JOE-11-0135.

Limbourg FP, Liao JK: Nontranscriptional actions of the glucocorticoid receptor. J Mol Med. 2003, 81: 168-174.

Van Beekum O, Kalkhoven E: Aberrant forms of histone acetyltransferases in human disease. Subcell Biochem. 2007, 41: 233-262.

York B, O'Malley BW: Steroid receptor coactivator (SRC) Family: Masters of Systems Biology. J Biol Chem. 2010, 285: 38743-38750. 10.1074/jbc.R110.193367.

Xu J, Wu RC, O'Malley BW: Normal and cancer-related functions of the p160 steroid receptor co-activator (SRC) family. Nat Rev Cancer. 2009, 9: 615-630. 10.1038/nrc2695.

Iyer NG, Ozdag H, Caldas C: p300/CBP and cancer. Oncogene. 2004, 23: 4225-4231. 10.1038/sj.onc.1207118.

Mullighan CG, Zhang J, Kasper LH: CREBBP mutations in relapsed acute lymphoblastic leukaemia. Nature. 2011, 471: 235-239. 10.1038/nature09727.

Tang Y, Zhao W, Chen Y, Zhao Y, Gu W: Acetylation is indispensable for p53 activation. Cell. 2008, 133: 612-626. 10.1016/j.cell.2008.03.025.

Ferreon JC, Lee CW, Arai M, Martinez-Yamout MA, Dyson HJ, Wright PE: Cooperative regulation of p53 by modulation of ternary complex formation with CBP/p300 and HDM2. Proc Natl Acad Sci USA. 2009, 106: 6591-6596. 10.1073/pnas.0811023106.

Shi D, Pop MS, Kulikov R, Love IM, Kung AL, Grossman SR: CBP and p300 are cytoplasmic E4 polyubiquitin ligases for p53. Proc Natl Acad Sci USA. 2009, 106: 16275-16280. 10.1073/pnas.0904305106.

Salicioni AM, Xi M, Vanderveer LA, Balsara B, Testa JR, Dunbrack RL, Godwin AK: Identification and structural analysis of human RBM8A and RBM8B: two highly conserved RNA-binding motif proteins that interact with OVCA1, a candidate tumor suppressor. Genomics. 2000, 69: 54-62. 10.1006/geno.2000.6315.

Pawlak G, Helfman DM: Cytoskeletal changes in cell transformation and tumorigenesis. Curr Opin Genet Dev. 2001, 11: 41-47. 10.1016/S0959-437X(00)00154-4.

Jordan MA, Wilson L: Microtubules and actin filaments: dynamic targets for cancer chemotherapy. Curr Opin Cell Biol. 1998, 10: 123-130. 10.1016/S0955-0674(98)80095-1.

Eilers M, Eisenman RN: Myc's broad reach. Genes Dev. 2008, 22: 2755-2766. 10.1101/gad.1712408.

Patel JH, Loboda AP, Showe MK, Showe LC, McMahon SB: Analysis of genomic targets reveals complex functions of MYC. Nat Rev Cancer. 2004, 4: 562-568. 10.1038/nrc1393.

Staller P, Peukert K, Kiermaier A, Seoane J, Lukas J, Karsunky H: Repression of p15INK4b expression by Myc through association with Miz-1. Nat Cell Biol. 2001, 3: 392-399. 10.1038/35070076.

Zeller KI, Zhao X, Lee CW, Chiu KP, Yao F, Yustein JT: Global mapping of c-Myc binding sites and target gene networks in human B cells. Proc Natl Acad Sci USA. 2006, 103: 17834-17839. 10.1073/pnas.0604129103.

Thông tin
Thông tin xuất bản

BMC Systems Biology

Tập 6

1-14

Thông tin tác giả