Top

Journal of Combinatorial Optimization

Published in:

02-06-2020

Searching and inferring colorful topological motifs in vertex-colored graphs

Authors: Diego P. Rubert, Eloi Araujo, Marco A. Stefanes, Jens Stoye, Fábio V. Martinez

Published in: Journal of Combinatorial Optimization | Issue 2/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

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.

previous article Approximation algorithms for the selling with preference

next article More on limited packings in graphs

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Notice that this problem was proposed previously and was shown W[1]-hard Marx (2007). Despite of that, our NP-completeness proof is simple and straightforward.

Our implementation, including documentation, compilation parameters and libraries used, can be found at http://simbio.wp.facom.ufms.br.

http://go.princeton.edu/cgi-bin/GOTermFinder

http://www.cs.tau.ac.il/~bnet/TORQUE_Input_format.htm

http://igm.univ-mlv.fr/AlgoB/gramofone/

Araujo E, Stefanes MA (2013) Some results on topological colored motifs in metabolic networks. In: Proceedings of the BIBE, pp 1–5

Ashburner M et al (2000) Gene ontology: tool for the unification of biology. Nat Genet 25(1):25–29CrossRef

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

Boyle EI et al (2004) 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–3715CrossRef

Bruckner S et al (2010) Topology-free querying of protein interaction networks. J Comput Biol 17(3):237–252MathSciNetCrossRef

Caspi R et al (2016) The MetaCyc database of metabolic pathways and enzymes and the BioCyc collection of pathway/genome databases. Nucleic Acids Res 44(D1):D471–80CrossRef

Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to algorithms, 3rd edn. The MIT Press, CambridgeMATH

Dondi R, Fertin G, Vialette S (2011) Complexity issues in vertex-colored graph pattern matching. J Discrete Algorithms 9(1):82–99MathSciNetCrossRef

Dost B et al (2008) QNet: a tool for querying protein interaction networks. J Comput Biol 15(7):913–925MathSciNetCrossRef

Erdös P (1947) Some remarks on the theory of graphs. Bull Am Math Soc 53(4):292–294MathSciNetCrossRef

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

Fellows MR, Fertin G, Hermelin D, Vialette S (2011) Upper and lower bounds for finding connected motifs in vertex-colored graphs. J Comput Syst Sci 77(4):799–811MathSciNetCrossRef

Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman and Company, Murray HillMATH

Guillemot S, Sikora F (2013) Finding and counting vertex-colored subtrees. Algorithmica 65:828–844MathSciNetCrossRef

Kashani ZRM et al (2009) Kavosh: a new algorithm for finding network motifs. BMC Bioinform 10:318CrossRef

Kelley BP et al (2003) Conserved pathways within bacteria and yeast as revealed by global protein network alignment. Proc Natl Acad Sci USA 100(20):11394–11399CrossRef

Lacroix V, Cottret L, Thébault P, Sagot MF (2008) An introduction to metabolic networks and their structural analysis. IEEE/ACM Trans Comput Biol Bioinform 5(4):594–617CrossRef

Lacroix V, Fernandes CG, Sagot MF (2005) Reaction motifs in metabolic networks. In: Proceedings of WABI, LNBI, vol 3692, pp 178–191

Lacroix V, Fernandes CG, Sagot MF (2006) Motif search in graphs: application to metabolic networks. IEEE/ACM Trans Comput Biol Bioinform 3(4):360–368CrossRef

Maier D (1978) The complexity of some problems on subsequences and supersequences. JACM 25(2):322–336MathSciNetCrossRef

Marx D (2007) Can you beat treewidth? In: Proceedings of FOCS, pp 169–179

Pinter R, Shachnai H, Zehavi M (2016) Deterministic parameterized algorithms for the graph motif problem. Discrete Appl Math 213:162–178MathSciNetCrossRef

Pinter R, Zehavi M (2014) Algorithms for topology-free and alignment network queries. J Discrete Algorithms 27:29–53MathSciNetCrossRef

Rubert DP, Araujo E, Stefanes MA (2015) SIMBio: searching and inferring colorful motifs in biological networks. In: Proceedings of BIBE, pp 1–6

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

Shen-Orr SS, Milo R, Mangan S, Alon U (2002) Network motifs in the transcriptional regulation network of Escherichia coli. Nat Genet 31(1):64–68CrossRef

Shlomi T, Segal D, Ruppin E, Sharan R (2006) QPath: a method for querying pathways in a protein–protein interaction network. BMC Bioinform 7:199CrossRef

Wernicke S, Rasche F (2006) FANMOD: a tool for fast network motif detection. Bioinformatics 22(9):1152CrossRef

Title: Searching and inferring colorful topological motifs in vertex-colored graphs
Authors: Diego P. Rubert
Eloi Araujo
Marco A. Stefanes
Jens Stoye
Fábio V. Martinez
Publication date: 02-06-2020
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 2/2020
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-020-00590-4

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 2/2020

More on limited packings in graphs

Integer linear programming formulations of the filter partitioning minimization problem

On theoretical and empirical algorithmic analysis of the efficiency gap measure in partisan gerrymandering

Approximation algorithms for the selling with preference

Crossing minimization in perturbed drawings

On the Roman domination subdivision number of a graph

Premium Partner