Stochastic Gradient Descent (SGD) and its variants are single-objective optimizers focused on minimizing training loss, often failing to address the generalization gap in deep learning. In this paper we introduce EvoBatch, a novel Hybrid Evolutionary Algorithm (HEA) that re-frames deep network optimization as an explicitly multi-objective problem. EvoBatch leverages a two-stage selection process, guided by both training loss and validation performance, to directly optimize for generalization. To overcome the historical computational barrier of EAs, EvoBatch uses mini-batch evolutionary local search, restricting each individual to local updates on unique, random data subsets. Theoretically, this M-ELS mechanism acts as a robust implicit regularizer by injecting heterogeneous noise, promoting the discovery of broader, flatter minima. This stability is the necessary condition that allows the explicit multi-objective selection to systematically and monotonically reduce the generalization gap. Empirically, EvoBatch demonstrates superior generalization profiles and consistently outperforms gradient-based baselines across image classification (ResNet, ViT) and language understanding (BERT) benchmarks. Our findings establish that compute-constrained, multi-objective evolutionary optimization offers both an effective and an efficient alternative to single-objective gradient methods when generalization is critical.

The dominant framing of Artificial General Intelligence (AGI) as a discrete breakthrough obscures the more urgent reality: AGI is arriving as a gradual, cumulative erosion of human verification power distributed across institutions and decision-making systems. This article reframes the AGI transition through the lens of absorption capacity; that is, the rate at which human systems can integrate, govern, and maintain meaningful oversight of increasingly autonomous AI. Drawing on empirical observations from deploying enterprise-scale generative AI in a large public university and personal experiences as a long-standing AI researcher and educator, in this article, I identify three critical asymmetries characterizing this transition: (1) governance lag, where policy cycles cannot match technological iteration speed; (2) institutional misalignment, where locally rational AI systems produce collectively irrational societal outcomes; and (3) capability inequality, where uneven access to AI amplifies structural advantage. I argue that the defining challenge is not achieving technical alignment with human values, but maintaining epistemic authority, which is the human capacity to verify, understand, and steer systems reasoning in latent spaces beyond direct audit. The article concludes that the true measure of preparedness for AGI is not computational power or algorithmic sophistication, but adaptive governance: institutional architectures capable of co-evolving with the technologies they must regulate. The frontier is not artificial superintelligence. It is collective human capacity to remain intelligible to ourselves while embedded in AI-mediated decision ecosystems.

This paper presents a novel Chemist-AI Alignment framework for generating novel structures of quaternary ammonium compounds (QACs), a crucial class of antimicrobial agents.The framework uniquely integrates AI-driven small molecule generation with iterative feedback from chemist experts, leveraging both rapid assessments and comprehensive wet-lab validations to optimize for biological potency and synthetic feasibility.Central to the framework is a hierarchical generative model that captures the QAC hierarchical topology.Extensive experiments highlight the efficacy of the framework in identifying promising QAC candidates, many

Generative AI is generating much enthusiasm on potentially advancing biological design in computational biology. In this paper we take a somewhat contrarian view, arguing that a broader and deeper understanding of existing biological sequences is essential before undertaking the design of novel ones. We draw attention, for instance, to current protein function prediction methods which currently face significant limitations due to incomplete data and inherent challenges in defining and measuring function. We propose a “blue sky” vision centered on both comprehensive and precise annotation of existing protein and DNA sequences, aiming to develop a more complete and precise understanding of biological function. By contrasting recent studies that leverage generative AI for biological design with the pressing need for enhanced data annotation, we underscore the importance of prioritizing robust predictive models over premature generative efforts. We advocate for a strategic shift toward thorough sequence annotation and predictive understanding, laying a solid foundation for future advances in biological design.

Efficient state space models (SSMs), including linear recurrent neural networks and linear attention variants, have emerged as potential alternative language models to Transformers.While efficient, SSMs struggle with tasks requiring in-context retrieval, such as text copying and associative recall, limiting their usefulness in practical settings.Prior work on how to meet this challenge has focused on the internal model architecture and not investigated the role of the training procedure.This paper proposes a new training procedure that improve the performance of SSMs on retrieval-intensive tasks.This novel pre-training procedure combines a bidirectional processing of the input with dynamic mixtures of pre-training objectives to improve the utilization of the SSM's fixed-size state.Our experimental evaluations show that this procedure significantly improves performance on retrieval-intensive tasks that challenge current SSMs, such as phone book lookup, long paragraph question-answering, and infilling tasks.Our findings offer insights into a new direction to advance the training of SSMs to close the performance gap with Transformers.

Local SGD, a cornerstone algorithm in federated learning, is widely used in training deep neural networks and shown to have strong empirical performance. A theoretical understanding of such performance on nonconvex loss landscapes is currently lacking. Analysis of the global convergence of SGD is challenging, as the noise depends on the model parameters. Indeed, many works narrow their focus to GD and rely on injecting noise to enable convergence to the local or global optimum. When expanding the focus to local SGD, existing analyses in the nonconvex case can only guarantee finding stationary points or assume the neural network is overparameterized so as to guarantee convergence to the global minimum through neural tangent kernel analysis. In this work, we provide the first global convergence analysis of the vanilla local SGD for two-layer neural networks \emph{without overparameterization} and \textit{without injecting noise}, when the input data is Gaussian. The main technical ingredients of our proof are \textit{a self-correction mechanism} and \textit{a new exact recursive characterization of the direction of global model parameters}. The self-correction mechanism guarantees the algorithm reaches a good region even if the initialization is in a bad region. A good (bad) region means updating the model by gradient descent will move closer to (away from) the optimal solution. The main difficulty in establishing a self-correction mechanism is to cope with the gradient dependency between two layers. To address this challenge, we divide the landscape of the objective into several regions to carefully control the interference of two layers during the correction process. As a result, we show that local SGD can correct the two layers and enter the good region in polynomial time. After that, we establish a new exact recursive characterization of the direction of global parameters, which is the key to showing convergence to the global minimum with linear speedup in the number of machines and reduced communication rounds. Experiments on synthetic data confirm theoretical results.

MOTIVATION: The two strands of the DNA double helix locally and spontaneously separate and recombine in living cells due to the inherent thermal DNA motion. This dynamics results in transient openings in the double helix and is referred to as "DNA breathing" or "DNA bubbles." The propensity to form local transient openings is important in a wide range of biological processes, such as transcription, replication, and transcription factors binding. However, the modeling and computer simulation of these phenomena, have remained a challenge due to the complex interplay of numerous factors, such as, temperature, salt content, DNA sequence, hydrogen bonding, base stacking, and others. RESULTS: We present pyDNA-EPBD, a parallel software implementation of the Extended Peyrard-Bishop-Dauxois (EPBD) nonlinear DNA model that allows us to describe some features of DNA dynamics in detail. The pyDNA-EPBD generates genomic scale profiles of average base-pair openings, base flipping probability, DNA bubble probability, and calculations of the characteristically dynamic length indicating the number of base pairs statistically significantly affected by a single point mutation using the Markov Chain Monte Carlo algorithm. AVAILABILITY AND IMPLEMENTATION: pyDNA-EPBD is supported across most operating systems and is freely available at https://github.com/lanl/pyDNA_EPBD. Extensive documentation can be found at https://lanl.github.io/pyDNA_EPBD/.

