Universität Bielefeld Electronic Collections animiertes Foto Universität Bielefeld

Zugang zum Dokument

Subgraph Queries by Context-free Grammars

Sevon, Petteri ; Eronen, Lauri

Journal of Integrative Bioinformatics - JIB (ISSN 1613-4516)

We describe a method for querying vertex- and edge-labeled graphs using context-free grammars to specify the class of interesting paths. We introduce a novel problem, finding the connection subgraph induced by the set of matching paths between given two vertices or two sets of vertices. Such a subgraph provides a concise summary of the relationship between the vertices. We also present novel algorithms for parsing subgraphs directly without enumerating all the individual paths. We evaluate experimentally the presented parsing algorithms on a set of real graphs derived from publicly available biomedical databases and on randomly generated graphs. The results indicate that parsing the connection subgraph directly is much more effective than parsing individual paths separately. Furthermore, we show that using a bidirectional parsing algorithm, in most cases, allows for searching twice as long paths as using a unidirectional search strategy.

Beteiligte Einrichtung: Technische Fakultät, Arbeitsgruppen der Informatik
DDC-Sachgruppe: Datenverarbeitung, Informatik

Sevon, Petteri ; Eronen, Lauri  (2008)  Subgraph Queries by Context-free Grammars. Journal of Integrative Bioinformatics - JIB (ISSN 1613-4516), 5(2), 2008

Online-Journal: http://journal.imbio.de/index.php?paper_id=100
URL: http://biecoll.ub.uni-bielefeld.de/volltexte/2008/294

 Fragen und Anregungen an: publikationsdienste.ub@uni-bielefeld.de
 Letzte Änderung: 15.2.2011
OPUS-Logo     OAI-zertifiziert      Universitätsbibliothek Bielefeld