Pattern Matching in Protein-Protein Interaction Graphs
Stéphane Vialette,
Université Paris-Est Marne-la-Vallée –
Abstract:
In the context of comparative analysis of protein-protein interaction graphs, we use a graph-based formalism to detect the preservation of a given protein complex (pattern graph) in the protein-protein interaction graph (target graph) of another species with respect to(w.r.t.) orthologous proteins. We give an efficient exponential-time randomized algorithm in case the occurrence of the pattern graph in the target graph is requiredto be exact. For approximate occurrences, we prove a tight inapproximability result and give four approximation algorithms that deal withbounded degree graphs, small ortholog numbers, linear forests andvery simple hard instances, respectively.
Date: 2008-Sep-18 Time: 14:00:00 Room: 336
For more information:
Upcoming Events
INESC-ID ESR Talks – February 2023

If you are a masters/PhD student or a postdoctoral fellow, come and present your work in an informal and friendly environment – and savour some tasty snacks!
Individual talks will be 10-15 minutes plus time for feedback. Enroll on your selected date by emailing pedro.ferreira[at]inesc-id.pt.
Happening on the second Wednesday of every month (4pm-5pm):
- 15 February (Alves Redol, Room 9)
- 15 March (Alves Redol, Room 9)
- 12 April (Alves Redol, Room 9)
- 10 May (Alves Redol, Room 9)
- 14 June (Alves Redol, Room 9)
- 12 July (Alves Redol, Room 9)
We hope to see you there!