Parameterized algorithmics for finding connected motifs in biological networks

Nadja Betzler, René Van Bevern, Michael R. Fellows, Christian Komusiewicz, Rolf Niedermeier

Результат исследования: Научные публикации в периодических изданияхстатьярецензирование

45 Цитирования (Scopus)


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

Язык оригиналаанглийский
Номер статьи5708132
Страницы (с-по)1296-1308
Число страниц13
ЖурналIEEE/ACM Transactions on Computational Biology and Bioinformatics
Номер выпуска5
СостояниеОпубликовано - 3 авг. 2011
Опубликовано для внешнего пользованияДа


Подробные сведения о темах исследования «Parameterized algorithmics for finding connected motifs in biological networks». Вместе они формируют уникальный семантический отпечаток (fingerprint).