Mining maximal frequent subgraphs in KEGG reaction networks

W.P.A. Ligtenberg, D. Bosnacki, P.A.J. Hilbers

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

1 Citation (Scopus)

Abstract

In this paper we employ a recent algorithm by Zantema et al. for detecting maximal frequent subgraphs (MFS) in collections of graphs corresponding tobiological networks from the KEGG database. Each graph of a particular collection corresponds to one organism and represents one pathway or a union of pathways of this organism. Previously the MFS algorithm has been applied only to graphs that have enzymes as nodes. In this paper we introduce a new type of graphs, reaction graphs, which contain more information than the enzyme graphs. We apply the MFS algorithm to reaction graphs obtained from the KEGG network. Earlier the MFS algorithm was tested only on smaller graphs of individual metabolic pathways. In this paper we show that the algorithm can cope with large collections (containing more than 600 graphs) of large graphs (comprising more than 5000 edges). Moreover, the results are produced in real time-within a few seconds-which is important for on-line applications of the algorithm. Also, our results confirm the the feasibility of the maximal frequent subgraphs approach for finding similarities and relationships between different organisms-the more similar the graphs in the collection, the larger the size of the found maximal frequent subgraphs.
Original languageEnglish
Title of host publicationDatabase and Expert Systems Applications (Proceedings 20th International Workshop, DEXA'09, Linz, Austria, August 31-September 4, 2009)
PublisherIEEE Computer Society
Pages213-217
ISBN (Print)978-0-7695-3763-4
DOIs
Publication statusPublished - 2009
Eventconference; DEXA '09. 20th International workshop on Database and Expert Systems Application.; 2008-08-31; 2009-09-04 -
Duration: 31 Aug 20084 Sep 2009

Conference

Conferenceconference; DEXA '09. 20th International workshop on Database and Expert Systems Application.; 2008-08-31; 2009-09-04
Period31/08/084/09/09
OtherDEXA '09. 20th International workshop on Database and Expert Systems Application.

Fingerprint Dive into the research topics of 'Mining maximal frequent subgraphs in KEGG reaction networks'. Together they form a unique fingerprint.

Cite this