title: Parameterized algorithmics for finding connected motifs in biological networks.
abstract: 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|.
authors.affiliation: Institut für Softwaretechnik und Theoretische Informatik, Technische Universtität Berlin, 10587 Berlin, Germany. nadja.betzler@campus.tu-berlin.de
authors.forename: Nadja
authors.initials: N
authors.lastname: Betzler
authors.forename: René
authors.initials: R
authors.lastname: van Bevern
authors.forename: Michael R
authors.initials: MR
authors.lastname: Fellows
authors.forename: Christian
authors.initials: C
authors.lastname: Komusiewicz
authors.forename: Rolf
authors.initials: R
authors.lastname: Niedermeier
mesh_terms: D000465:Algorithms; D000818:Animals; D003116:Color; D019295:Computational Biology / Q000379:methods*; D030562:Databases, Protein; D004175:Diptera; D006801:Humans; D010363:Pattern Recognition, Automated / Q000379:methods*; D025941:Protein Interaction Mapping / Q000379:methods*; D060066:Protein Interaction Maps; D015003:Yeasts