Finding the needle in the haystack: towards solving the protein-folding problem computationally

Prediction of protein tertiary structures from amino acid sequence and understanding the mechanisms of how proteins fold, collectively known as “the protein folding problem,” has been a grand challenge in molecular biology for over half a century. Theories have been developed that provide us with an unprecedented understanding of protein folding mechanisms. However, computational simulation of protein folding is still difficult, and prediction of protein tertiary structure from amino acid sequence is an unsolved problem. Progress toward a satisfying solution has been slow due to challenges in sampling the vast conformational space and deriving sufficiently accurate energy functions. Nevertheless, several techniques and algorithms have been adopted to overcome these challenges, and the last two decades have seen exciting advances in enhanced sampling algorithms, computational power and tertiary structure prediction methodologies. This review aims at summarizing these computational techniques, specifically conformational sampling algorithms and energy approximations that have been frequently used to study protein-folding mechanisms or to de novo predict protein tertiary structures. We hope that this review can serve as an overview on how the protein-folding problem can be studied computationally and, in cases where experimental approaches are prohibitive, help the researcher choose the most relevant computational approach for the problem at hand. We conclude with a summary of current challenges faced and an outlook on potential future directions.     

Interactive ant colony optimization (iACO) for early lifecycle software design

Finding good designs in the early stages of the software development lifecycle is a demanding multi-objective problem that is crucial to success. Previously, both interactive and non-interactive techniques based on evolutionary algorithms (EAs) have been successfully applied to assist the designer. However, recently ant colony optimization was shown to outperform EAs at optimising quantitative measures of software designs with a limited computational budget. In this paper, we propose a novel interactive ACO (iACO) approach, in which the search is steered jointly by an adaptive model that combines subjective and objective measures. Results show that iACO is speedy, responsive and effective in enabling interactive, dynamic multi-objective search. Indeed, study participants rate the iACO search experience as compelling. Moreover, inspection of the learned model facilitates understanding of factors affecting users’ judgements, such as the interplay between a design’s elegance and the interdependencies between its components.     

Computational issues in mapping variation affecting susceptibility to complex disorders: the chicken and the egg

Linkage mapping strategies for complex disorders have evolved under a variety of constraints. Some of these constraints reflect the nature of complex disorders and are manifest in limitations on the kinds of data that can be collected, while others were (at least historically) strictly computational. This paper focuses on how computational issues have impacted the design of studies on complex disorders and, conversely, how our study designs have influenced the computational issues that have been addressed. We now have unprecedented computational resources, but also face unprecedented computational and methodological challenges as we move from the linkage mapping of genes influencing susceptibility to complex disorders toward the identification of the actual variation affecting susceptibility to these disorders. The near-term computational and methodological issues we must address will be profoundly influenced by the study designs of the recent past. But future study designs, as well as our investments in computational and methodological research, ought to be developed considering the computational and informatics resources we now have at hand.     

EMILiO: a fast algorithm for genome-scale strain design

Systems-level design of cell metabolism is becoming increasingly important for renewable production of fuels, chemicals, and drugs. Computational models are improving in the accuracy and scope of predictions, but are also growing in complexity. Consequently, efficient and scalable algorithms are increasingly important for strain design. Previous algorithms helped to consolidate the utility of computational modeling in this field. To meet intensifying demands for high-performance strains, both the number and variety of genetic manipulations involved in strain construction are increasing. Existing algorithms have experienced combinatorial increases in computational complexity when applied toward the design of such complex strains. Here, we present EMILiO, a new algorithm that increases the scope of strain design to include reactions with individually optimized fluxes. Unlike existing approaches that would experience an explosion in complexity to solve this problem, we efficiently generated numerous alternate strain designs producing succinate, l-glutamate and l-serine. This was enabled by successive linear programming, a technique new to the area of computational strain design.     

Fast optimal genome tiling with applications to microarray design and homology search.

