Protein folding in the HP model on grid lattices with diagonals

The protein folding problem, i.e., the computational prediction of the three-dimensional structure of a protein from its amino acid sequence, is one of the most important and challenging problems in computational biology. Since a complete simulation of the folding process of a protein is far too complex to handle, one tries to find an approximate solution by using a simplified, abstract model. One of the most popular models is the so-called HP model, where the hydrophobic interactions between the amino acids are considered to be the main force in the folding process, and furthermore the folding space is modeled by a two- or three-dimensional grid lattice.In this paper, we will present some approximation algorithms for the protein folding problem in the HP model on an extended grid lattice with plane diagonals. The choice of this kind of lattice removes one of the major drawbacks of the original HP model, namely the bipartiteness of the grid which severely restricts the set of possible foldings. Our algorithms achieve an approximation ratio of for the two-dimensional and of for the three-dimensional lattice. This improves significantly over the best previously known approximation ratios for the protein folding problem in the HP model on any lattice.     

Using data mining to identify structural rules in proteins

The progress in bioinformatics and biotechnology area has generated a huge amount of sequences that requires a detailed analysis. There are several data mining techniques that can be used to discovery patterns in large databases. This paper describes the development of a tool/methodology to extract hydrophobicity patterns/profiles that archives a specific secondary structure in proteins. The results indicate that association rules can be efficient method to investigate this kind of problem. This work contributes for two areas: prediction of protein structure and protein folding.     

An optimization approach to the problem of protein structure prediction

We describe a large-scale, stochastic-perturbation global optimization algorithm used for determining the structure of proteins. The method incorporates secondary structure predictions (which describe the more basic elements of the protein structure) into the starting structures, and thereafter minimizes using a purely physics-based energy model. Results show this method to be particularly successful on protein targets where structural information from similar proteins is unavailable, i.e., the most difficult targets for most protein structure prediction methods. Our best result to date is on a protein target containing over 4000 atoms and 12,000 cartesian coordinates.     

Parallel continuation-based global optimization for molecular conformation and protein folding

This paper presents our recent work on developing parallel algorithms and software for solving the global minimization problem for molecular conformation, especially protein folding. Global minimization problems are difficult to solve when the objective functions have many local minimizers, such as the energy functions for protein folding. In our approach, to avoid directly minimizing a difficult function, a special integral transformation is introduced to transform the function into a class of gradually deformed, but smoother or easier functions. An optimization procedure is then applied to the new functions successively, to trace their solutions back to the original function. The method can be applied to a large class of nonlinear partially separable functions including energy functions for molecular conformation and protein folding. Mathematical theory for the method, as a special continuation approach to global optimization, is established. Algorithms with different solution tracing strategies are developed. Different levels of parallelism are exploited for the implementation of the algorithms on massively parallel architectures.     

现代优化计算方法在蛋白质结构预测中的应用

现代优化计算方法在蛋白质结构预测中占有重要地位.简要地介绍了模拟退火算法,遗传算法,人工神经网络和图论算法在蛋白质结构预测中的应用.对国内外近年来应用这些算法,特别是在蛋白质构象搜索问题中,解决蛋白质结构预测的研究作了回顾,并分析、比较了这几种算法的效果和特点.     

An improved hybrid global optimization method for protein tertiary structure prediction

First principles approaches to the protein structure prediction problem must search through an enormous conformational space to identify low-energy, near-native structures. In this paper, we describe the formulation of the tertiary structure prediction problem as a nonlinear constrained minimization problem, where the goal is to minimize the energy of a protein conformation subject to constraints on torsion angles and interatomic distances. The core of the proposed algorithm is a hybrid global optimization method that combines the benefits of the αBB deterministic global optimization approach with conformational space annealing. These global optimization techniques employ a local minimization strategy that combines torsion angle dynamics and rotamer optimization to identify and improve the selection of initial conformations and then applies a sequential quadratic programming approach to further minimize the energy of the protein conformations subject to constraints. The proposed algorithm demonstrates the ability to identify both lower energy protein structures, as well as larger ensembles of low-energy conformations.     

An implementation of exact knapsack separation

