基于混合遗传算法的蛋白质结构预测研究

将遗传算法与模拟退火算法相结合,提出一种新的混合遗传算法,并采用该算法对蛋白质的折叠过程进行研究.实验结果表明,采用该算法比单纯采用遗传算法或者采用模拟退火算法速度更快,计算结果更精确,是一种行之有效的新方法.     

蛋白质在格子模型中改进的PERM算法

PERM算法是当前蛋白质结构预测的格子模型优化算法中最为有效的一种算法,在该算法的基础上,我们提出了一种改进的增长算法IPERM。该方法简化了PERM算法中的权重计算公式,在遇到不同类型的残基时选用不同的上下限阂值以提高算法的有效性,并根据链长的大小使用不同的网格尺寸。实验结果表明,改进的增长算法使得HP序列在格子模型中能更快地找到其能量最低构象。     

改进的牵引移动的蚁群算法在2D HP模型中的应用

蛋白质折叠问题就是从氨基酸序列中预测蛋白质的构象,该问题是生物信息学的一个突出问题。主要研究二维HP格点模型,它是用于模拟蛋白质折叠问题的一个具有代表性的简化模型,并且将蚁群算法用于求解该二维HP蛋白质的折叠问题。此外,在局部搜索机制中引入一种改进的牵引移动方法,这是一个提高蛋白质构象的有效方法。实验结果表明,针对较长的氨基酸序列,改进的带牵引移动的蚁群算法(ACO+)比ACO能够获得更低能量的构象,证明了所提出的改进蚁群算法是预测蛋白质结构的有效方法。     

求解蛋白质折叠构形预测问题的PERM改进算法

PERM算法用来求解蛋白质折叠构形预测问题具有非常高的效率。本文介绍了PERM算法的思想，并详细介绍了一种我们改进的PERM算法。使用该算法求解蛋白质折叠构形预测的二维HP格点模型取得了相当好的计算结果。     

一种改进人口迁移算法在蛋白质折叠模拟中的应用

PMA（Population Migration Algorithm）算法已在蛋白质非晶格模型中做了模拟测试,结果表明具有较强的全局搜索能力和稳定性。针对PMA算法的思想,提出了对算法的一种改进。使用该改进算法求解蛋白质折叠构形预测的二维非晶格模型取得了较好的计算结果。     

基于Toy模型蛋白质折叠预测的多种群微粒群优化算法研究

基于Toy模型的蛋白质折叠结构预测问题是一个典型的NP问题.提出了多种群微粒群优化算法用于计算蛋白质能量最小值.该算法采用了一种新的算法结构,在该结构中,每一代的种群被分为精英子种群、开采子种群和勘探子种群三部分,通过改善种群的局部开采能力和全局勘探能力来提高算法的性能.分别采用Fibonacci蛋白质测试序列和真实蛋白质序列进行了折叠结构预测的仿真实验.实验结果表明该算法能够更精确地进行蛋白质折叠结构预测,为生物科学研究提供了一条有效途径.     

基于Spark的并行遗传算法在旅行商问题中的应用

传统遗传算法存在早熟现象,而且其在海量数据模型下的求解精度和可扩展性也有待提高。为了改进上述问题,在研究孤岛模型和细粒度模型优势基础上,利用遗传算法自身的并行性,提出一种仿细粒度的粗粒度并行模型,基于spark实现了一种双层并行的遗传算法。将改进算法应用于旅行商问题Berlin52数据集的求解,实验结果表明,与传统的并行模型相比,改进后的算法可以明显缩短计算时间,增大搜索范围,早熟现象也得到了改善。     

进化策略的一种改进及其在蛋白质结构预测中的应用

