一种在格点模型上模拟蛋白质折叠结构的优化算法

蛋白质折叠问题是生物信息学中一个经典的多项式复杂程度的非确定性(non-deterministic polynomial,NP)难度问题.势能曲面变平法(ELP)是一种启发式的全局优化算法.通过对ELP方法中的直方图函数提出一种新的更新机制,并将基于贪心策略的初始构象的产生,基于牵引移动的邻域搜索策略与ELP方法相结合,为面心立方体(FCC)格点模型的蛋白质折叠问题提出一种改进的势能曲面变平(ELP+)算法.采用文献中9条常用序列作为测试集.对于每条序列,ELP+算法均能找到与文献中的算法所得到的最低能量相等或更低的能量.实验结果表明,ELP+算法是求解FCC格点模型的蛋白质折叠问题的一种有效算法.     

真菌疏水蛋白结构研究进展

真菌疏水蛋白是由高等丝状真菌产生的小分子量(10kD左右)具有双亲性的蛋白质,它们在真菌生长和发育中起着重要的作用。通过研究发现疏水蛋白具有极高的表面活性,可以在界面通过自组装形成双亲性的蛋白膜,从而改变界面的亲疏水性质。值得注意的是,疏水蛋白的不同功能可归因于其双亲性蛋白质结构,使得其在不同的亲水/疏水界面处自组装以形成两性蛋白膜。基于这样的性质,疏水蛋白已经获得了国内外各领域的广泛应用。疏水蛋白潜在的应用价值激励了人们对其蛋白结构的探究从而解释其自组装机理。此篇综述总结了近些年人们通过不同手段及研究方法来解释疏水蛋白发挥功能的结构基础。     

心电逆问题的虚拟心脏模型参数解用于心室预激旁道定位的研究

提出了一种新的心电逆问题求解方法,即基于虚拟心脏模型的心电逆问题的模型参数解。详细研究了心室预激旁道位置与体表电位分布（ＢＳＰＭ：ＢｏｄｙＳｕｒｆａｃｅＰｏｔｅｎｔｉａｌＭａｐｐｉｎｇｓ）特征参数的关系,用ＢＳＰＭ的预激旁道位置敏感参数构造了优化系统的数学模型,给出了相应的优化算法及预激综合征旁道定位结果。研究结果表明：这种新的心电逆问题研究方法是可行、有效的,对心室内预激点的定位精度在三个心肌单元以内（即４．５ｍｍ）。     

人类群体遗传空间结构的"克立格"模型

通过将“克立格”技术应用于人类群体遗传学领域,构建了人类群体遗传空间结构的“克立格”模型,并论述了其原理和计算方法。以HLA-A基因座为例,应用“克立格”模型,定量分析了中国人群HLA-A基因座的空间遗传异质性;对HLA-A基因频率的空间数据矩阵进行了主成分分析,进而定义了人类群体遗传结构的综合遗传测度(SPC),绘制了综合遗传测度和主成分(PC)的“克立格”地图,分析了其群体遗传空间结构特性。与其他空间插值或平滑方法相比,人类群体遗传空间结构的“克立格”模型具有明显优点：1)“克立格”估计以空间遗传变异函数模型为基础,在绘制空间遗传结构地图之前,可利用变异函数模型定量分析所研究基因座(或多基因座)的空间遗传异质性;2)“克立格”插值方法是真正意义上的无偏估计模型,它利用待估区域周围的已知群体遗传调查点数据,并充分考虑调查点的空间影响范围,给出待估区域的最优估计值;3)“克立格”模型允许估计插值误差,这种插值误差既可用于评价空间估计效果,又可通过绘制误差地图指导在误差过高的地点增加新的群体遗传调查样本点,以优化估计效果。然而,人类群体遗传空间结构的“克立格”模型也存在一定缺点：1)若不能用任何理论遗传变异函数模型拟合观察遗传变异函数值,则不能建立“克立格”模型;2)若理论遗传变异函数的拟合优度很低,则据此建立的“克立格”模型的估计标准差在整个空间范围内会很大,此时“克立格”模型不适用于估计群体遗传空间结构。出现上述两种情形时,应选用不考虑空间相关性的空间随机插值方法绘制群体遗传结构地图,如基因绘图软件中的Cavalli-Sforza方法,反向距离加权法和条样函数插值法等。     