Cutting planes have been used with great success for solving mixed integer programs. In recent decades, many contributions have led to successive improvements in branch-and-cut methods which incorporate cutting planes in branch and bound algorithm. Using advances that have taken place over the years on 0–1 knapsack problem, we investigate an efficient approach for 0–1 programs with knapsack constraints as local structure. Our approach is based on an efficient implementation of knapsack separation problem which consists of the four phases: preprocessing, row generation, controlling numerical errors and sequential lifting. This approach can be used independently to improve formulations with cutting planes generated or incorporated in branch and cut to solve a problem. We show that this approach allows us to efficiently solve large-scale instances of generalized assignment problem, multilevel generalized assignment problem, capacitated \(p\)-median problem and capacitated network location problem to optimality.     

改进的自组织映射(SOM)蛋白质折叠算法和计算实现

蛋白质结构预测是生物信息学中的重要研究方向．为了研究蛋白质折叠的机理,人们引入了只考虑蛋白质疏水核心和亲水外围位置导致能量差别的简化HP模型．即使是求解二维HP模型已被证明是一个NP完全问题,因此需要设计有效的近似算法来求解较大规模的HP模型．从旅行商问题(TSP)的求解看,自组织映射是构造近似算法的有效工具．本文将归一化的F-W自组织模型应用到蛋白质二维HP问题的求解中,结合为克服多重映射构造的局部线搜索算法．数值试验表明,该算法改进了现有的HP模型的SOM求解算法, 只需很少的迭代步数就能找到最低能量构象．这一改进算法可以成为进一步研究的基础．     

A Geometric Build-Up Algorithm for Solving the Molecular Distance Geometry Problem with Sparse Distance Data

Nuclear magnetic resonance (NMR) structure modeling usually produces a sparse set of inter-atomic distances in protein. In order to calculate the three-dimensional structure of protein, current approaches need to estimate all other missing distances to build a full set of distances. However, the estimation step is costly and prone to introducing errors. In this report, we describe a geometric build-up algorithm for solving protein structure by using only a sparse set of inter-atomic distances. Such a sparse set of distances can be obtained by combining NMR data with our knowledge on certain bond lengths and bond angles. It can also include confident estimations on some missing distances. Our algorithm utilizes a simple geometric relationship between coordinates and distances. The coordinates for each atom are calculated by using the coordinates of previously determined atoms and their distances. We have implemented the algorithm and tested it on several proteins. Our results showed that our algorithm successfully determined the protein structures with sparse sets of distances. Therefore, our algorithm reduces the need of estimating the missing distances and promises a more efficient approach to NMR structure modeling.     

Efficient robust optimization for robust control with constraints

This paper proposes an efficient computational technique for the optimal control of linear discrete-time systems subject to bounded disturbances with mixed linear constraints on the states and inputs. The problem of computing an optimal state feedback control policy, given the current state, is non-convex. A recent breakthrough has been the application of robust optimization techniques to reparameterize this problem as a convex program. While the reparameterized problem is theoretically tractable, the number of variables is quadratic in the number of stages or horizon length N and has no apparent exploitable structure, leading to computational time of per iteration of an interior-point method. We focus on the case when the disturbance set is ∞-norm bounded or the linear map of a hypercube, and the cost function involves the minimization of a quadratic cost. Here we make use of state variables to regain a sparse problem structure that is related to the structure of the original problem, that is, the policy optimization problem may be decomposed into a set of coupled finite horizon control problems. This decomposition can then be formulated as a highly structured quadratic program, solvable by primal-dual interior-point methods in which each iteration requires time. This cubic iteration time can be guaranteed using a Riccati-based block factorization technique, which is standard in discrete-time optimal control. Numerical results are presented, using a standard sparse primal-dual interior point solver, that illustrate the efficiency of this approach.     

Protein Structure Prediction Using Bee Colony Optimization Metaheuristic

Predicting the native structure of proteins is one of the most challenging problems in molecular biology. The goal is to determine the three-dimensional structure from the one-dimensional amino acid sequence. De novo prediction algorithms seek to do this by developing a representation of the proteins structure, an energy potential and some optimization algorithm that finds the structure with minimal energy. Bee Colony Optimization (BCO) is a relatively new approach to solving optimization problems based on the foraging behaviour of bees. Several variants of BCO have been suggested in the literature. We have devised a new variant that unifies the existing and is much more flexible with respect to replacing the various elements of the BCO. In particular, this applies to the choice of the local search as well as the method for generating scout locations and performing the waggle dance. We apply our BCO method to generate good solutions to the protein structure prediction problem. The results show that BCO generally finds better solutions than simulated annealing which so far has been the metaheuristic of choice for this problem.     

