蛋白质构象空间局部增强差分进化搜索方法

针对蛋白质构象空间搜索问题,提出一种蛋白质构象空间局部增强差分进化搜索方法。在差分进化算法框架下,采用Rosetta Score3粗粒度知识能量模型有效降低构象空间的搜索维数,加快算法收敛速度;引入基于知识的片段组装技术可以有效提高预测精度;利用Monte Carlo算法良好的局部搜索性能对种群做局部增强,以得到更为优良的局部构象;结合差分进化算法较强的全局搜索能力,可以对构象空间进行更为有效的采样。5个测试蛋白实验结果表明,所提算法具有较好的搜索性能和预测精度。     

基于接触图残基对距离约束的蛋白质结构预测算法

从头预测是蛋白质结构建模的一种重要方法,该方法的研究有助于人类理解蛋白质功能,从而进行药物设计和疾病治疗。为了提高预测精度,文中提出了基于接触图残基对距离约束的蛋白质结构预测算法(CDPSP)。基于进化算法框架,CDPSP将构象空间采样分为探索和增强两个阶段。在探索阶段,设计基于残基对距离的变异与选择策略,即根据接触图的接触概率选择残基对,并通过片段组装技术对所选择的残基对的邻近区域进行变异;将残基对距离离散化为多个区域并为其分配期望概率,根据期望概率确定是否选择变异的构象,从而增加种群的多样性。在增强阶段,利用基于接触图信息的评分指标,结合能量函数,衡量构象的质量,从而选择较优的构象,达到增强CDPSP近天然态区域采样能力的效果。为了验证所提算法的性能,通过CASP12中的10个FM组目标蛋白质对其进行了测试,并将其与一些先进算法进行比较。实验结果表明,CDPSP可以预测得到精度较高的蛋白质三维结构模型。     

势能曲面变平法的改进及其在三维非格点模型中的应用

根据蛋白质的氨基酸序列预测其空间结构可以归纳为一个多极值的全局优化问题,缺少一种有效的全局寻优方法是阻碍这一难题解决的一个关键。势能曲面变平(ELP)法是一种启发式的全局优化算法,是一种推广的蒙特卡罗(MC)法,已被成功地应用于蛋白质结构预测问题。本文在ELP法的基础上,提出改进的势能曲面变平(ELP )算法。将ELP 算法应用于三维非格点的蛋白质AB模型,预测和发现蛋白质结构,数值实验表明ELP 算法是一种预测蛋白质结构的有效算法,计算结果优于ELP和MC算法。     

MOIRAE: A computational strategy to extract and represent structural information from experimental protein templates

The prediction and analysis of the three- dimensional (3D) structure of proteins is a key research problem in Structural Bioinformatics. The 1990’s Genome Projects resulted in a large increase in the number of available protein sequences. However, the number of identified 3D protein structures have not followed the same growth trend. Currently, the number of available protein sequences greatly exceeds the number of known 3D structures. Many computational methodologies, systems and algorithms have been proposed to address the protein structure prediction problem. However, the problem still remains challenging because of the complexity and high dimensionality of a protein conformational search space. The most significant progress in the last Critical Assessment of protein Structure Prediction was achieved by methods that use database information. Nevertheless, a major challenge remains in the development of better strategies for template identification and representation. This article describes a computational strategy to acquire and represent structural information of experimentally determined 3D protein structures. A clustering strategy was combined with artificial neural networks in order to extract structural information from experimental protein structure templates. In the proposed strategy, the main efforts focus on the acquisition of useful and accurate structural information from 3D protein templates stored in the Protein Data Bank (PDB). The proposed method was tested in twenty protein sequences whose sizes vary from 14 to 70 amino acid residues. Our results show that the proposed method is a good way to extract and represent valuable information obtained from the PDB and also significantly reduce the 3D protein conformational search space.     

结合蛋白质二级结构信息预测蛋白质空间结构中的二硫键*

在蛋白质空间结构预测中,二硫键的确定可以大大减少蛋白质构象的搜索空间。为提高二硫键预测的准确率,对形成二硫键的半胱氨酸及其周围的氨基酸残基在蛋白质二级结构形成上的偏性进行了分析,并提出将蛋白质二级结构信息加入到BP神经网络预测模型的输入编码信息中。研究对象为从SWISS-PROT数据库中选取的252条蛋白质序列,随机均分4组,对预测准确率进行4-交叉验证。各项准确率均比未加入蛋白质二级结构信息前,有明显提高。结果表明,结合蛋白质二级结构信息的编码方式是可行且有效的。     

Enhanced Van der Waals calculations in genetic algorithms for protein structure prediction

