Discovery and analysis of patterns in molecular networks: Link prediction, network analysis, and applications to novel drug target discovery

One of the most challenging problems in the post-genomic era for computer scientists and bioinformaticians is to identify meaningful patterns from a huge amount of data describing a variety of molecular systems. Networks provide a unifying representation for these various molecular systems, such as protein interaction maps, transcriptional regulations, metabolites and reactions, signaling transduction pathways, and functional associations. On one hand, computational determination of molecular networks is of interest due to the tremendous labor and cost associated with large-scale wet-lab experiments. On the other hand, novel methods and approaches are in need to extract useful and meaningful patterns from established large-scale molecular networks.;In this thesis, we tackle the problems of computationally predicting links to construct large-scale protein interaction maps, transcriptional regulatory networks, and disease related heterogeneous networks. In particular, we adopted a supervised learning framework for link prediction in protein interaction maps of a human pathogen, and performed network analysis to extract and identify novel drug targets for disease treatment. We developed and demonstrated a semi-supervised learning approach for link prediction in a transcriptional regulatory network, and further analyzed the biological relevance of identified links.;In the thesis, we also developed and performed computational approaches to extract biologically meaningful patterns in large-scale protein interaction maps and disease- and gene-related networks. Similar to other real-life systems, molecular networks are dynamic and context-dependent. We comparatively analyzed the static conglomerate networks and context-dependent networks and systematically revealed their differences in global topological characteristics, subnetwork structure components, and functional compartments. Finally, we applied network analysis to extract interesting patterns in networks of rare human diseases and disease causing genes and identified their unique properties.