Widening requirements capture with soft methods: an investigation of hybrid M&S studies in health care

A simulation study consists of several stages: problem formulation, model implementation, verification and validation, experimentation and output data analysis. The application of multiple techniques in the model implementation stage is referred to as hybrid simulation, which we distinguish in this paper from a hybrid M&S study, the latter referring to studies that apply methods and techniques from disciplines like Operations Research (OR), Systems Engineering and Computer Science to one or more stages of a simulation study. Our paper focuses on the contribution of soft OR methods in the problem formulation stage of a simulation study (and by extension a hybrid M&S study). Soft Systems Methodology (SSM) has, arguably, been the most widely used qualitative approach for eliciting system requirements. In this paper, we present Qualitative System Dynamics (QSD), a soft systems method, as having potential use in the problem formulation stage of a healthcare M&S study. The contribution of this paper is thus twofold: (1) a review of the literature in SSM for healthcare operations management and (2) an examination of QSD as an additional soft OR method, complementing (rather than supplanting) existing approaches, which can further aid the understanding of the system in the problem formulation/conceptual modelling stage of a hybrid M&S study.     

Framework for efficient feature selection in genetic algorithm based data mining

We present the design of more effective and efficient genetic algorithm based data mining techniques that use the concepts of feature selection. Explicit feature selection is traditionally done as a wrapper approach where every candidate feature subset is evaluated by executing the data mining algorithm on that subset. In this article we present a GA for doing both the tasks of mining and feature selection simultaneously by evolving a binary code along side the chromosome structure used for evolving the rules. We then present a wrapper approach to feature selection based on Hausdorff distance measure. Results from applying the above techniques to a real world data mining problem show that combining both the feature selection methods provides the best performance in terms of prediction accuracy and computational efficiency.     

Decomposition Techniques for Bilinear Saddle Point Problems and Variational Inequalities with Affine Monotone Operators

The majority of first-order methods for large-scale convex–concave saddle point problems and variational inequalities with monotone operators are proximal algorithms. To make such an algorithm practical, the problem’s domain should be proximal-friendly—admit a strongly convex function with easy to minimize linear perturbations. As a by-product, this domain admits a computationally cheap linear minimization oracle (LMO) capable to minimize linear forms. There are, however, important situations where a cheap LMO indeed is available, but the problem domain is not proximal-friendly, which motivates search for algorithms based solely on LMO. For smooth convex minimization, there exists a classical algorithm using LMO—conditional gradient. In contrast, known to us similar techniques for other problems with convex structure (nonsmooth convex minimization, convex–concave saddle point problems, even as simple as bilinear ones, and variational inequalities with monotone operators, even as simple as affine) are quite recent and utilize common approach based on Fenchel-type representations of the associated objectives/vector fields. The goal of this paper was to develop alternative (and seemingly much simpler) decomposition techniques based on LMO for bilinear saddle point problems and for variational inequalities with affine monotone operators.     

A parallel build-up algorithm for global energy minimizations of molecular clusters using effective energy simulated annealing

This work studies the build-up method for the global minimization problem for molecular conformation, especially protein folding. The problem is hard to solve for large molecules using general minimization approaches because of the enormous amount of required computation. We therefore propose a build-up process to systematically construct the optimal molecular structures. A prototype algorithm is designed using the anisotropic effective energy simulated annealing method at each build-up stage. The algorithm has been implemented on the Intel iPSC/860 parallel computer, and tested with the Lennard-Jones microcluster conformation problem. The experiments showed that the algorithm was effective for relatively large test problems, and also very suitable for massively parallel computation. In particular, for the 72-atom Lennard-Jones microcluster, the algorithm found a structure whose energy is lower than any others found in previous studies.     

Structure evaluation of materials by electrical methods

