Nothing Special   »   [go: up one dir, main page]
Skip to main content

Advertisement

Springer Nature Link
Log in

Essential proteins in cancer networks: a graph-based perspective using Dijkstra’s algorithm

  • Original Article
  • Published:
Network Modeling Analysis in Health Informatics and Bioinformatics Aims and scope Submit manuscript

Abstract

Identifying essential proteins within cancer-related PPI networks is a significant challenge due to the heterogeneity and complexity of cancer diseases. Identifying these proteins is crucial for developing effective therapeutic strategies and understanding cancer biology. This study introduces a novel graph-based approach to identify essential cancer proteins within PPI networks, focusing on breast, lung, colorectal, and ovarian cancers. The proposed methodology involves a multi-step process beginning with identifying and preprocessing common genes associated with breast, colorectal, lung, and ovarian cancers. The PPI networks are constructed using these common genes. The PPI networks are analyzed to find the shortest paths using centrality measures. Centrality measures, particularly betweenness centrality, prioritize proteins with the highest impact on cancer progression. Betweenness centrality is used as a threshold to exclude nonessential proteins. The identified proteins are validated and categorized into cancer-related pathways through permutation and enrichment tests. The proposed approach successfully identified 64 essential proteins across breast, lung, colorectal, and ovarian cancers. These proteins were categorized into 14 cancer-related pathways, including cell cycle regulation, Wnt/\(\beta \)-Catenin signaling, RTK/RAS/RAF/MEK/ERK signaling, and PI3K/AKT/mTOR signaling. The identified pathways highlight complex interactions of these proteins, pivotal functions in cancer progression, and therapeutic targets. The validation process, through permutation and enrichment tests, confirmed the robustness and relevance of these findings, indicating their significant impact on understanding and potentially treating cancer. Identifying essential cancer proteins using this novel graph-based approach has significant clinical relevance, particularly for precision medicine. These findings can guide personalized treatment strategies and enhance the understanding of cancer biology. Future research will extend this methodology to other types of cancers and clinical applicability.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Algorithm 1
Algorithm 2
Fig. 5
Algorithm 3
Algorithm 4
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11

Similar content being viewed by others

