基于新杂合进化算法的蛋白质折叠计算

蛋白质能量最小化是蛋白质折叠的重要内容。用于蛋白质折叠的新的杂合进化算法结合了交叉和柯西变异。基于toy模型的蛋白质能量最小化算例表明,这个新的杂合进化算法是有效的。     

A new computational approach for real protein folding prediction

An effective and fast minimization approach is proposed for the prediction of protein folding, in which the 'relative entropy' is used as a minimization function and the off-lattice model is used. In this approach, we only use the information of distances between the consecutive Calpha atoms along the peptide chain and a generalized form of the contact potential for 20 types of amino acids. Tests of the algorithm are performed on the real proteins. The root mean square deviations of the structures of eight folded target proteins versus the native structures are in a reasonable range. In principle, this method is an improvement on the energy minimization approach.     

The train fueling cost minimization problem with fuzzy fuel prices

The train fueling cost minimization problem is to find a scheduling and fueling strategy such that the fueling cost is minimized and no train runs out of fuel. Since fuel prices vary by location and time from month to month, we estimate them by fuzzy variables in this paper. Furthermore, we propose a fuzzy fueling cost minimization model by minimizing the expected fueling cost under the traversing time constraint, maximal allowable speed constraint, tank capacity constraint, and so on. In order to solve the model, we decompose it into a nonlinear scheduling strategy model and a linear fueling strategy model. Based on the Karush–Kuhn–Tucker conditions, we design an iterative algorithm to solve the scheduling strategy model, and furthermore design a numerical algorithm to solve the fuzzy fueling cost minimization model. Finally, some numerical examples are presented for showing the efficiency of the proposed approach on saving fueling cost.     

Numerical Solution to Generalized Burgers'-Fisher Equation Using Exp-Function Method Hybridized with Heuristic Computation

In this paper, a new heuristic scheme for the approximate solution of the generalized Burgers''-Fisher equation is proposed. The scheme is based on the hybridization of Exp-function method with nature inspired algorithm. The given nonlinear partial differential equation (NPDE) through substitution is converted into a nonlinear ordinary differential equation (NODE). The travelling wave solution is approximated by the Exp-function method with unknown parameters. The unknown parameters are estimated by transforming the NODE into an equivalent global error minimization problem by using a fitness function. The popular genetic algorithm (GA) is used to solve the minimization problem, and to achieve the unknown parameters. The proposed scheme is successfully implemented to solve the generalized Burgers''-Fisher equation. The comparison of numerical results with the exact solutions, and the solutions obtained using some traditional methods, including adomian decomposition method (ADM), homotopy perturbation method (HPM), and optimal homotopy asymptotic method (OHAM), show that the suggested scheme is fairly accurate and viable for solving such problems.     

VNF-EQ: dynamic placement of virtual network functions for energy efficiency and QoS guarantee in NFV

With the advances of network function virtualization and cloud computing technologies, a number of network services are implemented across data centers by creating a service chain using different virtual network functions (VNFs) running on virtual machines. Due to the complexity of network infrastructure, creating a service chain requires high operational cost especially in carrier-grade network service providers and supporting stringent QoS requirements from users is also a complicated task. There have been various research efforts to address these problems that only focus on one aspect of optimization goal either from users such as latency minimization and QoS based optimization, or from service providers such as resource optimization and cost minimization. However, meeting the requirements both from users and service providers efficiently is still a challenging issue. This paper proposes a VNF placement algorithm called VNF-EQ that allows users to meet their service latency requirements, while minimizing the energy consumption at the same time. The proposed algorithm is dynamic in a sense that the locations or the service chains of VNFs are reconfigured to minimize the energy consumption when the traffic passing through the chain falls below a pre-defined threshold. We use genetic algorithm to formulate this problem because it is a variation of the multi-constrained path selection problem known as NP-complete. The benchmarking results show that the proposed approach outperforms other heuristic algorithms by as much as 49% and reduces the energy consumptions by rearranging VNFs.     

A class of edit kernels for SVMs to predict translation initiation sites in eukaryotic mRNAs.

