Predicting protein interactions via parsimonious network history inference

MS-PyCloud: A Cloud Computing-Based Pipeline for Proteomic and Glycoproteomic Data Analyses

Rapid development and wide adoption of mass spectrometry-based glycoproteomic technologies have empowered scientists to study proteins and protein glycosylation in complex samples on a large scale. This progress has also created unprecedented challenges for individual laboratories to store, manage, and analyze proteomic and glycoproteomic data, both in the cost for proprietary software and high-performance computing and in the long processing time that discourages on-the-fly changes of data processing settings required in explorative and discovery analysis. We developed an open-source, cloud computing-based pipeline, MS-PyCloud, with graphical user interface (GUI), for proteomic and glycoproteomic data analysis. The major components of this pipeline include data file integrity validation, MS/MS database search for spectral assignments to peptide sequences, false discovery rate estimation, protein inference, quantitation of global protein levels, and specific glycan-modified glycopeptides as well as other modification-specific peptides such as phosphorylation, acetylation, and ubiquitination. To ensure the transparency and reproducibility of data analysis, MS-PyCloud includes open-source software tools with comprehensive testing and versioning for spectrum assignments. Leveraging public cloud computing infrastructure via Amazon Web Services (AWS), MS-PyCloud scales seamlessly based on analysis demand to achieve fast and efficient performance. Application of the pipeline to the analysis of large-scale LC-MS/MS data sets demonstrated the effectiveness and high performance of MS-PyCloud. The software can be downloaded at https://github.com/huizhanglab-jhu/ms-pycloud.

Proteogenomic insights suggest druggable pathways in endometrial carcinoma

We characterized a prospective endometrial carcinoma (EC) cohort containing 138 tumors and 20 enriched normal tissues using 10 different omics platforms. Targeted quantitation of two peptides can predict antigen processing and presentation machinery activity, and may inform patient selection for immunotherapy. Association analysis between MYC activity and metformin treatment in both patients and cell lines suggests a potential role for metformin treatment in non-diabetic patients with elevated MYC activity. PIK3R1 in-frame indels are associated with elevated AKT phosphorylation and increased sensitivity to AKT inhibitors. CTNNB1 hotspot mutations are concentrated near phosphorylation sites mediating pS45-induced degradation of β-catenin, which may render Wnt-FZD antagonists ineffective. Deep learning accurately predicts EC subtypes and mutations from histopathology images, which may be useful for rapid diagnosis. Overall, this study identified molecular and imaging markers that can be further investigated to guide patient stratification for more precise treatment of EC.

Ancestral state reconstruction of metabolic pathways across pangenome ensembles

As genome sequencing efforts are unveiling the genetic diversity of the biosphere with an unprecedented speed, there is a need to accurately describe the structural and functional properties of groups of extant species whose genomes have been sequenced, as well as their inferred ancestors, at any given taxonomic level of their phylogeny. Elaborate approaches for the reconstruction of ancestral states at the sequence level have been developed, subsequently augmented by methods based on gene content. While these approaches of sequence or gene-content reconstruction have been successfully deployed, there has been less progress on the explicit inference of functional properties of ancestral genomes, in terms of metabolic pathways and other cellular processes. Herein, we describe PathTrace, an efficient algorithm for parsimony-based reconstructions of the evolutionary history of individual metabolic pathways, pivotal representations of key functional modules of cellular function. The algorithm is implemented as a five-step process through which pathways are represented as fuzzy vectors, where each enzyme is associated with a taxonomic conservation value derived from the phylogenetic profile of its protein sequence. The method is evaluated with a selected benchmark set of pathways against collections of genome sequences from key data resources. By deploying a pangenome-driven approach for pathway sets, we demonstrate that the inferred patterns are largely insensitive to noise, as opposed to gene-content reconstruction methods. In addition, the resulting reconstructions are closely correlated with the evolutionary distance of the taxa under study, suggesting that a diligent selection of target pangenomes is essential for maintaining cohesiveness of the method and consistency of the inference, serving as an internal control for an arbitrary selection of queries. The PathTrace method is a first step towards the large-scale analysis of metabolic pathway evolution and our deeper understanding of functional relationships reflected in emerging pangenome collections.