In this paper, we consider several variations of the following basic tiling problem: given a sequence of real numbers with two size-bound parameters, we want to find a set of tiles of maximum total weight such that each tiles satisfies the size bounds. A solution to this problem is important to a number of computational biology applications such as selecting genomic DNA fragments for PCR-based amplicon microarrays and performing homology searches with long sequence queries. Our goal is to design efficient algorithms with linear or near-linear time and space in the normal range of parameter values for these problems. For this purpose, we first discuss the solution to a basic online interval maximum problem via a sliding-window approach and show how to use this solution in a nontrivial manner for many of the tiling problems introduced. We also discuss NP-hardness results and approximation algorithms for generalizing our basic tiling problem to higher dimensions. Finally, computational results from applying our tiling algorithms to genomic sequences of five model eukaryotes are reported.     

A highly efficient multi-core algorithm for clustering extremely large datasets

Background  

In recent years, the demand for computational power in computational biology has increased due to rapidly growing data sets from microarray and other high-throughput technologies. This demand is likely to increase. Standard algorithms for analyzing data, such as cluster algorithms, need to be parallelized for fast processing. Unfortunately, most approaches for parallelizing algorithms largely rely on network communication protocols connecting and requiring multiple computers. One answer to this problem is to utilize the intrinsic capabilities in current multi-core hardware to distribute the tasks among the different cores of one computer.     

Performance of Humans vs. Exploration Algorithms on the Tower of London Test

The Tower of London Test (TOL) used to assess executive functions was inspired in Artificial Intelligence tasks used to test problem-solving algorithms. In this study, we compare the performance of humans and of exploration algorithms. Instead of absolute execution times, we focus on how the execution time varies with the tasks and/or the number of moves. This approach used in Algorithmic Complexity provides a fair comparison between humans and computers, although humans are several orders of magnitude slower. On easy tasks (1 to 5 moves), healthy elderly persons performed like exploration algorithms using bounded memory resources, i.e., the execution time grew exponentially with the number of moves. This result was replicated with a group of healthy young participants. However, for difficult tasks (5 to 8 moves) the execution time of young participants did not increase significantly, whereas for exploration algorithms, the execution time keeps on increasing exponentially. A pre-and post-test control task showed a 25% improvement of visuo-motor skills but this was insufficient to explain this result. The findings suggest that naive participants used systematic exploration to solve the problem but under the effect of practice, they developed markedly more efficient strategies using the information acquired during the test.     

Multiplexing schemes for generic SNP genotyping assays.

Association studies in populations relate genomic variation among individuals with medical condition. Key to these studies is the development of efficient and affordable genotyping techniques. Generic genotyping assays are independent of the target SNPs and offer great flexibility in the genotyping process. Efficient use of such assays calls for identifying sets of SNPs that can be interrogated in parallel under constraints imposed by the genotyping technology. In this paper, we study problems arising in the design of genotyping experiments using generic assays. Our problem formulation deals with two main factors that affect the genotyping cost: the number of assays used and the number of PCR reactions required for sample preparation. We prove that the resulting computational problems are hard, but provide approximate and heuristic solutions to these problems. Our algorithmic approach is based on recasting the multiplexing problems as partitioning and packing problems on a bipartite graph. We tested our algorithmic approaches on an extensive collection of synthetic data and on data that was simulated using real SNP sequences. Our results show that the algorithms achieve near-optimal designs in many cases and demonstrate the applicability of generic assays to SNP genotyping.     

Automatically Generated Algorithms for the Vertex Coloring Problem

The vertex coloring problem is a classical problem in combinatorial optimization that consists of assigning a color to each vertex of a graph such that no adjacent vertices share the same color, minimizing the number of colors used. Despite the various practical applications that exist for this problem, its NP-hardness still represents a computational challenge. Some of the best computational results obtained for this problem are consequences of hybridizing the various known heuristics. Automatically revising the space constituted by combining these techniques to find the most adequate combination has received less attention. In this paper, we propose exploring the heuristics space for the vertex coloring problem using evolutionary algorithms. We automatically generate three new algorithms by combining elementary heuristics. To evaluate the new algorithms, a computational experiment was performed that allowed comparing them numerically with existing heuristics. The obtained algorithms present an average 29.97% relative error, while four other heuristics selected from the literature present a 59.73% error, considering 29 of the more difficult instances in the DIMACS benchmark.     

Learning strategies in table tennis using inverse reinforcement learning