We have long known that characterizing protein structures structure is key to understanding protein function. Computational approaches have largely addressed a narrow formulation of the problem, seeking to compute one native structure from an amino-acid sequence. Now AlphaFold2 is shown to be able to reveal a high-quality native structure for many proteins. However, researchers over the years have argued for broadening our view to account for the multiplicity of native structures. We now know that many protein molecules switch between different structures to regulate interactions with molecular partners in the cell. Elucidating such structures de novo is exceptionally difficult, as it requires exploration of possibly a very large structure space in search of competing, near-optimal structures. Here we report on a novel stochastic optimization method capable of revealing very different structures for a given protein from knowledge of its amino-acid sequence. The method leverages evolutionary search techniques and adapts its exploration of the search space to balance between exploration and exploitation in the presence of a computational budget. In addition to demonstrating the utility of this method for identifying multiple native structures, we additionally provide a benchmark dataset for researchers to continue work on this problem.

Designing molecules with desired biological properties remains an outstanding challenge both in the wet and dry laboratories. Meeting this challenge promises great translational impacts across drug discovery, material sciences, biotechnology, and more. Recent momentum in deep learning promises to advance our computational capabilities on molecule generation. In particular, deep graph generative models which treat molecule design as a graph generation problem are allowing us to directly learn from existing databases of small molecules and generate novel, valid molecules. Currently, these models have many shortcomings, including poor controllability of desired molecular properties, especially in practical application where the training data is usually small, noisy, and incomplete. This paper focuses on equipping graph variational autoencoders with the ability to control for desired properties and its practical application in a practical application which is the generation of Quaternary Ammonium Compounds (QAC). Several controllable graph generation mechanisms are investigated for their effectiveness. A general framework is then proposed to extend these mechanisms by our newly proposed objective function to handle the challenges in practical applications where the property value annotations are usually censored and not fully available in all training samples. The experimental evaluation considers an experimentally-characterized dataset of antimicrobial small molecules with wet-lab characterized activity against antibiotic-resistant bacteria. Extensive experiments demonstrate the superiority of the proposed models and control of desired properties.

Extensive research on deep neural networks shows that complex deep learning models have considerably improved our ability to predict the native structure of a protein amino acid sequence. With the release of AlphaFold2, an entirely data-driven approach to machine learning, we can now predict the native tertiary structure of a given protein sequence with great precision. On the other hand, research into deep learning frameworks that can take into account protein structural plasticity is in its early stages. Obtaining a multi-structure view of a protein molecule remains an outstanding challenge in computational structural biology. In this paper, we make two key contributions. We first propose a novel end-to-end generative model framework, a new formulation under Equivariant Graph Neural Networks (EGNN) based encoding and Graph Variational Autoencoder (GVAE), advancing our ability to generate realistic tertiary structures. Most existing models rely on 2D convolution, with protein structures represented by contact maps or distance matrices. In contrast, our presented model learns over both 3D coordinates of protein structure and sequence directly. The second contribution of this paper is control of tertiary structure realism. We show that through the loss function, we can control properties of generated tertiary structures. We suggest different terms in the loss function and analyze how those terms allow us to recover realistic patterns, such as backbone, short-range, and long-range contacts that we find in tertiary structures. Additionally, we conduct a careful analysis along several metrics that measure the physical realism of generated tertiary structures and show that EGNN encoding-based GVAE are effective models for generating physically-realistic structures.

Activity characterization, optimization, and generation of small molecules are increasingly active areas of research at the intersection of molecular chemistry and machine learning. Large datasets of small molecules have allowed training deep models that have been shown capable of exploring the underlying chemical space and generating valid, novel, and unique molecules. While this is a noteworthy achievement, what impedes operationalizing these models in the wet laboratory is the ability to link the chemical and biological space of small molecules. A central challenge to this is the lack of activity data on these entities. In this paper we relate a computational pipeline that permits linking the chemical and biological space of an important class of small molecules, quaternary ammonium compounds (QACs). Our experimental collaborators have characterized the activity of many QACs against Staphylococcus aureus. We train various generative models and evaluate their ability to generate valid, novel, and unique QACs. We then leverage classification models trained over activity data to evaluate the generated QACs. The resulting pipeline identifies valid, novel, unique, membrane-active QACs. This work opens the way to further avenues of research in machine learning models capable of jointly sampling the chemical and biological space of small molecules.

Developing deep generative models has been an emerging field due to the ability to model and generate complex data for various purposes, such as image synthesis and molecular design. However, the advance of deep generative models is limited by the challenges to generate objects that possess multiple desired properties because: 1) the existence of complex correlation among real-world properties is common but hard to identify; 2) controlling individual property enforces an implicit partially control of its correlated properties, which is difficult to model; 3) controlling multiple properties under variour manners simultaneously is hard and underexplored. We address these challenges by proposing a novel deep generative framework that recovers semantics and correlation of properties through disentangled latent vectors. The correlation is handled via an explainable mask pooling layer, and properties are precisely retained by the generated objects via the mutual dependence between latent vectors and properties. Our generative model preserves properties of interest while handles correlation and conflicts of properties under a multi-objective optimization framework. The experiments demonstrate our model's superior performance in generating objects with desired properties.

Designing molecules with specific properties is a long-lasting research problem and is central to advancing crucial domains such as drug discovery and material science. Recent advances in deep graph generative models treat molecule design as graph generation problems which provide new opportunities toward the breakthrough of this long-lasting problem. Existing models, however, have many shortcomings, including poor interpretability and controllability toward desired molecular properties. This paper focuses on new methodologies for molecule generation with interpretable and controllable deep generative models, by proposing new monotonically-regularized graph variational autoencoders. The proposed models learn to represent the molecules with latent variables and then learn the correspondence between them and molecule properties parameterized by polynomial functions. To further improve the intepretability and controllability of molecule generation towards desired properties, we derive new objectives which further enforce monotonicity of the relation between some latent variables and target molecule properties such as toxicity and clogP. Extensive experimental evaluation demonstrates the superiority of the proposed framework on accuracy, novelty, disentanglement, and control towards desired molecular properties. The code is anonymized at https://anonymous.4open.science/r/MDVAE-FD2C.

MOTIVATION: Expanding our knowledge of small molecules beyond what is known in nature or designed in wet laboratories promises to significantly advance cheminformatics, drug discovery, biotechnology and material science. In silico molecular design remains challenging, primarily due to the complexity of the chemical space and the non-trivial relationship between chemical structures and biological properties. Deep generative models that learn directly from data are intriguing, but they have yet to demonstrate interpretability in the learned representation, so we can learn more about the relationship between the chemical and biological space. In this article, we advance research on disentangled representation learning for small molecule generation. We build on recent work by us and others on deep graph generative frameworks, which capture atomic interactions via a graph-based representation of a small molecule. The methodological novelty is how we leverage the concept of disentanglement in the graph variational autoencoder framework both to generate biologically relevant small molecules and to enhance model interpretability. RESULTS: Extensive qualitative and quantitative experimental evaluation in comparison with state-of-the-art models demonstrate the superiority of our disentanglement framework. We believe this work is an important step to address key challenges in small molecule generation with deep generative frameworks. AVAILABILITY AND IMPLEMENTATION: Training and generated data are made available at https://ieee-dataport.org/documents/dataset-disentangled-representation-learning-interpretable-molecule-generation. All code is made available at https://anonymous.4open.science/r/D-MolVAE-2799/. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

