Skip to main content
Erschienen in: Journal of Combinatorial Optimization 2/2020

02.06.2020

Searching and inferring colorful topological motifs in vertex-colored graphs

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

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 2/2020

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

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!

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!

Fußnoten
1
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.
 
2
Our implementation, including documentation, compilation parameters and libraries used, can be found at http://​simbio.​wp.​facom.​ufms.​br.
 
Literatur
Zurück zum Zitat Araujo E, Stefanes MA (2013) Some results on topological colored motifs in metabolic networks. In: Proceedings of the BIBE, pp 1–5 Araujo E, Stefanes MA (2013) Some results on topological colored motifs in metabolic networks. In: Proceedings of the BIBE, pp 1–5
Zurück zum Zitat Ashburner M et al (2000) Gene ontology: tool for the unification of biology. Nat Genet 25(1):25–29CrossRef Ashburner M et al (2000) Gene ontology: tool for the unification of biology. Nat Genet 25(1):25–29CrossRef
Zurück zum Zitat 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 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
Zurück zum Zitat 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 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
Zurück zum Zitat Bruckner S et al (2010) Topology-free querying of protein interaction networks. J Comput Biol 17(3):237–252MathSciNetCrossRef Bruckner S et al (2010) Topology-free querying of protein interaction networks. J Comput Biol 17(3):237–252MathSciNetCrossRef
Zurück zum Zitat 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 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
Zurück zum Zitat Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to algorithms, 3rd edn. The MIT Press, CambridgeMATH Cormen TH, Leiserson CE, Rivest RL, Stein C (2009) Introduction to algorithms, 3rd edn. The MIT Press, CambridgeMATH
Zurück zum Zitat Dondi R, Fertin G, Vialette S (2011) Complexity issues in vertex-colored graph pattern matching. J Discrete Algorithms 9(1):82–99MathSciNetCrossRef Dondi R, Fertin G, Vialette S (2011) Complexity issues in vertex-colored graph pattern matching. J Discrete Algorithms 9(1):82–99MathSciNetCrossRef
Zurück zum Zitat 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 (2007) Sharp tractability borderlines for finding connected motifs in vertex-colored graphs. In: Proceedings of ICALP, LNCS, vol 4596, pp 340–351
Zurück zum Zitat 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 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
Zurück zum Zitat Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman and Company, Murray HillMATH Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman and Company, Murray HillMATH
Zurück zum Zitat Kashani ZRM et al (2009) Kavosh: a new algorithm for finding network motifs. BMC Bioinform 10:318CrossRef Kashani ZRM et al (2009) Kavosh: a new algorithm for finding network motifs. BMC Bioinform 10:318CrossRef
Zurück zum Zitat 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 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
Zurück zum Zitat 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, 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
Zurück zum Zitat 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 (2005) Reaction motifs in metabolic networks. In: Proceedings of WABI, LNBI, vol 3692, pp 178–191
Zurück zum Zitat 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 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
Zurück zum Zitat Marx D (2007) Can you beat treewidth? In: Proceedings of FOCS, pp 169–179 Marx D (2007) Can you beat treewidth? In: Proceedings of FOCS, pp 169–179
Zurück zum Zitat Pinter R, Shachnai H, Zehavi M (2016) Deterministic parameterized algorithms for the graph motif problem. Discrete Appl Math 213:162–178MathSciNetCrossRef Pinter R, Shachnai H, Zehavi M (2016) Deterministic parameterized algorithms for the graph motif problem. Discrete Appl Math 213:162–178MathSciNetCrossRef
Zurück zum Zitat Pinter R, Zehavi M (2014) Algorithms for topology-free and alignment network queries. J Discrete Algorithms 27:29–53MathSciNetCrossRef Pinter R, Zehavi M (2014) Algorithms for topology-free and alignment network queries. J Discrete Algorithms 27:29–53MathSciNetCrossRef
Zurück zum Zitat Rubert DP, Araujo E, Stefanes MA (2015) SIMBio: searching and inferring colorful motifs in biological networks. In: Proceedings of BIBE, pp 1–6 Rubert DP, Araujo E, Stefanes MA (2015) SIMBio: searching and inferring colorful motifs in biological networks. In: Proceedings of BIBE, pp 1–6
Zurück zum Zitat 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 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
Zurück zum Zitat 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 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
Zurück zum Zitat 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 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
Zurück zum Zitat Wernicke S, Rasche F (2006) FANMOD: a tool for fast network motif detection. Bioinformatics 22(9):1152CrossRef Wernicke S, Rasche F (2006) FANMOD: a tool for fast network motif detection. Bioinformatics 22(9):1152CrossRef
Metadaten
Titel
Searching and inferring colorful topological motifs in vertex-colored graphs
verfasst von
Diego P. Rubert
Eloi Araujo
Marco A. Stefanes
Jens Stoye
Fábio V. Martinez
Publikationsdatum
02.06.2020
Verlag
Springer US
Erschienen in
Journal of Combinatorial Optimization / Ausgabe 2/2020
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI
https://doi.org/10.1007/s10878-020-00590-4

Weitere Artikel der Ausgabe 2/2020

Journal of Combinatorial Optimization 2/2020 Zur Ausgabe