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:

• jcarrico@kdbio.inesc-id.pt