基于路网的土壤采样布局优化——模拟退火神经网络算法

以湖北省钟祥市东部的土壤有机质为研究对象,通过地形分析提取坡度、沿平面曲率、沿剖面曲率、地形湿度指数、汇流动力指数、沉积物运移指数等地形因子,在道路周边设置13种采样尺度,运用模拟退火算法对各样点的空间布局分别进行优化,以获取基于路网的土壤采样优化布局.在此基础上,对地形因子和优化后样点的有机质建立多元线性回归模型,同时建立基于神经网络的多层感知机模型,并用此模型精度与多元线性回归模型精度进行对比.结果表明:利用道路网制定土壤采样方案是可行的,优化后的采样点布局能够准确获取土壤景观知识,并且优于原始样点的精度.本研究利用道路空间分布格局、历史样点、数字高程数据等可利用资源设计采样方案,为降低采样成本、提高采样效率、展现有机质空间分布格局提供了有效手段与理论依据.     

氨基酸的亲、疏水性研究 Ⅰ.各种氨基酸及其残基的疏水性标度

蛋白质由20种氨基酸组成.它们的亲、疏水性的相互作用是维持蛋白质三级结构最重要的作用力之一.有些变性的蛋白质(即随机松散分布的多肽链)能够自动地重新折叠起来,成为具有生物活性、高度有序的天然构象,就是疏水基起着关键作用.因此,研究各种氨基酸侧链亲水性或疏水性的大小及其相互作用(该方面的工作是七十年代才开展起来的),对于深入了解蛋白质、核酸等生物大分子的结构与功能,具有重要意义. 一、疏水性的定义一般来说,基团的疏水性与其极性呈正比.     

基于HNP三态模型及相对熵方法的蛋白质折叠研究

把20种氨基酸简化为3类:疏水氨基酸(hydrophobic,H)、亲水氨基酸(hydrophilic,P)及中性氨基酸(neutral,N),每个氨基酸简化为一个点,用其C!原子来代替.采用非格点模型,以相对熵作为优化函数,进行蛋白质三维结构预测.为了与基于相对熵方法的蛋白质设计工作进行统一,采用了新的接触强度函数.选用蛋白质数据库中的天然蛋白质作为测试靶蛋白,结果表明,采用该模型和方法取得了较好的结果,预测结构相对于天然结构的均方根偏差在0.30～0.70nm之间.该工作为基于相对熵及HNP模型的蛋白质设计研究打下了基础.     

新型图形硬件支持下的动态规划局部比对算法加速研究

为探索准确、高效、低成本、通用性并存的生物序列局部比对方法。将点阵图算法、启发式算法等各种序列局部比对算法中准确性最高的动态规划局部比对算法在计算机中实现,并通过流式模型将其映射到图形硬件上以实现算法加速,再通过实例比对搜索数据库完成比对时间和每秒百万次格点更新（MCUPS）性能值评测。结果表明,该加速算法在保证比对准确性的同时,能显著提升比对速度。与目前最快的启发式算法相比,比对平均加速为14.5倍,最高加速可达22.9倍。     

血清白蛋白与降血糖药物相互作用的关键位点分析

用生物信息学的方法分析不同物种的血清白蛋白的亲缘关系,分析降血糖药物米格列醇和伏格列波糖与人血清白蛋白相互作用位点在其他亲缘关系较近的物种中相应的氨基酸变化特点。结果表明米格列醇、伏格列波糖与人血清白蛋白的结合位点都位于人血清白蛋白亚区IB的疏水腔中,其间的主要作用力是氢键和疏水作用力。米格列醇和伏格列波糖与血清白蛋白结合位点处的氨基酸在其他物种中大部分都是保守的,只有少数的氨基酸不同,且极性也不相同。血清白蛋白疏水性分析发现米格列醇和伏格列波糖与血清白蛋白结合位点处的氨基酸中亲水性的较多,疏水性的少,在其他4个亲缘关系较近的物种也具有同样的现象。这些分析结果为进一步研究降血糖药物在其他物种中的表现及相互作用等提供了重要的科学依据。     