进化策略算法是一种模拟自然界生物进化过程的全局优化方法。本文将一种改进的进化策略算法应用于蛋白质三维HPNX非格模型,较成功地预测了蛋白质序列1RPB、1BPI和1UBQ的折叠趋势,说明了三维HPNX非格模型比简化HP非格模型更能准确地描述蛋白质的折叠情况,同时表明了进化策略算法用于蛋白质结构预测问题是可行的、有效的。     

改进二进制量子粒子群算法在蛋白质折叠中的应用*

为了改善已有二维HP模型蛋白质折叠算法容易陷入局部最优、找不到理论最低能量构象的缺点,提出一种基于变异算子的改进二进制量子粒子群算法。采用二进制编码蛋白质序列,提出变异策略,并采用惩罚因子避免出现蛋白质重叠,最后将该算法应用于蛋白质序列进行测试。测试结果表明,改进算法能够找到更优的结果,算法具有一定的实用性和有效性。     

基于改进的禁忌搜索的蛋白质三维结构预测

禁忌搜索算法是一种局部搜索能力很强的全局迭代优化算法,已经被成功地应用到各种组合优化问题中。基于AB非格模型,该文将一种改进的禁忌搜索算法应用于蛋自质三维折叠结构预测。实验结果表明改进的禁忌算法求得的蛋白质三维最低能量构形的最低能量值比已有的算法求得的最低能量值要低,同时三维构形中形成了一个疏水核,被亲水残基包围,反映了真实蛋白质的结构特征。该算法效率高,可以有效地用于蛋白质三维折叠预测。     

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.     

蛋白质HP模型的改进和PERM算法求解

HP模型是一种被广泛研究的简化的蛋白质折叠模型.在蛋白质螺旋结构的预测上有很高的可信度.但是HP的正方格点模型存在能量计算缺陷,影响其对链上特定结构的计算.针对这一缺陷,给出一种模型上的修正,引入了三角化的格点模型.利用求解格点蛋白质模型高效的算法PERM对通用算例进行了基于2-D三角格点模型的仿真计算.得到了紧密的蛋白质链折叠构型.构型最小能量比正方格点模型更低,得到的标准算例构型比较吻合实际蛋白质折叠的直观构型.计算结果验证了改进模型的有效性.对后续的研究提出了建议.     

On the Intractability of Protein Folding with a Finite Alphabet of Amino Acids

We describe a proof of NP-hardness for a lattice protein folding model whose instances contain protein sequences defined with a fixed, finite alphabet that contains 12 amino acid types. This lattice model represents a protein's conformation as a self-avoiding path that is embedded on the three-dimensional cubic lattice. A contact potential is used to determine the energy of a sequence in a given conformation; a pair of amino acids contributes to the conformational energy only if they are adjacent on the lattice. This result overcomes a significant weakness of previous intractability results, which do not examine protein folding models that have a finite alphabet of amino acids together with physically interesting conformations. Received June 1, 1997; revised March 13, 1998.     

An efficient hybrid Taguchi-genetic algorithm for protein folding simulation

Given the amino-acid sequence of a protein, the prediction of a protein’s tertiary structure is known as the protein folding problem. The protein folding problem in the hydrophobic–hydrophilic lattice model is to find the lowest energy conformation. In order to enhance the performance of predicting protein structure, in this paper we propose an efficient hybrid Taguchi-genetic algorithm that combines genetic algorithm, Taguchi method, and particle swarm optimization (PSO). The GA has the capability of powerful global exploration, while the Taguchi method can exploit the optimum offspring. In addition, we present the PSO inspired by a mutation mechanism in a genetic algorithm. We demonstrate that our algorithm can be applied successfully to the protein folding problem based on the hydrophobic-hydrophilic lattice model. Simulation results indicate that our approach performs very well against existing evolutionary algorithm.     

A Constraint-Based Approach to Fast and Exact Structure Prediction in Three-Dimensional Protein Models

