Anzeige
Erschienen in:
2005 | OriginalPaper | Buchkapitel
Finding Exact and Maximum Occurrences of Protein Complexes in Protein-Protein Interaction Graphs
verfasst von : Guillaume Fertin, Romeo Rizzi, Stéphane Vialette
Erschienen in: Mathematical Foundations of Computer Science 2005
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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
.