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)-Matching problems, 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 [I. Fagnot, G. Lelandais, S. Vialette, Bounded list injective homomorphism for comparative analysis of protein–protein interaction graphs, Journal of Discrete Algorithms 6 (2) (2008) 178–191], 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, we essentially focus on bounded degree graphs and extremal small values of parameters μG and μH.

Finding occurrences of protein complexes in protein-protein interaction graphs.

RIZZI, ROMEO;
2009-01-01

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)-Matching problems, 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 [I. Fagnot, G. Lelandais, S. Vialette, Bounded list injective homomorphism for comparative analysis of protein–protein interaction graphs, Journal of Discrete Algorithms 6 (2) (2008) 178–191], 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, we essentially focus on bounded degree graphs and extremal small values of parameters μG and μH.
2009
Computational biology, Computational complexity, Approximation algorithm, Parameterized complexity, Protein–protein interaction graph
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: https://hdl.handle.net/11562/409557
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? ND
social impact