کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
431362 688513 2009 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Finding occurrences of protein complexes in protein–protein interaction graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Finding occurrences of protein complexes in protein–protein interaction graphs
چکیده انگلیسی

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)(μ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 protein–protein interaction graphs, Journal of Discrete Algorithms 6 (2) (2008) 178–191], 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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 7, Issue 1, March 2009, Pages 90–101
نویسندگان
, , ,