Several ab initio computational methods for protein structure prediction have been designed using full‐atom models and force field potentials to describe interactions among atoms. Those methods involve the solution of a combinatorial problem with a huge search space. Genetic algorithms (GAs) have shown significant performance increases for such methods. However, even a small protein may require hundreds of thousands of energy function evaluations making GAs suitable only for the prediction of very small proteins. We propose an efficient technique to compute the van der Waals energy (the greatest contributor to protein stability) speeding up the whole GA. First, we developed a Cell‐List Reconstruction procedure that divides the tridimensional space into a cell grid for each new structure that the GA generates. The cells restrict the calculations of van der Waals potentials to ranges in which they are significant, reducing the complexity of such calculations from quadratic to linear. Moreover, the proposal also uses the structure of the cell grid to parallelize the computation of the van der Waals energy, achieving additional speedup. The results have shown a significant reduction in the run time required by a GA. For example, the run time for the prediction of a protein with 147,980 atoms can be reduced from 217 days to 7 h. Copyright © 2012 John Wiley & Sons, Ltd.     

A multiple minima genetic algorithm for protein structure prediction

Protein structure prediction (PSP) has a large potential for valuable biotechnological applications. However the prediction itself encompasses a difficult optimization problem with thousands of degrees of freedom and is associated with extremely complex energy landscapes. In this work a simplified three-dimensional protein model (hydrophobic-polar model, HP in a cubic lattice) was used in order to allow for the fast development of a robust and efficient genetic algorithm based methodology. The new methodology employs a phenotype based crowding mechanism for the maintenance of useful diversity within the populations, which resulted in increased performance and granted the algorithm multiple solutions capabilities. Tests against several benchmark HP sequences and comparative results showed that the proposed genetic algorithm is superior to other evolutionary algorithms. The proposed algorithm was then successfully adapted to an all-atom protein model and tested on poly-alanines. The native structure, an alpha helix, was found in all test cases as a local or a global minimum, in addition to other conformations with similar energies. The results showed that optimization strategies with multiple solutions capability present two advantages for PSP applications. The first one is a more efficient investigation of complex energy landscapes; the second one is an increase in the probability of finding native structures, even when they are not at the global optimum.     

改进平衡优化器算法的WSN覆盖优化

针对无线传感器网络在节点部署过程中存在节点覆盖空白及重叠覆盖的问题,提出一种改进平衡优化器算法（IEO）的网络覆盖优化。首先,利用环绕反向学习提高初始化种群质量,增强算法的优化能力;其次,引入动态正余弦因子进一步平衡全局搜索与局部开发能力,促使粒子种群对搜索空间中进行广泛搜索和深度挖掘;最后,通过在浓度更新阶段加入Circle混沌映射增加种群多样性,提高算法逃离局部最优的能力。实验结果表明,将IEO算法应用于WSN的覆盖优化实验中,与标准平衡优化器算法及其他改进算法相比,有效降低部署成本,表现出更高的网络覆盖率,改善网络的监测质量。     

基于图的匹配方法预测蛋白质结构中的二硫键

摘要：在蛋白质结构预测的研究中,一个重要的问题就是正确预测二硫键的连接,二硫键的准确预测可以减少蛋白质构像的搜索空间,有利于蛋白质的3D结构的预测。本文将一个蛋白质结构中二硫键的预测问题,等价为一个寻找图的最大权的匹配问题。图的顶点表示序列中的半胱氨酸残基,边连接每一顶点,表示一种可能的连接方式,边的权根据一个权值函数赋值,用EJ算法寻找具有最大权的匹配,则这个匹配对应二硫键的正确连接。应用这个方法对蛋白质结构的二硫键进行了预测取得了良好的结果。     

基于并行群体模拟退火算法的蛋白质折叠研究

蛋白质折叠研究对于揭示蛋白结构和功能关系,进而了解相关疾病的致病机理意义重大。蛋白质折叠已被证明是 NP-完全问题。本文针对蛋白质折叠研究中的能量最小化问题,提出了一种新的并行群体模拟退火算法（Parallel Group Simulated Annealing,PGSA）及其改进型算法（PGSA_1/K)。该算法使用了降温因子加速收敛精度,并采用 MPI 消息传递并行编程技术加快蛋白质结构空间搜索以及能量最小化寻找速度。以 Met_Enkephalin 蛋白为对象的计算机模拟仿真结果表明,我们提出的算法及其改进型有很好的扩展性,可以高效搜索蛋白结构空间,从而找到相关蛋白的最小能量结构。     

一种禁忌搜索算法在二维HP非格模型中的应用

禁忌搜索算法是一种启发式的全局优化算法,是局部搜索算法的一种推广,已被成功地应用于许多组合优化问题,本文探讨将一种记忆的禁忌搜索算法应用于求解蛋白质结构预测问题。文中首先介绍了一种二维HP非格模型,此模型最后可以归结为一个全局优化问题,然后介绍了记忆的禁忌搜索算法在其中的应用,通过与PERM（Pruned—Enriched—Rosenbluth Method）比较,发现禁忌算法能得到较好的实验结果,经分析发现虽然二维HP非格模型很简单,但却能反映蛋白质结构的一些简单的性质,即在蛋白质结构中,疏水性氨基酸形成束,总是被极性氨基酸包围。数值实验表明该算法对于蛋白质结构预测是可行有效的。     

