Algorithms for topology-free and alignment network queries

In this article we address two pattern matching problems which have important applications to bioinformatics. First we address the topology-free network query problem: Given a set of labels L, a multiset P of labels from L, a graph H=(VH,EH) and a function LabelH:VH→2L, we need to find a subtree S of H which is an occurrence of P. We provide a parameterized algorithm with parameter k=|P| that runs in time O⁎(2k) and whose space complexity is polynomial. We also consider three variants of this problem. Then we address the alignment network query problem: Given two labeled graphs P and H, we need to find a subgraph S of H whose alignment with P is the best among all such subgraphs. We present two algorithms for cases in which P and H belong to certain families of DAGs. Their running times are polynomial and they are less restrictive than algorithms that are available today for alignment network queries. Topology-free and alignment network queries provide means to study the function and evolution of biological networks, and today, with the increasing amount of knowledge regarding biological networks, they are extremely relevant.