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 G in the protein-protein interaction graph H of another species with respect to (w.r.t.) orthologous proteins. Two problems are considered: the Exact-(μ G , μ H )-Matching problem and the Max-(μ G , μ H ) problem, where μ G (resp. μ H ) denotes in both problems the maximum number of orthologous proteins in H (resp. G) of a protein in G (resp. H). Following [FLV04], the Exact-(μ 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 )-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, the emphasis here is clearly on bounded degree graphs and extremal small values of parameters μ G and μ H .

Finding Exact and Maximum Occurrences of Protein Complexes in Protein-Protein Interaction Graphs

RIZZI, ROMEO;
2005

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 G in the protein-protein interaction graph H of another species with respect to (w.r.t.) orthologous proteins. Two problems are considered: the Exact-(μ G , μ H )-Matching problem and the Max-(μ G , μ H ) problem, where μ G (resp. μ H ) denotes in both problems the maximum number of orthologous proteins in H (resp. G) of a protein in G (resp. H). Following [FLV04], the Exact-(μ 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 )-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, the emphasis here is clearly on bounded degree graphs and extremal small values of parameters μ G and μ H .
3540287027
protein-protein interaction graphs; orthologous proteins; comparative analysis; bounded degree graphs
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11562/409593
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 9
  • ???jsp.display-item.citation.isi??? 8
social impact