A central challenge in protein modeling research and protein structure prediction in particular is known as decoy selection. The problem refers to selecting biologically-active/native tertiary structures among a multitude of physically-realistic structures generated by template-free protein structure prediction methods. Research on decoy selection is active. Clustering-based methods are popular, but they fail to identify good/near-native decoys on datasets where near-native decoys are severely under-sampled by a protein structure prediction method. Reasonable progress is reported by methods that additionally take into account the internal energy of a structure and employ it to identify basins in the energy landscape organizing the multitude of decoys. These methods, however, incur significant time costs for extracting basins from the landscape. In this paper, we propose a novel decoy selection method based on non-negative matrix factorization. We demonstrate that our method outperforms energy landscape-based methods. In particular, the proposed method addresses both the time cost issue and the challenge of identifying good decoys in a sparse dataset, successfully recognizing near-native decoys for both easy and hard protein targets.

Sophisticated deep neural networks have significantly advanced our ability to predict a native structure of a protein amino-acid sequence. However, going beyond a single-structure view remains challenging. While rapid advances are being made, fundamental questions on the ability of generative deep modeling to learn to generate physically-realistic tertiary structures remain. This paper makes two key contributions. It first extends deep convolutional variable autoencoder networks to be able to learn from experimentally-available tertiary structures of proteins of variable lengths. The presented models learn over distance matrix representations of tertiary structures. A systematic and detailed analysis demonstrates that the design of the training data is of primary importance to the ability of the proposed models to learn key characteristics of tertiary structures. The second contribution this paper makes is a careful analysis along several metrics that measure the physical realism of generated tertiary structures. The presented results are promising and show that once seeded with sufficient, physically-realistic structures, variational autoencoders are efficient models for generating physically-realistic tertiary structures.

Representation learning via deep generative models is opening a new avenue for small molecule generation in silico. Linking chemical and biological space remains a key challenge. In this paper, we debut a graph-based variational autoencoder framework to address this challenge under the umbrella of disentangled representation learning. The framework permits several inductive biases that connect the learned latent factors to molecular properties. Evaluation on diverse benchmark datasets shows that the resulting models are powerful and open up an exciting line of research on controllable molecule generation in support of cheminformatics, drug discovery, and other application settings.

This study elucidates the conformation dynamics of the free and antigen-bound antibody. Previous work has verified that antigen binding allosterically promotes Fc receptor recognition. Analysis of extensive molecular dynamics simulations finds that the energy landscape may play a decisive role in coordinating conformation changes but does not provide connections between the various conformational states. Here we provide such a connection. To obtain a detailed understanding of the impact of antigen binding on antibody conformation dynamics, this study utilizes Markov State Models to summarize the conformation dynamics probed in silico. We additionally equip these models with the ability to directly exploit the energy landscape view of dynamics via a computational method that detects energy basins and so allows utilizing detected basins as macrostates for the Markov State Model. Our study reveals many interesting findings and suggests that the antigen-bound form with high energy may provide many dynamic processes to further enhance co-factor binding of the antibody in the next step.

Mental health behaviors are now recognized as primary factors contributing to suicide. This paper puts forth a novel mental health language model to address mental health and makes several contributions. First, it proposes a taxonomy and puts forth a comprehensive dataset of social media text. Second, it proposes a two-stage framework, first discriminating text relevant to mental health from non-relevant text and then carrying out multi-class classification for detection of mental health behaviors. Third, it proposes a novel mental health language model, PsychBERT, which is pretrained on a large corpus of biomedical literature on mental health and social media data. Fourth, the framework additionally incorporates components that enhance its explainability. Our evaluation shows that the proposed framework is outperforms state-of-the-art methods and is interpretable. Pre-trained PsychBERT is made publicly available for the community at https://huggingface.co/mnaylor/psychbert-cased.

The so-called dark proteome, referring to regions of the protein universe that remain inaccessible by either wet-or dry-laboratory methods, continues to spur computational research in protein structure determination. An outstanding challenge relates to the ability to discriminate relevant tertiary structure(s) among many structures, also referred to as decoys, that are computed for a protein of interest. The problem is known as decoy selection. While prime for investigation as an inference problem, the decoy datasets generated in silico are sparse and highly imbalanced towards the negative class (irrelevant structures). These characteristics continue to challenge both supervised and unsupervised learning approaches to this problem. In this paper, we propose a novel decoy selection method based on symmetric non-negative matrix factorization in a graph clustering setting. The method is evaluated on two datasets, a benchmark dataset of ensembles of decoys for a varied list of protein molecules, and a dataset of decoy ensembles for targets drawn from the recent CASP competitions. The evaluation demonstrates that the proposed method outperforms several state-of-the-art decoy selection methods. This performance, as well as the method's computational expediency, suggest that the proposed method advances the state of the art in decoy selection and, in particular, our the ability to tackle inherent challenges related to imbalanced datasets.

Many regions of the protein universe remain inaccessible by wet-laboratory or homology modeling methods. Elucidating these regions necessitates structure determination in silico. Protein structure determination in the absence of a structural template remains a challenging task with two core problems, known as decoy generation and decoy selection. In this paper, we address the problem of decoy generation, which inherently involves exploring the unknown, vast, and high-dimensional structure space of a given amino-acid sequence in the presence of a finite computational budget for relevant structures. Leveraging a stochastic optimization framework, we first demonstrate how selection pressure can be employed to control the trade-off between exploration and exploitation. Moreover, we then propose a novel algorithm that tunes its behavior towards exploration or exploitation as needed via an adaptive selection mechanism. We present a thorough evaluation on 30 protein targets in a comparative setting, where we compare the proposed adaptive algorithm to state-of-the-art algorithms that include the top ten groups in the two recent CASP competitions. The results show that the proposed algorithm is not only competitive against several of these groups, but it additionally outperforms several of them on many targets, suggesting that adaptive stochastic optimization is a promising framework for decoy generation.

Disentangled representation learning has recently attracted a significant amount of attention, particularly in the field of image representation learning. However, learning the disentangled representations behind a graph remains largely unexplored, especially for the attributed graph with both node and edge features. Disentanglement learning for graph generation has substantial new challenges including 1) the lack of graph deconvolution operations to jointly decode node and edge attributes; and 2) the difficulty in enforcing the disentanglement among latent factors that respectively influence: i) only nodes, ii) only edges, and iii) joint patterns between them. To address these challenges, we propose a new disentanglement enhancement framework for deep generative models for attributed graphs. In particular, a novel variational objective is proposed to disentangle the above three types of latent factors, with novel architecture for node and edge deconvolutions. Qualitative and quantitative experiments on both synthetic and real-world datasets demonstrate the effectiveness of the proposed model and its extensions.