基于HP模型的蛋白质折叠问题的研究

基于蛋白质二维HP模型提出改进的遗传算法对真实蛋白质进行计算机折叠模拟。结果显示疏水能量函数最小值的蛋白质构象对应含疏水核心的稳定结构,疏水作用在蛋白质折叠中起主要作用。研究表明二维HP模型在蛋白质折叠研究中是可行的和有效的并为进一步揭示蛋白质折叠机理提供重要参考信息。     

Enhanced hybrid search algorithm for protein structure prediction using the 3D-HP lattice model

The problem of protein structure prediction in the hydrophobic-polar (HP) lattice model is the prediction of protein tertiary structure. This problem is usually referred to as the protein folding problem. This paper presents a method for the application of an enhanced hybrid search algorithm to the problem of protein folding prediction, using the three dimensional (3D) HP lattice model. The enhanced hybrid search algorithm is a combination of the particle swarm optimizer (PSO) and tabu search (TS) algorithms. Since the PSO algorithm entraps local minimum in later evolution extremely easily, we combined PSO with the TS algorithm, which has properties of global optimization. Since the technologies of crossover and mutation are applied many times to PSO and TS algorithms, so enhanced hybrid search algorithm is called the MCMPSO-TS (multiple crossover and mutation PSO-TS) algorithm. Experimental results show that the MCMPSO-TS algorithm can find the best solutions so far for the listed benchmarks, which will help comparison with any future paper approach. Moreover, real protein sequences and Fibonacci sequences are verified in the 3D HP lattice model for the first time. Compared with the previous evolutionary algorithms, the new hybrid search algorithm is novel, and can be used effectively to predict 3D protein folding structure. With continuous development and changes in amino acids sequences, the new algorithm will also make a contribution to the study of new protein sequences.     

An ant colony optimisation algorithm for the 2D and 3D hydrophobic polar protein folding problem

Background  

The protein folding problem is a fundamental problems in computational molecular biology and biochemical physics. Various optimisation methods have been applied to formulations of the ab-initio folding problem that are based on reduced models of protein structure, including Monte Carlo methods, Evolutionary Algorithms, Tabu Search and hybrid approaches. In our work, we have introduced an ant colony optimisation (ACO) algorithm to address the non-deterministic polynomial-time hard (NP-hard) combinatorial problem of predicting a protein's conformation from its amino acid sequence under a widely studied, conceptually simple model – the 2-dimensional (2D) and 3-dimensional (3D) hydrophobic-polar (HP) model.     

Optimal HP configurations of proteins by combining local search with elastic net algorithm

The prediction of protein conformation from its amino-acid sequence is one of the most prominent problems in computational biology. But it is NP-hard. Here, we focus on an abstraction widely studied of this problem, the two-dimensional hydrophobic-polar protein folding problem (2D HP PFP). Mathematical optimal model of free energy of protein is established. Native conformations are often sought using stochastic sampling methods, but which are slow. The elastic net (EN) algorithm is one of fast deterministic methods as travelling salesman problem (TSP) strategies. However, it cannot be applied directly to protein folding problem, because of fundamental differences in the two types of problems. In this paper, how the 2D HP protein folding problem can be framed in terms of TSP is shown. Combination of the modified elastic net algorithm and novel local search method is adopted to solve this problem. To our knowledge, this is the first application of EN algorithm to 2D HP model. The results indicate that our approach can find more optimal conformations and is simple to implement, computationally efficient and fast.     

Optimal HP configurations of proteins by combining local search with elastic net algorithm

