Sevon Petteri, Eronen Lauri
Helsinki Institute for Information Technology, Department of Computer Science,PO Box 68, FI-00014 University of Helsinki, Finland.
J Integr Bioinform. 2008 Aug 25;5(2):100. doi: 10.2390/biecoll-jib-2008-100.
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.
我们描述了一种使用上下文无关文法查询顶点和边标记图的方法，以指定感兴趣路径的类别。我们引入了一个新问题，即找到由给定两个顶点或两组顶点之间的匹配路径集所诱导的连接子图。这样的子图提供了顶点之间关系的简洁总结。我们还提出了直接解析子图的新算法，而无需枚举所有单个路径。我们在从公开可用的生物医学数据库派生的一组真实图以及随机生成的图上对所提出的解析算法进行了实验评估。结果表明，直接解析连接子图比单独解析单个路径要有效得多。此外，我们表明，在大多数情况下，使用双向解析算法比使用单向搜索策略能够搜索长度两倍的路径。