Uncovering the organization of a landscape that encapsulates all states of a dynamic system is a central task in many domains, as it promises to reveal, in an unsupervised manner, a system's inner working. One domain where this task is crucial is in bioinformatics, where the energy landscape that organizes three-dimensional structures of a molecule by their energetics is a powerful construct. The landscape can be leveraged, among other things, to reveal macrostates where a molecule is biologically-active. This is a daunting task, as landscapes of complex actuated systems, such as molecules, are inherently high-dimensional. Nonetheless, our laboratories have made some progress via topological and statistical analysis of spatial data over the recent years. We have proposed what is essentially a dichotomy, methods that are more pertinent for visualization-driven discovery, and methods that are more pertinent for discovery of the biologically-active macrostates but not amenable to visualization. In this paper, we present a novel, hybrid method that combines strengths of these methods, allowing both visualization of the landscape and discovery of macrostates. We demonstrate what the method is capable of uncovering in comparison with existing methods over structure spaces sampled with conformational sampling algorithms. Though the direct evaluation in this paper is on protein energy landscapes, the proposed method is of broad interest in cross-cutting problems that necessitate characterization of fitness and optimization landscapes.

Identifying biologically-active protein structure(s) from an ensemble of computed three-dimensional structures is a major challenge. Clustering-based methods are time-consuming and often under perform on structure datasets that are highly imbalanced. Energy landscape-based methods improve performance over imbalanced datasets but incur significant time costs. In this paper we propose a novel method based on non-negative matrix factorization. The method outperforms energy landscape-based clustering methods, addressing both time costs and challenges with imbalanced structure datasets.

Discriminating biologically-active/native tertiary protein structures from non-native ones is an outstanding challenge in computational structural biology. Computationally, the task involves teasing out near-native structures out of several thousands generated in silico. In this paper we build on the concept of anomaly detection in machine learning and propose several methods for discriminating near-native structures. Evaluations on benchmark datasets demonstrate that the proposed methods advance the state of the art and warrant further research on adapting concepts and techniques from machine learning to improve recognition of near-native structures in template-free protein structure prediction.

The emerging view in molecular biology is that molecules are intrinsically dynamic systems rearranging themselves into different structures to interact with molecules in the cell. Such rearrangements take place on energy landscapes that are vast and multimodal, with minima housing alternative structures. The multiplicity of biologically-active structures is prompting researchers to expand their treatment of classic computational biology problems, such as the template-free protein structure prediction problem (PSP), beyond the quest for the global optimum. In this paper, we revisit subpopulation-oriented EAs as vehicles to switch the objective from classic optimization to landscape mapping. Specifically, we present two EAs, one of which makes use of subpopulation competition to allocate more computational resources to fitter subpopulations, and another of which additionally utilizes a niche preservation technique to maintain stable and diverse subpopulations. Initial assessment on benchmark optimization problems confirms that stabler subpopulations are achieved by the niche-preserving EA. Evaluation on unknown energy landscapes in the context of PSP demonstrates superior mapping performance by both algorithms over a popular Monte Carlo-based method, with the niche-preserving EA achieving superior exploration of lower-energy regions. These results suggest that subpopulation EAs hold much promise for solving important mapping problems in computational structural biology.

BACKGROUND: Nearly all cellular processes involve proteins structurally rearranging to accommodate molecular partners. The energy landscape underscores the inherent nature of proteins as dynamic molecules interconverting between structures with varying energies. In principle, reconstructing a protein's energy landscape holds the key to characterizing the structural dynamics and its regulation of protein function. In practice, the disparate spatio-temporal scales spanned by the slow dynamics challenge both wet and dry laboratories. However, the growing number of deposited structures for proteins central to human biology presents an opportunity to infer the relevant dynamics via exploitation of the information encoded in such structures about equilibrium dynamics. RESULTS: Recent computational efforts using extrinsic modes of motion as variables have successfully reconstructed detailed energy landscapes of several medium-size proteins. Here we investigate the extent to which one can reconstruct the energy landscape of a protein in the absence of sufficient, wet-laboratory structural data. We do so by integrating intrinsic modes of motion extracted off a single structure in a stochastic optimization framework that supports the plug-and-play of different variable selection strategies. We demonstrate that, while knowledge of more wet-laboratory structures yields better-reconstructed landscapes, precious information can be obtained even when only one structural model is available. CONCLUSIONS: The presented work shows that it is possible to reconstruct the energy landscape of a protein with reasonable detail and accuracy even when the structural information about the protein is limited to one structure. By attenuating the dependence on structural data of methods designed to compute protein energy landscapes, the work opens up interesting venues of research on structure-based inference of dynamics. Of particular interest are directions of research that will extend such inference to proteins with no experimentally-characterized structures.

BACKGROUND: Computational approaches for the determination of biologically-active/native three-dimensional structures of proteins with novel sequences have to handle several challenges. The (conformation) space of possible three-dimensional spatial arrangements of the chain of amino acids that constitute a protein molecule is vast and high-dimensional. Exploration of the conformation spaces is performed in a sampling-based manner and is biased by the internal energy that sums atomic interactions. Even state-of-the-art energy functions that quantify such interactions are inherently inaccurate and associate with protein conformation spaces overly rugged energy surfaces riddled with artifact local minima. The response to these challenges in template-free protein structure prediction is to generate large numbers of low-energy conformations (also referred to as decoys) as a way of increasing the likelihood of having a diverse decoy dataset that covers a sufficient number of local minima possibly housing near-native conformations. RESULTS: In this paper we pursue a complementary approach and propose to directly control the diversity of generated decoys. Inspired by hard optimization problems in high-dimensional and non-linear variable spaces, we propose that conformation sampling for decoy generation is more naturally framed as a multi-objective optimization problem. We demonstrate that mechanisms inherent to evolutionary search techniques facilitate such framing and allow balancing multiple objectives in protein conformation sampling. We showcase here an operationalization of this idea via a novel evolutionary algorithm that has high exploration capability and is also able to access lower-energy regions of the energy landscape of a given protein with similar or better proximity to the known native structure than several state-of-the-art decoy generation algorithms. CONCLUSIONS: The presented results constitute a promising research direction in improving decoy generation for template-free protein structure prediction with regards to balancing of multiple conflicting objectives under an optimization framework. Future work will consider additional optimization objectives and variants of improvement and selection operators to apportion a fixed computational budget. Of particular interest are directions of research that attenuate dependence on protein energy models.

The six papers in this special section were presented at the ACM Conference on Bioinformatics, Computational Biology, and Health Informatics (ACM BCB) in 2017.

The papers in this special section was presented at the 8th ACM-BCB Conference that was held in August 2017 in Boston, MA.

Motivation: Bacterial resistance to antibiotics is a growing concern. Antimicrobial peptides (AMPs), natural components of innate immunity, are popular targets for developing new drugs. Machine learning methods are now commonly adopted by wet-laboratory researchers to screen for promising candidates. Results: In this work, we utilize deep learning to recognize antimicrobial activity. We propose a neural network model with convolutional and recurrent layers that leverage primary sequence composition. Results show that the proposed model outperforms state-of-the-art classification models on a comprehensive dataset. By utilizing the embedding weights, we also present a reduced-alphabet representation and show that reasonable AMP recognition can be maintained using nine amino acid types. Availability and implementation: Models and datasets are made freely available through the Antimicrobial Peptide Scanner vr.2 web server at www.ampscanner.com. Supplementary information: Supplementary data are available at Bioinformatics online.

