### Finding Motifs in Biological Networks

*Riccardo Dondi*

*Wednesday July 16, 2008, DISCo U14, T014, 12:45*

In the context of biological networks analysis, different graph motif problems have been recently introduced [1,4,5]. The vertices of such graph represent the biological components analyzed, while the edges of the graph represent the interactions among such components. Furthermore, the vertices of the graphs are associated with colors, representing the functionalities of the biological components considered. In [4,5] the following problem formulation was introduced: given a motif, where a motif is a multiset of colors, find a connected component of the graph colored by all the colors of the motif. Recently, new problem formulations have been introduced [2,3]. In [2], the following problem formulation was introduced: given a motif, find the minimum number of connected components colored by all the colors of the motif. The problem formulation introduced in [3] asks for the maximum cardinality submotif that occurs as a connected motif in the graph. In this talk, the computational complexity and the approximation complexity of different problem formulations will be discussed. Furthermore, exact and parameterized algorithms for some of the formulations will be presented.

References:

[1] Nadja Betzler, Michael R. Fellows, Christian Komusiewicz, Rolf Niedermeier. Parameterized Algorithms and Hardness Results for Some Graph Motif Problems. 19th Annual Symposium on Combinatorial Pattern Matching (CPM 2008), pp. 31-43, 2008.

[2] Riccardo Dondi, Guillaume Fertin and Stéphane Vialette. Weak pattern matching in colored graphs: Minimizing the number of connected components In Proc. 10th Italian Conference on Theoretical Computer Science (ICTCS 2007), Roma, Italy. World-Scientific Conference Proceedings, pp. 27-38, 2007.

[3] Riccardo Dondi, Guillaume Fertin and Stéphane Vialette. Pattern matching in vertex-colored graphs, Sottomesso.

[4] Michael Fellows, Guillaume Fertin, Danny Hermelin and Stéphane Vialette. Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs In Proc. 34th International Colloquium on Automata, Languages and Programming (ICALP 2007), pp. 340-351, 2007.

[5] Vincent Lacroix, Cristina G. Fernandes, Marie-France Sagot: Motif Search in Graphs: Application to Metabolic Networks. IEEE/ACM Trans. Comput. Biology Bioinform. 3(4): 360-368, 2006.