In the maximum common subgraph (MCS) problem, we are given a pair of graphs and asked to find the largest induced subgraph common to them both. With its plethora of applications, MCS is a familiar and challenging problem. Many algorithms exist that can deliver optimal MCS solutions, but whose asymptotic worst-case run times fail to do better than mere brute-force, which is exponential in the order of the smaller graph. In this paper, we present a faster solution to MCS. We transform an essential part of the search process into the task of enumerating maximal independent sets in only a part of only one of the input graphs. This is made possible by exploiting an efficient decomposition of a graph into a minimum vertex cover and the maximum independent set in its complement. The result is an algorithm whose run time is bounded by a function exponential in the order of the smaller cover rather than in the order of the smaller graph.

Background: Prostate cancer (PrC) is the second-most frequent cancer in men, its incidence is emerging globally and is the fifth leading cause of death worldwide. While diagnosis and prognosis of PrC have been studied well, the associated therapeutic biomarkers have not yet been investigated comprehensively. This systematic review and meta-analysis aim to evaluate the theragnostic effects of microRNA expressions on chemoresistance in prostate cancer and to analyse the utility of miRNAs as clinical theragnostic biomarkers. Methods: A systematic literature search for studies reporting miRNA expressions and their role in chemoresistance in PrC published until 2018 was collected from bibliographic databases. The evaluation of data was performed as per PRISMA guidelines for systematic review and meta-analysis. Meta-analysis was performed using a random-effects model using Comprehensive Meta-Analysis (CMA) software. Heterogeneity between studies was analysed using Cochran’s Q test, I² and the Tau statistic. Quality assessment of the studies was performed using the Newcastle–Ottawa Scale (NOS) for the methodological assessment of cohort studies. Publication bias was assessed using Egger’s bias indicator test, Orwin and classic fail-safe N test, Begg and Mazumdar rank collection test, and Duval and Tweedie’s trim and fill methods. Findings: Out of 2909 studies retrieved, 79 studies were shortlisted and reviewed. A total of 17 studies met our eligibility criteria, from which 779 PrC patients and 17 chemotherapy drugs were examined, including docetaxel and paclitaxel. The majority of the drug regulatory genes reported were involved in cell survival, angiogenesis and cell proliferation pathways. We studied 42 miRNAs across all studies, out of which two miRNAs were found to be influencing chemosensitivity, while 21 were involved in chemoresistance. However, the remaining 19 miRNAs did not appear to have any theragnostic effects. Besides, the prognostic impact of the miRNAs was evaluated and had a pooled HR value of 1.960 with 95% CI (1.377–2.791). Interpretation: The observation of the current study depicts the significance of miRNA expression as a theragnostic biomarker in medical oncology. This review suggests the involvement of specific miRNAs as predictors of chemoresistance and sensitivity in PrC. Hence, the current systematic review and meta-analysis provide insight on the use of miRNA as PrC biomarkers, which can be harnessed as molecular candidates for therapeutic targeting.