Quadratic programming with equality constraint (QPEC) problems have extensive applicability in many industries as a versatile nonlinear programming modeling tool. However, noise interference is inevitable when solving QPEC problems in complex environments, so research on noise interference suppression or elimination methods is of great interest. This article proposes a modified noise-immune fuzzy neural network (MNIFNN) model and use it to solve QPEC problems. Compared with the traditional gradient recurrent neural network (TGRNN) and traditional zeroing recurrent neural network (TZRNN) models, the MNIFNN model has the advantage of inherent noise tolerance ability and stronger robustness, which is achieved by combining proportional, integral, and differential elements. Furthermore, the design parameters of the MNIFNN model adopt two disparate fuzzy parameters generated by two fuzzy logic systems (FLSs) related to the residual and residual integral term, which can improve the adaptability of the MNIFNN model. Numerical simulations demonstrate the effectiveness of the MNIFNN model in noise tolerance.

MOTIVATION: Flux balance analysis (FBA) based bilevel optimization has been a great success in redesigning metabolic networks for biochemical overproduction. To date, many computational approaches have been developed to solve the resulting bilevel optimization problems. However, most of them are of limited use due to biased optimality principle, poor scalability with the size of metabolic networks, potential numeric issues or low quantity of design solutions in a single run. RESULTS: Here, we have employed a network interdiction model free of growth optimality assumptions, a special case of bilevel optimization, for computational strain design and have developed a hybrid Benders algorithm (HBA) that deals with complicating binary variables in the model, thereby achieving high efficiency without numeric issues in search of best design strategies. More importantly, HBA can list solutions that meet users' production requirements during the search, making it possible to obtain numerous design strategies at a small runtime overhead (typically ∼1 h, e.g. studied in this article). AVAILABILITY AND IMPLEMENTATION: Source code implemented in the MATALAB Cobratoolbox is freely available at https://github.com/chang88ye/NIHBA. CONTACT: [email protected] or [email protected]. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Population-based evolutionary algorithms have great potential to handle multiobjective optimisation problems . However, the performance of these algorithms depends largely on problem characteristics. There is a need to improve these algorithms for wide applicability. References, often specified by the decision maker’s preference in different forms, are very effective to boost the performance of algorithms. This paper proposes a novel framework for effective use of references to strengthen algorithms. This framework considers references as search targets which can be adjusted based on the information collected during the search. The proposed framework is combined with new strategies, such as reference adaptation and adaptive local mating, to solve different types of problems. The proposed algorithm is compared with state-of-the-arts on a wide range of problems with diverse characteristics. The comparison and extensive sensitivity analysis demonstrate that the proposed algorithm is competitive and robust across different types of problems studied in this paper.

Dynamic multiobjective optimization (DMO) has gained increasing attention in recent years. Test problems are of great importance in order to facilitate the development of advanced algorithms that can handle dynamic environments well. However, many of the existing dynamic multiobjective test problems have not been rigorously constructed and analyzed, which may induce some unexpected bias when they are used for algorithmic analysis. In this paper, some of these biases are identified after a review of widely used test problems. These include poor scalability of objectives and, more important, problematic overemphasis of static properties rather than dynamics making it difficult to draw accurate conclusion about the strengths and weaknesses of the algorithms studied. A diverse set of dynamics and features is then highlighted that a good test suite should have. We further develop a scalable continuous test suite, which includes a number of dynamics or features that have been rarely considered in literature but frequently occur in real life. It is demonstrated with empirical studies that the proposed test suite is more challenging to the DMO algorithms found in the literature. The test suite can also test algorithms in ways that existing test suites cannot.

MOTIVATION: 3D physical modelling is a powerful computational technique that allows for the simulation of complex systems such as consortia of mixed bacterial species. The complexities in physical modelling reside in the knowledge intensive model building process and the computational expense in calculating their numerical solutions. These models can offer insights into microbiology, both in understanding natural systems and as design tools for developing novel synthetic bacterial systems. Developing a robust synthetic system typically requires multiple iterations around the specify→design→build→test cycle to meet specifications. This process is laborious and expensive for both the computational and laboratory aspects, hence any improvement in any of the workflow steps would be welcomed. We have previously introduced Simbiotics, a powerful and flexible platform for designing and analyzing 3D simulations of mixed species bacterial populations. Simbiotics requires programming experience to use which creates barriers to entry for use of the tool. RESULTS: In the spirit of enabling biologists who may not have programming skills to install and utilize Simbiotics, we present in this application note Easybiotics, a user-friendly graphical user interface for Simbiotics. Users may design, simulate and analyze models from within the graphical user interface, with features such as live graph plotting and parameter sweeps. Easybiotics provides full access to all of Simbiotics simulation features, such as cell growth, motility and gene regulation. AVAILABILITY AND IMPLEMENTATION: Easybiotics and Simbiotics are free to use under the GPL3.0 licence, and can be found at: http://ico2s.org/software/simbiotics.html. We also provide readily downloadable virtual machine sandboxes to facilitate rapid installation.

Dynamic multiobjective optimisation deals with multiobjective problems whose objective functions, search spaces, or constraints are time-varying during the optimisation process. Due to wide presence in real-world applications, dynamic multiobjective problems (DMOPs) have been increasingly studied in recent years. Whilst most studies concentrated on DMOPs with only two objectives, there is little work on more objectives. This paper presents an empirical investigation of evolutionary algorithms for three-objective dynamic problems. Experimental studies show that all the evolutionary algorithms tested in this paper encounter performance degradedness to some extent. Amongst these algorithms, the multipopulation based change handling mechanism is generally more robust for a larger number of objectives, but has difficulty in deal with time-varying deceptive characteristics.

