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

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

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

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

基于多层量子粒子群优化算法和Toy模型的蛋白质结构预测研究

蛋白质结构预测,作为计算生物学基本问题之一,是个典型的NP难解问题.研究表明合理运用算法,借助物理模型,可用于预测蛋白质结构.Toy模型就是较为简单的类,其势能最低状态的确定则为结构预测的关键所在.量子粒子群算法是典型的智能优化算法,己广泛应用于多种系统寻优问题中.本篇文章提出使用1种改进的量子粒子群优化算法,并结合Toy模型,进行蛋白质结构预测.算法的改进在于对每次迭代的粒子,排序之后将种群分成精英子群、开采子群和勘探子群来区别处理,并通过实验进行运算和预测.结果表明运用改进的量子粒子群优化算法来进行蛋自质折叠结构预测是可行的且高效的.     

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

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

改进的蚁群算法及其在2DHP模型中的应用

为了提高蛋白质折叠问题解的质量,采用蚁群算法对蛋白质的折叠问题进行研究,并且在现有的蚁群算法的基础上成功引入了淘汰和克隆机制,使其具有更好的运算效率,并成功应用到2DHP模型中.在蚁群对最优值进行搜索的过程中,容易出现局部最优点,导致影响解的质量.为了避免计算结果收敛到局部最优点,引入了一种最大最小蚁群策略.选择测试序列进行实验,实验结果表明,该算法在保证解的质量的同时,还具有较高的效率.     

蛋白质折叠过程中的长短程作用研究

基于蛋白质二维HP非格模型和改进的模拟退火算法研究了长短程作用在蛋白质折叠过程中的作用。通过试验得出1ECD、2RNS、1PHT、1WBC等序列的折叠构型,并根据PDB中所提供的上述序列的结构信息,具体讨论了长程作用对蛋白质构型的影响,说明了：长程作用在三级结构的形成和稳定中,位于诸多影响因素的首位。     

蛋白质折叠问题的蚁群优化算法研究

蛋白质是一类重要的生物大分子,在生物体内占有特殊的地位,是生命的主要承担者。而研究蛋白质的折叠,是生命科学领域的前沿课题之一。在概述蚁群算法及2D HP蛋白质模型的基础上,针对蛋白质折叠问题提出一种蚁群优化算法,并用几个比较典型的模型对其进行仿真实验,结果表明该蚁群优化算法在求解蛋白质折叠问题时表现出了良好的性能。实践表明该算法具有很高的应用价值。     

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

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

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

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

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

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

Finding low autocorrelation binary sequences with memetic algorithms

This paper deals with the construction of binary sequences with low autocorrelation, a very hard problem with many practical applications. The paper analyzes several metaheuristic approaches to tackle this kind of sequences. More specifically, the paper provides an analysis of different local search strategies, used as stand-alone techniques and embedded within memetic algorithms. One of our proposals, namely a memetic algorithm endowed with a Tabu Search local searcher, performs at the state-of-the-art, as it consistently finds optimal sequences in considerably less time than previous approaches reported in the literature. Moreover, this algorithm is also able to provide new best-known solutions for large instances of the problem. In addition, a variant of this algorithm that explores only a promising subset of the whole search space (known as skew-symmetric sequences) is also analyzed. Experimental results show that this new algorithm provides new best-known solutions for very large instances of the problem.     

求解HP模型蛋白质折叠问题的启发式算法

构造了一个新的数学模型，把三维HP模型的蛋白质折叠问题由一个有约束的优化问题转化为无约束的优化问题，通过建立相对坐标和邻域结构，提出了一个局部搜索算法，并对文献中的链长不同的7个算例进行了测试。结果表明，该算法能在较短时间内找到其中5个算例的最优能量枸形，对另外2个难例，则可以找到能量仅比最优构形高一个单位的次优构形。     

基于h-距离的DNA编码序列设计

针对DNA编码序列设计问题,将其转换为带约束的多目标优化问题,在单链DNA集合中引入h-距离,构造了DNA序列间的共享函数,应用小种群遗传算法,对DNA编码序列设计问题进行求解。与已有结果比较,算法可以得到更好的DNA序列且计算效率较高。算法可用于DNA计算中编码序列的具体设计。     

模型未知的非双曲型非线性序列去噪算法