A parsimonious approach for recognizing SARS-CoV-2 and host interactions

Effective countermeasures against the severe acute respiratory syndrome coronavirus 2 (SARS‐CoV‐2) demand a better understanding of the pathogen‐host interactions. However, such information about the targets, responses, and effects in the host due to the virus is limited, especially so in the case of newly emerged pathogens. The peptide domains that form the interfaces of host and pathogen interacting proteins being evolutionarily conserved, it may be hypothesized that such interactions can be inferred from the similarities in the nucleotide sequences between the host and the pathogen. This communication reports the results of a study based on a parsimonious approach for the identification of the host‐virus interactions, where sequence complementarity between the human and SARS‐Cov‐2 genomes was used to predict several interactions between the host and SARS‐CoV‐2 at different levels of biological organization. In particular, the findings are suggestive of a direct effect of SARS‐CoV‐2 on cardiac health. The existing literature on host responses to SARS‐CoV‐2 and other viruses attest to many of these predicted interactions, supporting the utility of the proposed approach for the identification of host interactions with other novel pathogens.

Maximum likelihood reconstruction of ancestral networks by integer linear programming

MOTIVATION

The study of the evolutionary history of biological networks enables deep functional understanding of various bio-molecular processes. Network growth models, such as the Duplication-Mutation with Complementarity (DMC) model, provide a principled approach to characterizing the evolution of protein-protein interactions (PPIs) based on duplication and divergence. Current methods for model-based ancestral network reconstruction primarily use greedy heuristics and yield sub-optimal solutions.

RESULTS

We present a new Integer Linear Programming (ILP) solution for maximum likelihood reconstruction of ancestral PPI networks using the DMC model. We prove the correctness of our solution that is designed to find the optimal solution. It can also use efficient heuristics from general-purpose ILP solvers to obtain multiple optimal and near-optimal solutions that may be useful in many applications. Experiments on synthetic data show that our ILP obtains solutions with higher likelihood than those from previous methods, and is robust to noise and model mismatch. We evaluate our algorithm on two real PPI networks, with proteins from the families of bZIP transcription factors and the Commander complex. On both the networks, solutions from our ILP have higher likelihood and are in better agreement with independent biological evidence from other studies.

AVAILABILITY AND IMPLEMENTATION

A Python implementation is available at https://bitbucket.org/cdal/network-reconstruction.

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.

A New Paradigm for Identifying Reconciliation-Scenario Altering Mutations Conferring Environmental Adaptation

An important goal in microbial computational genomics is to identify crucial events in the evolution of a gene that severely alter the duplication, loss, and mobilization patterns of the gene within the genomes in which it disseminates. In this article, we formalize this microbiological goal as a new pattern-matching problem in the domain of gene tree and species tree reconciliation, denoted "Reconciliation-Scenario Altering Mutation (RSAM) Discovery." We propose an [Formula: see text] time algorithm to solve this new problem, where m and n are the number of vertices of the input gene tree and species tree, respectively, and k is a user-specified parameter that bounds from above the number of optimal solutions of interest. The algorithm first constructs a hypergraph representing the k highest scoring reconciliation scenarios between the given gene tree and species tree, and then interrogates this hypergraph for subtrees matching a prespecified RSAM pattern. Our algorithm is optimal in the sense that the number of hypernodes in the hypergraph can be lower bounded by [Formula: see text]. We implement the new algorithm as a tool, called RSAM-finder, and demonstrate its application to the identification of RSAMs in toxins and drug resistance elements across a data set spanning hundreds of species.

Algorithms for Regular Tree Grammar Network Search and Their Application to Mining Human-viral Infection Patterns

