The de novo design of median molecules within a property range of interest

Summary In this paper an application is presented of the median molecule workflow to the de novo design of novel molecular entities with a property profile of interest. Median molecules are structures that are optimised to be similar to a set of existing molecules of interest as an approach for lead exploration and hopping. An overview of this workflow is provided together with an example of an instance using the similarity to camphor and menthol as objectives. The methodology of the experiments is defined and the workflow is applied to designing novel molecules for two physical property datasets: mean molecular polarisability and aqueous solubility. This paper concludes with a discussion of the characteristics of this method.     

Hybrid genetic algorithm–tabu search approach for optimising multilayer optical coatings

Constructing multilayer optical coatings (MOCs) is a difficult large-scale optimisation problem due to the enormous size of the search space. In the present paper, a new approach for designing MOCs is presented using genetic algorithms (GAs) and tabu search (TS). In this approach, it is not necessary to specify how many layers will be present in a design, only a maximum needs to be defined. As it is generally recognised that the existence of specific repeating blocks is beneficial for a design, a specific GA representation of a design is used which promotes the occurrence of repeating blocks. Solutions found by GAs are improved by a new refinement method, based on TS, a global optimisation method which is loosely based on artificial intelligence. The improvements are demonstrated by creating a visible transmitting/infrared reflecting filter with a wide variety of materials.     

Protein fold recognition

Summary An important, yet seemingly unattainable, goal in structural molecular biology is to be able to predict the native three-dimensional structure of a protein entirely from its amino acid sequence. Prediction methods based on rigorous energy calculations have not yet been successful, and best results have been obtained from homology modelling and statistical secondary structure prediction. Homology modelling is limited to cases where significant sequence similarity is shared between a protein of known structure and the unknown. Secondary structure prediction methods are not only unreliable, but also do not offer any obvious route to the full tertiary structure. Recently, methods have been developed whereby entire protein folds are recognized from sequence, even where little or no sequence similarity is shared between the proteins under consideration. In this paper we review the current methods, including our own, and in particular offer a historical background to their development. In addition, we also discuss the future of these methods and outline the developments under investigation in our laboratory.     

GO-MOCE: Greedy Order Method of Conditional Expectations for Max Sat

In this paper we present and study a new algorithm for the Maximum Satisfiability (Max Sat) problem. The algorithm is based on the Method of Conditional Expectations (MOCE, also known as Johnson’s Algorithm) and applies a greedy variable ordering to MOCE. Thus, we name it Greedy Order MOCE (GO-MOCE). We also suggest a combination of GO-MOCE with CCLS, a state-of-the-art solver. We refer to this combined solver as GO-MOCE-CCLS.We conduct a comprehensive comparative evaluation of GO-MOCE versus MOCE on random instances and on public competition benchmark instances. We show that GO-MOCE reduces the number of unsatisfied clauses by tens of percents, while keeping the runtime almost the same. The worst case time complexity of GO-MOCE is linear. We also show that GO-MOCE-CCLS improves on CCLS consistently by up to about 80%.We study the asymptotic performance of GO-MOCE. To this end, we introduce three measures for evaluating the asymptotic performance of algorithms for Max Sat. We point out to further possible improvements of GO-MOCE, based on an empirical study of the main quantities managed by GO-MOCE during its execution.     

Efficient simulation of general stochastic hybrid systems

General Stochastic Hybrid System (SHS) are characterised by Stochastic Differential Equations (SDEs) with discontinuities and Poisson jump processes. SHS are useful in model based design of Cyber-Physical System (CPS) controllers under uncertainty. Industry standard model based design tools such as Simulink/Stateflow® are inefficient when simulating, testing, and validating SHS, because of dependence on fixed-step Euler–Maruyama (EM) integration and discontinuity detection. We present a novel efficient adaptive step-size simulation/integration technique for general SHSs modelled as a network of Stochastic Hybrid Automatons (SHAs). We propose a simulation algorithm where each SHA in the network executes synchronously with the other, at an integration step-size computed using adaptive step-size integration. Ito’ multi-dimensional lemma and the inverse sampling theorem are leveraged to compute the integration step-size by making the SDEs and Poisson jump rate integration dependent upon discontinuities. Existence and convergence analysis along with experimental results show that the proposed technique is substantially faster than Simulink/Stateflow®when simulating general SHSs.     