The prediction of translation initiation sites (TISs) in eukaryotic mRNAs has been a challenging problem in computational molecular biology. In this paper, we present a new algorithm to recognize TISs with a very high accuracy. Our algorithm includes two novel ideas. First, we introduce a class of new sequence-similarity kernels based on string editing, called edit kernels, for use with support vector machines (SVMs) in a discriminative approach to predict TISs. The edit kernels are simple and have significant biological and probabilistic interpretations. Although the edit kernels are not positive definite, it is easy to make the kernel matrix positive definite by adjusting the parameters. Second, we convert the region of an input mRNA sequence downstream to a putative TIS into an amino acid sequence before applying SVMs to avoid the high redundancy in the genetic code. The algorithm has been implemented and tested on previously published data. Our experimental results on real mRNA data show that both ideas improve the prediction accuracy greatly and that our method performs significantly better than those based on neural networks and SVMs with polynomial kernels or Salzberg kernels.     

A method of minimization of ECG artifacts in digital EEG

An off-line algorithm of automatic detection and minimization of ECG artifacts in digital EEG without using the ECG channel is proposed. A possibility of application of this technique for processing another high-frequency artifacts and different waveforms in biosignals is discussed.     

基于动态规划的快速序列比对算法

序列比对算法是生物信息学中重要的研究方向之一,而动态规划法是序列比对算法中最有效最基本的方法．由于原有的基本动态规划方法时间和空间复杂度大,不适合实际的生物序列比对,因此本文在分析介绍几种相关动态规划算法的基础上,提出了一种基于动态规划的快速序列比对算法UKK_FA．实验结果表明,该算法有效地降低了时间复杂度,具有一定的实用性。     

Optimality in forward dynamics simulations

This paper discusses a methodology and an algorithm for the analysis of dynamics of bio-mechanical systems, and in particular of optimal movement patterns between initial and target configurations. The basic formulation utilizes a finite element time discretization and establishes a large set of equations in displacements and forces. These are solved simultaneously for the whole time interval considered. The algorithm allows different optimization criteria for the movement, based on either the smoothness of the movement or the minimization of needed controls or control rates. It is primarily aimed at musculoskeletal simulations with either the joint resultant moments or the redundant muscular tensions as unknowns. Kinetic and kinematic constraints can be introduced for the obtained movement. Examples show that the obtained results are strongly dependent on the optimality criterion used. Systematic usage of the algorithm can improve knowledge about optimal motion planning.     

Efficient Deterministic Finite Automata Minimization Based on Backward Depth Information

Obtaining a minimal automaton is a fundamental issue in the theory and practical implementation of deterministic finite automatons (DFAs). A minimization algorithm is presented in this paper that consists of two main phases. In the first phase, the backward depth information is built, and the state set of the DFA is partitioned into many blocks. In the second phase, the state set is refined using a hash table. The minimization algorithm has a lower time complexity O(n) than a naive comparison of transitions O(n²). Few states need to be refined by the hash table, because most states have been partitioned by the backward depth information in the coarse partition. This method achieves greater generality than previous methods because building the backward depth information is independent of the topological complexity of the DFA. The proposed algorithm can be applied not only to the minimization of acyclic automata or simple cyclic automata, but also to automata with high topological complexity. Overall, the proposal has three advantages: lower time complexity, greater generality, and scalability. A comparison to Hopcroft’s algorithm demonstrates experimentally that the algorithm runs faster than traditional algorithms.     

Clustering analysis of Enkephalin conformations

A combination of a Monte-Carlo sampling, a clustering method, and a minimization algorithm is proposed for the calculation of conformational properties of molecules in solutions. This approach is applied to the determination of stable conformations of the peptide hormone Enkephalin in solution and it gives good agreement with experimental data.     

An Improved Method with High Anti-interference Ability for R Peak Detection in Wearable Devices

The rapid development of the wearable electrocardiogram monitoring equipment increases the requirements for R peak detection in wearable devices. An improved method called ISC algorithm is proposed with high anti-interference ability for R peak detection in wearable devices based on a simple basic algorithm called SC algorithm. The proposed method is characterized by using the updated amplitude selection threshold, updated slope comparison threshold and RR interval judgement to reduce false positives and false negatives. For data from MIT-BIH Arrhythmia Database, the positive predictivity P+ of ISC algorithm can reach 99.12%, and the sensitivity Se of ISC algorithm is more than 95%. For MIT-BIH Noise Stress Test Database, the accuracy of ISC algorithm for both sensitivity Se and positive predictivity P+ can exceed 94% under three common noise, baseline wander, muscle artifact, and electrode motion artifact, where the positive predictivity P+ of ISC algorithm is 44.46% higher than that of SC algorithm on average. For wearable devices in exercise, even under the exercise intensity of 7 km per hour, the average positive predictivity P+ of ISC algorithm is 99.32%, which is 60.93% higher than that of SC algorithm. The high anti-interference ability shows that ISC algorithm is suitable for R peak detection in wearable devices.     