Learning a complex task such as table tennis is a challenging problem for both robots and humans. Even after acquiring the necessary motor skills, a strategy is needed to choose where and how to return the ball to the opponent’s court in order to win the game. The data-driven identification of basic strategies in interactive tasks, such as table tennis, is a largely unexplored problem. In this paper, we suggest a computational model for representing and inferring strategies, based on a Markov decision problem, where the reward function models the goal of the task as well as the strategic information. We show how this reward function can be discovered from demonstrations of table tennis matches using model-free inverse reinforcement learning. The resulting framework allows to identify basic elements on which the selection of striking movements is based. We tested our approach on data collected from players with different playing styles and under different playing conditions. The estimated reward function was able to capture expert-specific strategic information that sufficed to distinguish the expert among players with different skill levels as well as different playing styles.     

Evolutionary psychology and the generation of culture,part II: Case study: A computational theory of social exchange

Models of the various adaptive specializations that have evolved in the human psyche could become the building blocks of a scientific theory of culture. The first step in creating such models is the derivation of a so-called “computational theory” of the adaptive problem each psychological specialization has evolved to solve. In Part II, as a case study, a sketch of a computational theory of social exchange (cooperation for mutual benefit) is developed. The dynamics of natural selection in Pleistocene ecological conditions define adaptive information processing problems that humans must be able to solve in order to participate in social exchange: individual recognition, memory for one's history of interaction, value communication, value modeling, and a shared grammar of social contracts that specifies representational structure and inferential procedures. The nature of these adaptive information processing problems places constraints on the class of cognitive programs capable of solving them; this allows one to make empirical predictions about how the cognitive processes involved in attention, communication, memory, learning, and reasoning are mobilized in situations of social exchange. Once the cognitive programs specialized for regulating social exchange are mapped, the variation and invariances in social exchange within and between cultures can be meaningfully discussed.     

Spatial Ultimatum Games, collaborations and the evolution of fairness

It is often the case that individuals in a social group can perform certain tasks (such as hunting, for example) more efficiently if they collaborate with other individuals than if they act alone. In such situations one is necessarily faced with the problem of how the resource obtained as the result of such a collaboration should be divided among the collaborating individuals. If one of the individuals in the collaboration is in a position (through its dominance rank, for example) to impose a particular division of the resource on the other members of the collaboration then we show that an evolutionary dilemma arises which prevents such collaborations being evolutionarily stable. This dilemma, which is closely related to the well-known Ultimatum Game, results from the fact that in such situations natural selection favours individuals who, if dominant, offer smaller and smaller shares of the resource to the others and, if subdominant, will accept lower and lower offers. We also show, however, that this dilemma is naturally resolved in a spatially structured population with selection favouring the evolution of a fair division of the resource and consequently ensuring the evolutionary stability of collaborations of this type.     

Modeling planarian regeneration: a primer for reverse-engineering the worm

A mechanistic understanding of robust self-assembly and repair capabilities of complex systems would have enormous implications for basic evolutionary developmental biology as well as for transformative applications in regenerative biomedicine and the engineering of highly fault-tolerant cybernetic systems. Molecular biologists are working to identify the pathways underlying the remarkable regenerative abilities of model species that perfectly regenerate limbs, brains, and other complex body parts. However, a profound disconnect remains between the deluge of high-resolution genetic and protein data on pathways required for regeneration, and the desired spatial, algorithmic models that show how self-monitoring and growth control arise from the synthesis of cellular activities. This barrier to progress in the understanding of morphogenetic controls may be breached by powerful techniques from the computational sciences-using non-traditional modeling approaches to reverse-engineer systems such as planaria: flatworms with a complex bodyplan and nervous system that are able to regenerate any body part after traumatic injury. Currently, the involvement of experts from outside of molecular genetics is hampered by the specialist literature of molecular developmental biology: impactful collaborations across such different fields require that review literature be available that presents the key functional capabilities of important biological model systems while abstracting away from the often irrelevant and confusing details of specific genes and proteins. To facilitate modeling efforts by computer scientists, physicists, engineers, and mathematicians, we present a different kind of review of planarian regeneration. Focusing on the main patterning properties of this system, we review what is known about the signal exchanges that occur during regenerative repair in planaria and the cellular mechanisms that are thought to underlie them. By establishing an engineering-like style for reviews of the molecular developmental biology of biomedically important model systems, significant fresh insights and quantitative computational models will be developed by new collaborations between biology and the information sciences.     