Network querying is a powerful approach to mine molecular interaction networks. Most state-of-the-art network querying tools either confine the search to a prespecified topology in the form of some template subnetwork, or do not specify any topological constraints at all. Another approach is grammar-based queries, which are more flexible and expressive as they allow for expressing the topology of the sought pattern according to some grammar-based logic. Previous grammar-based network querying tools were confined to the identification of paths. In this article, we extend the patterns identified by grammar-based query approaches from paths to trees. For this, we adopt a higher order query descriptor in the form of a regular tree grammar (RTG). We introduce a novel problem and propose an algorithm to search a given graph for the k highest scoring subgraphs matching a tree accepted by an RTG. Our algorithm is based on the combination of dynamic programming with color coding, and includes an extension of previous k-best parsing optimization approaches to avoid isomorphic trees in the output. We implement the new algorithm and exemplify its application to mining viral infection patterns within molecular interaction networks. Our code is available online.

Multivariate Analysis of Side Effects of Drug Molecules Based on Knowledge of Protein Bindings and ProteinProtein Interactions

Here, we examined the relationships between 969 side effects associated with 658 drugs and their 1368 human protein targets using our hybrid approaches. Firstly, L-shaped PLS (LPLS) was used to construct a multivariate model of side effects and protein bindings of drug molecules. LPLS is an extension of standard PLS regression, where, in addition to the response matrix Y and the regressor matrix X, an extra data matrix Z is constructed that summarizes the background information of X. X and Y are matrices comprising drugs-target proteins, and drugs-side effects, respectively. The Z matrix is the proteinprotein interaction data. From the loading plot of Y, we could identify two remarkable side effects (urinary incontinence and increased salivation) From the corresponding loading plot of X, the responsible protein targets causing each side effect could be estimated (sodium channels and gamma-aminobutyric acid (GABA) receptors). The loading plot of the Z matrix indicated that the GABA receptors interact with each other and they heavily influence the side effect of increased salivation. Secondly, Bayesian classifier methods were separately applied to the cases of the two side effects. That is, the Bayesian classifier method was used to classify drug molecules as binding or not binding to the responsible protein targets associated with each side effect. Using atom-coloring techniques, it was possible to estimate which fragments on the drug molecule might cause the specific side effects. This information is valuable for drug design to avoid specific side effects.

LocalAli: an evolutionary-based local alignment approach to identify functionally conserved modules in multiple networks

MOTIVATION

Sequences and protein interaction data are of significance to understand the underlying molecular mechanism of organisms. Local network alignment is one of key systematic ways for predicting protein functions, identifying functional modules and understanding the phylogeny from these data. Most of currently existing tools, however, encounter their limitations, which are mainly concerned with scoring scheme, speed and scalability. Therefore, there are growing demands for sophisticated network evolution models and efficient local alignment algorithms.

RESULTS

We developed a fast and scalable local network alignment tool called LocalAli for the identification of functionally conserved modules in multiple networks. In this algorithm, we firstly proposed a new framework to reconstruct the evolution history of conserved modules based on a maximum-parsimony evolutionary model. By relying on this model, LocalAli facilitates interpretation of resulting local alignments in terms of conserved modules, which have been evolved from a common ancestral module through a series of evolutionary events. A meta-heuristic method simulated annealing was used to search for the optimal or near-optimal inner nodes (i.e. ancestral modules) of the evolutionary tree. To evaluate the performance and the statistical significance, LocalAli were tested on 26 real datasets and 1040 randomly generated datasets. The results suggest that LocalAli outperforms all existing algorithms in terms of coverage, consistency and scalability, meanwhile retains a high precision in the identification of functionally coherent subnetworks.

AVAILABILITY

The source code and test datasets are freely available for download under the GNU GPL v3 license at https://code.google.com/p/localali/.

CONTACT

jialu.hu@fu-berlin.de or knut.reinert@fu-berlin.de.

SUPPLEMENTARY INFORMATION

Supplementary data are available at Bioinformatics online.