Parameterized Algorithmics for Finding Connected Motifs in Biological Networks (Homepage of René van Bevern)

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), pp. 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.

Download

The paper is available in PDF format from TU Berlin and IEEE (original publication). You can also download Gram—the graph motif solving program used in the experiments section of the paper.

BibTex Entry

For information on using BibTex in your LaTeX documents, refer to the chapter "Bibliography management" in the wikibook for LaTeX.

@article{BBFKN10,
  author = {Nadja Betzler and Ren{\'e} van Bevern and Michael
    R. Fellows and Christian Komusiewicz and Rolf Niedermeier},
  title = {Parameterized Algorithmics for Finding Connected Motifs in
    Biological Networks},
  journal = {IEEE/ACM Transactions on Computational Biology and
    Bioinformatics},
  doi = {10.1109/TCBB.2011.19},
  pages = {1296--1308},
  volume = {8},
  number = {5},
  year = {2011},
}