Standard

Parameterized algorithmics for finding connected motifs in biological networks. / Betzler, Nadja; Van Bevern, René; Fellows, Michael R. et al.

In: IEEE/ACM Transactions on Computational Biology and Bioinformatics, Vol. 8, No. 5, 5708132, 03.08.2011, p. 1296-1308.

Research output: Contribution to journal › Article › peer-review

Harvard

Betzler, N, Van Bevern, R, Fellows, MR, Komusiewicz, C & Niedermeier, R 2011, 'Parameterized algorithmics for finding connected motifs in biological networks', IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol. 8, no. 5, 5708132, pp. 1296-1308. https://doi.org/10.1109/TCBB.2011.19

APA

Betzler, N., Van Bevern, R., Fellows, M. R., Komusiewicz, C., & Niedermeier, R. (2011). Parameterized algorithmics for finding connected motifs in biological networks. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 8(5), 1296-1308. [5708132]. https://doi.org/10.1109/TCBB.2011.19

Vancouver

Betzler N, Van Bevern R, Fellows MR, Komusiewicz C, Niedermeier R. Parameterized algorithmics for finding connected motifs in biological networks. IEEE/ACM Transactions on Computational Biology and Bioinformatics. 2011 Aug 3;8(5):1296-1308. 5708132. doi: 10.1109/TCBB.2011.19

Author

Betzler, Nadja ; Van Bevern, René ; Fellows, Michael R. et al. / Parameterized algorithmics for finding connected motifs in biological networks. In: IEEE/ACM Transactions on Computational Biology and Bioinformatics. 2011 ; Vol. 8, No. 5. pp. 1296-1308.

BibTeX

@article{ba9710c8045846b6a94c03d3a6d79214,
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|.",
keywords = "color-coding, list-colored graphs, Parameterized complexity, pattern matching in graphs, protein-interaction networks",
author = "Nadja Betzler and {Van Bevern}, Ren{\'e} and Fellows, {Michael R.} and Christian Komusiewicz and Rolf Niedermeier",
year = "2011",
month = aug,
day = "3",
doi = "10.1109/TCBB.2011.19",
language = "English",
volume = "8",
pages = "1296--1308",
journal = "IEEE/ACM Transactions on Computational Biology and Bioinformatics",
issn = "1545-5963",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "5",

}

RIS

TY - JOUR

T1 - Parameterized algorithmics for finding connected motifs in biological networks

AU - Betzler, Nadja

AU - Van Bevern, René

AU - Fellows, Michael R.

AU - Komusiewicz, Christian

AU - Niedermeier, Rolf

PY - 2011/8/3

Y1 - 2011/8/3

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

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

KW - color-coding

KW - list-colored graphs

KW - Parameterized complexity

KW - pattern matching in graphs

KW - protein-interaction networks

UR - http://www.scopus.com/inward/record.url?scp=79960896907&partnerID=8YFLogxK

U2 - 10.1109/TCBB.2011.19

DO - 10.1109/TCBB.2011.19

M3 - Article

C2 - 21282862

AN - SCOPUS:79960896907

VL - 8

SP - 1296

EP - 1308

JO - IEEE/ACM Transactions on Computational Biology and Bioinformatics

JF - IEEE/ACM Transactions on Computational Biology and Bioinformatics

SN - 1545-5963

IS - 5

M1 - 5708132

ER -

ID: 22342126