Multiobjective optimisation in dynamic environments is challenging due to the presence of dynamics in the problems in question. Whilst much progress has been made in benchmarks and algorithm design for dynamic multiobjective optimisation, there is a lack of work on the detectability of environmental changes and how this affects the performance of evolutionary algorithms. This is not intentionally left blank but due to the unavailability of suitable test cases to study. To bridge the gap, this work presents several scenarios where environmental changes are less likely to be detected. Our experimental studies suggest that the less detectable environments pose a big challenge to evolutionary algorithms.

Motivation: Formal verification is a computational approach that checks system correctness (in relation to a desired functionality). It has been widely used in engineering applications to verify that systems work correctly. Model checking, an algorithmic approach to verification, looks at whether a system model satisfies its requirements specification. This approach has been applied to a large number of models in systems and synthetic biology as well as in systems medicine. Model checking is, however, computationally very expensive, and is not scalable to large models and systems. Consequently, statistical model checking (SMC), which relaxes some of the constraints of model checking, has been introduced to address this drawback. Several SMC tools have been developed; however, the performance of each tool significantly varies according to the system model in question and the type of requirements being verified. This makes it hard to know, a priori, which one to use for a given model and requirement, as choosing the most efficient tool for any biological application requires a significant degree of computational expertise, not usually available in biology labs. The objective of this article is to introduce a method and provide a tool leading to the automatic selection of the most appropriate model checker for the system of interest. Results: We provide a system that can automatically predict the fastest model checking tool for a given biological model. Our results show that one can make predictions of high confidence, with over 90% accuracy. This implies significant performance gain in verification time and substantially reduces the 'usability barrier' enabling biologists to have access to this powerful computational technology. Availability and implementation: SMC Predictor tool is available at http://www.smcpredictor.com. Supplementary information: Supplementary data are available at Bioinformatics online.

We recently reported the design for a DNA nano-device that can record and store molecular signals. Here we present an evolutionary algorithm tailored to optimising nucleic acid sequences that predictively fold into our desired target structures. In our approach, a DNA device is first specified abstractly: the topology of the individual strands and their desired foldings into multi-strand complexes are described at the domain-level. Initially, this design is decomposed into a set of pairwise strand interactions. Then, we optimize candidate domains, such that the resulting sequences fold with high accuracy into desired target structures both (a) individually and (b) jointly, but also (c) to show high affinity for binding desired partners and simultaneously low affinity to bind with any undesired partner. As optimization heuristic we use a genetic algorithm that employs a linear combination of the above scores. Our algorithm was able to generate DNA sequences that satisfy all given criteria. Even though we cannot establish the theoretically achievable optima (as this would require exhaustive search), our solutions score 90% of an upper bound that ignores conflicting objectives. We envision that this approach can be generalized towards a broad class of toehold-mediated strand displacement systems.

In the past decades many definitions of complexity have been proposed. Most of these definitions are based either on Shannon's information theory or on Kolmogorov complexity; these two are often compared, but very few studies integrate the two ideas. In this article we introduce a new measure of complexity that builds on both of these theories. As a demonstration of the concept, the technique is applied to elementary cellular automata and simulations of the self-organization of porphyrin molecules.

SUMMARY: JEPETTO (Java Enrichment of Pathways Extended To TOpology) is a Cytoscape 3.x plugin performing integrative human gene set analysis. It identifies functional associations between genes and known cellular pathways, and processes using protein interaction networks and topological analysis. The plugin integrates information from three separate web servers we published previously, specializing in enrichment analysis, pathways expansion and topological matching. This integration substantially simplifies the analysis of user gene sets and the interpretation of the results. We demonstrate the utility of the JEPETTO plugin on a set of misregulated genes associated with Alzheimer's disease. AVAILABILITY: Source code and binaries are freely available for download at http://apps.cytoscape.org/apps/jepetto, implemented in Java and multi-platform. Installable directly via Cytoscape plugin manager. Released under the GNU General Public Licence.

As unconventional computation matures and non-standard programming frameworks are demonstrated, the need for formal verification will become more prevalent. This is so because “programming” in unconventional substrates is difficult. In this paper we

Biological systems employ compartmentalization and other co-localization strategies in order to orchestrate a multitude of biochemical processes by simultaneously enabling “data hiding” and modularization. This article presents recent research that embraces compartmentalization and co-location as an organizational programmatic principle in synthetic biological and biomimetic systems. In these systems, artificial vesicles and synthetic minimal cells are envisioned as nanoscale reactors for programmable biochemical synthesis and as chassis for molecular information processing. We present P systems, brane calculi, and the recently developed chemtainer calculus as formal frameworks providing data hiding and modularization and thus enabling the representation of highly complicated hierarchically organized compartmentalized reaction systems. We demonstrate how compartmentalization can greatly reduce the complexity required to implement computational functionality, and how addressable compartments permit the scaling-up of programmable chemical synthesis.

In this paper, we propose a multi-restart memetic algorithm framework for box constrained global continuous optimisation. In this framework, an evolutionary algorithm (EA) and a local optimizer are employed as separated building blocks. The EA is used to explore the search space for very promising solutions (e.g., solutions in the attraction basin of the global optimum) through its exploration capability and previous EA search history, and local search is used to improve these promising solutions to local optima. An estimation of distribution algorithm (EDA) combined with a derivative free local optimizer, called NEWUOA (M. Powell, Developments of NEWUOA for minimization without derivatives. Journal of Numerical Analysis, 28:649-664, 2008), is developed based on this framework and empirically compared with several well-known EAs on a set of 40 commonly used test functions. The main components of the specific algorithm include: (1) an adaptive multivariate probability model, (2) a multiple sampling strategy, (3) decoupling of the hybridisation strategy, and (4) a restart mechanism. The adaptive multivariate probability model and multiple sampling strategy are designed to enhance the exploration capability. The restart mechanism attempts to make the search escape from local optima, resorting to previous search history. Comparison results show that the algorithm is comparable with the best known EAs, including the winner of the 2005 IEEE Congress on Evolutionary Computation (CEC2005), and significantly better than the others in terms of both the solution quality and computational cost.