A Multi-objective variable neighborhood search for the maximal covering location problem with customer preferences

This paper considers a variant of maximal covering location problem with customer preferences and two objectives involved: maximization of the weighted sum of the covered demand and minimization of the number of uncovered customers. The problem has important applications in service network design, such as telecommunication and computer networks, service placement problem, etc. This paper proposes a multi-objective variable neighborhood search (MO-VNS) as a metaheuristic approach for the considered problem. Following the concepts of basic, reduced, and general VNS in single-objective optimization, three MO-VNS variants are proposed: MO-BVNS, MO-RVNS, and MO-GVNS. The proposed MO-VNS implementations were compared with each other and with the existing multi-objective evolutionary algorithms (MOEAs). The MO-VNS concept showed to be superior over MOEA, as all MO-VNS variants outperform MOEAs in the sense of solution quality, especially on the largest size test instances.

     

A Positive Detecting Code and Its Decoding Algorithm for DNA Library Screening

The study of gene functions requires high-quality DNA libraries. However, a large number of tests and screenings are necessary for compiling such libraries. We describe an algorithm for extracting as much information as possible from pooling experiments for library screening. Collections of clones are called pools, and a pooling experiment is a group test for detecting all positive clones. The probability of positiveness for each clone is estimated according to the outcomes of the pooling experiments. Clones with high chance of positiveness are subjected to confirmatory testing. In this paper, we introduce a new positive clone detecting algorithm, called the Bayesian network pool result decoder (BNPD). The performance of BNPD is compared, by simulation, with that of the Markov chain pool result decoder (MCPD) proposed by Knill et al. in 1996. Moreover, the combinatorial properties of pooling designs suitable for the proposed algorithm are discussed in conjunction with combinatorial designs and dhbox{-}{rm disjunct} matrices. We also show the advantage of utilizing packing designs or BIB designs for the BNPD algorithm.     

Determining minimum energy conformations of polypeptides by dynamic programming

A combinatorial optimization approach is used for solving the multiple-minima problem when determining the low-energy conformations of short polypeptides. Each residue is represented by a finite number of discrete states corresponding to single residue local minima of the energy function. These precomputed values constitute a search table and define the conformational space for discrete minimization by a generalized dynamic programming algorithm that significantly limits the number of intermediate conformations to be generated during the search. Since dynamic programming involves stagewise decisions, it results in buildup-type procedures implemented in two different forms. The first procedure predicts a number of conformations by a completely discrete search and these are subsequently refined by local minimization. The second involves limited continuous local minimization within the combinatorial algorithm, generally restricted to two dihedral angles in a buildup step. Both procedures are tested on 17 short peptides previously studied by other global minimization methods but involving the same potential energy function. The discrete method is extremely fast, but proves to be successful only in 14 of the 17 test problems. The version with limited local minimization finds, however, conformations in all the 17 examples that are close to the ones previously presented in the literature or have lower energies. In addition, results are almost independent of the cutoff energy, the most important parameter governing the search. Although the limited local minimization increases the number of energy evaluations, the method still offers substantial advantages in speed.     

Constrained Total Generalized p-Variation Minimization for Few-View X-Ray Computed Tomography Image Reconstruction

Total generalized variation (TGV)-based computed tomography (CT) image reconstruction, which utilizes high-order image derivatives, is superior to total variation-based methods in terms of the preservation of edge information and the suppression of unfavorable staircase effects. However, conventional TGV regularization employs l₁-based form, which is not the most direct method for maximizing sparsity prior. In this study, we propose a total generalized p-variation (TGpV) regularization model to improve the sparsity exploitation of TGV and offer efficient solutions to few-view CT image reconstruction problems. To solve the nonconvex optimization problem of the TGpV minimization model, we then present an efficient iterative algorithm based on the alternating minimization of augmented Lagrangian function. All of the resulting subproblems decoupled by variable splitting admit explicit solutions by applying alternating minimization method and generalized p-shrinkage mapping. In addition, approximate solutions that can be easily performed and quickly calculated through fast Fourier transform are derived using the proximal point method to reduce the cost of inner subproblems. The accuracy and efficiency of the simulated and real data are qualitatively and quantitatively evaluated to validate the efficiency and feasibility of the proposed method. Overall, the proposed method exhibits reasonable performance and outperforms the original TGV-based method when applied to few-view problems.     

