speCial interest page
isomorphic protein Graphs
The question of whether two graphs are isomorphic
may seem to be of only academic interest, but in fact it
is an important question in modern biological research.
We are all familiar with the concept that the DNA in
our cells carries our genetic information. But each cell
also contains thousands of proteins, long chains of various kinds of amino acids. There are up to 20 different
kinds of amino acids, and the sequence of amino acids determines the three-dimensional shape of a given
protein as well as its function within the cell. Common
categories of proteins according to their functions include the following:
Enzymes: Initiate chemical processes within the
cell and form new molecules
Antibodies: Recognize and defend against foreign
particles such as bacteria
Transport: Carry molecules such as oxygen
throughout the cell and the body
Structural: Give the cell its shape and structure
Hormones: Transmit signals throughout the body
to coordinate biological processes
Proteins within a cell do not act in isolation;
rather, they interact with other proteins in the cell to
carry out complex tasks such as DNA replication or
to transport oxygen throughout the cell. Protein-toprotein interactions (PPI) are therefore what make a
cell function, and any change, however minor, in a
given protein could affect the PPIs for that protein and
thus affect the entire cell. Knowledge of cell biology
at the PPI level is of great interest for identifying the
underlying cause of disease and development of therapeutics.
Now consider the various proteins within a
given cell as nodes, and two proteins that interact as
connected by an arc. Voilà—we have a graph! And
given the number of proteins within a cell and the number and complexity of their interactions, it is a huge
graph. A number of experiments have been done to
determine what this graph looks like in various organisms, but the data gained seem to have low reliability. This problem has promoted interest in comparing
PPIs across species to find commonalities that would
reinforce information about the functionality of those
interactions. Basically, researchers are looking for isomorphic graphs (or subgraphs) between cells from two
different species.
The general problem of determining whether two
graphs are isomorphic has no known polynomial-time
solution—there is no known efficient algorithm. The
performance of an inefficient algorithm might improve
if certain conditions on the graphs are met: Are they
both planar? Are they both trees? Such simplifications
are unlikely to occur in the biological world of cell proteins. Consequently, various “heuristic” approaches
(read “educated guesses”) are used. One of these approaches ranks the similarities between the sequences
of amino acids forming the proteins, one from each
species, that might be considered as matching pairs
for a graph isomorphism. This ranking algorithm is
based on the iterative PageRank algorithm (invented
by Google cofounder Larry Page) that ranks Web page
x based on the number of pages that link to x and the
PageRank value of those pages.
“Comparative Analysis of Protein Networks: Hard Problems, Practical Solutions,” Atias. N., and Sharan, R.,
Communications of the ACM, May 2012.
http://www.ncbi.nlm.nih.gov/About/primer/genetics_
genome.html
http://ghr.nlm.nih.gov/handbook/howgeneswork/protein
C h a p t e r
6 6
isomorphic protein Graphs
The question of whether two graphs are isomorphic
may seem to be of only academic interest, but in fact it
is an important question in modern biological research.
We are all familiar with the concept that the DNA in
our cells carries our genetic information. But each cell
also contains thousands of proteins, long chains of various kinds of amino acids. There are up to 20 different
kinds of amino acids, and the sequence of amino acids determines the three-dimensional shape of a given
protein as well as its function within the cell. Common
categories of proteins according to their functions include the following:
Enzymes: Initiate chemical processes within the
cell and form new molecules
Antibodies: Recognize and defend against foreign
particles such as bacteria
Transport: Carry molecules such as oxygen
throughout the cell and the body
Structural: Give the cell its shape and structure
Hormones: Transmit signals throughout the body
to coordinate biological processes
Proteins within a cell do not act in isolation;
rather, they interact with other proteins in the cell to
carry out complex tasks such as DNA replication or
to transport oxygen throughout the cell. Protein-toprotein interactions (PPI) are therefore what make a
cell function, and any change, however minor, in a
given protein could affect the PPIs for that protein and
thus affect the entire cell. Knowledge of cell biology
at the PPI level is of great interest for identifying the
underlying cause of disease and development of therapeutics.
Now consider the various proteins within a
given cell as nodes, and two proteins that interact as
connected by an arc. Voilà—we have a graph! And
given the number of proteins within a cell and the number and complexity of their interactions, it is a huge
graph. A number of experiments have been done to
determine what this graph looks like in various organisms, but the data gained seem to have low reliability. This problem has promoted interest in comparing
PPIs across species to find commonalities that would
reinforce information about the functionality of those
interactions. Basically, researchers are looking for isomorphic graphs (or subgraphs) between cells from two
different species.
The general problem of determining whether two
graphs are isomorphic has no known polynomial-time
solution—there is no known efficient algorithm. The
performance of an inefficient algorithm might improve
if certain conditions on the graphs are met: Are they
both planar? Are they both trees? Such simplifications
are unlikely to occur in the biological world of cell proteins. Consequently, various “heuristic” approaches
(read “educated guesses”) are used. One of these approaches ranks the similarities between the sequences
of amino acids forming the proteins, one from each
species, that might be considered as matching pairs
for a graph isomorphism. This ranking algorithm is
based on the iterative PageRank algorithm (invented
by Google cofounder Larry Page) that ranks Web page
x based on the number of pages that link to x and the
PageRank value of those pages.
“Comparative Analysis of Protein Networks: Hard Problems, Practical Solutions,” Atias. N., and Sharan, R.,
Communications of the ACM, May 2012.
http://www.ncbi.nlm.nih.gov/About/primer/genetics_
genome.html
http://ghr.nlm.nih.gov/handbook/howgeneswork/protein
C h a p t e r
6 6