References

  • Ahmed MR, Rehana H, Asaduzzaman S (2021) Protein interaction network and drug design of stomach cancer and associated disease: a bioinformatics approach. J Proteins Proteomics 12:33–43

    Article  Google Scholar 

  • Amala A, Emerson IA (2019) Identification of target genes in cancer diseases using protein-protein interaction networks. Netw Model Anal Health Inform Bioinform 8:1–13

    Article  Google Scholar 

  • Amanatidou AI, Dedoussis GV (2021) Construction and analysis of protein-protein interaction network of non-alcoholic fatty liver disease. Comput Biol Med 131:104243

    Article  Google Scholar 

  • Chen C, Shen H, Zhang LG et al (2016) Construction and analysis of protein-protein interaction networks based on proteomics data of prostate cancer. Int J Mol Med 37(6):1576–1586

    Article  Google Scholar 

  • Chen J, Cai Y, Xu R et al (2020) Identification of four hub genes as promising biomarkers to evaluate the prognosis of ovarian cancer in silico. Cancer Cell Int 20:1–11

    Google Scholar 

  • Chen L, Chu C, Kong X et al (2015) Discovery of new candidate genes related to brain development using protein interaction information. PLoS One 10(1):e0118003

    Article  Google Scholar 

  • Chen L, Hao Xing Z, Huang T et al (2016) Application of the shortest path algorithm for the discovery of breast cancer-related genes. Curr Bioinform 11(1):51–58

    Article  Google Scholar 

  • Chen L, Yang J, Huang T et al (2016) Mining for novel tumor suppressor genes using a shortest path approach. J Biomol Struct Dyn 34(3):664–675

    Article  Google Scholar 

  • Chen L, Zhang YH, Huang T et al (2016) Identifying novel protein phenotype annotations by hybridizing protein-protein interactions and protein sequence similarities. Mol Genet Genomics 291(2):913–934

    Article  Google Scholar 

  • Chen SJ, Liao DL, Chen CH et al (2019) Construction and analysis of protein-protein interaction network of heroin use disorder. Sci Rep 9(1):1–9

    Google Scholar 

  • Dalkılıç F, Işik Z (2021) Compound target identification in tissue-specific interaction networks. IEEE Access 9:81702–81716

    Article  Google Scholar 

  • Failli M, Paananen J, Fortino V (2019) Prioritizing target-disease associations with novel safety and efficacy scoring methods. Sci Rep 9(1):9852

    Article  Google Scholar 

  • Gormen T (1990) Leiserson, rivest r. introduction to algorithms

  • Gui T, Dong X, Li R et al (2015) Identification of hepatocellular carcinoma-related genes with a machine learning and network analysis. J Comput Biol 22(1):63–71

    Article  Google Scholar 

  • Guo X, Gao L, Wei C et al (2011) A computational method based on the integration of heterogeneous networks for predicting disease-gene associations. PloS one 6(9):e24171

    Article  Google Scholar 

  • Hanahan D (2022) Hallmarks of cancer: new dimensions. Cancer Discovery 12(1):31–46

    Article  Google Scholar 

  • Hasan MR, Paul BK, Ahmed K et al (2020) Design protein-protein interaction network and protein-drug interaction network for common cancer diseases: a bioinformatics approach. Inform Med Unlocked 18:100311

    Article  Google Scholar 

  • He B, Tang J, Ding Y et al (2011) Mining relational paths in integrated biomedical data. PLoS One 6(12):e27506

    Article  Google Scholar 

  • Huang DW, Sherman BT, Tan Q et al (2007) The david gene functional classification tool: a novel biological module-centric algorithm to functionally analyze large gene lists. Genome Biol 8(9):1–16

    Article  Google Scholar 

  • INSTITUTE NC (2022) Network-based analysis in cancer research. https://www.ocg.cancer.gov/e-newsletter-issue/issue-8/network-based-analysis-cancer-research, data as per NIH

  • Jafari S, Ravan M, Karimi-Sani I, et al (2023) Screening and identification of potential biomarkers for pancreatic cancer: an integrated bioinformatics analysis. Pathology-Research and Practice p 154726

  • Jeong H, Mason SP, Barabási AL et al (2001) Lethality and centrality in protein networks. Nature 411(6833):41–42

    Article  Google Scholar 

  • Jiang M, Chen Y, Zhang Y et al (2013) Identification of hepatocellular carcinoma related genes with k-th shortest paths in a protein-protein interaction network. Mol BioSyst 9(11):2720–2728

    Article  Google Scholar 

  • Karaoz U, Murali T, Letovsky S et al (2004) Whole-genome annotation by using evidence integration in functional-linkage networks. Proc Natl Acad Sci 101(9):2888–2893

    Article  Google Scholar 

  • Li BQ, Huang T, Liu L et al (2012) Identification of colorectal cancer related genes with mrmr and shortest path in protein-protein interaction network. PloS one 7(4):e33393

    Article  Google Scholar 

  • Li BQ, You J, Chen L, et al (2013) Identification of lung-cancer-related genes with the shortest path approach in a protein-protein interaction network. BioMed research international 2013

  • Li Z, Zhou Y, Tian G et al (2021) Identification of core genes and key pathways in gastric cancer using bioinformatics analysis. Russian J Genet 57(8):963–971

    Article  Google Scholar 

  • Lu XQ, Zhang JQ, Zhang SX et al (2021) Identification of novel hub genes associated with gastric cancer using integrated bioinformatics analysis. BMC Cancer 21:1–17

    Article  Google Scholar 

  • Masood MMD, Manjula D, Sugumaran V (2018) Identification of new disease genes from protein–protein interaction network. Journal of Ambient Intelligence and Humanized Computing pp 1–9

  • Mering CV, Huynen M, Jaeggi D et al (2003) String: a database of predicted functional associations between proteins. Nucl Acids Res 31(1):258–261

    Article  Google Scholar 

  • Murphy M, Brown G, Wallin C, et al (2021) Gene help: integrated access to genes of genomes in the reference sequence collection. In: Gene Help [Internet]. National Center for Biotechnology Information (US)

  • Nabieva E, Jim K, Agarwal A, et al (2005) Whole-proteome prediction of protein function via graph-theoretic analysis of interaction maps. Bioinformatics 21(suppl_1):i302–i310

  • Nithya C, Kiran M, Nagarajaram HA (2023) Dissection of hubs and bottlenecks in a protein-protein interaction network. Comput Biol Chem 102:107802

    Article  Google Scholar 

  • Ramadan E, Alinsaif S, Hassan MR (2016) Network topology measures for identifying disease-gene association in breast cancer. BMC Bioinform 17:473–480

    Article  Google Scholar 

  • Ran J, Li H, Fu J et al (2013) Construction and analysis of the protein-protein interaction network related to essential hypertension. BMC Syst Biol 7:1–12

    Article  Google Scholar 

  • Rangarajan PK, Gurusamy BM, Rajasekar E, et al (2023) Retroactive data structure for protein–protein interaction in lung cancer using dijkstra algorithm. Int J Inform Technol pp 1–13

  • Rangarajan PK, Gurusamy BM, Rajasekar E et al (2024) Retroactive data structure for protein-protein interaction in lung cancer using dijkstra algorithm. Int J Inform Technol 16(2):1239–1251

    Google Scholar 

  • Rout T, Mohapatra A, Kar M (2024) A systematic review of graph-based explorations of ppi networks: methods, resources, and best practices. Netw Model Anal Health Inform Bioinform 13(1):29

    Article  Google Scholar 

  • Rual JF, Venkatesan K, Hao T et al (2005) Towards a proteome-scale map of the human protein-protein interaction network. Nature 437(7062):1173–1178

    Article  Google Scholar 

  • Stelzl U, Worm U, Lalowski M et al (2005) A human protein-protein interaction network: a resource for annotating the proteome. Cell 122(6):957–968

    Article  Google Scholar 

  • Szklarczyk D, Franceschini A, Wyder S et al (2015) String v10: protein-protein interaction networks, integrated over the tree of life. Nucl Acids Res 43(D1):D447–D452

    Article  Google Scholar 

  • Taz TA, Kawsar M, Paul BK et al (2020) Computational analysis of regulatory genes network pathways among devastating cancer diseases. J Proteins Proteomics 11(1):63–76

    Article  Google Scholar 

  • Teulière J, Bernard C, Corel E et al (2023) Network analyses unveil ageing-associated pathways evolutionarily conserved from fungi to animals. GeroScience 45(2):1059–1080

    Article  Google Scholar 

  • Tumuluru P, Ravi B (2017) Dijkstra’s based identification of lung cancer related genes using ppi networks. Int J Comput Appl 975:8887

    Google Scholar 

  • Viale PH (2020) The american cancer society’s facts & figures: 2020 edition. Journal of the Advanced Practitioner in Oncology 11(2):135

  • Wahab Khattak F, Salamah Alhwaiti Y, Ali A, et al (2021) Protein-protein interaction analysis through network topology (oral cancer). J Healthcare Eng 2021

  • Wang S, Huang G, Hu Q, et al (2016) A network-based method for the identification of putative genes related to infertility. Biochimica et Biophysica Acta (BBA)-General Subjects 1860(11):2716–2724

  • Wen CG, Liu JX, Qin L, et al (2020) Essential proteins identification based on integrated network. In: Intelligent Computing Theories and Application: 16th International Conference, ICIC 2020, Bari, Italy, October 2–5, 2020, Proceedings, Part I 16, Springer, pp 81–91

  • Yang D, He Y, Wu B et al (2020) Integrated bioinformatics analysis for the screening of hub genes and therapeutic drugs in ovarian cancer. J Ovarian Res 13:1–18

    Article  Google Scholar 

  • Yang L, Wang J, Wang H et al (2014) Analysis and identification of essential genes in humans using topological properties and biological information. Gene 551(2):138–151

    Article  Google Scholar 

  • Yu H, Kim PM, Sprecher E et al (2007) The importance of bottlenecks in protein networks: correlation with gene essentiality and expression dynamics. PLoS Comput Biol 3(4):e59

    Article  MathSciNet  Google Scholar 

  • Zhang J, Jiang M, Yuan F, et al (2013) Identification of age-related macular degeneration related genes by applying shortest path algorithm in protein-protein interaction network. BioMed research international 2013

  • Zhang J, Suo Y, Zhang YH, et al (2016a) Mining for genes related to choroidal neovascularization based on the shortest path algorithm and protein interaction information. Biochimica et Biophysica Acta (BBA)-General Subjects 1860(11):2740–2749

  • Zhang YH, Chu C, Wang S et al (2016) The use of gene ontology term and kegg pathway enrichment for analysis of drug half-life. PLoS One 11(10):e0165496

    Article  Google Scholar 

Download references

Acknowledgements

We gratefully acknowledge the computational resources provided by the DST-FIST Bioinformatics Lab at IIIT Bhubaneswar for conducting this study.

Author information

Authors and Affiliations

  1. Department of Computer Science, IIIT, Bhubaneswar, 751003, Odisha, India

    Trilochan Rout & Anjali Mohapatra

  2. Department Surgical Oncology, AIIMS, Bhubaneswar, 751003, Odisha, India

    Madhabananda Kar & Dillip Kumar Muduly

Authors
  1. Trilochan Rout
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Anjali Mohapatra
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Madhabananda Kar
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Dillip Kumar Muduly
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Trilochan Rout.

Ethics declarations

Conflict of interest

On behalf of all authors, the corresponding author confirms that there are no Conflict of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Rout, T., Mohapatra, A., Kar, M. et al. Essential proteins in cancer networks: a graph-based perspective using Dijkstra’s algorithm. Netw Model Anal Health Inform Bioinforma 13, 42 (2024). https://doi.org/10.1007/s13721-024-00477-y

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s13721-024-00477-y

Keywords

Search

Navigation