Partial Information Network Queries

• Introducing the Partial Information Network Query (PINQ) problem.
• Developing a parameterized algorithm for PINQ.
• For topology-free network queries: improving upon previous running times.
• For two types of alignment network queries: improving upon previous running times.

We study the Partial Information Network Query (PINQ) problem, which generalizes two problems that often arise in bioinformatics: the Alignment Network Query (ANQ) problem and the Topology-Free Network Query (TFNQ)   problem. In both ANQ and TFNQ we have a pattern PP and a graph H, and we seek a subgraph of H that resembles  PP. ANQ requires knowing the topology of PP, while TFNQ ignores it. PINQ fits the scenario where partial information is available on the topology of PP. Our main result is a parameterized algorithm that handles inputs for PINQ in which PP is a set of trees. This algorithm significantly improves the best known O⁎O⁎ running time in solving TFNQ. We also improve the best known O⁎O⁎ running times in solving two special cases of ANQ.