## Nadja Betzler, René van Bevern, Michael R. Fellows, Christian Komusiewicz, and
Rolf Niedermeier.
Parameterized algorithmics for finding connected motifs in biological
networks.
*IEEE/ACM Transactions on Computational Biology and
Bioinformatics*, 8(5):1296–1308, 2011.

We study the NP-hard LIST-COLORED GRAPH MOTIF problem
which, given an undirected list-colored graph G = (V,
E) and a multiset M of colors, asks for
maximum-cardinality sets S ⊆ V and M' ⊆ M such that
G[S] is connected and contains exactly (with respect
to multiplicity) the colors in M'. LIST-COLORED GRAPH
MOTIF has applications in the analysis of biological
networks. We study LIST-COLORED GRAPH MOTIF with
respect to three different parameterizations. For the
parameters motif size |M| and solution size |S|, we
present fixed-parameter algorithms, whereas for the
parameter |V| - |M|, we show W[1]-hardness for general
instances and achieve fixed-parameter tractability for
a special case of LIST-COLORED GRAPH MOTIF. We
implemented the fixed-parameter algorithms for
parameters |M| and |S|, developed further speed-up
heuristics for these algorithms, and applied them in
the context of querying protein-interaction networks,
demonstrating their usefulness for realistic
instances. Furthermore, we show that extending the
request for motif connectedness to stronger demands,
such as biconnectedness or bridge-connectedness leads
to W[1]-hard problems when the parameter is the motif
size |M|.

[ bib |
DOI |
source code |
.pdf ]
Back

*This file was generated by
bibtex2html 1.98.*