IEEE/ACM Transactions on Computational Biology and Bioinformatics · 2011 · 60 citations · 24 references
Life SciencesBiologyAlgorithmsComputational BiologyNetwork BiologyBiological NetworksGraph AlgorithmsGraph ColoringGraph TheoryNetwork MotifsProtein-protein Interaction NetworksApproximation Algorithms For ColoringComputational Complexity Of Graph AlgorithmsFixed-parameter TractabilityGraph Coloring ComplexityHeuristicsMotif AnalysisParameterized Graph AlgorithmsParameterized Graph Coloring
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|.
24
Network motifs in the transcriptional regulation network of Escherichia coli
Shai S. Shen-Orr, Ron Milo, Shmoolik Mangan et al. · Nature Genetics · 2002 · 3.1K citations
Michael R. Fellows · Electronic Notes in Theoretical Computer Science · 2002 · 2.9K citations · Full text
Elizabeth I. Boyle, Shuai Weng, Jeremy Gollub et al. · Bioinformatics · 2004 · 2.2K citations · Full text
Noga Alon, Raphael Yuster, Uri Zwick · Journal of the ACM · 1995 · 1K citations · Full text
FlyBase: enhancing Drosophila Gene Ontology annotations
Susan Tweedie, Michael Ashburner, Kathleen Falls et al. · Nucleic Acids Research · 2008 · 709 citations · Full text