Searching and inferring colorful topological motifs in vertex-colored graphs
Authors: 
Diego P. Rubert, Eloi Araujo, Marco A. Stefanes, Jens Stoye, Fábio V. MartinezAuthors Info & Claims
Pages 379 - 411
Abstract
The analysis of biological networks allows the understanding of many biological processes, including the structure, function, interaction and evolutionary relationships of their components. One of the most important concepts in biological network analysis is that of network motifs, which are patterns of interconnections that occur in a given network at a frequency higher than expected in a random network. In this work we are interested in searching and inferring network motifs in a class of biological networks that can be represented by vertex-colored graphs. We show the computational complexity for many problems related to colorful topological motifs and present efficient algorithms for special cases. A colorful motif can be represented by a graph in which each vertex has a different color. We also present a probabilistic strategy to detect highly frequent motifs in vertex-colored graphs. Experiments on real data sets show that our algorithms are very competitive both in efficiency and in quality of the solutions.
References
[1]
Araujo E, Stefanes MA (2013) Some results on topological colored motifs in metabolic networks. In: Proceedings of the BIBE, pp 1–5
[2]
Ashburner M et al. Gene ontology: tool for the unification of biology Nat Genet 2000 25 1 25-29
[3]
Blin G, Sikora F, Vialette S (2010) GraMoFoNe: a cytoscape plugin for querying motifs without topology in protein-protein interactions networks. In: Proceedings of BICoB, pp 38–43
[4]
Boyle EI et al. GO::TermFinder-open source software for accessing Gene Ontology information and finding significantly enriched Gene Ontology terms associated with a list of genes Bioinformatics 2004 20 18 3710-3715
[5]
Bruckner S et al.Topology-free querying of protein interaction networksJ Comput Biol2010173237-2522609132
[6]
Caspi R et al. The MetaCyc database of metabolic pathways and enzymes and the BioCyc collection of pathway/genome databases Nucleic Acids Res 2016 44 D1 D471-80
[7]
Cormen TH, Leiserson CE, Rivest RL, and Stein C Introduction to algorithms 2009 3 Cambridge The MIT Press
[8]
Dondi R, Fertin G, and Vialette SComplexity issues in vertex-colored graph pattern matchingJ Discrete Algorithms20119182-992771171
[9]
Dost B et al.QNet: a tool for querying protein interaction networksJ Comput Biol2008157913-9252438283
[10]
Erdös PSome remarks on the theory of graphsBull Am Math Soc1947534292-29419911
[11]
Fellows MR, Fertin G, Hermelin D, Vialette S (2007) Sharp tractability borderlines for finding connected motifs in vertex-colored graphs. In: Proceedings of ICALP, LNCS, vol 4596, pp 340–351
[12]
Fellows MR, Fertin G, Hermelin D, and Vialette SUpper and lower bounds for finding connected motifs in vertex-colored graphsJ Comput Syst Sci2011774799-8112799278
[13]
Garey MR and Johnson DS Computers and intractability: a guide to the theory of NP-completeness 1979 Murray Hill W. H. Freeman and Company
[14]
Guillemot S and Sikora FFinding and counting vertex-colored subtreesAlgorithmica201365828-8443018153
[15]
Kashani ZRM et al. Kavosh: a new algorithm for finding network motifs BMC Bioinform 2009 10 318
[16]
Kelley BP et al. Conserved pathways within bacteria and yeast as revealed by global protein network alignment Proc Natl Acad Sci USA 2003 100 20 11394-11399
[17]
Lacroix V, Cottret L, Thébault P, and Sagot MF An introduction to metabolic networks and their structural analysis IEEE/ACM Trans Comput Biol Bioinform 2008 5 4 594-617
[18]
Lacroix V, Fernandes CG, Sagot MF (2005) Reaction motifs in metabolic networks. In: Proceedings of WABI, LNBI, vol 3692, pp 178–191
[19]
Lacroix V, Fernandes CG, and Sagot MF Motif search in graphs: application to metabolic networks IEEE/ACM Trans Comput Biol Bioinform 2006 3 4 360-368
[20]
Maier DThe complexity of some problems on subsequences and supersequencesJACM1978252322-336483700
[21]
Marx D (2007) Can you beat treewidth? In: Proceedings of FOCS, pp 169–179
[22]
Pinter R, Shachnai H, and Zehavi MDeterministic parameterized algorithms for the graph motif problemDiscrete Appl Math2016213162-1783544577
[23]
Pinter R and Zehavi MAlgorithms for topology-free and alignment network queriesJ Discrete Algorithms20142729-533227237
[24]
Rubert DP, Araujo E, Stefanes MA (2015) SIMBio: searching and inferring colorful motifs in biological networks. In: Proceedings of BIBE, pp 1–6
[25]
Schbath S, Lacroix V, Sagot MF (2009) Assessing the exceptionality of coloured motifs in networks. EURASIP J Bioinform Syst Biol Article ID 616234, 9 pages
[26]
Shen-Orr SS, Milo R, Mangan S, and Alon U Network motifs in the transcriptional regulation network of Escherichia coli Nat Genet 2002 31 1 64-68
[27]
Shlomi T, Segal D, Ruppin E, and Sharan R QPath: a method for querying pathways in a protein–protein interaction network BMC Bioinform 2006 7 199
[28]
Wernicke S and Rasche F FANMOD: a tool for fast network motif detection Bioinformatics 2006 22 9 1152
Recommendations
Detecting list-colored graph motifs in biological networks using branch-and-bound strategy
AbstractIn 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 ...
Highlights- A new motif detection procedure is designed for solving list-colored motif problem.
- An initial vertex selection strategy is given to determine search scope of motif.
- Our method performs better than other existing methods in ...
Finding approximate and constrained motifs in graphs
One of the most relevant topics in the analysis of biological networks is the identification of functional motifs inside a network. A recent approach introduced in literature, called Graph Motif, represents the network as a vertex-colored graph, and the ...
Maximum Colorful Cliques in Vertex-Colored Graphs
Computing and CombinatoricsAbstractIn this paper we study the problem of finding a maximum colorful clique in vertex-colored graphs. Specifically, given a graph with colored vertices, we wish to find a clique containing the maximum number of colors. Note that this problem is harder ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© Springer Science+Business Media, LLC, part of Springer Nature 2020.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 01 August 2020
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 15 Jan 2025