{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T07:42:49Z","timestamp":1776325369802,"version":"3.50.1"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,3,16]],"date-time":"2021-03-16T00:00:00Z","timestamp":1615852800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"},{"start":{"date-parts":[[2021,3,16]],"date-time":"2021-03-16T00:00:00Z","timestamp":1615852800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"National Science Foundation","award":["RII Track-2 FEC 1826834"],"award-info":[{"award-number":["RII Track-2 FEC 1826834"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BioData Mining"],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Background<\/jats:title>\n                    <jats:p>Given a collection of coexpression networks over a set of genes, identifying subnetworks that appear frequently is an important research problem known as mining frequent subgraphs. Maximal frequent subgraphs are a representative set of frequent subgraphs; A frequent subgraph is maximal if it does not have a super-graph that is frequent. In the bioinformatics discipline, methodologies for mining frequent and\/or maximal frequent subgraphs can be used to discover interesting network motifs that elucidate complex interactions among genes, reflected through the edges of the frequent subnetworks. Further study of frequent coexpression subnetworks enhances the discovery of biological modules and biological signatures for gene expression and disease classification.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>We propose a reverse search algorithm, called RASMA, for mining frequent and maximal frequent subgraphs in a given collection of graphs. A key innovation in RASMA is a connected subgraph enumerator that uses a reverse-search strategy to enumerate connected subgraphs of an undirected graph. Using this enumeration strategy, RASMA obtains all maximal frequent subgraphs very efficiently. To overcome the computationally prohibitive task of enumerating all frequent subgraphs while mining for the maximal frequent subgraphs, RASMA employs several pruning strategies that substantially improve its overall runtime performance. Experimental results show that on large gene coexpression networks, the proposed algorithm efficiently mines biologically relevant maximal frequent subgraphs.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Conclusion<\/jats:title>\n                    <jats:p>Extracting recurrent gene coexpression subnetworks from multiple gene expression experiments enables the discovery of functional modules and subnetwork biomarkers. We have proposed a reverse search algorithm for mining maximal frequent subnetworks. Enrichment analysis of the extracted maximal frequent subnetworks reveals that subnetworks that are frequent are highly enriched with known biological ontologies.<\/jats:p>\n                  <\/jats:sec>","DOI":"10.1186\/s13040-021-00250-1","type":"journal-article","created":{"date-parts":[[2021,3,16]],"date-time":"2021-03-16T06:03:44Z","timestamp":1615874624000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["RASMA: a reverse search algorithm for mining maximal frequent subgraphs"],"prefix":"10.1186","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6478-4674","authenticated-orcid":false,"given":"Saeed","family":"Salem","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohammed","family":"Alokshiya","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohammad Al","family":"Hasan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,3,16]]},"reference":[{"issue":"6","key":"250_CR1","doi-asserted-by":"publisher","first-page":"1085","DOI":"10.1101\/gr.1910904","volume":"14","author":"HK Lee","year":"2004","unstructured":"Lee HK, Hsu AK, Sajdak J, Qin J, Pavlidis P. Coexpression analysis of human genes across many microarray data sets. Genome Res. 2004; 14(6):1085\u201394.","journal-title":"Genome Res"},{"issue":"Suppl 1","key":"250_CR2","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1093\/bioinformatics\/bti1049","volume":"21","author":"H Hu","year":"2005","unstructured":"Hu H, Yan X, Huang Y, Zhou XJ. Mining coherent dense subgraphs across massive biological networks for functional discovery. Bioinformatics. 2005; 21(Suppl 1):213\u201321.","journal-title":"Bioinformatics"},{"issue":"6","key":"250_CR3","doi-asserted-by":"publisher","first-page":"1001106","DOI":"10.1371\/journal.pcbi.1001106","volume":"7","author":"W Li","year":"2011","unstructured":"Li W, Liu C-C, Zhang T, Li H, Waterman MS, Zhou XJ. Integrative analysis of many weighted co-expression networks using tensor computation. PLoS Comput Biol. 2011; 7(6):1001106.","journal-title":"PLoS Comput Biol"},{"issue":"Suppl 1","key":"250_CR4","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1093\/bioinformatics\/18.suppl_1.S233","volume":"18","author":"T Ideker","year":"2002","unstructured":"Ideker T, Ozier O, Schwikowski B, Siegel AF. Discovering regulatory and signalling circuits in molecular interaction networks. Bioinformatics. 2002; 18(Suppl 1):233\u201340.","journal-title":"Bioinformatics"},{"key":"250_CR5","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1038\/msb4100180","volume":"3","author":"H Chuang","year":"2007","unstructured":"Chuang H, Lee E, Liu Y, Lee D, Ideker T. Network-based classification of breast cancer metastasis. Mol Syst Biol. 2007; 3:140.","journal-title":"Mol Syst Biol"},{"key":"250_CR6","doi-asserted-by":"crossref","unstructured":"Li J, Zhou D, Qiu W, Shi Y, Yang J-J, Chen S, Wang Q, Pan H. Application of weighted gene co-expression network analysis for data from paired design. Sci Rep. 2018; 8(622).","DOI":"10.1038\/s41598-017-18705-z"},{"issue":"7","key":"250_CR7","doi-asserted-by":"publisher","first-page":"1299","DOI":"10.1089\/cmb.2006.13.1299","volume":"13","author":"M Koyut\u00fcrk","year":"2006","unstructured":"Koyut\u00fcrk M, Kim Y, Subramaniam S, Szpankowski W, Grama A. Detecting conserved interaction patterns in biological networks. J Comput Biol. 2006; 13(7):1299\u2013322.","journal-title":"J Comput Biol"},{"key":"250_CR8","unstructured":"Kuramochi M, Karypis G. Frequent subgraph discovery. In: Proceedings of International Conference on Data Mining ICDM \u201902: 2001. p. 313\u201320."},{"key":"250_CR9","unstructured":"Yan X, Han J. gSpan: graph-based substructure pattern mining. In: Proceedings of International Conference on Data Mining ICDM \u201902: 2002. p. 721\u20134."},{"issue":"1","key":"250_CR10","first-page":"77","volume":"127","author":"S Nijssen","year":"2005","unstructured":"Nijssen S, Kok JN. The gaston tool for frequent subgraph mining. Proc Int Work Graph-Based Tools. 2005; 127(1):77\u201387.","journal-title":"Proc Int Work Graph-Based Tools"},{"issue":"Suppl 1","key":"250_CR11","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1093\/bioinformatics\/bth919","volume":"20","author":"M Koyut\u00fcrk","year":"2004","unstructured":"Koyut\u00fcrk M, Grama A, Szpankowski W. An efficient algorithm for detecting frequent subgraphs in biological networks. Bioinformatics. 2004; 20(Suppl 1):200\u20137.","journal-title":"Bioinformatics"},{"key":"250_CR12","volume-title":"Algorithms and data structure. WADS 2015. Lecture Notes in Computer Science, vol 9214","author":"T Uno","year":"2015","unstructured":"Uno T. Constant time enumeration by amortization In: Dehne F, Sack JR, Stege U, editors. Algorithms and data structure. WADS 2015. Lecture Notes in Computer Science, vol 9214. Cham: Springer Cham: 2015. p. 593\u2013605."},{"issue":"1","key":"250_CR13","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/0166-218X(95)00026-N","volume":"65","author":"D Avis","year":"1996","unstructured":"Avis D, Fukuda K. Reverse search for enumeration. Discret Appl Math. 1996; 65(1):21\u201346.","journal-title":"Discret Appl Math"},{"key":"250_CR14","doi-asserted-by":"crossref","unstructured":"Eppstein D. All maximal independent sets and dynamic dominance for sparse graphs. ACM Trans Algorithm. 2009; 5(4).","DOI":"10.1145\/1597036.1597042"},{"issue":"4","key":"250_CR15","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1109\/TCBB.2006.51","volume":"3","author":"S Wernicke","year":"2006","unstructured":"Wernicke S. Efficient detection of network motifs. IEEE\/ACM Trans Comput Biol Bioinforma. 2006; 3(4):347\u201359.","journal-title":"IEEE\/ACM Trans Comput Biol Bioinforma"},{"key":"250_CR16","doi-asserted-by":"crossref","unstructured":"Kashani ZRM, Ahrabian H, Elahi E, Nowzari-Dalini A, Ansari ES, Asadi S, Mohammadi S, Schreiber F, Masoudi-Nejad A. Kavosh: a new algorithm for finding network motifs. BMC Bioinformatics. 2009; 10(1).","DOI":"10.1186\/1471-2105-10-318"},{"key":"250_CR17","doi-asserted-by":"crossref","unstructured":"Komusiewicz C, Sommer F. Enumerating connected induced subgraphs: Improved delay and experimental comparison. Discret Appl Math. 2020. https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0166218X20302377.","DOI":"10.1016\/j.dam.2020.04.036"},{"issue":"12","key":"250_CR18","first-page":"319","volume":"20","author":"M Alokshyia","year":"2019","unstructured":"Alokshyia M, Salem S, Abed F. A linear delay algorithm for enumerating all connected induced subgraphs. Bioinformatics. 2019; 20(12):319.","journal-title":"Bioinformatics"},{"key":"250_CR19","volume-title":"Technical Report E4","author":"T Uno","year":"2003","unstructured":"Uno T. Two general methods to reduce delay and change of enumeration algorithms. In: Technical Report E4. Japan: National Institute of Informatics: 2003."},{"issue":"5","key":"250_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1371\/journal.pcbi.1004220","volume":"11","author":"E Pierson","year":"2015","unstructured":"Pierson E, GTEx Consortium, Koller D, Battle A, Mostafavi S. Sharing and specificity of co-expression networks across 35 human tissues. PLOS Comput Biol. 2015; 11(5):1\u201319.","journal-title":"PLOS Comput Biol"},{"issue":"43","key":"250_CR21","doi-asserted-by":"publisher","first-page":"15545","DOI":"10.1073\/pnas.0506580102","volume":"102","author":"A Subramanian","year":"2005","unstructured":"Subramanian A, Tamayo P, Mootha VK, Mukherjee S, Ebert BL, Gillette MA, Paulovich A, Pomeroy SL, Golub TR, Lander ES, Mesirov JP. Gene set enrichment analysis: A knowledge-based approach for interpreting genome-wide expression profiles. Proc Natl Acad Sci. 2005; 102(43):15545\u201350.","journal-title":"Proc Natl Acad Sci"},{"issue":"6","key":"250_CR22","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1016\/j.cels.2015.12.004","volume":"1","author":"A Liberzon","year":"2015","unstructured":"Liberzon A, Birger C, Thorvaldsd\u00f3ttir H, Ghandi M, Mesirov J, Tamayo P. The molecular signatures database hallmark gene set collection. Cell Syst. 2015; 1(6):417\u201325.","journal-title":"Cell Syst"},{"issue":"3","key":"250_CR23","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1002\/mc.20376","volume":"47","author":"M Lara","year":"2008","unstructured":"Lara M, Garc\u00eda-Escudero R, Ruiz S, Santos M, Moral M, Mart\u00ednez-Cruz A, Segrelles C, Lorz C, Paramio J. Gene profiling approaches help to define the specific functions of retinoblastoma family in epidermis. Mol Carcinog. 2008; 47(3):209\u201321.","journal-title":"Mol Carcinog"},{"issue":"20","key":"250_CR24","doi-asserted-by":"publisher","first-page":"17873","DOI":"10.18632\/oncotarget.4286","volume":"6","author":"P Indovina","year":"2015","unstructured":"Indovina P, Pentimalli F, Casini N, Vocca I, Giordano A. RB1 dual role in proliferation and apoptosis: Cell fate control and implications for cancer therapy. Oncotarget. 2015; 6(20):17873\u201390.","journal-title":"Oncotarget"},{"issue":"12","key":"250_CR25","doi-asserted-by":"publisher","first-page":"2006","DOI":"10.1016\/j.celrep.2015.02.059","volume":"10","author":"R Cook","year":"2015","unstructured":"Cook R, Zoumpoulidou G, Luczynski MT, Rieger S, Moquet J, Spanswick VJ, Hartley JA, Rothkamm K, Huang PH, Mittnacht S. Direct involvement of retinoblastoma family proteins in dna repair by Non-homologous End-joining. Cell Rep. 2015; 10(12):2006\u201318.","journal-title":"Cell Rep"},{"key":"250_CR26","doi-asserted-by":"crossref","unstructured":"Ma Y, Croxton R, Jr RLM, Cress WD. Identification of novel E2F1-regulated genes by microarray. Arch Biochem Biophys. 2002; 399(2):212\u201324.","DOI":"10.1006\/abbi.2002.2761"},{"issue":"7","key":"250_CR27","doi-asserted-by":"publisher","first-page":"3903","DOI":"10.1158\/0008-5472.CAN-05-4363","volume":"66","author":"CJ Creighton","year":"2006","unstructured":"Creighton CJ, Hilger AM, Murthy S, Rae JM, Chinnaiyan AM, El-Ashry D. Activation of mitogen-activated protein kinase in estrogen receptor alpha-positive breast cancer cells in vitro induces an in vivo molecular phenotype of estrogen receptor alpha-negative human breast tumors. Cancer Res. 2006; 66(7):3903\u201311.","journal-title":"Cancer Res"}],"container-title":["BioData Mining"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13040-021-00250-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1186\/s13040-021-00250-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1186\/s13040-021-00250-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,16]],"date-time":"2021-03-16T06:05:11Z","timestamp":1615874711000},"score":1,"resource":{"primary":{"URL":"https:\/\/biodatamining.biomedcentral.com\/articles\/10.1186\/s13040-021-00250-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,16]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["250"],"URL":"https:\/\/doi.org\/10.1186\/s13040-021-00250-1","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-46148\/v3","asserted-by":"object"},{"id-type":"doi","id":"10.21203\/rs.3.rs-46148\/v2","asserted-by":"object"},{"id-type":"doi","id":"10.21203\/rs.3.rs-46148\/v1","asserted-by":"object"}]},"ISSN":["1756-0381"],"issn-type":[{"value":"1756-0381","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,3,16]]},"assertion":[{"value":"19 July 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 February 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 March 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Not applicable","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethics approval and consent to participate"}},{"value":"Not applicable","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Consent for publication"}},{"value":"The authors declare that they have no competing interests.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"19"}}