{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T02:21:07Z","timestamp":1787019667966,"version":"3.56.0"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1","content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["BMC Bioinformatics"],"published-print":{"date-parts":[[2014,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:sec>\n                    <jats:title>Background<\/jats:title>\n                    <jats:p>Integrating and analyzing heterogeneous genome-scale data is a huge algorithmic challenge for modern systems biology. Bipartite graphs can be useful for representing relationships across pairs of disparate data types, with the interpretation of these relationships accomplished through an enumeration of maximal bicliques. Most previously-known techniques are generally ill-suited to this foundational task, because they are relatively inefficient and without effective scaling. In this paper, a powerful new algorithm is described that produces all maximal bicliques in a bipartite graph. Unlike most previous approaches, the new method neither places undue restrictions on its input nor inflates the problem size. Efficiency is achieved through an innovative exploitation of bipartite graph structure, and through computational reductions that rapidly eliminate non-maximal candidates from the search space. An iterative selection of vertices for consideration based on non-decreasing common neighborhood sizes boosts efficiency and leads to more balanced recursion trees.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Results<\/jats:title>\n                    <jats:p>The new technique is implemented and compared to previously published approaches from graph theory and data mining. Formal time and space bounds are derived. Experiments are performed on both random graphs and graphs constructed from functional genomics data. It is shown that the new method substantially outperforms the best previous alternatives.<\/jats:p>\n                  <\/jats:sec>\n                  <jats:sec>\n                    <jats:title>Conclusions<\/jats:title>\n                    <jats:p>\n                      The new method is streamlined, efficient, and particularly well-suited to the study of huge and diverse biological data. A robust implementation has been incorporated into GeneWeaver, an online tool for integrating and analyzing functional genomics experiments, available at\n                      <jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" xlink:href=\"http:\/\/geneweaver.org\" ext-link-type=\"uri\">http:\/\/geneweaver.org<\/jats:ext-link>\n                      . The enormous increase in scalability it provides empowers users to study complex and previously unassailable gene-set associations between genes and their biological functions in a hierarchical fashion and on a genome-wide scale. This practical computational resource is adaptable to almost any applications environment in which bipartite graphs can be used to model relationships between pairs of heterogeneous entities.\n                    <\/jats:p>\n                  <\/jats:sec>","DOI":"10.1186\/1471-2105-15-110","type":"journal-article","created":{"date-parts":[[2014,4,14]],"date-time":"2014-04-14T21:04:19Z","timestamp":1397509459000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":144,"title":["On finding bicliques in bipartite graphs: a novel algorithm and its application to the integration of diverse biological data types"],"prefix":"10.1186","volume":"15","author":[{"given":"Yun","family":"Zhang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Charles A","family":"Phillips","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gary L","family":"Rogers","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Erich J","family":"Baker","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Elissa J","family":"Chesler","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael A","family":"Langston","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2014,4,15]]},"reference":[{"key":"6830_CR1","unstructured":"Malgrange Y: Recherche des sous-matrices premi\u00e8res d\u2019une matrice \u00e0 coefficients binaires. Applications \u00e0 certains probl\u00e8mes de graphe. Proceedings of the Deuxi\u00e8me Congr\u00e8s de l\u2019AFCALTI. Paris: Gauthier-Villars; 1962"},{"issue":"1\u20134","key":"6830_CR2","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1007\/s10472-007-9063-4","volume":"49","author":"A Berry","year":"2007","unstructured":"Berry A, Bordat JP, Sigayret A: A local approach to concept generation. Ann Math Artif Intell. 2007, 49 (1\u20134): 117-136.","journal-title":"Ann Math Artif Intell"},{"key":"6830_CR3","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1080\/09528130210164170","volume":"14","author":"SO Kuznetsov","year":"2002","unstructured":"Kuznetsov SO, Obiedkov S: Comparing performance of algorithms for generating concept lattices. J Exp Theor Artif Intell. 2002, 14: 189-216. 10.1080\/09528130210164170.","journal-title":"J Exp Theor Artif Intell"},{"key":"6830_CR4","first-page":"439","volume-title":"Modelling, Computation and Optimization in Information Systems and Management Sciences, Volume 14 of Communications in Computer and Information Science","author":"M Kaytoue-Uberall","year":"2008","unstructured":"Kaytoue-Uberall M, Duplessis S, Napoli A: Using formal concept analysis for the extraction of groups of co-expressed genes. Modelling, Computation and Optimization in Information Systems and Management Sciences, Volume 14 of Communications in Computer and Information Science. Edited by: Le Thi H, Bouvry P, Pham Dinh T. 2008, Springer Berlin Heidelberg, 439-449."},{"key":"6830_CR5","doi-asserted-by":"publisher","first-page":"1989","DOI":"10.1016\/j.ins.2010.07.007","volume":"181","author":"M Kaytoue","year":"2011","unstructured":"Kaytoue M, Kuznetsovb SO, Napoli A, Duplessis S: Mining gene expression data with pattern structures in formal concept analysis. Inform Sci. 2011, 181: 1989-2001. 10.1016\/j.ins.2010.07.007.","journal-title":"Inform Sci"},{"key":"6830_CR6","first-page":"93","volume-title":"Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology","author":"Y Cheng","year":"2000","unstructured":"Cheng Y, Church GM: Biclustering of expression data. Proceedings of the Eighth International Conference on Intelligent Systems for Molecular Biology. 2000, La Jolla: AAAI Press, 93-103."},{"key":"6830_CR7","doi-asserted-by":"publisher","first-page":"S136","DOI":"10.1093\/bioinformatics\/18.suppl_1.S136","volume":"18","author":"A Tanay","year":"2002","unstructured":"Tanay A, Sharan R, Shamir R: Discovering statistically significant biclusters in gene expression data. Bioinformatics. 2002, 18: S136-S144. 10.1093\/bioinformatics\/18.suppl_1.S136.","journal-title":"Bioinformatics"},{"key":"6830_CR8","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1145\/564691.564737","volume-title":"SIGMOD \u201802: Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data","author":"H Wang","year":"2002","unstructured":"Wang H, Wang W, Yang J, Yu PS: Clustering by pattern similarity in large data sets. SIGMOD \u201802: Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data. 2002, Madison: ACM Press, 394-405."},{"issue":"7","key":"6830_CR9","doi-asserted-by":"publisher","first-page":"1036","DOI":"10.1093\/molbev\/msg115","volume":"20","author":"MJ Sanderson","year":"2003","unstructured":"Sanderson MJ, Driskell AC, Ree RH, Eulenstein O, Langley S: Obtaining maximal concatenated phylogenetic data sets from large sequence databases. Mol Biol Evol. 2003, 20 (7): 1036-1042. 10.1093\/molbev\/msg115.","journal-title":"Mol Biol Evol"},{"key":"6830_CR10","unstructured":"Chesler EJ, Langston MA: Combinatorial genetic regulatory network analysis tools for high throughput transcriptomic data. Report 575, University of Tennessee 2006."},{"issue":"6","key":"6830_CR11","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1016\/j.ygeno.2009.08.016","volume":"94","author":"EJ Baker","year":"2009","unstructured":"Baker EJ, Jay J, Philip V, Zhang Y, Li Z, Kirova R, Langston MA, Chesler EJ: Ontological discovery environment: A system for integrating gene-phenotype associations. Genomics. 2009, 94 (6): 377-387. 10.1016\/j.ygeno.2009.08.016.","journal-title":"Genomics"},{"key":"6830_CR12","unstructured":"Kirova R, Langston MA, Peng X, Perkins AD, Chesler EJ: A systems genetic analysis of chronic fatigue syndrome: combinatorial data integration from SNPs to differential diagnosis of disease. Proceedings, International Conference for the Critical Assessment of Microarray Data Analysis (CAMDA06). Durham, North Carolina; June 2006"},{"key":"6830_CR13","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1147\/sj.461.0135","volume":"46","author":"RA Mushlin","year":"2007","unstructured":"Mushlin RA, Kershenbaum A, Gallagher ST, Rebbeck TR: A graph-theoretical approach for pattern discovery in epidemiological research. IBM Syst J. 2007, 46: 135-149.","journal-title":"IBM Syst J"},{"key":"6830_CR14","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1109\/ICDM.2003.1250919","volume-title":"ICDM \u201803: Proceedings of the Third IEEE International Conference on Data Mining","author":"J Liu","year":"2003","unstructured":"Liu J, Wang W: OP-Cluster: clustering by tendency in high dimensional space. ICDM \u201803: Proceedings of the Third IEEE International Conference on Data Mining. 2003, Washington, DC: IEEE Computer Society, 187-187."},{"key":"6830_CR15","volume-title":"Computers and Intractability","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS: Computers and Intractability. 1979, New York: W. H. Freeman"},{"issue":"3","key":"6830_CR16","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1016\/S0166-218X(03)00333-0","volume":"131","author":"R Peeters","year":"2003","unstructured":"Peeters R: The maximum edge biclique problem is NP-complete. Discrete Appl Math. 2003, 131 (3): 651-654. 10.1016\/S0166-218X(03)00333-0.","journal-title":"Discrete Appl Math"},{"issue":"4","key":"6830_CR17","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/0020-0190(94)90121-X","volume":"51","author":"D Eppstein","year":"1994","unstructured":"Eppstein D: Arboricity and bipartite subgraph listing algorithms. Inf Process Lett. 1994, 51 (4): 207-211. 10.1016\/0020-0190(94)90121-X.","journal-title":"Inf Process Lett"},{"key":"6830_CR18","first-page":"260","volume-title":"Proceedings, 9th Scandinavian Workshop on Algorithm Theory","author":"K Makino","year":"2004","unstructured":"Makino K, Uno T: New algorithms for enumerating all maximal cliques. Proceedings, 9th Scandinavian Workshop on Algorithm Theory. 2004, Humlebaek: Springer, 260-272."},{"key":"6830_CR19","volume-title":"Proceedings, 3rd SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery","author":"MJ Zaki","year":"1998","unstructured":"Zaki MJ, Ogihara M: Theoretical foundations of association rules. Proceedings, 3rd SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery. 1998, Seattle, Washington: ACM"},{"key":"6830_CR20","first-page":"146","volume-title":"PKDD","author":"J Li","year":"2005","unstructured":"Li J, Li H, Soh D, Wong L: A correspondence between maximal complete bipartite subgraphs and closed patterns. PKDD. 2005, Berlin Heidelberg: Springer-Verlag, 146-156."},{"key":"6830_CR21","first-page":"398","volume-title":"Proceedings, 2nd SIAM International Conference on Data Mining","author":"MJ Zaki","year":"2002","unstructured":"Zaki MJ, Hsiao C: Charm: An efficient algorithm for closed itemset mining. Proceedings, 2nd SIAM International Conference on Data Mining. 2002, Arlington, Virginia, 398-416."},{"key":"6830_CR22","first-page":"236","volume-title":"Proceedings, 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"J Wang","year":"2003","unstructured":"Wang J, Pei J, Han J: Closet+: Searching for the best strategies for mining frequent closed itemsets. Proceedings, 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2003, Washington, DC, 236-245."},{"key":"6830_CR23","volume-title":"Proceedings, FIMI\u201903: Workshop on Frequent Itemset Mining Implementations","author":"G Grahne","year":"2003","unstructured":"Grahne G, Zhu J: Efficiently using prefix-trees in mining frequent itemsets. Proceedings, FIMI\u201903: Workshop on Frequent Itemset Mining Implementations. 2003, Melbourne, Florida: CEUR-WS.org"},{"key":"6830_CR24","unstructured":"Zhu J, Grahne G: Reducing the main memory consumptions of FPmax* and FPclose. Proceedings, FIMI\u201904: Workshop on Frequent Itemset Mining Implementations. Brighton, UK, November 2004"},{"key":"6830_CR25","volume-title":"Proceedings, FIMI\u201904: Workshop on Frequent Itemset Mining Implementations","author":"T Uno","year":"2004","unstructured":"Uno T, Kiyomi M, Arimura H: LCM ver.2: Efficient mining algorithms for frequent\/closed\/maximal itemsets. Proceedings, FIMI\u201904: Workshop on Frequent Itemset Mining Implementations. 2004, Brighton, UK: CEUR-WS.org"},{"issue":"12","key":"6830_CR26","doi-asserted-by":"publisher","first-page":"1625","DOI":"10.1109\/TKDE.2007.190660","volume":"19","author":"J Li","year":"2007","unstructured":"Li J, Liu G, Li H, Wong L: Maximal Biclique subgraphs and closed pattern pairs of the adjacency matrix: a one-to-one correspondence and mining algorithms. IEEE Trans Knowl Data Eng. 2007, 19 (12): 1625-1637.","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"6830_CR27","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1016\/j.dam.2003.09.004","volume":"145","author":"G Alexe","year":"2004","unstructured":"Alexe G, Alexe S, Crama Y, Foldes S, Hammer PL, Simeone B: Consensus algorithms for the generation of all maximal bicliques. Discrete Appl Math. 2004, 145: 11-21. 10.1016\/j.dam.2003.09.004.","journal-title":"Discrete Appl Math"},{"key":"6830_CR28","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/11823728_42","volume-title":"The 8th International Conference on Data Warehousing and Knowledge Discovery (DaWaK 2006)","author":"G Liu","year":"2006","unstructured":"Liu G, Sim K, Li J: Efficient mining of large maximal Bicliques. The 8th International Conference on Data Warehousing and Knowledge Discovery (DaWaK 2006). 2006, Krakow, Poland, 437-448."},{"issue":"9","key":"6830_CR29","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1145\/362342.362367","volume":"16","author":"C Bron","year":"1973","unstructured":"Bron C, Kerbosch J: Algorithm 457: finding all cliques of an undirected graph. Commun ACM. 1973, 16 (9): 575-577. 10.1145\/362342.362367.","journal-title":"Commun ACM"},{"key":"6830_CR30","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1016\/j.tcs.2006.06.015","volume":"363","author":"E Tomita","year":"2006","unstructured":"Tomita E, Tanaka A, Takahashi H: The worst-case time complexity for generating all maximal cliques and computational experiments. Theor Comput Sci. 2006, 363: 28-42. 10.1016\/j.tcs.2006.06.015.","journal-title":"Theor Comput Sci"},{"issue":"3","key":"6830_CR31","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0020-0190(88)90065-8","volume":"27","author":"DS Johnson","year":"1988","unstructured":"Johnson DS, Papadimitriou CH: On generating all maximal independent sets. Inform Process Lett. 1988, 27 (3): 119-123. 10.1016\/0020-0190(88)90065-8.","journal-title":"Inform Process Lett"},{"issue":"4","key":"6830_CR32","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1385\/NI:1:4:343","volume":"1","author":"E Chesler","year":"2003","unstructured":"Chesler E, Wang J, Lu L, Qu Y, Manly K, Williams RW: Genetic correlates of gene expression in recombinant inbred strains: a relational model system to explore neurobehavioral phenotypes. Neuroinformatics. 2003, 1 (4): 343-357. 10.1385\/NI:1:4:343.","journal-title":"Neuroinformatics"},{"key":"6830_CR33","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1385\/NMM:5:1:085","volume":"5","author":"M Kreek","year":"2004","unstructured":"Kreek M, Nielsen D, LaForge K: Genes associated with addiction: alcoholism, opiate, and cocaine addiction. Neuromolecular Med. 2004, 5: 85-108. 10.1385\/NMM:5:1:085.","journal-title":"Neuromolecular Med"},{"issue":"10","key":"6830_CR34","doi-asserted-by":"crossref","first-page":"2304","DOI":"10.1038\/sj.npp.1301089","volume":"31","author":"D Albertson","year":"2006","unstructured":"Albertson D, Schmidt C, Kapatos G, Bannon M: Distinctive profiles of gene expression in the human nucleus accumbens associated with cocaine and heroin abuse. Neuropsychopharmacology. 2006, 31 (10): 2304-2312.","journal-title":"Neuropsychopharmacology"},{"issue":"11","key":"6830_CR35","doi-asserted-by":"publisher","first-page":"e1187","DOI":"10.1371\/journal.pone.0001187","volume":"2","author":"D Mash","year":"2007","unstructured":"Mash D, Ffrench-Mullen J, Adi N, Qin Y, Buck A, Pablo J: Gene expression in human hippocampus from cocaine abusers identifies genes which regulate extracellular matrix remodeling. PLoS ONE. 2007, 2 (11): e1187-10.1371\/journal.pone.0001187.","journal-title":"PLoS ONE"}],"container-title":["BMC Bioinformatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/1471-2105-15-110.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,2]],"date-time":"2021-09-02T10:40:08Z","timestamp":1630579208000},"score":1,"resource":{"primary":{"URL":"https:\/\/bmcbioinformatics.biomedcentral.com\/articles\/10.1186\/1471-2105-15-110"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,4,15]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,12]]}},"alternative-id":["6830"],"URL":"https:\/\/doi.org\/10.1186\/1471-2105-15-110","relation":{},"ISSN":["1471-2105"],"issn-type":[{"value":"1471-2105","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,4,15]]},"assertion":[{"value":"27 July 2013","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 March 2014","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 April 2014","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"110"}}