A global optimization strategy for predicting alpha-helical protein tertiary structure

We present a global optimization strategy that incorporates predicted restraints in both a local optimization context and as directives for global optimization approaches, to predict protein tertiary structure for alpha-helical proteins. Specifically, neural networks are used to predict the secondary structure of a protein, restraints are defined as manifestations of the network with a predicted secondary structure and the secondary structure is formed using local minimizations on a protein energy surface, in the presence of the restraints. Those residues predicted to be coil, by the network, define a conformational sub-space that is subject to optimization using a global approach known as stochastic perturbation that has been found to be effective for Lennard-Jones clusters and homo-polypeptides. Our energy surface is an all-atom 'gas phase' molecular mechanics force field, that is combined with a new solvation energy function that penalizes hydrophobic group exposure. This energy function gives the crystal structure of four different alpha-helical proteins as the lowest energy structure relative to other conformations, with correct secondary structure but incorrect tertiary structure. We demonstrate this global optimization strategy by determining the tertiary structure of the A-chain of the alpha-helical protein, uteroglobin and of a four-helix bundle, DNA binding protein.     

A hybrid variable neighborhood search for solving the hybrid flow shop scheduling problem

This paper proposes a hybrid variable neighborhood search (HVNS) algorithm that combines the chemical-reaction optimization (CRO) and the estimation of distribution (EDA), for solving the hybrid flow shop (HFS) scheduling problems. The objective is to minimize the maximum completion time. In the proposed algorithm, a well-designed decoding mechanism is presented to schedule jobs with more flexibility. Meanwhile, considering the problem structure, eight neighborhood structures are developed. A kinetic energy sensitive neighborhood change approach is proposed to extract global information and avoid being stuck at the local optima. In addition, contrary to the fixed neighborhood set in traditional VNS, a dynamic neighborhood set update mechanism is utilized to exploit the potential search space. Finally, for the population of local optima solutions, an effective EDA-based global search approach is investigated to direct the search process to promising regions. The proposed algorithm is tested on sets of well-known benchmark instances. Through the analysis of experimental results, the high performance of the proposed HVNS algorithm is shown in comparison with four efficient algorithms from the literature.     

A new class of hybrid global optimization algorithms for peptide structure prediction: integrated hybrids

A novel class of hybrid global optimization methods for application to the structure prediction in protein-folding problem is introduced. These optimization methods take the form of a hybrid between a deterministic global optimization algorithm, the αBB, and a stochastically based method, conformational space annealing (CSA), and attempt to combine the beneficial features of these two algorithms. The αBB method as previously extant exhibits consistency, as it guarantees convergence to the global minimum for twice-continuously differentiable constrained nonlinear programming problems, but can benefit from improvements in the computational front. Computational studies for met-enkephalin demonstrate the promise for the proposed hybrid global optimization method.     

ESSAWOA: Enhanced Whale Optimization Algorithm integrated with Salp Swarm Algorithm for global optimization

In this paper, a novel hybrid meta-heuristic algorithm called ESSAWOA is proposed for solving global optimization problems. The main idea of ESSAWOA is to enhance Whale Optimization Algorithm (WOA) by combining the mechanism of Salp Swarm Algorithm (SSA) and Lens Opposition-based Learning strategy (LOBL). The hybridization process includes three parts: First, the leader mechanism with strong exploitation of SSA is applied to update the population position before the basic WOA operation. Second, the nonlinear parameter related to the convergence property in SSA is introduced to the two phases of encircling prey and bubble-net attacking in WOA. Third, LOBL strategy is used to increase the population diversity of the proposed optimizer. The hybrid design is expected to significantly enhance the exploitation and exploration capacity of the proposed algorithm. To investigate the effectiveness of ESSAWOA, twenty-three benchmark functions of different dimensions and three classical engineering design problems are performed. Furthermore, SSA, WOA and seven other well-known meta-heuristic algorithms are employed to compare with the proposed optimizer. Our results reveal that ESSAWOA can effectively and quickly obtain the promising solution of these optimization problems in the search space. The performance of ESSAWOA is significantly superior to the basic WOA, SSA and other meta-heuristic algorithms.

     

A GMDH polynomial neural network-based method to predict approximate three-dimensional structures of polypeptides

