Parameterized Algorithmics for Finding Connected Motifs in Biological Networks

• Published in: IEEE/ACM transactions on computational biology and bioinformatics 2011-09, Vol.8 (5), p.1296-1308
• Main Authors: Betzler, N., van Bevern, R., Fellows, M. R., Komusiewicz, C., Niedermeier, R.
• Format: Article
• Language: English
• Subjects: Algorithms; Animals; Color; color-coding; Complexity theory; Computational Biology - methods; Databases, Protein; Diptera; Dynamic programming; Error probability; Humans; Labeling; list-colored graphs; Parameterized complexity; pattern matching in graphs; Pattern Recognition, Automated - methods; Protein Interaction Mapping - methods; Protein Interaction Maps; protein-interaction networks; Proteins; Studies; Topology; Yeasts
• ISSN: 1545-5963; 1557-9964
• DOI: 10.1109/TCBB.2011.19

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|.