Motivation: Elucidation of protein native states from amino acid sequences is a primary computational challenge. Modern computational and experimental methodologies, such as molecular coevolution and chemical cross-linking mass-spectrometry allowed protein structural characterization to previously intangible systems. Despite several independent successful examples, data from these distinct methodologies have not been systematically studied in conjunction. One challenge of structural inference using coevolution is that it is limited to sequence fragments within a conserved and unique domain for which sufficient sequence datasets are available. Therefore, coupling coevolutionary data with complimentary distance constraints from orthogonal sources can provide additional precision to structure prediction methodologies. Results: In this work, we present a methodology to combine residue interaction data obtained from coevolutionary information and cross-linking/mass spectrometry distance constraints in order to identify functional states of proteins. Using a combination of structure-based models (SBMs) with optimized Gaussian-like potentials, secondary structure estimation and simulated annealing molecular dynamics, we provide an automated methodology to integrate constraint data from diverse sources in order to elucidate the native conformation of full protein systems with distinct complexity and structural topologies. We show that cross-linking mass spectrometry constraints improve the structure predictions obtained from SBMs and coevolution signals, and that the constraints obtained by each method have a useful degree of complementarity that promotes enhanced fold estimates. Availability and implementation: Scripts and procedures to implement the methodology presented herein are available at https://github.com/mcubeg/DCAXL. Supplementary information: Supplementary data are available at Bioinformatics online.

Group testing, also known as pooling, is a common technique used in high-throughput experiments in molecular biology to significantly reduce the number of tests required to identify rare biological interactions while correcting for experimental noise. Central to the group testing problem are 1) a pooling design that lays out how items are grouped together into pools for testing and 2) a decoder that interprets the results of the tested pools, identifying the active compounds. In this work, we take advantage of decoder guarantees from the field of compressed sensing (CS) to address the problem of efficient and reliable detection of biological interaction in noisy high-throughput experiments. We also use efficient combinatorial algorithms from group testing as well as established measurement matrices from CS to create pooling designs. First, we formulate the group testing problem in terms of a Boolean CS framework. We then propose a low-complexity l1-norm decoder to interpret pooling test results and identify active compounds. We demonstrate the robustness of the proposed l1-norm decoder in simulated experiments with false-positive and false-negative error rates typical of high-throughput experiments. When benchmarked against the current state-of-the-art methods, the proposed l1-norm decoder provides superior error correction for the majority of the cases considered while being notably faster computationally. Additionally, we test the performance of the l1-norm decoder against a real experimental data set, where 12,675 prey proteins were screened against 12 bait proteins. Lastly, we study the impact of different sparse pooling design matrices on decoder performance and show that the shifted transversal design (STD) is the most suitable among the pooling designs surveyed for biological applications of CS.

Protein-protein interactions are often mediated by flexible loops that experience conformational dynamics on the microsecond to millisecond time scales. NMR relaxation studies can map these dynamics. However, defining the network of inter-converting conformers that underlie the relaxation data remains generally challenging. Here, we combine NMR relaxation experiments with simulation to visualize networks of inter-converting conformers. We demonstrate our approach with the apo Pin1-WW domain, for which NMR has revealed conformational dynamics of a flexible loop in the millisecond range. We sample and cluster the free energy landscape using Markov State Models (MSM) with major and minor exchange states with high correlation with the NMR relaxation data and low NOE violations. These MSM are hierarchical ensembles of slowly interconverting, metastable macrostates and rapidly interconverting microstates. We found a low population state that consists primarily of holo-like conformations and is a "hub" visited by most pathways between macrostates. These results suggest that conformational equilibria between holo-like and alternative conformers pre-exist in the intrinsic dynamics of apo Pin1-WW. Analysis using MutInf, a mutual information method for quantifying correlated motions, reveals that WW dynamics not only play a role in substrate recognition, but also may help couple the substrate binding site on the WW domain to the one on the catalytic domain. Our work represents an important step towards building networks of inter-converting conformational states and is generally applicable.

In this paper, a novel framework is presented to estimate protein-protein interactions (PPIs) and domain-domain interactions (DDIs) based on a belief propagation estimation method that efficiently computes interaction probabilities. Experimental interactions, domain architecture, and gene ontology (GO) annotations are used to create a factor graph representation of the joint probability distribution of pairwise protein and domain interactions. Bound structures are used asa priorievidence of domain interactions. These structures come from experiments documented in iPfam. The probability distribution contained in the factor graph is then efficiently marginalized with a message passing algorithm called the sum-product algorithm (SPA). This method is compared against two other approaches: maximum-likelihood estimation (MLE) and maximum specificity set cover (MSSC). SPA performs better for simulated scenarios and for inferring high-quality PPI data ofSaccharomyces cerevisiae. This framework can be used to predict potential protein and domain interactions at a genome wide scale and for any organism with identified protein-domain architectures.

UNLABELLED: Cytoprophet is a software tool that allows prediction and visualization of protein and domain interaction networks. It is implemented as a plug-in of Cytoscape, an open source software framework for analysis and visualization of molecular networks. Cytoprophet implements three algorithms that predict new potential physical interactions using the domain composition of proteins and experimental assays. The algorithms for protein and domain interaction inference include maximum likelihood estimation (MLE) using expectation maximization (EM); the set cover approach maximum specificity set cover (MSSC) and the sum-product algorithm (SPA). After accepting an input set of proteins with Uniprot ID/Accession numbers and a selected prediction algorithm, Cytoprophet draws a network of potential interactions with probability scores and GO distances as edge attributes. A network of domain interactions between the domains of the initial protein list can also be generated. Cytoprophet was designed to take advantage of the visual capabilities of Cytoscape and be simple to use. An example of inference in a signaling network of myxobacterium Myxococcus xanthus is presented and available at Cytoprophet's website. AVAILABILITY: http://cytoprophet.cse.nd.edu.

Abstract An additional reference is needed in the article Cytoprophet: a Cytoscape plug-in for protein and domain interaction networks inference. We include this reference as a matter of addendum. Contact: [email protected]

One goal of contemporary proteome research is the elucidation of cellular protein interactions. Based on currently available protein-protein interaction and domain data, we introduce a novel method, Maximum Specificity Set Cover (MSSC), for the prediction of protein-protein interactions. In our approach, we map the relationship between interactions of proteins and their corresponding domain architectures to a generalized weighted set cover problem. The application of a greedy algorithm provides sets of domain interactions which explain the presence of protein interactions to the largest degree of specificity. Utilizing domain and protein interaction data of S. cerevisiae, MSSC enables prediction of previously unknown protein interactions, links that are well supported by a high tendency of coexpression and functional homogeneity of the corresponding proteins. Focusing on concrete examples, we show that MSSC reliably predicts protein interactions in well-studied molecular systems, such as the 26S proteasome and RNA polymerase II of S. cerevisiae. We also show that the quality of the predictions is comparable to the Maximum Likelihood Estimation while MSSC is faster. This new algorithm and all data sets used are accessible through a Web portal at http://ppi.cse.nd.edu.