A theoretical and practical framework of different problems has been discussed to explain advantages and limitations of techniques based on electrical sensing methods which are consistent to implement structure evaluation of materials. The term structure evaluation is generally used here to mean extracting the quantitative information of interest of a material or an object to be examined from a physical measurement, or more typically from a set of physical measurements, that themselves may be only indirectly related to the quantitative information desired. The paper emphasizes the point that the structure evaluation is a typical inverse problem and as such is made more difficult, since inverse problems are characteristically illconditioned, that is, small errors in the measurement typically lead to large errors in the solution. Use of physically motivated a priori information to diminishing such ill-conditioning is discussed. Features of updated electrical sensing methods, particularly those used for nondestructive testing (NDT) are considered. Potential advantages of the electrical methods compared to other NDT techniques are that they offer inexpensive, safe, nonharmful, and fast testing. Some novel achievements including excitation with a number of complex electric field excitation patterns on the object together with computer-assisted information acquisition have considerably extended both the potential and the scope of the electrical methods which will still be recognized. In order to present an up-to-date perspective, some conceptual and methodologic aspects have been considered for two structure evaluation problems, i.e., for generating a) algorithms for determining structural parameters of materials, such as density, moisture content, polymerization degree, etc., from dielectric spectra; b) tomographic cross-sectional maps of electrical parameters of the object to be examined.Presented at the Ninth International Conference on the Mechanics of Composite Materials, Riga, October, 1995.Institute of Polymer Mechanics, Riga, Latvia. Published in Mekhanika Kompozitnykh Materialov, No. 1, pp. 124–134, January–February, 1996.     

Protein structure optimization by side-chain positioning via beta-complex

A molecular structure determines a molecular function(s) and a correct understanding of molecular structure is important for biotechnology. The computational prediction of molecular structure is a frequent requirement for important biomolecular applications such as a homology modeling, a docking simulation, a protein design, etc. where the optimization of molecular structure is fundamental. One of the core problems in the optimization of protein structure is the optimization of side-chains called the side-chain positioning problem. The side-chain positioning problem, assuming the rigidity of backbone and a rotamer library, attempts to optimally assign a rotamer to each residue so that the potential energy of protein is minimized in its entirety. The optimal solution approach using (mixed) integer linear programming, with the dead-end elimination technique, suffers even for moderate-sized proteins because the side-chain positioning problem is NP-hard. On the other hand, popular heuristic approaches focusing on speed produce solutions of low quality. This paper presents an efficient algorithm, called the BetaSCP, for the side-chain positioning problem based on the beta-complex which is a derivative geometric construct of the Voronoi diagram. Placing a higher priority on solution quality, the BetaSCP algorithm produces a solution very close to the optima within a reasonable computation time. The effectiveness and efficiency of the BetaSCP are experimentally shown via a benchmark test against well-known algorithms using twenty test models selected from Protein Data Bank.     

A robust support vector regression with a linear-log concave loss function

Support vector regression (SVR) is one of the most popular nonlinear regression techniques with the aim to approximate a nonlinear system with a good generalization capability. However, SVR has a major drawback in that it is sensitive to the presence of outliers. The ramp loss function for robust SVR has been introduced to resolve this problem, but SVR with ramp loss function has a non-differentiable and non-convex formulation, which is not easy to solve. Consequently, SVR with the ramp loss function requires smoothing and Concave-Convex Procedure techniques, which transform the non-differentiable and non-convex optimization to a differentiable and convex one. We present a robust SVR with linear-log concave loss function (RSLL), which does not require the transformation technique, where the linear-log concave loss function has a similar effect as the ramp loss function. The zero norm approximation and the difference of convex functions problem are employed for solving the optimization problem. The proposed RSLL approach is used to develop a robust and stable virtual metrology (VM) prediction model, which utilizes the status variables of process equipment to predict the process quality of wafer level in semiconductor manufacturing. We also compare the proposed approach to existing SVR-based methods in terms of the root mean squared error of prediction using both synthetic and real data sets. Our experimental results show that the proposed approach performs better than existing SVR-based methods regardless of the data set and type of outliers (ie, X-space and Y-space outliers), implying that it can be used as a useful alternative when the regression data contain outliers.     

Solution of Special Linear Programming Problems with Additional Constraints

This paper gives a method of solution for linear programming problems whose constraints can be split into two sets, the first having a special structure, such as that of the transportation problem for example, while the second set is quite general. A problem with only the first set of constraints is referred to as a favoured problem, while a problem with both sets is called a complete problem.The proposed method is basically the simplex procedure specialized for a problem with a particular structure, and the feasibility and optimality criteria and the rules for basis change are the same as those used in the simplex procedure. However, the method takes advantage of the simple algorithms developed for the favoured problem and uses them to solve the complete problem in an efficient manner.Such problems could also be solved by the Decomposition Principle and, vice versa, Decomposition problems can be solved by the present method. The two methods are, however, essentially different in their approach to the problem.