Finding occurrences of protein complexes in proteinprotein interaction graphs ? ??
In the context of comparative analysis of proteinprotein interaction graphs, we use a graph-based formalism to detect the preservation of a given protein complex G in the proteinprotein interaction graph H of another species with respect to (w.r.t.) orthologous proteins. Two problems are considered: the Exact-(?G,?H) ( ? G , ? H ) -Matching problem and the Max-(?G,?H) ( ? G , ? H ) -Matching problems, where ?G ? G (resp. ?H ? H ) denotes in both problems the maximum number of orthologous proteins in H (resp. G) of a protein in G (resp. H). Following [I. Fagnot, G. Lelandais, S. Vialette, Bounded list injective homomorphism for comparative analysis of proteinprotein interaction graphs, Journal of Discrete Algorithms 6 (2) (2008) 178191], the Exact-(?G,?H) ( ? G , ? H ) -Matching problem asks for an injective homomorphism of G to H w.r.t. orthologous proteins. The optimization version is called the Max-(?G,?H) ( ? G , ? H ) -Matching problem and is concerned with finding an injective mapping of a graph G to a graph H w.r.t. orthologous proteins that matches as many edges of G  as possible. For both problems, we essentially focus on bounded degree graphs and extremal small values of parameters ?G ? G and ?H ? H .
proteinprotein interaction graph computational biology computational complexity approximation algorithm parameterized complexity