In the context of Parallel Evolutionary Algorithms, it has been shown that different population structures induce different search performances. Nevertheless, no work has shown a clear cut evidence that there is a correlation between the solver’s population structure and the problem’s network structure. In this work, we verify this correlation performing a clear and systematic analysis of a large set of population structures (based on the well known β -graphs and NK -landscape problems. Furthermore, we go beyond our findings in these idealised experiments by analysing the performance of variable-topology EAs on a dynamic real-world problem, the Multi-Skills Call Centre.

This paper proposes three post-processing operators (rule cleaning, rule pruning and rule swapping) which combined together in different ways can help reduce the complexity of decision lists evolved by means of genetics-based machine learning. While the first two operators work on the independent rules to reduce the number of expressed attributes, the last one changes the order of the rules (based on the similarities between them) to identify and delete the unnecessary ones. These operators were tested using the BioHEL system over 35 different problems. Our results show that it is possible to reduce the number of specified attributes per rule and the number rules up to 30% in some problems, without producing significant changes in the test accuracy. Moreover, the approaches presented in this paper can be easily extended to other learning paradigms and representations.

MOTIVATION: The prediction of a protein's contact map has become in recent years, a crucial stepping stone for the prediction of the complete 3D structure of a protein. In this article, we describe a methodology for this problem that was shown to be successful in CASP8 and CASP9. The methodology is based on (i) the fusion of the prediction of a variety of structural aspects of protein residues, (ii) an ensemble strategy used to facilitate the training process and (iii) a rule-based machine learning system from which we can extract human-readable explanations of the predictor and derive useful information about the contact map representation. RESULTS: The main part of the evaluation is the comparison against the sequence-based contact prediction methods from CASP9, where our method presented the best rank in five out of the six evaluated metrics. We also assess the impact of the size of the ensemble used in our predictor to show the trade-off between performance and training time of our method. Finally, we also study the rule sets generated by our machine learning system. From this analysis, we are able to estimate the contribution of the attributes in our representation and how these interact to derive contact predictions. AVAILABILITY: http://icos.cs.nott.ac.uk/servers/psp.html. CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: Assessing functional associations between an experimentally derived gene or protein set of interest and a database of known gene/protein sets is a common task in the analysis of large-scale functional genomics data. For this purpose, a frequently used approach is to apply an over-representation-based enrichment analysis. However, this approach has four drawbacks: (i) it can only score functional associations of overlapping gene/proteins sets; (ii) it disregards genes with missing annotations; (iii) it does not take into account the network structure of physical interactions between the gene/protein sets of interest and (iv) tissue-specific gene/protein set associations cannot be recognized. RESULTS: To address these limitations, we introduce an integrative analysis approach and web-application called EnrichNet. It combines a novel graph-based statistic with an interactive sub-network visualization to accomplish two complementary goals: improving the prioritization of putative functional gene/protein set associations by exploiting information from molecular interaction networks and tissue-specific gene expression data and enabling a direct biological interpretation of the results. By using the approach to analyse sets of genes with known involvement in human diseases, new pathway associations are identified, reflecting a dense sub-network of interactions between their corresponding proteins. AVAILABILITY: EnrichNet is freely available at http://www.enrichnet.org. CONTACT: [email protected], [email protected] or [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics Online.

In this talk I will overview ten years of research in the application of evolutionary computation ideas in the natural sciences. The talk will take us on a tour that will cover problems in nanoscience, e.g. controlling self-organizing systems, optimizing scanning probe microscopy, etc., problems arising in bioinformatics, such as predicting protein structures and their features, to challenges emerging in systems and synthetic biology. Although the algorithmic solutions involved in these problems are different from each other, at their core, they retain Darwin's wonderful insights. I will conclude the talk by giving a personal view on why EC has been so successful and where, in my mind, the future lies.

Models in Genetic Based Machine Learning (GBML) systems are commonly used to gain understanding of how the system works and, as a consequence, adjust it better. In this paper we propose models for the probability of having a good initial population using the Attribute List Knowledge Representation (ALKR) for discrete inputs using the GABIL encoding. We base our work in the schema and covering bound models previously proposed for XCS. The models are extended to (a) deal with the combination of ALKR+GABIL representation, (b) explicitly handle datasets with niche overlap and (c) model the impact of using covering and a default rule in the representation. The models are designed and evaluated within the framework of the BioHEL GBML system and are empirically evaluated using first boolean datasets and later also nominal datasets of higher cardinality. The models in this paper allow us to evaluate the challenges presented by problems with high cardinality (in terms of number of attributes and values of the attributes) as well as the benefits contributed by each of the components of BioHEL's representation and initialisation operators.

SUMMARY: The Infobiotics Workbench is an integrated software suite incorporating model specification, simulation, parameter optimization and model checking for Systems and Synthetic Biology. A modular model specification allows for straightforward creation of large-scale models containing many compartments and reactions. Models are simulated either using stochastic simulation or numerical integration, and visualized in time and space. Model parameters and structure can be optimized with evolutionary algorithms, and model properties calculated using probabilistic model checking. AVAILABILITY: Source code and binaries for Linux, Mac and Windows are available at http://www.infobiotics.org/infobiotics-workbench/; released under the GNU General Public License (GPL) version 3. CONTACT: [email protected].

Developing a problem-domain independent methodology to automatically generate high performing solving strategies for specific problems is one of the challenging trends on hyper-heuristics design. Designing hyper-heuristics is important because they raise the level of generality on automated problem solving by attempting to select and/or generate tailored heuristics for the problem at hand. In this paper, we present a three-steps methodology that combines multiple sequence alignment and grammatical induction in order to automatically generate high performing solving strategies for a combinatorial optimisation problem. We present proof-of-concept results of applying this methodology to instances of the well-known symmetric TSP. The goal here is to demonstrate feasibility rather than compete with state of the art TSP solvers. This TSP is chosen only because it is an easy to state and well known problem.

In this paper we introduce a method for computing fitness in evolutionary learning systems based on NVIDIA's massive parallel technology using the CUDA library. Both the match process of a population of classifiers against a training set and the computation of the fitness of each classifier from its matches have been parallelized. This method has been integrated within the BioHEL evolutionary learning system. The methodology presented in this paper can be easily extended to any evolutionary learning system. The method has been tested using a broad set of problems with varying number of attributes and instances. The evaluation function by itself achieves speedups up to 52.4X while its integration with the entire learning process achieves speedups up to 58.1X. Moreover, the speedup increases when the CUDA-based fitness computation is combined with other efficiency enhancement mechanisms.

Executable Biology, also called Algorithmic Systems Biology, uses rigorous concepts from computer science and mathematics to build computational models of biological entities. P systems are emerging as one of the key modelling frameworks within Executable Biology. In this paper, we address the continuous backward problem: given a P system model structure and a target phenotype (i.e. an intended biological behaviour), one is tasked with finding the (near) optimal parameters for the model that would make the P system model produce the target behaviour as closely as possible. We test several real-valued parameter optimisation algorithms on this problem. More specifically, using four different test cases of increasing complexity, we perform experiments with four evolutionary algorithms, and one variable neighbourhood search method combining three other evolutionary algorithms. The results show that, when there are few parameters to optimise, a genetic and two differential evolution based algorithms are robust optimisers attaining the best results. However, when the number of parameters increases, the variable neighbourhood search approach performs better.

UNLABELLED: TopoGSA (Topology-based Gene Set Analysis) is a web-application dedicated to the computation and visualization of network topological properties for gene and protein sets in molecular interaction networks. Different topological characteristics, such as the centrality of nodes in the network or their tendency to form clusters, can be computed and compared with those of known cellular pathways and processes. AVAILABILITY: Freely available at http://www.infobiotics.net/topogsa.

BACKGROUND: Cellular processes and pathways, whose deregulation may contribute to the development of cancers, are often represented as cascades of proteins transmitting a signal from the cell surface to the nucleus. However, recent functional genomic experiments have identified thousands of interactions for the signalling canonical proteins, challenging the traditional view of pathways as independent functional entities. Combining information from pathway databases and interaction networks obtained from functional genomic experiments is therefore a promising strategy to obtain more robust pathway and process representations, facilitating the study of cancer-related pathways. RESULTS: We present a methodology for extending pre-defined protein sets representing cellular pathways and processes by mapping them onto a protein-protein interaction network, and extending them to include densely interconnected interaction partners. The added proteins display distinctive network topological features and molecular function annotations, and can be proposed as putative new components, and/or as regulators of the communication between the different cellular processes. Finally, these extended pathways and processes are used to analyse their enrichment in pancreatic mutated genes. Significant associations between mutated genes and certain processes are identified, enabling an analysis of the influence of previously non-annotated cancer mutated genes. CONCLUSIONS: The proposed method for extending cellular pathways helps to explain the functions of cancer mutated genes by exploiting the synergies of canonical knowledge and large-scale interaction data.

Assessment of the (Multi) Similarity among a set of protein structures is achieved through an ensemble of protein structure comparison methods/algorithms. This leads to the generation of a multitude of data that varies both in type and size. After passing through standardization and normalization, this data is further used in consensus development; providing domain independent and highly reliable view of the assessment of (di)similarities. This paper briefly describes some of the techniques used for the estimation of missing/invalid values resulting from the process of multi-comparison of very large scale datasets in a distributed/grid environment. This is followed by an empirical study on the storage capacity and query processing time required to cope with the results of such comparisons. In particular we investigate and compare the storage/query overhead of two commonly used database technologies such as the Hierarchical Data Format (HDF) (HDF5) and Relational Database Management System (RDBMS) (Oracle/SQL) in terms of our application deployed on the National Grid Service (NGS), UK. As the technologies explored under this investigation are quite generic in the science and engineering domain, our findings would also be beneficial for other scientific applications having related magnitude of data and functionality.

Automatic protein structure predictors use the notion of energy to guide the search towards good candidate structures. The energy functions used by the state-of-the-art predictors are defined as a linear combination of several energy terms designed by human experts. We hypothesised that the energy based guidance could be more accurate if the terms were combined more freely. To test this hypothesis, we designed a genetic programming algorithm to evolve the protein energy function. Using several different fitness functions we examined the potential of the evolutionary approach on a set of candidate structures generated during the protein structure prediction process. Although our algorithms were able to improve over the random walk, the fitness of the best individuals was far from the optimum. We discuss the shortcomings of our initial algorithm design and the possible directions for further research.

Data mining is the analysis of experimental datasets to extract trends and relationships that can be meaningful for the user. In genetic studies these techniques have revealed interesting findings, especially in the heritable predisposition to contract specific diseases. One of these diseases which is still under extensive analysis is pre-eclampsia, a progressive disorder which occurs during pregnancy and soon after the birth, affecting both the mothers and their babies. There are many choices to be made in the application of the various data mining techniques that may be used to study general genotype-phenotype associations. The aim of this paper is to describe the general framework that we adopted in the application of decision tree algorithms to the analysis of SNPs data related to cases of pre-eclampsia. The results show the validity of this methodology to detect a subset of attributes associated with the predictable variable, providing a reduction in the size of the dataset. Moreover, from the clinical point of view, it confirmed the medical interpretation of the ‘corrected birth-weight centile’ (CBC) value of 10 being a meaningful cut-off and confirmed association between an infant's CBC and the ‘week of delivery’ parameter. We hope that the generic framework described here will be of use to other researchers analysing such data.

Datasets with a large number of attributes are a difficult challenge for evolutionary learning techniques. The recently proposed attribute list rule representation has shown to be able to significantly improve the overall performance (e.g. run-time, accuracy, rule set size) of the BioHEL Iterative Evolutionary Rule Learning system. In this paper we, first, extend the attribute list rule representation so it can handle not only continuous domains, but also datasets with a very large number of mixed discrete-continuous attributes. Secondly, we benchmark the new representation with a diverse set of large-scale datasets and, third, we compare the new algorithms with several well-known machine learning methods. The experimental results we describe in the paper show that the new representation is equal or better than the stateof-the-art in evolutionary rule representations both in terms of the accuracy obtained with the benchmark datasets used, as well as in terms of the computational time requirements needed to achieve these improved accuracies. The new attribute list representation puts BioHEL on an equal footing with other well-established machine learning techniques in terms of accuracy. In the paper, we also analyse and discuss the current weaknesses behind the current representation and indicate potential avenues for correcting them.

VLSI research, in its continuous push toward further miniaturisation, is seeking to break through the limitations of current circuit manufacture techniques by moving towards biomimetic methodologies that rely on self-assembly, selforganisation and evodevo-like processes. On the other hand, Systems and Synthetic biology's quest to achieve ever more detailed (multi)cell models are relying more and more on concepts derived from computer science and engineering such as the use of logic gates, clocks and pulse generator analogs to describe a cell's decision making behavior. This paper is situated at the crossroad of these two enterprises. That is, a novel method of non-conventional computation based on the encapsulation of simple gene regulatory-like networks within liposomes is described. Three transcription Boolean logic gates were encapsulated and simulated within liposomes self-assembled from DMPC (dimyristoylphosphatidylcholine) amphiphiles using an implementation of Dissipative Particle Dynamics (DPD) created with the NVIDIA CUDA framework, and modified to include a simple collision chemistry in a stochastic environment. The response times of the AND, OR and NOT gates were shown to be positively effected by the encapsulation within the liposome inner volume.

BACKGROUND: We investigate automated and generic alphabet reduction techniques for protein structure prediction datasets. Reducing alphabet cardinality without losing key biochemical information opens the door to potentially faster machine learning, data mining and optimization applications in structural bioinformatics. Furthermore, reduced but informative alphabets often result in, e.g., more compact and human-friendly classification/clustering rules. In this paper we propose a robust and sophisticated alphabet reduction protocol based on mutual information and state-of-the-art optimization techniques. RESULTS: We applied this protocol to the prediction of two protein structural features: contact number and relative solvent accessibility. For both features we generated alphabets of two, three, four and five letters. The five-letter alphabets gave prediction accuracies statistically similar to that obtained using the full amino acid alphabet. Moreover, the automatically designed alphabets were compared against other reduced alphabets taken from the literature or human-designed, outperforming them. The differences between our alphabets and the alphabets taken from the literature were quantitatively analyzed. All the above process had been performed using a primary sequence representation of proteins. As a final experiment, we extrapolated the obtained five-letter alphabet to reduce a, much richer, protein representation based on evolutionary information for the prediction of the same two features. Again, the performance gap between the full representation and the reduced representation was small, showing that the results of our automated alphabet reduction protocol, even if they were obtained using a simple representation, are also able to capture the crucial information needed for state-of-the-art protein representations. CONCLUSION: Our automated alphabet reduction protocol generates competent reduced alphabets tailored specifically for a variety of protein datasets. This process is done without any domain knowledge, using information theory metrics instead. The reduced alphabets contain some unexpected (but sound) groups of amino acids, thus suggesting new ways of interpreting the data.

BACKGROUND: Statistical analysis of DNA microarray data provides a valuable diagnostic tool for the investigation of genetic components of diseases. To take advantage of the multitude of available data sets and analysis methods, it is desirable to combine both different algorithms and data from different studies. Applying ensemble learning, consensus clustering and cross-study normalization methods for this purpose in an almost fully automated process and linking different analysis modules together under a single interface would simplify many microarray analysis tasks. RESULTS: We present ArrayMining.net, a web-application for microarray analysis that provides easy access to a wide choice of feature selection, clustering, prediction, gene set analysis and cross-study normalization methods. In contrast to other microarray-related web-tools, multiple algorithms and data sets for an analysis task can be combined using ensemble feature selection, ensemble prediction, consensus clustering and cross-platform data integration. By interlinking different analysis tools in a modular fashion, new exploratory routes become available, e.g. ensemble sample classification using features obtained from a gene set analysis and data from multiple studies. The analysis is further simplified by automatic parameter selection mechanisms and linkage to web tools and databases for functional annotation and literature mining. CONCLUSION: ArrayMining.net is a free web-application for microarray analysis combining a broad choice of algorithms based on ensemble and consensus methods, using automatic parameter selection and integration with annotation databases.

In this paper we empirically evaluate several local search (LS) mechanisms that heuristically edit classification rules and rule sets to improve their performance. Two kinds of operators are studied, (1) rule-wise operators, which edit individual rules, and (2) a rule set-wise operator, which takes the rules from N parents (N > or = 2) to generate a new offspring, selecting the minimum subset of candidate rules that obtains maximum training accuracy. Moreover, various ways of integrating these operators within the evolutionary cycle of learning classifier systems are studied. The combinations of LS operators and policies are integrated in a Pittsburgh approach framework that we call MPLCS for memetic Pittsburgh learning classifier system. MPLCS is systematically evaluated using various metrics. Several datasets were employed with the objective of identifying which combination of operators and policies scale well, are robust to noise, generate compact solutions, and use the least amount of computational resources to solve the problems.

A cellular genetic algorithm (CGA) is a decentralized form of GA where individuals in a population are usually arranged in a 2D grid and interactions among individuals are restricted to a set neighborhood. In this paper, we extend the notion of cellularity to memetic algorithms (MA), a configuration termed cellular memetic algorithm (CMA). In addition, we propose adaptive mechanisms that tailor the amount of exploration versus exploitation of local solutions carried out by the CMA. We systematically benchmark this adaptive mechanism and provide evidence that the resulting adaptive CMA outperforms other methods both in the quality of solutions obtained and the number of function evaluations for a range of continuous optimization problems.

In our previous work Li et al., in Proc of 3rd IEEE Int Workshop on Engineering of Automatic & Automation Systems, Potsdam, Germany, 2006, pp 25–34; Li et al., in Proc Workshop on Nature Inspired Cooperative Strategies for Optimization, Granada, Spain, 2006, pp 123–134, we introduced automated self-assembly programming paradigm (ASAP2) using unguided self-assembly and swarm-inspired methodologies. We investigated how external environment settings affect software self-assembly speed and diversity of the generated programs. In this paper, we extend our previous work with a diversified compartments approach based on general graphs. This diversified compartments approach is integrated into a network structure such that each compartment can be seen as a node in the network. We investigate how structures of the network impacts on software self-assembly speed, complexity, and diversity of generated programs. Results indicate that network structure can substantially affect the dynamics, diversity, and complexity of generated programs. © 2009 Wiley Periodicals, Inc.

Genetic-Based Machine Learning Systems (GBML) are comparable in accuracy with other learning methods. However, efficiency is a significant drawback. This paper presents a new representation for continuous attributes motivated by our previous work in large-scale Bioinformatics datasets, where we can observe that, very often, a very small fraction of the attributes of a domain are expressed at the same time in a rule. Automatically discovering these few key attributes and only keeping track of them contributes to a substantial speed up by avoiding useless match operations with irrelevant attributes, while potentially leading to a better learning process. The representation we propose has been tested within the BioHEL GBML system, and our experiments show that this representation has competent learning performance and reduces considerably the system run-time, up to 2-3 times faster than the state-of-the-art in fast GBML representations for datasets with hundreds of attributes.

In this work we present a new methodology for structure and parameter estimation in cell systems biology modelling. Our modelling framework is based on P systems, an unconventional computational paradigm that abstracts from the structure and functioning of the living cell. The process of designing models, consisting of both the optimisation of the modular structure and of the stochastic kinetic parameters, is performed using a memetic algorithm. Specically, we use a nested evolutionary algorithm where the first layer evolves rule structures while the inner layer, implemented also as a genetic algorithm (GA), fine tunes the parameters of the model. Our approach consists of an incremental methodology. Starting from very simple P system modules specifying basic molecular interactions, more complicated modules are produced to model more complex molecular systems. These newly found modules are in turn added to the library of available P systems modules so as to be used subsequently to develop more intricate and circuitous cellular models. The effectiveness of the algorithm was tested on three case studies, namely, molecular complexation, enzymatic reactions and autoregulation in transcriptional networks.

Compartmentalisation is thought to have been a crucial step in the origin of life. To help us bridge the gap between selfassembly processes behind the formation of bio-compartments and metabolic and information bearing processes we refer to DPD and P Systems Simulations. In this paper we computational formalism (P Systems) with a molecular scale model (Dissipative Particle Dynamics) by linking the membranes which delimit the cellular regions within P Systems to self-assembled phospholipid based vesicles in DPD. We test the platform by modelling a passive transport process involving vesicles containing membrane inclusions similar to pore complexes such as α-hemolysin. In doing so, we illustrate the usefulness of the modelling approach and derive a more realistic parameter set for the P system through the dissipative particle dynamics simulation.

The comparison of protein tertiary structures is a key milestone in many structural bioinformatics activities that rely in comparing very large structure datasets. As the number of proteins in the dataset increases, the corresponding computational time taken by the protein structure comparison algorithms also increases, squarely for an all-against-all comparison and linearly for an all-against-target assessment. Thus ever larger proteomics problems call for the distribution of pairwise comparison jobs in the form of well granulated subsets/packages to be run in parallel on a pool of networked processors/workstations under the coordination of a message passing interface (MPI) environment. This paper evaluates the effect on the performance of such jobs when the MPI environment is integrated with a local resource management system (LRMS) such as sun grid engine (SGE). From our experiments with different ways of integration we draw a comparative picture of all possible approaches with the description of resource usage information for each parallel job on each processor. Understanding of different ways of integration sheds light on the most promising routes for setting up an efficient environment for very large scale protein structure comparisons.

MOTIVATION: We introduce a new method for designating the location of residues in folded protein structures based on the recursive convex hull (RCH) of a point set of atomic coordinates. The RCH can be calculated with an efficient and parameterless algorithm. RESULTS: We show that residue RCH class contains information complementary to widely studied measures such as solvent accessibility (SA), residue depth (RD) and to the distance of residues from the centroid of the chain, the residues' exposure (Exp). RCH is more conserved for related structures across folds and correlates better with changes in thermal stability of mutants than the other measures. Further, we assess the predictability of these measures using three types of machine-learning technique: decision trees (C4.5), Naive Bayes and Learning Classifier Systems (LCS) showing that RCH is more easily predicted than the other measures. As an exemplar application of predicted RCH class (in combination with other measures), we show that RCH is potentially helpful in improving prediction of residue contact numbers (CN).

Over the recent years, there has been increasing research activities made on improving the efficacy of memetic algorithm (MA) for solving complex optimization problems. Particularly, these efforts have revealed the success of MA on a wide range of real world problems. MAs not only converge to high quality solutions, but also search more efficiently than their conventional counterparts. Despite the success and surge in interests on MAs, there is still plenty of scope for furthering our understanding on how and why synergy between population- based and individual learning searchers would lead to successful Memetic Algorithms. In this paper we outline several important design issues of Memetic Algorithms and present a systematic study on each. In particular, we conduct extensive experimental studies on the impact of each individual design issue and their relative impacts on memetic search performances by means of three commonly used synthetic problems. From the empirical studies obtained, we attempt to reveal the behaviors of several MA variants to enhance our understandings on MAs.

Self-assembly is a distributed, asynchronous mechanism that is pervasive across natural systems where hierarchical complex structures are built from the bottom-up. The lack of a centralised master plan, no external intervention, and preprogrammed interactions among entities are within its most relevant and technologically appealing properties. This paper tackles the self-assembly Wang tiles designability problem by means of artificial evolution. This research is centred in the use of tiles that are extended with rotation and probabilistic motion, and an evolutionary algorithm using the Morphological Image Analyses method as a fitness function. The obtained results support this approach as a successful engineering mechanism for the computer-aided design of self-assembled patterns.

This paper focuses on automated procedures to reduce the dimensionality of protein structure prediction datasets by simplifying the way in which the primary sequence of a protein is represented. The potential benefits of this procedure are faster and easier learning process as well as the generation of more compact and human-readable classifiers. The dimensionality reduction procedure we propose consists on the reduction of the 20-letter amino acid (AA) alphabet, which is normally used to specify a protein sequence, into a lower cardinality alphabet. This reduction comes about by a clustering of AA types accordingly to their physical and chemical similarity. Our automated reduction procedure is guided by a fitness function based on the Mutual Information between the AA-based input attributes of the dataset and the protein structure feature that being predicted. To search for the optimal reduction, the Extended Compact Genetic Algorithm (ECGA) was used, and afterwards the results of this process were fed into (and validated by) BioHEL, a genetics-based machine learning technique. BioHEL used the reduced alphabet to induce rules for protein structure prediction features. BioHEL results are compared to two standard machine

BACKGROUND: We introduce the decision support system for Protein (Structure) Comparison, Knowledge, Similarity and Information (ProCKSI). ProCKSI integrates various protein similarity measures through an easy to use interface that allows the comparison of multiple proteins simultaneously. It employs the Universal Similarity Metric (USM), the Maximum Contact Map Overlap (MaxCMO) of protein structures and other external methods such as the DaliLite and the TM-align methods, the Combinatorial Extension (CE) of the optimal path, and the FAST Align and Search Tool (FAST). Additionally, ProCKSI allows the user to upload a user-defined similarity matrix supplementing the methods mentioned, and computes a similarity consensus in order to provide a rich, integrated, multicriteria view of large datasets of protein structures. RESULTS: We present ProCKSI's architecture and workflow describing its intuitive user interface, and show its potential on three distinct test-cases. In the first case, ProCKSI is used to evaluate the results of a previous CASP competition, assessing the similarity of proposed models for given targets where the structures could have a large deviation from one another. To perform this type of comparison reliably, we introduce a new consensus method. The second study deals with the verification of a classification scheme for protein kinases, originally derived by sequence comparison by Hanks and Hunter, but here we use a consensus similarity measure based on structures. In the third experiment using the Rost and Sander dataset (RS126), we investigate how a combination of different sets of similarity measures influences the quality and performance of ProCKSI's new consensus measure. ProCKSI performs well with all three datasets, showing its potential for complex, simultaneous multi-method assessment of structural similarity in large protein datasets. Furthermore, combining different similarity measures is usually more robust than relying on one single, unique measure. CONCLUSION: Based on a diverse set of similarity measures, ProCKSI computes a consensus similarity profile for the entire protein set. All results can be clustered, visualised, analysed and easily compared with each other through a simple and intuitive interface.ProCKSI is publicly available at http://www.procksi.net for academic and non-commercial use.

The ten papers in this special section are devoted to memetic algorithms. The papers are loosely grouped into two categories: memetic algorithm methodologies and domain-specific memetic algorithms. Briefly summarizes the articles included in this section.

This paper proposes a new smart crossover operator for a Pittsburgh Learning Classifier System. This operator, unlike other recent LCS approaches of smart recombination, does not learn the structure of the domain, but it merges the rules of N parents (N ≥ 2) to generate a new offspring. This merge process uses an heuristic that selects the minimum subset of candidate rules that obtains maximum training accuracy. Moreover the operator also includes a rule pruning scheme to avoid the inclusion of over-specific rules, and to guarantee as much as possible the robust behaviour of the LCS. This operator takes advantage from the fact that each individual in a Pittsburgh LCS is a complete solution, and the system has a global view of the solution space that the proposed rule selection algorithm exploits. We have empirically evaluated this operator using a recent LCS called GAssist. First with the standard LCS benchmark, the 11 bits multiplexer, and later using 25 standard real datasets. The results of the experiments over these datasets indicate that the new operator manages to increase the accuracy of the system over the classical crossover in 16 of the 25 datasets, and never having a significantly worse performance than the classic operator.

The prediction of the coordination number (CN) of an amino acid in a protein structure has recently received renewed attention. In a recent paper, Kinjo et al. proposed a real-valued definition of CN and a criterion to map it onto a finite set of classes, in order to predict it using classification approaches. The literature reports several kinds of input information used for CN prediction. The aim of this paper is to assess the performance of a state-of-the-art learning method, Learning Classifier Systems (LCS) on this CN definition, with various degrees of precision, based on several combinations of input attributes. Moreover, we will compare the LCS performance to other well-known learning techniques. Our experiments are also intended to determinethe minimum set of input information needed to achieve good predictive performance, so as to generate competent yet simple and interpretable classification rules. Thus, the generated predictors (rule sets) are analyzed for their interpretability.

This paper reports an improvement to genetic programming (GP) search for the symbolic regression domain, based on an analysis of dissimilarity and mating. GP search is generally difficult to characterise for this domain, preventing well motivated algorithmic improvements. We first examine the ability of various solutions to contribute to the search process. Further analysis highlights the numerous solutions produced during search with no change to solution quality. A simple algorithmic enhancement is made that reduces these events and produces a statistically significant improvement in solution quality. We conclude by verifying the generalisability of these results on several other regression instances

Self-assembly is a powerful autopoietic mechanism ubiquitous throughout the natural world. It may be found at the molecular scale and also at astronomical scales. Self-assembly power lays in the fact that it is a distributed, not necessarily synchronous, control mechanism for the bottom-up manufacture of complex systems. Control of the assembly process is shared across a myriad of elemental components, none of which has either the storage or the computation capabilities to know and follow a master plan for the assembly of the intended system. In this paper we present an evolutionary algorithm which is capable of programming the so called "Wang tiles" for the self-assembly of two-dimensional squares.

The combination of evolutionary algorithms with local search was named "memetic algorithms" (MAs) (Moscato, 1989). These methods are inspired by models of natural systems that combine the evolutionary adaptation of a population with individual learning within the lifetimes of its members. Additionally, MAs are inspired by Richard Dawkin's concept of a meme, which represents a unit of cultural evolution that can exhibit local refinement (Dawkins, 1976). In the case of MA's, "memes" refer to the strategies (e.g., local refinement, perturbation, or constructive methods, etc.) that are employed to improve individuals. In this paper, we review some works on the application of MAs to well-known combinatorial optimization problems, and place them in a framework defined by a general syntactic model. This model provides us with a classification scheme based on a computable index D, which facilitates algorithmic comparisons and suggests areas for future research. Also, by having an abstract model for this class of metaheuristics, it is possible to explore their design space and better understand their behavior from a theoretical standpoint. We illustrate the theoretical and practical relevance of this model and taxonomy for MAs in the context of a discussion of important design issues that must be addressed to produce effective and efficient MAs.

Abstract Motivation: As an increasing number of protein structures become available, the need for algorithms that can quantify the similarity between protein structures increases as well. Thus, the comparison of proteins' structures, and their clustering accordingly to a given similarity measure, is at the core of today's biomedical research. In this paper, we show how an algorithmic information theory inspired Universal Similarity Metric (USM) can be used to calculate similarities between protein pairs. The method, besides being theoretically supported, is surprisingly simple to implement and computationally efficient. Results: Structural similarity between proteins in four different datasets was measured using the USM. The sample employed represented alpha, beta, alpha–beta, tim–barrel, globins and serpine protein types. The use of the proposed metric allows for a correct measurement of similarity and classification of the proteins in the four datasets. Availability: All the scripts and programs used for the preparation of this paper are available at http://www.cs.nott.ac.uk/~nxk/USM/protocol.html. In that web-page the reader will find a brief description on how to use the various scripts and programs. Supplementary information: The protein datasets used are collected in http://www.cs.nott.ac.uk/~nxk/USM/datasets.html. The calculated similarity values for the proteins used in this paper can be found in http://www.cs.nott.ac.uk/~nxk/USM/similar.html. The clustering of the dataset based on these similarity values can be found in http://www.cs.nott.ac.uk/~nxk/USM/clustering.html

This paper presents a real-coded memetic algorithm that applies a crossover hill-climbing to solutions produced by the genetic operators. On the one hand, the memetic algorithm provides global search (reliability) by means of the promotion of high levels of population diversity. On the other, the crossover hill-climbing exploits the self-adaptive capacity of real-parameter crossover operators with the aim of producing an effective local tuning on the solutions (accuracy). An important aspect of the memetic algorithm proposed is that it adaptively assigns different local search probabilities to individuals. It was observed that the algorithm adjusts the global/local search balance according to the particularities of each problem instance. Experimental results show that, for a wide range of problems, the method we propose here consistently outperforms other real-coded memetic algorithms which appeared in the literature.

This paper presents an analysis of increased diversity in genetic programming. A selection strategy based on genetic lineages is used to increase genetic diversity. A genetic lineage is defined as the path from an individual to individuals which were created from its genetic material. The method is applied to three problem domains: artificial ant, even-5-parity and symbolic regression of the binomial-3 function. We examine how increased diversity affects problems differently and draw conclusions about the types of diversity which are more important for each problem. Results indicate that diversity in the ant problem helps to overcome deception, while elitism in combination with diversity is likely to benefit the parity and regression problems.

No abstract available.

No abstract available.