title: Algorithms for Regular Tree Grammar Network Search and Their Application to Mining Human-viral Infection Patterns.
abstract: Network querying is a powerful approach to mine molecular interaction networks. Most state-of-the-art network querying tools either confine the search to a prespecified topology in the form of some template subnetwork, or do not specify any topological constraints at all. Another approach is grammar-based queries, which are more flexible and expressive as they allow for expressing the topology of the sought pattern according to some grammar-based logic. Previous grammar-based network querying tools were confined to the identification of paths. In this article, we extend the patterns identified by grammar-based query approaches from paths to trees. For this, we adopt a higher order query descriptor in the form of a regular tree grammar (RTG). We introduce a novel problem and propose an algorithm to search a given graph for the k highest scoring subgraphs matching a tree accepted by an RTG. Our algorithm is based on the combination of dynamic programming with color coding, and includes an extension of previous k-best parsing optimization approaches to avoid isomorphic trees in the output. We implement the new algorithm and exemplify its application to mining viral infection patterns within molecular interaction networks. Our code is available online.
authors.affiliation: 1 Department of Computer Science, Ben-Gurion University of the Negev , Beer-Sheva, Israel .
authors.forename: Ilan
authors.initials: I
authors.lastname: Smoly
authors.affiliation: 1 Department of Computer Science, Ben-Gurion University of the Negev , Beer-Sheva, Israel .
authors.forename: Amir
authors.initials: A
authors.lastname: Carmel
authors.affiliation: 2 Department of Virology, Ben-Gurion University of the Negev , Beer-Sheva, Israel .
authors.forename: Yonat
authors.initials: Y
authors.lastname: Shemer-Avni
authors.affiliation: 3 Clinical Biochemistry and Pharmacology, Ben-Gurion University of the Negev , Beer-Sheva, Israel .
authors.forename: Esti
authors.initials: E
authors.lastname: Yeger-Lotem
authors.affiliation: 1 Department of Computer Science, Ben-Gurion University of the Negev , Beer-Sheva, Israel .
authors.forename: Michal
authors.initials: M
authors.lastname: Ziv-Ukelson
mesh_terms: D000465:Algorithms; D057225:Data Mining / Q000379:methods*; D054884:Host-Pathogen Interactions; D006801:Humans; D014780:Viruses / Q000472:pathogenicity*
keywords: RNA secondary structure; algorithms; computational molecular biology; phylogenetic trees; sequence analysis