With the advent of high-throughput wet lab technologies the amount of protein interaction data available publicly has increased substantially, in turn spurring a plethora of computational methods for in silico knowledge discovery from this data. In t
his paper, we focus on parameterized methods for modeling and solving complex computational problems encountered in such knowledge discovery from protein data. Specifically, we concentrate on three relevant problems today in proteomics, namely detection of lethal proteins, functional modules and alignments from protein interaction networks. We propose novel graph theoretic models for these problems and devise practical parameterized algorithms. At a broader level, we demonstrate how these methods can be viable alternatives for the several heurestic, randomized, approximation and sub-optimal methods by arriving at parameterized yet optimal solutions for these problems. We substantiate these theoretical results by experimenting on real protein interaction data of S. cerevisiae (budding yeast) and verifying the results using gene ontology.
Cancer forms a robust system and progresses as stages over time typically with increasing aggressiveness and worsening prognosis. Characterizing these stages and identifying the genes driving transitions between them is critical to understand cancer
progression and to develop effective anti-cancer therapies. Here, we propose a novel model of the cancer system as a Boolean state space in which a Boolean network, built from protein interaction and gene-expression data from different stages of cancer, transits between Boolean satisfiability states by editing interactions and flipping genes. The application of our model (called BoolSpace) on three case studies - pancreatic and breast tumours in human and post spinal-cord injury in rats - reveals valuable insights into the phenomenon of cancer progression. In particular, we notice that several of the genes flipped are serine/threonine kinases which act as natural cellular switches and that different sets of genes are flipped during the initial and final stages indicating a pattern to tumour progression. We hypothesize that robustness of cancer partly stems from passing of the baton between genes at different stages, and therefore an effective therapy should target a cover set of these genes. A C/C++ implementation of BoolSpace is freely available at: http://www.bioinformatics.org.au/tools-data
Protein complexes conserved across species indicate processes that are core to cellular machinery (e.g. cell-cycle or DNA damage-repair complexes conserved across human and yeast). While numerous computational methods have been devised to identify co
mplexes from the protein interaction (PPI) networks of individual species, these are severely limited by noise and errors (false positives) in currently available datasets. Our analysis using human and yeast PPI networks revealed that these methods missed several important complexes including those conserved between the two species (e.g. the MLH1-MSH2-PMS2-PCNA mismatch-repair complex). Here, we note that much of the functionalities of yeast complexes have been conserved in human complexes not only through sequence conservation of proteins but also of critical functional domains. Therefore, integrating information of domain conservation might throw further light on conservation patterns between yeast and human complexes.
Over the last few years, several computational techniques have been devised to recover protein complexes from the protein interaction (PPI) networks of organisms. These techniques model dense subnetworks within PPI networks as complexes. However, our
comprehensive evaluations revealed that these techniques fail to reconstruct many gold standard complexes that are sparse in the networks (only 71 recovered out of 123 known yeast complexes embedded in a network of 9704 interactions among 1622 proteins). In this work, we propose a novel index called Component-Edge (CE) score to quantitatively measure the notion of complex derivability from PPI networks. Using this index, we theoretically categorize complexes as sparse or dense with respect to a given network. We then devise an algorithm SPARC that selectively employs functional interactions to improve the CE scores of predicted complexes, and thereby elevates many of the sparse complexes to dense. This empowers existing methods to detect these sparse complexes. We demonstrate that our approach is effective in reconstructing significantly many complexes missed previously (104 recovered out of the 123 known complexes or ~47% improvement).
Complexes of physically interacting proteins are one of the fundamental functional units responsible for driving key biological mechanisms within the cell. Their identification is therefore necessary not only to understand complex formation but also
the higher level organization of the cell. With the advent of high-throughput techniques in molecular biology, significant amount of physical interaction data has been cataloged from organisms such as yeast, which has in turn fueled computational approaches to systematically mine complexes from the network of physical interactions among proteins (PPI network). In this survey, we review, classify and evaluate some of the key computational methods developed till date for the identification of protein complexes from PPI networks. We present two insightful taxonomies that reflect how these methods have evolved over the years towards improving automated complex prediction. We also discuss some open challenges facing accurate reconstruction of complexes, the crucial ones being presence of high proportion of errors and noise in current high-throughput datasets and some key aspects overlooked by current complex detection methods. We hope this review will not only help to condense the history of computational complex detection for easy reference, but also provide valuable insights to drive further research in this area.
