This thesis describes the development of PINALOG, a protein interaction
network alignment method, and its application to the area of protein function
prediction and protein complex detection. Protein-protein interactions
(PPI) play an important role in the function of biological processes. Advances
in high-throughput technology have produced a large amount of
protein-protein interaction data, enabling analyses at the system level. Although
protein-protein interaction networks (PPINs) vary between species,
there are components of them that perform similar biological functions and
these are likely to be conserved across species. Comparison of the protein
interaction networks from different species yields understanding of the
evolution of species, as well as a means to predict protein function and
conserved components.
An alignment method, PINALOG, has been developed which globally
aligns the similar parts of the networks using information from protein
sequences, protein functions and network topology in a seed-and-extend
framework. The results on human and yeast network alignment revealed
conserved subnetworks that are components of similar biological processes
such as the proteasome or transcription related processes. The alignments
of several pairs of species confirm the superior performance of PINALOG
over commonly used methods such as Graemlin and IsoRank in terms of finding
a large conserved network as well as detecting biologically meaningful
mappings of the proteins in the two aligned species.
The alignment method also suggested an approach to perform protein
complex prediction by knowledge transfer from one species to another. In
addition the implications for function prediction of proteins in the "twilight"
zone where there is little or no sequence similarity were explored. A web
server for PINALOG was developed to provide users access to the alignment
method.