Computational structural biology is an important, growing research area that includes diverse problems, such as protein structure prediction, computational molecular assembly, and computer-assisted drug design problems, that include protein-ligand binding, protein-protein, protein-RNA, and protein-DNA docking, as well as computer assisted wet-laboratory structure resolving problems, like registration, reconstruction, and refinement. The focus of this special section is on the application of non-linear optimization to problems in structural biology, thus turning the spotlight on a growing area of interdisciplinary research that brings together expertise in meta-heuristic optimization and computational structural biology. The five articles included in this section provide a glimpse of the diversity of work in this area, highlighting the adaptation and use of a variety of state-of-the-art meta-heuristics for a range of problems linked to the wider area of structural biology.

Proteins are macromolecules in perpetual motion, switching between structural states to modulate their function. A detailed characterization of the precise yet complex relationship between protein structure, dynamics, and function requires elucidating transitions between functionally-relevant states. Doing so challenges both wet and dry laboratories, as protein dynamics involves disparate temporal scales. In this paper, we present a novel, sampling-based algorithm to compute transition paths. The algorithm exploits two main ideas. First, it leverages known structures to initialize its search and define a reduced conformation space for rapid sampling. This is key to address the insufficient sampling issue suffered by sampling-based algorithms. Second, the algorithm embeds samples in a nearest-neighbor graph where transition paths can be efficiently computed via queries. The algorithm adapts the probabilistic roadmap framework that is popular in robot motion planning. In addition to efficiently computing lowest-cost paths between any given structures, the algorithm allows investigating hypotheses regarding the order of experimentally-known structures in a transition event. This novel contribution is likely to open up new venues of research. Detailed analysis is presented on multiple-basin proteins of relevance to human disease. Multiscaling and the AMBER ff14SB force field are used to obtain energetically-credible paths at atomistic detail.

Stochastic search is often the only viable option to address complex optimization problems. Recently, evolutionary algorithms have been shown to handle challenging continuous optimization problems related to protein structure modeling. Building on recent work in our laboratories, we propose an evolutionary algorithm for efficiently mapping the multi-basin energy landscapes of dynamic proteins that switch between thermodynamically stable or semi-stable structural states to regulate their biological activity in the cell. The proposed algorithm balances computational resources between exploration and exploitation of the nonlinear, multimodal landscapes that characterize multi-state proteins via a novel combination of global and local search to generate a dynamically-updated, information-rich map of a protein's energy landscape. This new mapping-oriented EA is applied to several dynamic proteins and their disease-implicated variants to illustrate its ability to map complex energy landscapes in a computationally feasible manner. We further show that, given the availability of such maps, comparison between the maps of wildtype and variants of a protein allows for the formulation of a structural and thermodynamic basis for the impact of sequence mutations on dysfunction that may prove useful in guiding further wet-laboratory investigations of dysfunction and molecular interventions.

Many pathogenic mutations percolate to protein dysfunction by altering dynamics. Reconstructing protein energy landscapes promises to relate dynamics to function but is generally infeasible due to the disparate spatio-temporal scales involved. Recent algorithmic innovation allows reconstructing energy landscapes of medium-size proteins in the presence of sufficient prior wet-laboratory structure data. The ability to do so on healthy and pathogenic variants of a protein is renewing the need for landscape analysis and comparison. Here we describe a novel landscape analysis method that detects altered landscape features in response to mutations and allows formulating hypotheses on the impact of mutations on (dys)function. This work opens up interesting avenues into automated analysis and summarization of landscapes.

Proteins of importance to human biology can populate significantly different three-dimensional (3d) structures at equilibrium. By doing so, a protein is able to interface with different molecules in the cell and so modulate its function. A structure-by-structure characterization of a protein's transition between two structures is central to elucidate the role of structural dynamics in regulating molecular interactions, understand the impact of sequence mutations on function, and design molecular therapeutics. Much wet- and dry-laboratory research is devoted to characterizing structural transitions. Computational approaches rely on constructing a full or partial, structured representation of the energy landscape that organizes structures by potential energy. The representation readily yields one or more paths that consist of series of structures connecting start and goal structures of interest. In this paper, we propose instead to cast the problem of computing transition paths as a multiobjective optimization one. We identify two desired characteristics of computed paths, energetic cost and structural resolution, and propose a novel evolutionary algorithm (EA) to compute low-cost and highresolution paths. The EA evolves paths representing a specific structural excursion without a priori constructing the energy landscape. Preliminary applications suggest the EA is effective while operating under a reasonable computational budget.

Growing bacterial resistance to antibiotics is spurring research on utilizing naturally-occurring antimicrobial peptides (AMPs) as templates for novel drug design. While experimentalists mainly focus on systematic point mutations to measure the effect on antibacterial activity, the computational community seeks to understand what determines such activity in a machine learning setting. The latter seeks to identify the biological signals or features that govern activity. In this paper, we advance research in this direction through a novel method that constructs and selects complex sequence-based features which capture information about distal patterns within a peptide. Comparative analysis with state-of-the-art methods in AMP recognition reveals our method is not only among the top performers, but it also provides transparent summarizations of antibacterial activity at the sequence level. Moreover, this paper demonstrates for the first time the capability not only to recognize that a peptide is an AMP or not but also to predict its target selectivity based on models of activity against only Gram-positive, only Gram-negative, or both types of bacteria. The work described in this paper is a step forward in computational research seeking to facilitate AMP design or modification in the wet laboratory.

Recent work in computational structural biology focuses on modeling intrinsically dynamic proteins important to human biology and health. The energy landscapes of these proteins are rich in minima that correspond to alternative structures with which a dynamic protein binds to molecular partners in the cell. On such landscapes, evolutionary algorithms that switch their objective from classic optimization to mapping are more informative of protein structure function relationships. While techniques for mapping energy landscapes have been developed in computational chemistry and physics, protein landscapes are more difficult for mapping due to their high dimensionality and multimodality. In this paper, we describe a memetic evolutionary algorithm that is capable of efficiently mapping complex landscapes. In conjunction with a hall of fame mechanism, the algorithm makes use of a novel, lineage- and neighborhood-aware local search procedure or better exploration and mapping of complex landscapes. We evaluate the algorithm on several benchmark problems and demonstrate the superiority of the novel local search mechanism. In addition, we illustrate its effectiveness in mapping the complex multimodal landscape of an intrinsically dynamic protein important to human health.

More than fifty years of research in molecular biology have demonstrated that the ability of small and large molecules to interact with one another and propagate the cellular processes in the living cell lies in the ability of these molecules to assume and switch between specific structures under physiological conditions. Elucidating biomolecular structure and dynamics at equilibrium is therefore fundamental to furthering our understanding of biological function, molecular mechanisms in the cell, our own biology, disease, and disease treatments. By now, there is a wealth of methods designed to elucidate biomolecular structure and dynamics contributed from diverse scientific communities. In this survey, we focus on recent methods contributed from the Robotics community that promise to address outstanding challenges regarding the disparate length and time scales that characterize dynamic molecular processes in the cell. In particular, we survey robotics-inspired methods designed to obtain efficient representations of structure spaces of molecules in isolation or in assemblies for the purpose of characterizing equilibrium structure and dynamics. While an exhaustive review is an impossible endeavor, this survey balances the description of important algorithmic contributions with a critical discussion of outstanding computational challenges. The objective is to spur further research to address outstanding challenges in modeling equilibrium biomolecular structure and dynamics.

