Protein functionality analysis through protein-protein interaction networks

Since the sequencing of the human genome was brought to fruition [142, 66], the field of genetics now stands on the threshold of significant theoretical and practical advances. Crucial to furthering these investigations is a comprehensive understanding of the expression, function, and regulation of the proteins encoded by an organism [155]. This understanding is the subject of the discipline of proteomics. Proteomics encompasses a wide range of approaches and applications intended to explicate how complex biological processes occur at a molecular level, how they differ in various cell types, and how they are altered in disease states. In particular, the elucidation of protein function has been, and remains, one of the most central problems in computational biology. Proteins are macromolecules that serve as building blocks and functional components of a cell, and account for the second largest fraction of the cellular weight after water. Proteins are responsible for some of the most important functions in an organism, such as constitution of the organs (structural proteins), the catalysis of biochemical reactions necessary for metabolism (enzymes), and the maintenance of the cellular environment (transmembrane proteins). Thus, proteins are the most essential and versatile macromolecules of life, and the knowledge of their functions is a crucial link in the development of new drugs, better crops, and even the development of synthetic biochemicals such as biofuels [49]. A recent review noted that a large fraction of currently sequenced complete genomes has at least half of their gene entries having ambiguous annotations [59]. The classical way to predict protein functions is to find homologies between an unannotated protein and other proteins using sequence similarity algorithms, such as FASTA [106] and PSI-BLAST [85]. The function of the unannotated protein can then be assigned according to the annotated proteins with similar sequences. In addition, several computational approaches are proposed based on correlated evolution mechanisms of genes. For example, the domain fusion analysis infers that a pair of proteins interacts with each other and thus performs related functions [88]. In recent years, the high-throughput bio-techniques have provided additional opportunities for inference of protein functions. Protein-protein interaction (PPI) data, enriched by high-throughput experiments including yeast two-hybrid analysis [67][139], mass spectrometry [50][62] and synthetic lethality screen [3], have provided the important clues of functional associations between proteins. It has been observed that proteins seldom act as single isolated species in the performance of their functions; rather, proteins involved in the same cellular processes often interact with each other. Therefore, the functions of uncharacterized proteins can be predicted through comparison with the interactions of similar known proteins. A detailed examination of a protein-protein interaction network can thus yield significant new insights into protein functions. The protein interaction network can be described as a complex system of proteins linked by interactions. Examples of complex systems include social networks, the World Wide Web and biological systems such as metabolic networks, gene regulatory networks and protein interaction networks. Recently, the studies of complex systems [4, 96] have attempted to understand and characterize the structural behaviors of the systems in a topological perspective. As interesting features, the small-world properties [147], scale-free degree distributions [14, 15] and hierarchical modularity [115] have been observed in complex systems. These unique characteristics can facilitate the efficient and accurate analysis of protein interaction networks. The study in this dissertation is based on the theoretical and quantitative characterization of protein interaction networks. In particular, it focuses on the efficientand accurate analysis of protein functionality through protein interaction networks. As a preliminary work of this dissertation, the reliabilities of protein-protein interactions are assessed using the topological features of the network. A novel measurement to quantify the interaction is proposed. In the next step, the weighted interaction networks of proteins, which are created by assigning the reliability to each edge as a weight, are used to detect functional modules and predict protein functions. Novel algorithms, based on information flow, spanning tree, and neural networks are proposed. This study can be underlying bases for functional characterization of proteins and also provides a guideline for the deeper analysis of biological networks such as network inference and network dynamics.