An exact algorithm for the capacitated shortest spanning arborescence

We are given a complete and loop-free digraphG=(V, A), whereV={1,...,n} is the vertex set,A={(i, j) :i, j V} the arc set, andr V is a distinguishedroot vertex. For each arc (i, j) A, letc _ij be the associatedcost, and for each vertexi, letq _i 0 be the associateddemand (withq _r =0). Moreover, a nonnegativebranch capacity, Q, is defined.A Capacitated Shortest Spanning Arborescence rooted at r (CSSA _r ) is a minimum cost partial digraph such that: (i) each vertexj r has exactly one entering arc; (ii) for each vertexj r, a path fromr toj exists; (iii) for each branch leaving vertexr, the total demand of the vertices does not exceed the branch capacity,Q. A variant of theCSSA _r problem (calledD-CSSA _r ) arises when the out-degree of the root vertex is constrained to be equal to a given valueD. These problems are strongly NP-hard, and find practical applications in routing and network design. We describe a new Lagrangian lower bound forCSSA _r andD-CSSA _r problems, strengthened in a cutting plane fashion by iteratively adding violated constraints to the Lagrangian problem. We also present a new lower bound based on projection leading to the solution of min-cost flow problems. The two lower bounds are then combined so as to obtain an overall additive lower bounding procedure. The additive procedure is then imbedded in a branch-and-bound algorithm whose performance is enhanced by means of reduction procedures, dominance criteria, feasibility checks and upper bounding. Computational tests on asymmetric and symmetric instances from the literature, involving up to 200 vertices, are given, showing the effectiveness of the proposed approach.     

Stochastic on-line knapsack problems

Different classes of on-line algorithms are developed and analyzed for the solution of {0, 1} and relaxed stochastic knapsack problems, in which both profit and size coefficients are random variables. In particular, a linear time on-line algorithm is proposed for which the expected difference between the optimum and the approximate solution value isO(log^3/2 n). An(1) lower bound on the expected difference between the optimum and the solution found by any on-line algorithm is also shown to hold.Corresponding author.Partially supported by the Basic Research Action of the European Communities under Contract 3075 (Alcom).Partially supported by research project Models and Algorithms for Optimization of the Italian Ministry of University and Scientific and Technological Research (MURST 40%).     

Randomized algorithms for the separation of point sets and for solving quadratic programs

A randomized algorithm for finding a hyperplane separating two finite point sets in the Euclidean space ^d and a randomized algorithm for solving linearly constrained general convex quadratic problems are proposed. The expected running time of the separating algorithm isO(dd! (m + n)), wherem andn are cardinalities of sets to be separated. The expected running time of the algorithm for solving quadratic problems isO(dd! s) wheres is the number of inequality constraints. These algorithms are based on the ideas of Seidel's linear programming algorithm [6]. They are closely related to algorithms of [8], [2], and [9] and belong to an abstract class of algorithms investigated in [1]. The algorithm for solving quadratic problems has some features of the one proposed in [7].This research was done when the author was supported by the Alexander von Humboldt Foundation, Germany.On leave from the Institute of Mathematics and Mechanics, Ural Department of the Russian Academy of Sciences, 620219 Ekaterinburg, S. Kovalevskaya str. 16, Russia.     

The ground-state energy of the ±J sping glass. A comparison of various biologically motivated algorithms

We compare various evlutionary strategies to determine the ground-state energy of the ±J spin glass. We show that the choice of different evolution laws is less important than a suitable treatment of the free spins of the system At least one combination of these strategies does not give the correct results, but the ground states of the other different strategies coincide. Therefore we are able to extrapolate the infinit-size ground-state energy for the square lattice to –1.401±0.0015 and for the simple cubic lattice to –1.786±0.004.