Investigation of macromolecular structure and dynamics is fundamental to understanding how macromolecules carry out their functions in the cell. Significant advances have been made toward this end in silico, with a growing number of computational methods proposed yearly to study and simulate various aspects of macromolecular structure and dynamics. This review aims to provide an overview of recent advances, focusing primarily on methods proposed for exploring the structure space of macromolecules in isolation and in assemblies for the purpose of characterizing equilibrium structure and dynamics. In addition to surveying recent applications that showcase current capabilities of computational methods, this review highlights state-of-the-art algorithmic techniques proposed to overcome challenges posed in silico by the disparate spatial and time scales accessed by dynamic macromolecules. This review is not meant to be exhaustive, as such an endeavor is impossible, but rather aims to balance breadth and depth of strategies for modeling macromolecular structure and dynamics for a broad audience of novices and experts.

Proteins are macromolecules in perpetual motion, switching between structural states to modulate their function. A detailed characterization of the precise yet complex relationship between protein structure, dynamics, and function requires elucidating transitions between functionally-relevant states. Doing so challenges both wet and dry laboratories, as protein dynamics involves disparate temporal scales. In this paper we present a novel, sampling-based algorithm to compute transition paths. The algorithm exploits two main ideas. First, it leverages known structures to initialize its search and define a reduced conformation space for rapid sampling. This is key to address the insufficient sampling issue suffered by sampling-based algorithms. Second, the algorithm embeds samples in a nearest-neighbor graph where transition paths can be efficiently computed via queries. The algorithm adapts the probabilistic roadmap framework that is popular in robot motion planning. In addition to efficiently computing lowest-cost paths between any given structures, the algorithm allows investigating hypotheses regarding the order of experimentally-known structures in a transition event. This novel contribution is likely to open up new venues of research. Detailed analysis is presented on multiple-basin proteins of relevance to human disease. Multiscaling and the AMBER ff12SB force field are used to obtain energetically-credible paths at atomistic detail.

Protein function is the result of a complex yet precise relationship between protein structure and dynamics. The ability of a protein to assume different structural states is key to biomolecular recognition and function modulation. Protein modeling research is driven by the need to complement experimental techniques in obtaining a comprehensive and detailed characterization of protein equilibrium dynamics. This is a non-trivial task, as it requires mapping the structure space (and underlying energy landscape) available to a protein under physiological conditions. Existing algorithms invariably adopt a stochastic optimization approach to explore the non-linear and multimodal protein energy landscapes. At the present, such algorithms suffer from limited sampling, particularly in high-dimensional and non-linear variable spaces rich in local minima. In this paper, we equip a recently published evolutionary algorithm with novel evolutionary search strategies to enhance the sampling capability for mapping multi-basin protein energy landscapes. We investigate initialization strategies to delay premature convergence and techniques to maintain and update on-the-fly a sample-based representation that serves as a map of the energy landscape. Applications on three proteins central to human disease show that the novel strategies are effective at locating basins in complex energy landscapes with a practical computational budget.

The focus on important diseases of our time has prompted many experimental labs to resolve and deposit functional structures of disease-causing or disease-participating proteins. At this point, many functional structures of wildtype and disease-involved variants of a protein exist in structural databases. The objective for computational approaches is to employ such information to discover features of the underlying energy landscape on which functional structures reside. Important questions about which subset of structures are most thermodynamically-stable remain unanswered. The challenge is how to transform an essentially discrete problem into one where continuous optimization is suitable and effective. In this paper, we present such a transformation, which allows adapting and applying evolution strategies to explore an underlying continuous variable space and locate the global optimum of a multimodal fitness landscape. The paper presents results on wildtype and mutant sequences of proteins implicated in human disorders, such as cancer and Amyotrophic lateral sclerosis. More generally, the paper offers a methodology for transforming a discrete problem into a continuous optimization one as a way to possibly address outstanding discrete problems in the evolutionary computation community.

An important goal in molecular biology is to understand functional changes upon single-point mutations in proteins. Doing so through a detailed characterization of structure spaces and underlying energy landscapes is desirable but continues to challenge methods based on Molecular Dynamics. In this paper we propose a novel algorithm, SIfTER, which is based instead on stochastic optimization to circumvent the computational challenge of exploring the breadth of a protein's structure space. SIfTER is a data-driven evolutionary algorithm, leveraging experimentally-available structures of wildtype and variant sequences of a protein to define a reduced search space from where to efficiently draw samples corresponding to novel structures not directly observed in the wet laboratory. The main advantage of SIfTER is its ability to rapidly generate conformational ensembles, thus allowing mapping and juxtaposing landscapes of variant sequences and relating observed differences to functional changes. We apply SIfTER to variant sequences of the H-Ras catalytic domain, due to the prominent role of the Ras protein in signaling pathways that control cell proliferation, its well-studied conformational switching, and abundance of documented mutations in several human tumors. Many Ras mutations are oncogenic, but detailed energy landscapes have not been reported until now. Analysis of SIfTER-computed energy landscapes for the wildtype and two oncogenic variants, G12V and Q61L, suggests that these mutations cause constitutive activation through two different mechanisms. G12V directly affects binding specificity while leaving the energy landscape largely unchanged, whereas Q61L has pronounced, starker effects on the landscape. An implementation of SIfTER is made available at http://www.cs.gmu.edu/~ashehu/?q=OurTools. We believe SIfTER is useful to the community to answer the question of how sequence mutations affect the function of a protein, when there is an abundance of experimental structures that can be exploited to reconstruct an energy landscape that would be computationally impractical to do via Molecular Dynamics.

