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|.
Download full-text PDF |
Source |
|---|---|
| http://dx.doi.org/10.1109/TCBB.2011.19 | DOI Listing |
Publication Analysis
Top Keywords
Similar Publications
Detecting list-colored graph motifs in biological networks using branch-and-bound strategy.
Comput Biol Med
April 2019
School of Computer and Electronics and Information, Guangxi Key Laboratory of Multimedia Communications Network Technology, Guangxi University, Nanning, 530004, China. Electronic address:
In this work, we study the list-colored graph motif problem, which was introduced to detect functional motifs in biological networks. Given a multi-set M of colors as the query motif and a list-colored graph G where each vertex in G is associated with a set of colors, the aim of this problem is to find a sub-graph of G whose vertex set is colored exactly as motif M. To solve this problem, we present a heuristic method to efficiently and accurately detect list-colored graph motifs in biological networks using branch-and-bound strategy.
View Article and Find Full Text PDFCeFunMO: A centrality based method for discovering functional motifs with application in biological networks.
Comput Biol Med
September 2016
Laboratory of Systems Biology and Bioinformatics (LBB), Institute of Biochemistry and Biophysics, University of Tehran, Tehran, Iran. Electronic address:
Detecting functional motifs in biological networks is one of the challenging problems in systems biology. Given a multiset of colors as query and a list-colored graph (an undirected graph with a set of colors assigned to each of its vertices), the problem is reduced to finding connected subgraphs, which best cover the multiset of query. To solve this NP-complete problem, we propose a new color-based centrality measure for list-colored graphs.
View Article and Find Full Text PDFRANGI: a fast list-colored graph motif finding algorithm.
IEEE/ACM Trans Comput Biol Bioinform
February 2014
Faculty of Electrical and Computer Engineering, Tarbiat Modares University, Tehran, Iran, PO Box 14115-194, Tehran, Iran.
Given a multiset of colors as the query and a list-colored graph, i.e., an undirected graph with a set of colors assigned to each of its vertices, in the NP-hard list-colored graph motif problem the goal is to find the largest connected subgraph such that one can select a color from the set of colors assigned to each of its vertices to obtain a subset of the query.
View Article and Find Full Text PDFParameterized algorithmics for finding connected motifs in biological networks.
IEEE/ACM Trans Comput Biol Bioinform
January 2012
Institut für Softwaretechnik und Theoretische Informatik, Technische Universtität Berlin, 10587 Berlin, Germany.
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.
View Article and Find Full Text PDFWant AI Summaries of new PubMed Abstracts delivered to your In-box?
Enter search terms and have AI summaries delivered each week - change queries or unsubscribe any time!