The prediction of protein conformation from its amino-acid sequence is one of the most prominent problems in computational biology. But it is NP-hard. Here, we focus on an abstraction widely studied of this problem, the two-dimensional hydrophobic-polar protein folding problem (2D HP PFP). Mathematical optimal model of free energy of protein is established. Native conformations are often sought using stochastic sampling methods, but which are slow. The elastic net (EN) algorithm is one of fast deterministic methods as travelling salesman problem (TSP) strategies. However, it cannot be applied directly to protein folding problem, because of fundamental differences in the two types of problems. In this paper, how the 2D HP protein folding problem can be framed in terms of TSP is shown. Combination of the modified elastic net algorithm and novel local search method is adopted to solve this problem. To our knowledge, this is the first application of EN algorithm to 2D HP model. The results indicate that our approach can find more optimal conformations and is simple to implement, computationally efficient and fast.     

Novel Approach to Nonlinear PID Parameter Optimization Using Ant Colony Optimization Algorithm

This paper presents an application of an Ant Colony Optimization （ACO） algorithm to optimize the parameters in the design of a type of nonlinear PID controller. The ACO algorithm is a novel heuristic bionic algorithm, which is based on the behaviour of real ants in nature searching for food. In order to optimize the parameters of the nonlinear PID controller using ACO algorithm, an objective function based on position tracing error was constructed, and elitist strategy was adopted in the improved ACO algorithm. Detailed simulation steps are presented. This nonlinear PID controller using the ACO algorithm has high precision of control and quick response.     

On lattice protein structure prediction revisited

Protein structure prediction is regarded as a highly challenging problem both for the biology and for the computational communities. In recent years, many approaches have been developed, moving to increasingly complex lattice models and off-lattice models. This paper presents a Large Neighborhood Search (LNS) to find the native state for the Hydrophobic-Polar (HP) model on the Face-Centered Cubic (FCC) lattice or, in other words, a self-avoiding walk on the FCC lattice having a maximum number of H-H contacts. The algorithm starts with a tabu-search algorithm, whose solution is then improved by a combination of constraint programming and LNS. The flexible framework of this hybrid algorithm allows an adaptation to the Miyazawa-Jernigan contact potential, in place of the HP model, thus suggesting its potential for tertiary structure prediction. Benchmarking statistics are given for our method against the hydrophobic core threading program HPstruct, an exact method which can be viewed as complementary to our method.     

Learning cluster-based classification systems with ant colony optimization algorithms

Classification is a data mining task the goal of which is to learn a model, from a training dataset, that can predict the class of a new data instance, while clustering aims to discover natural instance-groupings within a given dataset. Learning cluster-based classification systems involves partitioning a training set into data subsets (clusters) and building a local classification model for each data cluster. The class of a new instance is predicted by first assigning the instance to its nearest cluster and then using that cluster’s local classification model to predict the instance’s class. In this paper, we present an ant colony optimization (ACO) approach to building cluster-based classification systems. Our ACO approach optimizes the number of clusters, the positioning of the clusters, and the choice of classification algorithm to use as the local classifier for each cluster. We also present an ensemble approach that allows the system to decide on the class of a given instance by considering the predictions of all local classifiers, employing a weighted voting mechanism based on the fuzzy degree of membership in each cluster. Our experimental evaluation employs five widely used classification algorithms: naïve Bayes, nearest neighbour, Ripper, C4.5, and support vector machines, and results are reported on a suite of 54 popular UCI benchmark datasets.     

A novel ACO algorithm for optimization via reinforcement and initial bias

In this paper, we introduce the MAF-ACO algorithm, which emulates the foraging behavior of ants found in nature. In addition to the usual pheromone model present in ACO algorithms, we introduce an incremental learning component. We view the components of the MAF-ACO algorithm as stochastic approximation algorithms and use the ordinary differential equation (o.d.e.) method to analyze their convergence. We examine how the local stigmergic interaction of the individual ants results in an emergent dynamic programming framework. The MAF-ACO algorithm is also applied to the multi-stage shortest path problem and the traveling salesman problem. Research of Prof. V.S. Borkar was supported in part by grant no. III.5(157)/99-ET and a J.C. Bose Fellowship from the Department of Science and Technology, Government of India.