All processes that maintain and replicate a living cell involve fluctuating biological macromolecules. As computational biologists, our aim is to discern the behavior of macromolecules in a way that experimental biology is not able to achieve. No single technique—experimental or computational—can capture all the relevant scales of cellular functional behavior. In principle, computations are the tools that can integrate different kinds of experimental and computational characterizations at different resolutions to obtain a more complete description of the processes of life. Computer simulations can act as a bridge between the microscopic length and time scales, and the macroscopic world of the laboratory. They can start from a macroscopic experiment-based guess of interactions between molecules, and obtain “exact” predictions of bulk and detailed properties subject to limitations. They are able to test a theory by constructing and simulating the model, and comparing the results with experimental measurements; and they are able to provide models that experiments can test. Computations can provide leads by processing large sets of data, predicting molecular behaviors, and supplying the mechanistic underpinning that experiments alone may not be able to achieve. Macromolecules play a vital role in countless biological processes, including DNA replication, transcription, genome reorganization in development and in disease, protein synthesis, protein folding, and active transport with molecular motors. Cell signaling, a multistep pathway on length scales from nanometers to micrometers, provides another inclusive example, incorporating all of the above over time and space. Signals are relayed from the extracellular space to the nucleus through dynamic shifts of molecular ensembles. Macromolecular fluctuations underlie signal amplification; they result in a large number of activated molecules across the cell, creating multiple reactions and producing a major cellular response. Changes in fluctuations through binding second messengers can regulate catalysis, and dynamic shifts in conformational ensembles can also take place through binding to membrane lipids. Key hub proteins that govern cell behaviors are often membrane-anchored. Helped by experimental data, computations can model the components of the systems and their transient interactions to provide a useful, integrated view of the flow of information, its regulation, and its deregulation. Ultimately, we want to make direct quantitative comparisons with experimental data. We would like to reduce the amount of fitting and guesswork; but at the same time we may also be interested in phenomena of a generic nature, or in discriminating between good and bad theories. Doing this well is challenging. To understand the dynamic interplay across multiple scales, to link it to the atomic-scale physicochemical basis of the conformational behavior of single molecules and their interactions, and, ultimately, to relate it to cellular function, we need efficient and reliable methods to sample the macromolecular fluctuations and identify the biological and disease-related states and their transitions. Inspiration may come from a combination of biology and other fields that model dynamic systems. Macromolecules move, and their movements are needed for a complete picture of life. Computational biology, with concepts imported from physics and chemistry, increasingly plays a major role, which has recently been recognized by the Nobel Committee [1]. The energy landscape underscores the inherent nature of biomolecules, which are dynamical objects that are always interconverting between structures with varying energies. It affirms that biomolecules must be described statistically, not statically. Macromolecules are not static objects; rather, they populate ensembles of conformations. The transitions between these states occur on length scales from tenths of an Angstrom to nanometers, and time scales that can vary from nanoseconds to seconds. These are linked to functionally relevant phenomena such as allosteric signaling and enzyme catalysis. Computational methods also include those for molecular modeling and refinement of three-dimensional structures, de novo design of proteins, prediction and modeling of protein-ligand interactions and development of docking protocols, and prediction of macromolecular interactions at varying spatial resolutions and timescales. They further encompass methods of ligand screening in drug development and protein-protein docking, methods for assessing sequence-structure-function relationships and prediction of macromolecular function, protocols for molecular visualization and annotation, and geometric and topological characterization of proteins and polynucleotides. This list is still far from complete. To celebrate its tenth anniversary [2], PLOS Computational Biology presents a special collection of manuscripts focusing on methods exploring macromolecular structure and dynamics. This collection does not aim to cover all methods; it does, however, aim to provide a taste of currently available approaches and strategies toward these aims. Altogether, the collection covers a broad ground: from sampling, detection of rare events, and exposing hidden alternative backbone conformations in X-ray crystallography, to multi-scale visualization of molecular architecture using real-time ambient occlusion; from discrimination between obligatory and non-obligatory protein-protein interactions based on the dynamics of the complex to binding free energies of inhibitors, to predicting the effect of mutations on protein-protein interactions by exploiting interface profiles; from a virtual mixture approach to the study of multistate equilibrium, to identification of misfolded intermediates; from multiscale estimation of binding kinetics using a combination of Brownian dynamics, molecular dynamics, and mile-stoning, to mapping the protein fold universe. This collection underscores the breadth of computational methods in structural biology, and only some of them made it into this special PLOS Computational Biology collection. Computational structural biology has made tremendous progress over the last two decades. Computational methods were developed for protein structure prediction, macromolecular function and protein design, as well as for drug discovery. It has also undertaken computational challenges related to experimental approaches in structural biology. Along with new experimental tools, higher resolution, and the rising efficiency of experimental approaches leading to huge amounts of accumulating data, computational biology is pushing the frontiers to meet its challenges. We expect that, in the future, the focus of our methods and tools may shift and more integrative tools will be developed, along with methodological adaptation to massively larger quantities of data. Experimentally, the biological and chemical sciences are now attempting to push boundaries in drug discovery. We may expect that a translational direction will also prevail in computational structural biology. This, however, does not mean only direct drug discovery; for these efforts to be successful, the underlying mechanistic basis of diseases needs to be understood as well. In addition, we expect even stronger emphasis on the human microbiome and its relationship to human health. PLOS Computational Biology aims to meet this challenge and place a larger focus on this important and certain-to-become-central area in the biological sciences. Clearly, many challenges remain for computational biologists in the coming years. PLOS Computational Biology, along with the computational biology community and the International Society for Computational Biology (ISCB), are poised to take on this challenge. We view this collection as the first in this direction, helping the community toward this aim.

Obtaining accurate representations of energy landscapes of biomolecules such as proteins and peptides is central to structure-function studies. Peptides are particularly interesting, as they exploit structural flexibility to modulate their biological function. Despite their small size, peptide modeling remains challenging due to the complexity of the energy landscape of such highly-flexible dynamic systems. Currently, only sampling-based methods can efficiently explore the conformational space of a peptide. In this paper, we suggest to combine two such methods to obtain a full characterization of energy landscapes of small yet flexible peptides. First, we propose a simplified version of the classical Basin Hopping algorithm to quickly reveal the meta-stable structural states of a peptide and the corresponding low-energy basins in the landscape. Then, we present several variants of a robotics-inspired algorithm, the Transition-based Rapidly-exploring Random Tree, to quickly determine transition state and transition path ensembles, as well as transition probabilities between meta-stable states. We demonstrate this combined approach on the terminally-blocked alanine.

Growing bacterial resistance to antibiotics is urging the development of new lines of treatment. The discovery of naturally-occurring antimicrobial peptides (AMPs) is motivating many experimental and computational researchers to pursue AMPs as possible templates. In the experimental community, the focus is generally on systematic point mutation studies to measure the effect on antibacterial activity. In the computational community, the goal is to understand what determines such activity in a machine learning setting. In the latter, it is essential to identify biological signals or features in AMPs that are predictive of antibacterial activity. Construction of effective features has proven challenging. In this paper, we advance research in this direction. We propose a novel method to construct and select complex sequence-based features able to capture information about distal patterns within a peptide. Thorough comparative analysis in this paper indicates that such features compete with the state-of-the-art in AMP recognition while providing transparent summarizations of antibacterial activity at the sequence level. We demonstrate that these features can be combined with additional physicochemical features of interest to a biological researcher to facilitate specific AMP design or modification in the wet laboratory. Code, data, results, and analysis accompanying this paper are publicly available online at: http://cs.gmu.edu/~ashehu/?q=OurTools.

BACKGROUND: Due to rapid sequencing of genomes, there are now millions of deposited protein sequences with no known function. Fast sequence-based comparisons allow detecting close homologs for a protein of interest to transfer functional information from the homologs to the given protein. Sequence-based comparison cannot detect remote homologs, in which evolution has adjusted the sequence while largely preserving structure. Structure-based comparisons can detect remote homologs but most methods for doing so are too expensive to apply at a large scale over structural databases of proteins. Recently, fragment-based structural representations have been proposed that allow fast detection of remote homologs with reasonable accuracy. These representations have also been used to obtain linearly-reducible maps of protein structure space. It has been shown, as additionally supported from analysis in this paper that such maps preserve functional co-localization of the protein structure space. METHODS: Inspired by a recent application of the Latent Dirichlet Allocation (LDA) model for conducting structural comparisons of proteins, we propose higher-order LDA-obtained topic-based representations of protein structures to provide an alternative route for remote homology detection and organization of the protein structure space in few dimensions. Various techniques based on natural language processing are proposed and employed to aid the analysis of topics in the protein structure domain. RESULTS: We show that a topic-based representation is just as effective as a fragment-based one at automated detection of remote homologs and organization of protein structure space. We conduct a detailed analysis of the information content in the topic-based representation, showing that topics have semantic meaning. The fragment-based and topic-based representations are also shown to allow prediction of superfamily membership. CONCLUSIONS: This work opens exciting venues in designing novel representations to extract information about protein structures, as well as organizing and mining protein structure space with mature text mining tools.

