review articles

Doi: 10.1145/2160718.2160738

By NiR AtiAs AND RoDeD shARAN
Comparative
Analysis of
Protein
Networks:
hard Problems,
Practical
solutions

many diseases (for example, Huntington’s disease26) are the result of small changes to a single protein and, consequently, to its set of interacting partners and functionality. The mapping of proteins and their interactions and the interpretation of this data are thus a fundamental challenge in modern biology with important applications in disease diagnosis and therapy. 15

The last two decades have witnessed a great shift in biological research. While classical research focused on a single gene or subsystem of a specific organism, the emergence of high-throughput technologies for measuring different molecular aspects of the cell has led to a different, systems-level approach. By this approach, genome-wide data is used to build computational models of certain aspects of the cell, thereby generating new biological hypotheses that can be experimentally tested and used to further improve the models in an iterative manner.

A prime example for this technological revolution is the development of techniques for measuring protein– protein interactions (PPIs). Historically, such interactions were measured at small scale—one or few interactions at a time. The development of automated, large-scale measurement technologies such as the yeast two-hybrid system10 and the co-immunoprecipita-tion assay1 has enabled the mapping of

Examining tools that provide valuable insight about molecular components within a cell.

key insights

A Holy GrAIl of biological research is deciphering the workings of a cell—the elementary unit of life. The main building blocks of the cell are macromolecules called proteins; they are key factors in driving cellular processes and determining the structure and function of cells. Proteins do not work in isolation but rather physically interact to form cellular machineries or transmit molecular signals. A modification of a single protein may have dramatic effects on the cell; indeed,

the explosion of biological network
data necessitates methods to filter,
interpret, and organize this data into
modules of cellular machinery.
the comparative analysis of networks
from multiple species has proven to
be a powerful tool in detecting
significant biological patterns that
are conserved across species and in
enabling their interpretation.
Comparative network analysis presents
hard computational challenges such as
graph and subgraph isomorphism and
detecting heavy subgraphs; these can be
tackled to near-optimality by a combination
of heuristic, parameterized, and integer
programming-based approaches.