Distributed graph coloring: an approach based on the calling behavior of Japanese tree frogs

Graph coloring—also known as vertex coloring—considers the problem of assigning colors to the nodes of a graph such that adjacent nodes do not share the same color. The optimization version of the problem concerns the minimization of the number of colors used. In this paper we deal with the problem of finding valid graphs colorings in a distributed way, that is, by means of an algorithm that only uses local information for deciding the color of the nodes. The algorithm proposed in this paper is inspired by the calling behavior of Japanese tree frogs. Male frogs use their calls to attract females. Interestingly, groups of males that are located near each other desynchronize their calls. This is because female frogs are only able to correctly localize male frogs when their calls are not too close in time. The proposed algorithm makes use of this desynchronization behavior for the assignment of different colors to neighboring nodes. We experimentally show that our algorithm is very competitive with the current state of the art, using different sets of problem instances and comparing to one of the most competitive algorithms from the literature.     

Molecular Modeling of Proteins: A Strategy for Energy Minimization by Molecular Mechanics in the AMBER Force Field

Abstract

Energy minimization is an important step in molecular modeling of proteins. In this study, we sought to develop a minimization strategy which would give the best final structures with the shortest computer time in the AMBER force field. In the all-atom model, we performed energy minimization of the melittin (mostly α-helical) and cardiotoxin (mostly β-sheet and β-turns) crystal structures by both constrained and unconstrained pathways. In the constrained path, which has been recommended in the energy minimization of proteins, hydrogens were relaxed first, followed by the side chains of amino acid residues, and finally the whole molecule. Despite the logic of this approach, however, the structures minimized by the unconstrained path fit the experimental structures better than those minimized by constrained paths. Moreover, the unconstrained path saved considerable computer time. We also compared the effects of the steepest descents and conjugate gradients algorithms in energy minimization. Previously, steepest descents has been used in the initial stages of minimization and conjugate gradients in the final stages of minimization. We therefore studied the effect on the final structure of performing an initial minimization by steepest descents. The structures minimized by conjugate gradients alone resembled the structures minimized initially by the steepest descents and subsequently by the conjugate gradients algorithms. Thus an initial minimization using steepest descents is wasteful and unnecessary, especially when starting from the crystal structure. Based on these results, we propose the use of an unconstrained path and conjugate gradients for energy minimization of proteins. This procedure results in low energy structures closer to the experimental structures, and saves about 70–80% of computer time. This procedure was applied in building models of lysozyme mutants. The crystal structure of native T₄ lysozyme was mutated to three different mutants and the structures were minimized. The minimized structures closely fit the crystal structures of the respective mutants (< 0.3 Å root-mean-square, RMS, deviation in the position of all heavy atoms). These results confirm the efficiency of the proposed minimization strategy in modeling closely related homologs. To determine the reliability of the united atom approximation, we also performed all of the above minimizations with united atom models. This approximation gave structures with similar but slightly higher RMS deviations than the all-atom model, but gave further savings of60-70% in computer time. However, we feel further investigation is essential to determine the reliability of this approximation. Finally, to determine the limitation of the procedure, we built the melittin molecule interactively in an α-helical conformation and this model showed an RMS deviation greater than 2.8 Å when compared to the melittin crystal structure. This model was minimized by various strategies. None of the minimized structures converged towards the crystal structure. Thus, although the proposed method seems to give valid structures starting from closely related crystal structures, it cannot predict the native structure when the starting structure is far from the native structure. From these results, we recommend the use of the proposed strategy of minimizing by an unconstrained path using the conjugate gradients algorithm, but only for modeling of closely related structural homologs of proteins.     

A parallel optimization approach for controlling allele diversity in conservation schemes

We propose a novel method to control allelic diversity in conservation schemes based on an optimization problem, characterized by a convex program subject to integer linear constraints. Departing from previous studies considering similar problems, we implement a parallel simulated annealing algorithm to minimize the number of alleles lost across generations. The proposed algorithm shows excellent timing and minimization performances. Execution time decreases linearly with the number of processors used, providing similar results in all cases.