Tertiary Protein Structure Prediction is one of the most important problems in Structural Bioinformatics. Along the last 20 years many algorithms have been proposed as to solve this problem. However, it still remains a challenging issue because of the complexity and of the dimensionality of the protein conformational search space. In this article a first principle method which uses database information for the prediction of the 3-D structure of polypeptides is presented. The technique is based on the Group Method of Data Handling (GMDH) algorithm, implemented by a software tool introduced on this work. GMDH Polynomial Neural Networks have been used with success in many fields such as data mining, knowledge discovery, pattern recognition and prediction. The proposed method was tested with seven protein sequences whose sizes vary from 14 to 54 amino acid residues. Results show that the predicted tertiary structures adopt a fold similar to the experimental structures. RMSD and secondary structure analysis reveal that the proposed method present accurate results in their predictions. The predicted structures can be used as input structures in refinement methods based on molecular mechanics (MM), e.g. molecular dynamics (MD) simulations. The search space is expected to be greatly reduced and the ab initio methods can demand a much reduced computational time to achieve a more accurate polypeptide structure.     

Attributed multi-objective comprehensive learning particle swarm optimization for optimal security of networks

In particle swarm optimization (PSO) each particle uses its personal and global or local best positions by linear summation. However, it is very time consuming to find the global or local best positions in case of complex problems. To overcome this problem, we propose a new multi-objective variant of PSO called attributed multi-objective comprehensive learning particle swarm optimizer (A-MOCLPSO). In this technique, we do not use global or local best positions to modify the velocity of a particle; instead, we use the best position of a randomly selected particle from the whole population to update the velocity of each dimension. This method not only increases the speed of the algorithm but also searches in more promising areas of the search space. We perform an extensive experimentation on well-known benchmark problems such as Schaffer (SCH), Kursawa (KUR), and Zitzler–Deb–Thiele (ZDT) functions. The experiments show very convincing results when the proposed technique is compared with existing versions of PSO known as multi-objective comprehensive learning particle swarm optimizer (MOCLPSO) and multi-objective particle swarm optimization (MOPSO), as well as non-dominated sorting genetic algorithm II (NSGA-II). As a case study, we apply our proposed A-MOCLPSO algorithm on an attack tree model for the security hardening problem of a networked system in order to optimize the total security cost and the residual damage, and provide diverse solutions for the problem. The results of our experiments show that the proposed algorithm outperforms the previous solutions obtained for the security hardening problem using NSGA-II, as well as MOCLPSO for the same problem. Hence, the proposed algorithm can be considered as a strong alternative to solve multi-objective optimization problems.     

一种蛋白质点突变计算机预测的并行模型

认识和预测蛋白质天然构象的波动对蛋白质-蛋白质对接和设计等应用是非常重要的.但是许多骨架柔性的方法会导致骨架较大幅度的波动.Backrub模型能够对骨架进行微小的扰动,符合高分辨率晶体结构中观察到的构象的微妙变化.本文提出了一种基于Backrub的并行扰动骨架和侧链的模型,可以对天然构象的等价状态进行模拟.这种并行扰动方式更加接近于真实情况下蛋白质构象的运动方式,更好地模拟了实验数据.通过预测10个点突变实例,相比串行随机扰动模型产生的构象,并行模型不仅从时间上提高了产生构象的速度,更提高了侧链的预测精度.     

一种基于片段组装的蛋白质构象空间优化算法

针对蛋白质构象空间优化问题,提出一种基于片段组装的构象空间优化算法。算法利用基于Rosetta粗粒度的知识能量模型有效地提高了收敛速度;同时,借助片段组装技术可以有效弥补因能量函数不精确而导致的预测精度不足的缺陷;此外,差分进化算法的引入使得算法具有较好的全局搜索能力。5种测试蛋白的实验结果表明,所提算法具有较好的搜索性能和预测精度。     

Protein Folding in Simplified Models With Estimation of Distribution Algorithms

Simplified lattice models have played an important role in protein structure prediction and protein folding problems. These models can be useful for an initial approximation of the protein structure, and for the investigation of the dynamics that govern the protein folding process. Estimation of distribution algorithms (EDAs) are efficient evolutionary algorithms that can learn and exploit the search space regularities in the form of probabilistic dependencies. This paper introduces the application of different variants of EDAs to the solution of the protein structure prediction problem in simplified models, and proposes their use as a simulation tool for the analysis of the protein folding process. We develop new ideas for the application of EDAs to the bidimensional and tridimensional (2-d and 3-d) simplified protein folding problems. This paper analyzes the rationale behind the application of EDAs to these problems, and elucidates the relationship between our proposal and other population-based approaches proposed for the protein folding problem. We argue that EDAs are an efficient alternative for many instances of the protein structure prediction problem and are indeed appropriate for a theoretical analysis of search procedures in lattice models. All the algorithms introduced are tested on a set of difficult 2-d and 3-d instances from lattice models. Some of the results obtained with EDAs are superior to the ones obtained with other well-known population-based optimization algorithms.