This paper considers the NP-hard protein side-chain positioning (SCP) problem, an important final task of protein structure prediction. We formulate the SCP as an integer quadratic program and derive its doubly nonnegative (DNN) (convex) relaxation. Strict feasibility fails for this DNN relaxation. We apply facial reduction to regularize the problem. This gives rise to a natural splitting of the variables. We then use a variation of the Peaceman-Rachford splitting method to solve the DNN relaxation. The resulting relaxation and rounding procedures provide strong approximate solutions. Empirical evidence shows that almost all our instances of this NP-hard SCP problem, taken from the Protein Data Bank, are solved to provable optimality. Our large problems correspond to solving a DNN relaxation with 2,883,601 binary variables to provable optimality. History: Accepted by Paul Brooks, Area Editor for Applications in Biology, Medicine, & Healthcare. Funding: This research was supported by the Natural Sciences and Engineering Research Council of Canada [Grants 50503-10827 and RGPIN-2016-04660]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0094 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0094 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

“Elastic network interpolation (ENI)” generates a series of transitional conformations between two protein conformations by interpolating inter-atomic distances. A group of atoms that maintain their inter-atomic distances while moving concurrently in a protein is known as a rigid cluster; “rigid cluster ENI” is the interpolation of the rotations and translations of rigid clusters. Rank 3 positive semidefinite (PSD) matrix manifolds have faces that are defined by these rigid clusters. This facial structure strongly suggests that these matrix manifolds are a natural choice for modelling rigid cluster transitions. In this paper, we show that rigid cluster ENI can be formulated as a facially reduced rank 3 PSD matrix manifold optimization problem.

MOTIVATION: Inferring structural dependencies among a protein's side chains helps us understand their coupled motions. It is known that coupled fluctuations can reveal pathways of communication used for information propagation in a molecule. Side-chain conformations are commonly represented by multivariate angular variables, but existing partial correlation methods that can be applied to this inference task are not capable of handling multivariate angular data. We propose a novel method to infer direct couplings from this type of data, and show that this method is useful for identifying functional regions and their interactions in allosteric proteins. RESULTS: We developed a novel extension of canonical correlation analysis (CCA), which we call 'kernelized partial CCA' (or simply KPCCA), and used it to infer direct couplings between side chains, while disentangling these couplings from indirect ones. Using the conformational information and fluctuations of the inactive structure alone for allosteric proteins in the Ras and other Ras-like families, our method identified allosterically important residues not only as strongly coupled ones but also in densely connected regions of the interaction graph formed by the inferred couplings. Our results were in good agreement with other empirical findings. By studying distinct members of the Ras, Rho and Rab sub-families, we show further that KPCCA was capable of inferring common allosteric characteristics in the small G protein super-family. AVAILABILITY AND IMPLEMENTATION: https://github.com/lsgh/ismb15

Determination of a protein's structure can facilitate an understanding of how the structure changes when that protein combines with other proteins or smaller molecules. In this paper we study a semidefinite programming (SDP) relaxation of the (NP-hard) side chain positioning problem presented in Chazelle et al [Chazelle B, Kingsford C, Singh M (2004) A semidefinite programming approach to side chain positioning with new rounding strategies. INFORMS J. Comput. 16:380-392]. We show that the Slater constraint qualification (strict feasibility) fails for the SDP relaxation. We then show the advantages of using facial reduction to regularize the SDP. In fact, after applying facial reduction, we have a smaller problem that is more stable both in theory and in practice. We include cutting planes to improve the rounded SDP approximate solutions.

Protein side chains populate diverse conformational ensembles in crystals. Despite much evidence that there is widespread conformational polymorphism in protein side chains, most of the X-ray crystallography data are modeled by single conformations in the Protein Data Bank. The ability to extract or to predict these conformational polymorphisms is of crucial importance, as it facilitates deeper understanding of protein dynamics and functionality. In this paper, we describe a computational strategy capable of predicting side-chain polymorphisms. Our approach extends a particular class of algorithms for side-chain prediction by modeling the side-chain dihedral angles more appropriately as continuous rather than discrete variables. Employing a new inferential technique known as particle belief propagation, we predict residue-specific distributions that encode information about side-chain polymorphisms. Our predicted polymorphisms are in relatively close agreement with results from a state-of-the-art approach based on X-ray crystallography data, which characterizes the conformational polymorphisms of side chains using electron density information, and has successfully discovered previously unmodeled conformations.

Quantitative structure-activity relationships (QSARs) correlate biological activities of chemical compounds with their physicochemical descriptors. By modeling the observed relationship seen between molecular descriptors and their corresponding biological activities, we may predict the behavior of other molecules with similar descriptors. In QSAR studies, it has been shown that the quality of the prediction model strongly depends on the selected features within molecular descriptors. Thus, methods capable of automatic selection of relevant features are very desirable. In this paper, we present a new feature selection algorithm for a QSAR study based on kernel alignment which has been used as a measure of similarity between two kernel functions. In our algorithm, we deploy kernel alignment as an evaluation tool, using recursive feature elimination to compute a molecular descriptor containing the most important features needed for a classification application. Empirical results show that the algorithm works well for the computation of descriptors for various applications involving different QSAR data sets. The prediction accuracies are substantially increased and are comparable to those from earlier studies.

We introduce a crossover operator that is not dependent on the initial layout of the genome. While maintaining a low positional bias, the MISC (mutual information and shuffle crossover) algorithm is competitive with one-point crossover and works by automatically regrouping bits that are considered to be interdependent. The heuristic strategy is to derive an operator that promotes the expansion of building blocks as required by a genetic algorithm.

