×

zbMATH — the first resource for mathematics

Searching and inferring colorful topological motifs in vertex-colored graphs. (English) Zbl 1447.92172
Summary: 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.
MSC:
92C42 Systems biology, networks
05C90 Applications of graph theory
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
92-08 Computational methods for problems pertaining to biology
PDF BibTeX XML Cite
Full Text: DOI
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., Gene ontology: tool for the unification of biology, Nat Genet, 25, 1, 25-29 (2000)
[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, GO::TermFinder-open source software for accessing Gene Ontology information and finding significantly enriched Gene Ontology terms associated with a list of genes, Bioinformatics, 20, 18, 3710-3715 (2004)
[5] Bruckner, S., Topology-free querying of protein interaction networks, J Comput Biol, 17, 3, 237-252 (2010)
[6] Caspi, R., The MetaCyc database of metabolic pathways and enzymes and the BioCyc collection of pathway/genome databases, Nucleic Acids Res, 44, D1, D471-80 (2016)
[7] Cormen, TH; Leiserson, CE; Rivest, RL; Stein, C., Introduction to algorithms (2009), Cambridge: The MIT Press, Cambridge
[8] Dondi, R.; Fertin, G.; Vialette, S., Complexity issues in vertex-colored graph pattern matching, J Discrete Algorithms, 9, 1, 82-99 (2011) · Zbl 1222.05053
[9] Dost, B., QNet: a tool for querying protein interaction networks, J Comput Biol, 15, 7, 913-925 (2008)
[10] Erdös, P., Some remarks on the theory of graphs, Bull Am Math Soc, 53, 4, 292-294 (1947) · Zbl 0032.19203
[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 · Zbl 1171.68497
[12] Fellows, MR; Fertin, G.; Hermelin, D.; Vialette, S., Upper and lower bounds for finding connected motifs in vertex-colored graphs, J Comput Syst Sci, 77, 4, 799-811 (2011) · Zbl 1210.68060
[13] Garey, MR; Johnson, DS, Computers and intractability: a guide to the theory of NP-completeness (1979), Murray Hill: W. H. Freeman and Company, Murray Hill
[14] Guillemot, S.; Sikora, F., Finding and counting vertex-colored subtrees, Algorithmica, 65, 828-844 (2013) · Zbl 1263.05029
[15] Kashani, ZRM, Kavosh: a new algorithm for finding network motifs, BMC Bioinform, 10, 318 (2009)
[16] Kelley, BP, Conserved pathways within bacteria and yeast as revealed by global protein network alignment, Proc Natl Acad Sci USA, 100, 20, 11394-11399 (2003)
[17] Lacroix, V.; Cottret, L.; Thébault, P.; Sagot, MF, An introduction to metabolic networks and their structural analysis, IEEE/ACM Trans Comput Biol Bioinform, 5, 4, 594-617 (2008)
[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; Sagot, MF, Motif search in graphs: application to metabolic networks, IEEE/ACM Trans Comput Biol Bioinform, 3, 4, 360-368 (2006)
[20] Maier, D., The complexity of some problems on subsequences and supersequences, JACM, 25, 2, 322-336 (1978) · Zbl 0371.68018
[21] Marx D (2007) Can you beat treewidth? In: Proceedings of FOCS, pp 169-179 · Zbl 1213.68316
[22] Pinter, R.; Shachnai, H.; Zehavi, M., Deterministic parameterized algorithms for the graph motif problem, Discrete Appl Math, 213, 162-178 (2016) · Zbl 1344.05136
[23] Pinter, R.; Zehavi, M., Algorithms for topology-free and alignment network queries, J Discrete Algorithms, 27, 29-53 (2014) · Zbl 1362.05123
[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.; Alon, U., Network motifs in the transcriptional regulation network of Escherichia coli, Nat Genet, 31, 1, 64-68 (2002)
[27] Shlomi, T.; Segal, D.; Ruppin, E.; Sharan, R., QPath: a method for querying pathways in a protein-protein interaction network, BMC Bioinform, 7, 199 (2006)
[28] Wernicke, S.; Rasche, F., FANMOD: a tool for fast network motif detection, Bioinformatics, 22, 9, 1152 (2006)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.