蚂蚁群落优化算法在蛋白质折叠二维亲-疏水格点模型中的应用

氨基酸的亲疏水格点模型是研究蛋白质折叠的一种重要的简化模型,其优化问题是一个非确定型的多项式问题。采用蚂蚁群落优化算法对这一问题进行了研究,对测试数据的计算结果表明,在一定规模下,此算法能够有效地获得亲-疏水格点模型的最优解,其效率优于传统的Monte Carlo仿真等方法。     

Fibers with Integrated Mechanochemical Switches: Minimalistic Design Principles Derived from Fibronectin

Inspired by molecular mechanisms that cells exploit to sense mechanical forces and convert them into biochemical signals, chemists dream of designing mechanochemical switches integrated into materials. Using the adhesion protein fibronectin, whose multiple repeats essentially display distinct molecular recognition motifs, we derived a computational model to explain how minimalistic designs of repeats translate into the mechanical characteristics of their fibrillar assemblies. The hierarchy of repeat-unfolding within fibrils is controlled not only by their relative mechanical stabilities, as found for single molecules, but also by the strength of cryptic interactions between adjacent molecules that become activated by stretching. The force-induced exposure of cryptic sites furthermore regulates the nonlinearity of stress-strain curves, the strain at which such fibers break, and the refolding kinetics and fraction of misfolded repeats. Gaining such computational insights at the mesoscale is important because translating protein-based concepts into novel polymer designs has proven difficult.     

Simulating the Real Origins of Communication

How communication systems emerge is a topic of relevance to several academic disciplines. Numerous existing models, both mathematical and computational, study this emergence. However, with few exceptions, these models all build some form of communication into their initial specification. Consequently, what these models study is how communication systems transition from one form to another, and not how communication itself emerges in the first place. Here we present a new computational model of the emergence of communication which, unlike previous models, does not pre-specify the existence of communication. We conduct two experiments using this model, in order to derive general statements about how communication systems emerge. The two main routes to communication that we identify correspond with findings from the empirical literature on the evolution of animal signals. We use this finding to explain when and why we should expect communication to emerge in nature. We also compare our model to experimental research on the origins of human communication systems, and hence show that humans are an important exception to the general trends we observe. We argue that this is because humans, and probably only humans, are able to ‘signal signalhood’, i.e. to express communicative intentions.     

Gene Regulatory Network Inferences Using a Maximum-Relevance and Maximum-Significance Strategy

Recovering gene regulatory networks from expression data is a challenging problem in systems biology that provides valuable information on the regulatory mechanisms of cells. A number of algorithms based on computational models are currently used to recover network topology. However, most of these algorithms have limitations. For example, many models tend to be complicated because of the “large p, small n” problem. In this paper, we propose a novel regulatory network inference method called the maximum-relevance and maximum-significance network (MRMSn) method, which converts the problem of recovering networks into a problem of how to select the regulator genes for each gene. To solve the latter problem, we present an algorithm that is based on information theory and selects the regulator genes for a specific gene by maximizing the relevance and significance. A first-order incremental search algorithm is used to search for regulator genes. Eventually, a strict constraint is adopted to adjust all of the regulatory relationships according to the obtained regulator genes and thus obtain the complete network structure. We performed our method on five different datasets and compared our method to five state-of-the-art methods for network inference based on information theory. The results confirm the effectiveness of our method.     

Rational design of complex phenotype via network models

We demonstrate a modeling and computational framework that allows for rapid screening of thousands of potential network designs for particular dynamic behavior. To illustrate this capability we consider the problem of hysteresis, a prerequisite for construction of robust bistable switches and hence a cornerstone for construction of more complex synthetic circuits. We evaluate and rank most three node networks according to their ability to robustly exhibit hysteresis where robustness is measured with respect to parameters over multiple dynamic phenotypes. Focusing on the highest ranked networks, we demonstrate how additional robustness and design constraints can be applied. We compare our results to more traditional methods based on specific parameterization of ordinary differential equation models and demonstrate a strong qualitative match at a small fraction of the computational cost.