News is information about recent events of general interest, especially as currently reported by newspapers, periodicals, radio, or television. News is the quintessential multimedia data. While newspaper editors (human and/or algorithmic) may still define the core content of electronic news, new communication technologies will enable the integration of news from a wide variety of sources and provide access to supplemental material from enormous archives of electronic news data (text, photos, and video) in digital libraries as well as the continual streams of newly created data. The goal of electronic news delivery within this context is, however, distinguishable from both news groups and document retrieval. Electronic news promises to deliver to the reader an edited collage of recent events from wide domains in a manner that is both comprehensive and personalized. As part of a long-term research project into the design of future news delivery systems, we have developed an overall architecture and several prototypes. These prototypes are presented in the article, along with a discussion of issues related to the presentation metaphor and to the functionality of electronic news delivery services. A prototype was demonstrated at the 1995 G-7 Economic Summit in Halifax, Canada, integrating newspaper text and photographs with television news video clips across an ATM network. © 1998 John Wiley & Sons, Inc.

A query algebra is presented that expresses searches on structured text. In addition to traditional full-text boolean queries that search a pre-defined collection of documents, the algebra permits queries that harness document structure. The algebra manipulates arbitrary intervals of text, which are recognized in the text from implicit or explicit markup. The algebra has seven operators, which combined intervals to yield new ones: containing, not containing, contained in, not contained in, one of, both of, followed by. The ultimate result of a query is the set of intervals that satisfy it. An implementation framework is given based on four primitive access functions. Each access function finds the solution to a query nearest to a given position in the database. Recursive definitions for the seven operators are given in terms of these access functions. Search time is at worst proportional to the time required to evaluate the access functions for occurrences of the elementary terms in a query.

The first part of this paper briefly describes a mathematical framework (called the containment model) that provides the operations and data structures for a text dominated database with a hierarchical structure. The database is considered to be a hierarchical collection of continuous extents each extent being a word, word phrase, text element or non-text element. The filter operations making up a search command are expressed in terms of containment criteria that specify whether a contiguous extent will be selected or rejected during a search. This formalism, comprised of the mathematical framework and its associated language, defines a conceptual layer upon which we can construct a well-defined higher level layer, specifically the user interface that serves to provide a level of functionality that is closer to the needs of the user and the application domain.With the conceptual layer established, we go on to describe the design and implementation of a versatile interface which handles queries that search and navigate a heterogeneous collection of structured documents. Interface functionality is provided by a set of “worker” modules supported by an “environment” that is the same for all interfaces. The interface environment allows a worker to communicate with the underlying text retrieval engine using a well-defined command protocol that is based on a small set of filter operators. The overall design emphasizes: a) interface flexibility for a variety of search and browsing capabilities, b) the modular independence of the interface with respect to its underlying retrieval engine, and c) the advantages to be accrued by defining retrieval commands using operators that are part of a text algebra that provides a sound theoretical foundation for the database.

This paper presents a new data structure and an associated strategy to be utilized by indexing facilities for text retrieval systems. The paper starts by reviewing some of the goals that may be considered when designing such an index and continues with a small survey of various current strategies. It then presents an indexing strategy referred to as surrogate subsets discussing its appropriateness in the light of the specified goals. Various design issues and implementation details are discussed. Our strategy requires that a surrogate file be divided into a large number of subsets separated by free space which will allow the index to expand when new material is appended to the database. Experimental results report on the utilization of free space when the database is enlarged.

This paper describes the motivation for a set of intertask communication primitives, the hardware support of these primitives, the architecture used in the Sylvan project which studies these issues, and the experience gained from various experiments conducted in this area. We start by describing how these facilities have been implemented in a multiprocessor configuration that utilizes a shared backplane. This configuration represents a single node in the system. The latter part of the paper discusses a distributed multiple node system and the extension of the primitives that are used in this expanded environment.

The main intent of this paper will be the description of a multiprocessor system that uses microprogrammed hardware to support operating system primitives that contribute to its high performance vector processing capability. The system consists of nodes that communicate over a system interconnect. Each node is a tripartite subsystem that consists of a host processor complex running application code, a vector co-processor and a kernel support processor that handles both operating system functions and control of the vector co-processor. The microcoded kernel processor is used to support a message based operating system that allows concurrent processes to communicate while residing in the same node or in different nodes. Since the kernel processor controls the functioning of the vector co-processor as well as the management of processes (for example, context switching), the node can utilize the resources of the co-processor very effectively.

In an effort to minimize traffic in the distribution network of a static dataflow machine the design of the system includes alternate data paths so that data movement may take place over “shorter” paths when it is permissible to do so. The main emphasis of this approach is to allow rapid transfer of data in sequential code segments residing in single memory blocks. This decreases crowding in the more expensive distribution network utilized by data that fans out to two or more blocks as required when more concurrent activity is to be initiated during the execution of the program. The objective of data movement minimization has also influenced the design of the instruction set. In this case, composite, that is, “multi-actor” instructions have been proposed as an effective strategy. This has been done without compromizing the utility of the instructions or overly increasing the time and space requirements of their execution. In the paper, these principles are illustrated by defining controlled instructions that are especially useful in the management of loops.

This paper discusses the hardware design of a term detection unit which may be used in the scanning of text emanating from a serial source such as disk or bubble memory. The main objective of this design is the implementation of a high performance unit which can detect any one of many terms (e.g., 1024 terms) while accepting source text at disk transfer rates. The unit incorporates "off-the-shelf" currently available chips. The design involves a hardware-based hashing scheme that allows incoming text to be compared to selected terms in a RAM which contains all of the strings to be detected. The organization of data in the RAM of the term detector is dependent on a graph-theoretic algorithm which computes maximal matchings on bipartite graphs. The capability of the unit depends on various parameters in the design, and this dependence is demonstrated by means of various tables that report on the results of various simulation studies.