Parameterized algorithms for the Module Motif problem

Module Motif is a pattern matching problem that was introduced in the context of biological networks. Informally, given a multiset of colors P and a graph H in which each node is associated with a set of colors, it asks if P occurs in a module of H (i. e. , in a set of nodes that have the same neighborhood outside the set). We present three parameterized algorithms for this problem, which both measure similarity between matched colors and handle deletions and insertions of colors to P. Moreover, we observe that the running times of two of them might be essentially tight, and prove that the problem is unlikely to admit a polynomial kernel.

Authors

• Meirav Zehavi

Keywords

• Module motif
• Pattern matching
• Parameterized algorithm
• Kernelization
• Computational biology