کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
431680 688613 2008 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Bounded list injective homomorphism for comparative analysis of protein–protein interaction graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Bounded list injective homomorphism for comparative analysis of protein–protein interaction graphs
چکیده انگلیسی

Comparing genomic properties of multiple species at varying evolutionary distances is a powerful approach for studying biological and evolutionary principles. 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. We show that the problem is polynomial-time solvable provided that each protein has at most two orthologs in the other species, but is hard for three. Also, we suggest ways to cope with hardness by proposing three translations of the problem into well-known combinatorial optimization problems, thereby allowing the use of many recent results in fast exponential-time algorithms. Motivated by the need for more accurate models, we conclude by giving and discussing three natural extensions of the problem.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Discrete Algorithms - Volume 6, Issue 2, June 2008, Pages 178–191
نویسندگان
, , ,