Algorithmic and Artificial Intelligence Methods for Protein Bioinformatics

Chapter 18

Network Algorithms For Protein Interactions

SUELY OLIVEIRA

18.1 Introduction

Graphs or networks are a fundamental way of representing connections between objects or concepts. Connections between proteins can identify functional groups of proteins, and how various proteins work together. Studies of the function of proteins are fundamental in current biological research [40]. We have been able to sequence entire genomes and can identify large numbers of individual genes. However, while the syntax of the genes is rapidly becoming clearer, the semantics or meaning of those genes is still mostly shrouded in mystery. This mystery has deepened in recent years as it has become apparent hat there is no one-to-one connection between genes and the proteins that actually perform functions in organisms.

In order to unlock the information about how proteins carry out their function, we first need to understand which proteins work together. High-throughput experiments have been able to create interaction networks for large numbers of proteins. One particular method is tandem affinity purification (TAP), which was developed in the late 1990s [31], and has been used to obtain large-scale interaction networks. For example, a large-scale protein–protein interaction (PPI) network was constructed for baker's yeast (Saccharomyces cerevisiae) [21] using TAP combined with mass spectrometry to identify the proteins in the complexes. The study [21] identified 7123 interactions among a set of ...