Ab-initio structure prediction refers to the problem of using only knowledge of the sequence of amino acids in a protein molecule to find spatial arrangements, or conformations, of the amino-acid chain capturing the protein in its biologically-active or native state. This problem is a central challenge in computational biology. It can be posed as an optimization problem, but current top ab-initio protocols employ Monte Carlo sampling rather than evolutionary algorithms (EAs) for conformational search. This paper presents a hybrid EA that incorporates successful strategies used in state-of-the-art ab-initio protocols. Comparison to a top Monte-Carlo-based sampling method shows that the domain-specific enhancements make the proposed hybrid EA competitive. A detailed analysis on the role of crossover operators and a novel implementation of homologous 1-point crossover shows that the use of crossover with mutation is more effective than mutation alone in navigating the protein energy surface.

Adequate sampling of the conformational space is a central challenge in ab initio protein structure prediction. In the absence of a template structure, a conformational search procedure guided by an energy function explores the conformational space, gathering an ensemble of low-energy decoy conformations. If the sampling is inadequate, the native structure may be missed altogether. Even if reproduced, a subsequent stage that selects a subset of decoys for further structural detail and energetic refinement may discard near-native decoys if they are high energy or insufficiently represented in the ensemble. Sampling should produce a decoy ensemble that facilitates the subsequent selection of near-native decoys. In this paper, we investigate a robotics-inspired framework that allows directly measuring the role of energy in guiding sampling. Testing demonstrates that a soft energy bias steers sampling toward a diverse decoy ensemble less prone to exploiting energetic artifacts and thus more likely to facilitate retainment of near-native conformations by selection techniques. We employ two different energy functions, the associative memory Hamiltonian with water and Rosetta. Results show that enhanced sampling provides a rigorous testing of energy functions and exposes different deficiencies in them, thus promising to guide development of more accurate representations and energy functions.

We present a novel probabilistic search algorithm to efficiently search the structure space of protein dimers. The algorithm is based on the basin hopping framework that repeatedly follows up structural perturbation with energy minimization to obtain a coarse-grained view of the dimeric energy surface in terms of its local minima. A Metropolis criterion biases the search towards lower-energy minima over time. Extensive analysis highlights efficient and effective implementations for the perturbation and minimization components. Testing on a broad list of dimers shows the algorithm recovers the native dimeric configuration with great accuracy and produces many minima near the native configuration. The algorithm can be employed to efficiently produce relevant decoys that can be further refined at greater detail to predict the native configuration.

The vast and rugged protein energy surface can be effectively represented in terms of local minima. The basin-hopping framework, where a structural perturbation is followed by an energy minimization, is particularly suited to obtaining this coarse-grained representation. Basin hopping is effective for small systems both in locating lower-energy minima and obtaining conformations near the native structure. The efficiency decreases for large systems. Our recent work improves efficiency on large systems through molecular fragment replacement. In this paper, we conduct a detailed investigation of two components in basin hopping, perturbation and minimization, and how they work in concert to affect the sampling of near-native local minima. We show that controlling the magnitude of perturbation jumps is related to the ability to effectively steer the exploration towards conformations near the protein native state. In minimization, we show that a simple greedy search is just as effective as Metropolis Monte Carlo-based minimization. Finally, we show that an evolutionary-inspired approach based on the Pareto front is particularly effective in reducing the ensemble of sampled local minima and obtains a simpler representation of the probed energy surface.

Associating functional information with biological sequences remains a challenge for machine learning methods. The performance of these methods often depends on deriving predictive features from the sequences sought to be classified. Feature generation is a difficult problem, as the connection between the sequence features and the sought property is not known a priori. It is often the task of domain experts or exhaustive feature enumeration techniques to generate a few features whose predictive power is then tested in the context of classification. This paper proposes an evolutionary algorithm to effectively explore a large feature space and generate predictive features from sequence data. The effectiveness of the algorithm is demonstrated on an important component of the gene-finding problem, DNA splice site prediction. This application is chosen due to the complexity of the features needed to obtain high classification accuracy and precision. Our results test the effectiveness of the obtained features in the context of classification by Support Vector Machines and show significant improvement in accuracy and precision over state-of-the-art approaches.

Protein Modeling conceptualizes the protein energy landscape as a funnel with the native structure at the low-energy minimum. Current protein structure prediction algorithms seek the global minimum by searching for low- energy conformations in the hope that some of these reside in local minima near the native structure. The search techniques employed, however, fail to explicitly model these local minima. This work proposes a memetic algorithm which combines methods from evolutionary computation with cutting-edge structure prediction protocols. The Protein Local Optima Walk (PLOW) algorithm proposed here explores the space of local minima by explicitly projecting each move in the conformation space to a nearby local minimum. This allows PLOW to jump over local energy barriers and more effectively sample near-native conformations. Analysis across a broad range of proteins shows that PLOW outperforms an MMC-based method and compares favorably against other published ab-inito structure prediction algorithms.

Prediction of promoter regions continues to be a challenging subproblem in mapping out eukaryotic DNA. While this task is key to understanding the regulation of differential transcription, the gene-specific architecture of promoter sequences does not readily lend itself to general strategies. To date, the best approaches are based on Support Vector Machines (SVMs) that employ standard "spectrum" features and achieve promoter region classification accuracies from a low of 84% to a high of 94% depending on the particular species involved. In this paper, we propose a general and powerful methodology that uses Genetic Programming (GP) techniques to generate more complex and more gene-specific features to be used with a standard SVM for promoter region identification. We evaluate our methodology on three data sets from different species and observe consistent classification accuracies in the 94 95% range. In addition, because the GP-generated features are gene-specific, they can be used by biologists to advance their understanding of the architecture of eukaryotic promoter regions.

Support vector machines (SVMs) are now one of the most popular machine learning techniques for solving difficult classification problems. Their effectiveness depends on two critical design decisions: 1) mapping a decision problem into an n-dimensional feature space, and 2) choosing a kernel function that maps the n-dimensional feature space into a higher dimensional and more effective classification space. The choice of kernel functions is generally limited to a small set of well-studied candidates. However, the choice of a feature set is much more open-ended without much design guidance. In fact, many SVMs are designed with standard generic feature space mappings embedded a priori. In this paper we describe a procedure for using an evolutionary algorithm to design more compact non-standard feature mappings that, for a fixed kernel function, significantly improves the classification accuracy of the constructed SVM.

This paper proposes a method to improve the recognition of regulatory genomic sequences. Annotating sequences that regulate gene transcription is an emerging challenge in genomics research. Identifying regulatory sequences promises to reveal underlying reasons for phenotypic differences among cells and for diseases associated with pathologies in protein expression. Computational approaches have been limited by the scarcity of experimentally-known features specific to regulatory sequences. High-throughput experimental technology is finally revealing a wealth of hypersensitive (HS) sequences that are reliable markers of regulatory sequences and currently the focus of classification methods. The contribution of this paper is a novel method that combines evolutionary computation and SVM classification to improve the recognition of HS sequences. Based on experimental evidence that HS regions employ sequence features to interact with enzymes, the method seeks motifs to discriminate between HS and non-HS sequences. An evolutionary algorithm (EA) searches the space of sequences of different lengths to obtain such motifs. Experiments reveal that these motifs improve recognition of HS sequences by more than 10% compared to state-of-the-art classification methods. Analysis of these motifs reveals interesting insight into features employed by regulatory sequences to interact with DNA-binding enzymes.