针对模型未知的非双曲型非线性序列难以实现去噪和轨迹重影的问题,基于模型选取的最小描述长度准则,从过拟合和欠拟合的角度分析边缘误差算法对离散系统的非最优性和不适应性,利用改进的全局误差算法对系统进行建模,结合梯度下降方法的稳定性和Newton-Raphson算法的快速收敛性提出一种融合算法,用于在机器精度内实现非双曲型非线性离散系统时间序列的去噪和轨迹重影。通过辅以极少点数的无污染序列和仅从单变量受扰观测序列2项实验验证该算法的有效性。     

Application of Monte Carlo method to optimal control for linear systems under measurement noise with Markov dependent statistical property

This paper presents an optimal control algorithm for linear systems with measurement noise which has a Markov dependent statistical property. Ordinarily, the optimal control for this problem involves a very large number of sequences, and the usual calculation method becomes impractical. In the algorithm proposed here, the optimal control is calculated with a relatively small number of sequences, sampled at random from the set of all the sequences.

Evidently, the algorithm for a control problem should be obtained directly from the performance criterion. Unlike the state estimation problem, the problem considered here has a difficulty that there exists an interaction between the algorithm and the state of the system. Because of this, a special consideration is required for the design of the algorithm. In this paper control-free measurement data are introduced to establish the convergence of the algorithm and to find a desirable way of sampling the sequences. Then, certain approximations are made to design a practical and efficient algorithm. A few digital simulation results appear to show the effectiveness of the proposed method.     

Dijkstra算法在蛋白质序列比对中的研究

提出一种基于Dijkstra算法的序列比对方法,该算法主要用于求最短路径,而序列比对可以转化为在有向无环图中寻找最短路径问题。对于少量序列比对,使用该算法可以求出最优解。对于多序列比对,可将在N维空间求解最短路径问题转化为在二维空间求解最短路径。该算法可以简化问题复杂度,能求得相对最优解。     

Halftoning of image sequences

We present an algorithm for the halftoning of greyscale image sequences. This facilitates the display of video sequences on black-and-white visual displays (e.g., high-qualityX-terminals) for multimedia applications. The main problem to be overcome when halftoning sequences is the temporal flicker between successive images.The classical problem of halftoning a static greyscale image may be posed as an optimization problem. We present an iterative algorithm for its solution. At the expense of being slower, our algorithm achieves visual results on static images better than those obtained from classic halftoning algorithms.We extend our static halftoning algorithm to image sequence halftoning. Temporal correlation between the halftoned versions of image sequences is guaranteed by using an incremental algorithm transfering information between the images. This results in binary sequences with relatively little high-frequency temporal noise, a feature that facilitates efficient no-loss compression (14) of the results.     

事件序列中的知识发现研究

事件的序列是数据的一种常见形式,其中的知识发现问题是近年来ＫＤＤ的一个活跃的研究领域。本文首先给出了事件序列中知识发现问题的形式描述和框架算法,然后讨论了数据库中发现大序列的问题,具体描述了发现数据库中大序列的算法。     

A new algorithm for aligning nested arc-annotated sequences under arbitrary weight schemes

In this paper, we propose a new algorithm for the alignment of nested arc-annotated sequences, having applications in the comparison of RNA secondary structures without pseudo-knots. We use a general edit distance model between arc-annotated sequences, that considers classical sequences of edit operations and structural edit operations on arcs. In this model, the general edit distance problem under a non-constrained weight scheme, is NP-hard. Recently, a hierarchy of arc-annotated sequence alignment problems that highlights less general, but tractable, problems was introduced. We refine this hierarchy of alignment problems and extend the class of tractable alignment problems. Up to date, the alignment problem we solve is the most general one that is known to be tractable in the considered edit distance model and under arbitrary weight schemes. This algorithm is efficient, as its asymptotic time and space complexities are the same as the complexities of the best previously published algorithm.     

求解蛋白质折叠问题的模拟退火算法

通过构造新的数学模型,把三维AB模型的蛋白质折叠问题由一个带约束的优化问题转化为无约束优化问题,然后提出一个模拟退火算法.对如何得到初始构形,提出了一个启发式策略.实算结果表明,本文算法效率较高,对四条氨基酸测试序列,本文算法得到的最低能量都要优于nPERM算法得到的结果.