Simplified protein models are used for investigating general properties of proteins and principles of protein folding. Furthermore, they are suited for hierarchical approaches to protein structure prediction. A well known protein model is the HP-model of Lau and Dill [Lau, K. F., & Dill, K. A. (1989)]. A lattice statistical mechanics model of the conformational and sequence spaces of proteins. Macromolecules, 22, 3986–3997) which models the important aspect of hydrophobicity. One can define the HP-model for various lattices, among them two-dimensional and three-dimensional ones. Here, we investigate the three-dimensional case. The main motivation for studying simplified protein models is to be able to predict model structures much more quickly and more accurately than is possible for real proteins. However, up to now there was a dilemma: the algorithmically tractable, simple protein models can not model real protein structures with good quality and introduce strong artifacts. We present a constraint-based method that largely improves this situation. It outperforms all existing approaches for lattice protein folding in HP-models. This approach is the first one that can be applied to two three-dimensional lattices, namely the cubic lattice and the face-centered-cubic (FCC) lattice. Moreover, it is the only exact method for the FCC lattice. The ability to use the FCC lattice is a significant improvement over the cubic lattice. The key to our approach is the ability to compute maximally compact sets of points (used as hydrophobic cores), which we accomplish for the first time for the FCC lattice.     

求解HP格点模型的最佳优先搜索算法

HP格点模型是目前预测蛋白质折叠结构的一种最简单和最流行的模型,该模型已被证明是NP完全问题。将问题的解空间组织成树型结构,利用启发式规则—k步探测法对结点的可能分支进行评估,采用最佳优先策略搜索解空间树。最后用最佳优先搜索算法(BF)对一组公认的算例进行了实算,计算结果表明,BF计算效率优于传统的遗传算法和Monte Carlo方法。     

Automatically obtaining a cellular automaton scheme for modeling protein folding using the FCC model

This paper proposes to model protein folding as an emergent process, using machine learning to infer the folding modeling only from information of known protein structures. Using the face-centered cubic lattice for protein conformation representation, the dynamic nature of protein folding is captured with an evolved neural cellular automaton that defines the amino acids moves along the protein chain and across time. The results of the final folded conformations are compared, using different protein benchmarks, with other methods used in the traditional protein structure prediction problem, highlighting the capabilities and problems found with this modeling.

     

Monte Carlo simulations of systems with complex energy landscapes

Non-traditional Monte Carlo simulations are a powerful approach to the study of systems with complex energy landscapes. After reviewing several of these specialized algorithms we shall describe the behavior of typical systems including spin glasses, lattice proteins, and models for “real” proteins. In the Edwards-Anderson spin glass it is now possible to produce probability distributions in the canonical ensemble and thermodynamic results of high numerical quality. In the hydrophobic-polar (HP) lattice protein model Wang-Landau sampling with an improved move set (pull-moves) produces results of very high quality. These can be compared with the results of other methods of statistical physics. A more realistic membrane protein model for Glycophorin A is also examined. Wang-Landau sampling allows the study of the dimerization process including an elucidation of the nature of the process.     

三角网格模型的快速树搜索算法及可设计性分析

在蛋白质折叠格子模型的可设计性特征研究中,为了克服以往方格模型具有奇偶问题这一缺点,本文利用三角网格模型来进行穷举搜索。在简化的网格模型中,序列折叠为某一结构的能量值为在结构心部疏水氨基酸的个数取负值。在蛋白质折叠模型的二维4 5 6 5 4三角网格中穷举了所有的序列和致密结构。其中序列由两类氨基酸(疏水氨基酸和亲水氨基酸)组成,排除正反对称序列共2~(12) 2~(23)=8392704种不同序列。在由24个格点组成的三角网格模型中共得到219093种简化结构串。在穷尽搜索算法中,为实现快速搜索,通过树结构将相似的结构串尽量聚类,通过计算各树结点的目标能量值以减少搜索算法中所需的计算量。经并行实验验证,利用该树结构可使快速搜索算法达到指数级加速比。最后对计算所得结果进行了统计分析。