Article ID Journal Published Year Pages File Type
431680 Journal of Discrete Algorithms 2008 14 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,