Prof. Michal Ziv-Yukelson

Network querying is a powerful approach to mine molecular interaction networks. Most network querying tools support queries in the form of a template sub-network, in case of topology-constrained queries, or a set of colored vertices in case of topology-free queries. A third approach is grammar-based queries, which are more flexible and expressive as they allow the addition of logic rules to the query. Previous grammar-based querying tools defined queries via string grammars and identified paths in graphs. In this paper, we extend the scope of grammar-based queries to regular tree grammar (RTG), and the scope of the identified sub-graphs from paths to trees. We introduce a new problem and propose a novel algorithm to search a given graph for the k highest scoring sub-graphs matching a tree accepted by an RTG. Our algorithm is based on dynamic programming and combines an extension to k-best parsing optimization with color coding. We implement the new algorithm and exemplify its application to mining the human-viral interaction network. Our code is available at http://www.cs.bgu.ac.il/~smolyi/RTGnet/.