求解蛋白质折叠问题的拟物拟人算法
|
摘要
蛋白质所具有的生物学功能取决于蛋白质的空间折叠结构,研究蛋白质的空间结构在生物学领域具有重要意义。Anfinsen等人的研究工作表明,给定蛋白质一级结构序列,利用理论计算对蛋白质结构进行预测是一个可行的方法。由于蛋白质折叠问题的复杂度太高,理论界提出了一些简化模型。其中,Dill等提出的HP模型和Stillinger提出的AB模型最受欢迎,研究也最为广泛。基于HP模型和AB模型的蛋白质折叠问题都已被证明是NP完全问题,这意味着不存在既完整严格又不是太慢的求解算法。为了满足实际需要,人们于是着手研究非绝对完整但是是快速实用的启发式算法。沿着拟物拟人的工作途径,分别对基于HP模型和AB模型的蛋白质折叠问题的高效求解进行了研究。
为了减小搜索空间,给出了一种带随机策略的剪枝算法来求解基于二维HP模型的蛋白质折叠问题。在算法中,保留那些前景好的结点,并允许它以一定概率向下分支,而那些前景不太好的结点则以一定概率被删除,其下相连的分支也被“剪掉”。这样减小了搜索空间,使得相应的搜索时间也大大降低。
基于裁剪复制策略的PERM (pruned-enriched Rosenbluth method)算法是一种链生长算法,它通过制定一定的评判准则,让有前途的个体得以繁衍,而不具备发展潜力的个体停止繁殖,从而减少了搜索树的分支数。通过分析PERM算法,指出了影响PERM算法效率的关键,并从拟人思想的角度对PERM算法做出了进一步的分析:PERM算法实际上可以理解为一种人口控制策略,通过对社会中的个体给出评价,然后给出个体的生育指标,从而实现“优生优育”。在这样一个生动形象的背景的指导下,提出了更为合理和有效的评判准则,从而得到了一种改进的PERM算法。计算结果表明改进的PERM算法在求解基于HP模型的蛋白质折叠问题时表现出非常高的效率。
通过拟物思想,引入引力势能和斥力势能,建立了一个启发式的引导函数,把基于三维HP模型的蛋白质折叠问题由一个约束优化问题转化为无约束优化问题,然后给出了一个基于局部搜索策略的启发式算法。
为基于三维AB模型的蛋白质折叠问题找到了一个贴切的物理模型,该物理模型是一个力学系统。将氨基酸单体看作弹性小球,想象在蛋白质链上相邻两球球心之间连接着一根长度为1的弹簧。这样,系统能量中除了Lennard-Jones势能、弯曲势能和扭转势能外,还有弹簧势能。弹簧势能相当于一个罚函数,它是“松弛”约束条件的关键,把基于三维AB模型的蛋白质折叠问题由一个约束优化问题转化为无约束的优化问题。对此无约束优化问题,给出了一个梯度算法,并设计了一个产生初始构形的启发式策略。
在用梯度法求解的过程中,计算很容易落入局部极小值的陷阱。为了跳出局部极小值陷阱,让计算走向前景更好的区域中去,在拟物算法的基础上,分别与模拟退火算法和禁忌搜索算法相结合,得到了效率更高的、具有全局优化能力的混合算法。尤其值得指出的是,以ELP (energy landscape paving minimizer)算法得到的结果构形作为拟物算法的初始构形,对于文献中的绝大多数算例,拟人算法都找到了当今国际学术界最好的构形,这种构形比文献中报道的构形具有更低的势能。
以上研究工作表明,通过对物理世界中物质运动的演化规律和人类的社会经验进行抽象和形式化,可以启发人们为蛋白质折叠问题设计出高效的求解算法。在以后的研究工作中,我们将沿着拟物拟人的思路继续为基于其它模型的蛋白质折叠问题和其它NP完全问题寻求高效的求解算法。
Since the proteins’biological properties rest on their dimensional folding structures, the study of the proteins’structure is of great significance in theoretical structural biology. According to the research of Anfinsen et al, predicting the native structure of a protein from its amino acid sequence by using theoretical computing method is a feasible approach. The theoretical science community has introduced and examined several highly simplified models since the protein folding problem is too difficult to be approached with fully realistic potentials. Among the simplified models, HP model of Dill and AB model of Stillinger are the most popular ones and have been studied extensively. Even in these highly simplified models, it is not easy to predict the native state for the protein folding problem, which has been recognized to be NP-complete. As a NP hard problem, it means that there does not exist an algorithm that is complete, rigorous and efficient. Consequently, people hope to obtain a heuristic algorithm for solving NP hard problems that is not absolutely complete, but is of high speed, high reliability and high efficiency. Through the so-called quasi-physical and quasi-human strategy, we proposed some efficient and effective algorithms for solving the protein folding problems based on HP model and AB model, respectively.
In order to reduce the search space, a pruning algorithm with random strategy was proposed to solve the two-dimensional protein folding problem based on HP model. In this algorithm, only the promising nodes are kept for further branching with certain probability, while those nodes not promising enough are pruned with certain probability. With this pruning algorithm, the search space is reduced and the corresponding search time is decreased accordingly.
Based on pruning and enrichment strategy, PERM (pruned-enriched Rosenbluth method) is a kind of chain growth algorithm. By formulating some certain evaluation criteria, PERM enriches those promising branches and prunes those with poor quality so that the search space is reduced. Via analyzing PERM, the factors that essentially affect the efficiency of PERM were indicated, and then some further analyses from the personification explanation were made. PERM can be viewed as a population control strategy, by means of which, the quality of an individual is evaluated, and then a guideline on procreation of the individual can be obtained, thus realizing the aim of“go with the winners”. With such a vivid background, a much more reasonable rule for evaluation was generated, and an improved version of PERM was proposed. Computational results indicate that the improved PERM performs efficiently with benchmarks of protein folding problem.
Based on the quasi-physical idea, a new mathematical model including attraction potential and exclusion potential is constructed so that the three dimensional protein folding problem based on HP model is converted from a nonlinear constraint-satisfied problem to an unconstrained one. A heuristic algorithm based on local search strategy was proposed for solving the problem.
A perfect physical model, that is, a mechanical system, is constructed for the three-dimensional AB mode-based protein folding problem. In this system, an amino acid monomer is regarded as a smooth elastic ball. Assume that the centers of any two successive balls along the chain are linked by springs with natural length to be 1. Therefore, apart from the energy contributions from Lennard-Jones, bond angles and torsion angles, the elastic potential energy of springs is also a part of the total potential of the configuration. The elastic energy of the springs acts as a penalty function of the degree of departure of a configuration from a legal one, and it is the key to relax the constraints. Accordingly, the protein folding is converted from a constraint optimization problem into an unconstrained one, which could be solved by the gradient method. A heuristic strategy was proposed to generate promising initial configurations.
In the course of solution using the gradient method, it is often possible for the calculation to fall into the trap of local minimum. To jump out of the trap of local minimum and guide the search to the points with better prospects, we combined our quasi-physical algorithms with other methods with global-search ability, and then obtained a simulated annealing method and a Tabu search method, which are more efficient than the quasi-physical algorithm. It is noteworthy that based on the initial configurations obtained by ELP (energy landscape paving minimizer), most of our results for the benchmark instances are better than the best values previously reported in literature.
The research in this dissertation indicates that by abstracting and formalizing the evolution rule of the motion of matter in the physical world and the humanity’s social experience, we could design highly efficient algorithm for solving the protein folding problem. Through this working path, we are trying to seek for high-efficent algorithms for other model-based protein folding problem and other NP-complete problems in our future study.
为了减小搜索空间,给出了一种带随机策略的剪枝算法来求解基于二维HP模型的蛋白质折叠问题。在算法中,保留那些前景好的结点,并允许它以一定概率向下分支,而那些前景不太好的结点则以一定概率被删除,其下相连的分支也被“剪掉”。这样减小了搜索空间,使得相应的搜索时间也大大降低。
基于裁剪复制策略的PERM (pruned-enriched Rosenbluth method)算法是一种链生长算法,它通过制定一定的评判准则,让有前途的个体得以繁衍,而不具备发展潜力的个体停止繁殖,从而减少了搜索树的分支数。通过分析PERM算法,指出了影响PERM算法效率的关键,并从拟人思想的角度对PERM算法做出了进一步的分析:PERM算法实际上可以理解为一种人口控制策略,通过对社会中的个体给出评价,然后给出个体的生育指标,从而实现“优生优育”。在这样一个生动形象的背景的指导下,提出了更为合理和有效的评判准则,从而得到了一种改进的PERM算法。计算结果表明改进的PERM算法在求解基于HP模型的蛋白质折叠问题时表现出非常高的效率。
通过拟物思想,引入引力势能和斥力势能,建立了一个启发式的引导函数,把基于三维HP模型的蛋白质折叠问题由一个约束优化问题转化为无约束优化问题,然后给出了一个基于局部搜索策略的启发式算法。
为基于三维AB模型的蛋白质折叠问题找到了一个贴切的物理模型,该物理模型是一个力学系统。将氨基酸单体看作弹性小球,想象在蛋白质链上相邻两球球心之间连接着一根长度为1的弹簧。这样,系统能量中除了Lennard-Jones势能、弯曲势能和扭转势能外,还有弹簧势能。弹簧势能相当于一个罚函数,它是“松弛”约束条件的关键,把基于三维AB模型的蛋白质折叠问题由一个约束优化问题转化为无约束的优化问题。对此无约束优化问题,给出了一个梯度算法,并设计了一个产生初始构形的启发式策略。
在用梯度法求解的过程中,计算很容易落入局部极小值的陷阱。为了跳出局部极小值陷阱,让计算走向前景更好的区域中去,在拟物算法的基础上,分别与模拟退火算法和禁忌搜索算法相结合,得到了效率更高的、具有全局优化能力的混合算法。尤其值得指出的是,以ELP (energy landscape paving minimizer)算法得到的结果构形作为拟物算法的初始构形,对于文献中的绝大多数算例,拟人算法都找到了当今国际学术界最好的构形,这种构形比文献中报道的构形具有更低的势能。
以上研究工作表明,通过对物理世界中物质运动的演化规律和人类的社会经验进行抽象和形式化,可以启发人们为蛋白质折叠问题设计出高效的求解算法。在以后的研究工作中,我们将沿着拟物拟人的思路继续为基于其它模型的蛋白质折叠问题和其它NP完全问题寻求高效的求解算法。
Since the proteins’biological properties rest on their dimensional folding structures, the study of the proteins’structure is of great significance in theoretical structural biology. According to the research of Anfinsen et al, predicting the native structure of a protein from its amino acid sequence by using theoretical computing method is a feasible approach. The theoretical science community has introduced and examined several highly simplified models since the protein folding problem is too difficult to be approached with fully realistic potentials. Among the simplified models, HP model of Dill and AB model of Stillinger are the most popular ones and have been studied extensively. Even in these highly simplified models, it is not easy to predict the native state for the protein folding problem, which has been recognized to be NP-complete. As a NP hard problem, it means that there does not exist an algorithm that is complete, rigorous and efficient. Consequently, people hope to obtain a heuristic algorithm for solving NP hard problems that is not absolutely complete, but is of high speed, high reliability and high efficiency. Through the so-called quasi-physical and quasi-human strategy, we proposed some efficient and effective algorithms for solving the protein folding problems based on HP model and AB model, respectively.
In order to reduce the search space, a pruning algorithm with random strategy was proposed to solve the two-dimensional protein folding problem based on HP model. In this algorithm, only the promising nodes are kept for further branching with certain probability, while those nodes not promising enough are pruned with certain probability. With this pruning algorithm, the search space is reduced and the corresponding search time is decreased accordingly.
Based on pruning and enrichment strategy, PERM (pruned-enriched Rosenbluth method) is a kind of chain growth algorithm. By formulating some certain evaluation criteria, PERM enriches those promising branches and prunes those with poor quality so that the search space is reduced. Via analyzing PERM, the factors that essentially affect the efficiency of PERM were indicated, and then some further analyses from the personification explanation were made. PERM can be viewed as a population control strategy, by means of which, the quality of an individual is evaluated, and then a guideline on procreation of the individual can be obtained, thus realizing the aim of“go with the winners”. With such a vivid background, a much more reasonable rule for evaluation was generated, and an improved version of PERM was proposed. Computational results indicate that the improved PERM performs efficiently with benchmarks of protein folding problem.
Based on the quasi-physical idea, a new mathematical model including attraction potential and exclusion potential is constructed so that the three dimensional protein folding problem based on HP model is converted from a nonlinear constraint-satisfied problem to an unconstrained one. A heuristic algorithm based on local search strategy was proposed for solving the problem.
A perfect physical model, that is, a mechanical system, is constructed for the three-dimensional AB mode-based protein folding problem. In this system, an amino acid monomer is regarded as a smooth elastic ball. Assume that the centers of any two successive balls along the chain are linked by springs with natural length to be 1. Therefore, apart from the energy contributions from Lennard-Jones, bond angles and torsion angles, the elastic potential energy of springs is also a part of the total potential of the configuration. The elastic energy of the springs acts as a penalty function of the degree of departure of a configuration from a legal one, and it is the key to relax the constraints. Accordingly, the protein folding is converted from a constraint optimization problem into an unconstrained one, which could be solved by the gradient method. A heuristic strategy was proposed to generate promising initial configurations.
In the course of solution using the gradient method, it is often possible for the calculation to fall into the trap of local minimum. To jump out of the trap of local minimum and guide the search to the points with better prospects, we combined our quasi-physical algorithms with other methods with global-search ability, and then obtained a simulated annealing method and a Tabu search method, which are more efficient than the quasi-physical algorithm. It is noteworthy that based on the initial configurations obtained by ELP (energy landscape paving minimizer), most of our results for the benchmark instances are better than the best values previously reported in literature.
The research in this dissertation indicates that by abstracting and formalizing the evolution rule of the motion of matter in the physical world and the humanity’s social experience, we could design highly efficient algorithm for solving the protein folding problem. Through this working path, we are trying to seek for high-efficent algorithms for other model-based protein folding problem and other NP-complete problems in our future study.
引文
[1]骆奸新,郑崛村.人类基因组计划与后基因组时代.中国生物工程杂志, 2003, 23(11):87294
[2]朱杰.生物信息学的研究现状及其发展问题的探讨.生物信息学, 2005, 3: 185-188
[3] Creighton T E. Protein folding. New York: Freeman, 1992
[4]邹承鲁.第二遗传密码:新生肤链及蛋白质折叠的研究,第一版.长沙:湖南科学技术出版社, 1997
[5]赵南明,周海梦.生物物理学,第一版.北京:高等教育出版社, 2000
[6]邹承餐,王志珍.立足国内走向世界从吴宪教授六十四年前一篇论文的重新发表谈起.生理科学进展, 1996, 27(1): 5-6
[7] Anfinsen C B. Principles that govern the folding of protein chains. Science, 1973, 181(96): 223-230
[8]阎隆飞,孙之荣.蛋白质分子结构.北京:清华大学出版社,1999
[9]刘东升,王金凤.结构基因组学研究与核磁共振.生物化学与生物物理进展, 2001, 28(6):827-831
[10] Swiss-Prot. Swiss-Prot protein knowledgebase release 49.5 statistics [EB/OL]. http://www. expasy.ch /sprot/relnotes/relstat.htm
[11] Cynthia G, Jambeck P. Developing bioinformatics computer skills, 1st edition. New York: O'Reilly Media, 2001
[12]靳利霞,唐焕文.蛋白质结构预测方法简述.自然杂志,2003, 23(4): 217-221
[13]殷志祥.蛋白质结构预测方法的研究进展.计算机工程与应用,2004,20:54-57
[14] Luo L F. The time scale of protein simple model of chaperones. Acta SNUN, 1994, 25:52-56
[15] Haknovich E I, Rutin A M. Formation of unique structure in polypeptide chains. Biophysical Chemistry, 1989, 34:187-193
[16] Ponnuswamy P K. Hydrophobic characteristics of folded protein. Progress in Biophysics & Molecular Biology, 1993, 59(1): 57-103
[17] Philip E B, Helge W. Structural bioinformatics. Chichester: John Wiley & Sons, 2003
[18] Tsai C S. An Introduction to computational biochemistry. New York: Wiley-Liss, 2002
[19]宁正元,林世强.蛋白质结构的预测及其应用.福建农林大学学报(自然科学版), 2006, 35(3):308-313
[20] Dill K A. Theory for the folding and stability of globular proteins. Biochemistry, 1985, 24: 1501-1509
[21] Dill K A, Bromberg S, Yue K, et al. Principles of protein folding: A perspective from simple exactmodels. Protein Science, 1995, 4: 561-602
[22] Dill K A, Fiebig K M, Chan H S. Cooperativity in protein folding Kinetics. Proceedings of the National Academy of Sciences of USA, 1993, 90: 1942-1946
[23] Hunt N G, Gregoret L M, Cohen F E. The origin of protein secondary structure: effects of packing density and hydrogen bonding studies by a fast conformational search. Journal of Molecular Biology, 1994, 241: 214-225
[24] Sali A, Shakhnovich E I, Karplus M. Kinetics of protein folding. A lattice model study of the requirements for folding to the native state. Journal of Molecular Biology, 1994, 235: 1614-1636
[25] Yee D P, Chan H S, Havel T F, et al. Does compactness induce secondary structure in proteins? Journal of Molecular Biology, 1994, 241:557-573
[26] Gutin A M, Abkevich V I, Shakhnovich E I. Evolution like selection of fast folding model proteins. Proceedings of the National Academy of Sciences of USA, 1995, 92: 1282-1286
[27] Gutin A M, Abkevich V I, Shakhnovich E I. Is burst hydrophobic collapse necessary for protein folding? Biochemistry, 1995, 34: 3066-3076
[28] Dill K A. Dominant forces in protein folding. Biochemistry, 1990, 29(31):7133-7155
[29] Shih C T, Su Z Y, Gwan J F, et al. The HP model, designability, and alpha-helices in protein structures. Physical Review Letters, 2000, 84(2): 384-389
[30] Bonnie B, Tom L. Protein folding in the hydrophobic-hydrophilic model is NP-complete. RECOMB 98. New York. 1998. 30-39
[31] Garey M R, Johnson D S. Computer and intractability: a guide to the theory of NP-Completeness. San Francisco: Freeman, 1978
[32] Hochbaum D S, Maass W. Approximation schemes for covering and packing problems in image processing and VLSI, Journal of the Association for Computing Machinery, 1985, 32 (1):130–136
[33] Unger R, Moult J. Genetic algorithms for protein folding simulations. Journal of Molecular Biology, 1993, 231: 75-81
[34] Beutler T, Dill K. A fast conformational search strategy for finding low energy structures of model proteins. Protein Science, 1996, 5: 2037- 2043
[35] Toma L, Toma S. Contact interactions method: A new algorithm for protein folding simulations. Protein Science, 1996, 5: 147- 153
[36] Bastolla U, Frauenkron H, Gerstner E, et al. Testing a new Monte Carlo algorithm for protein folding. PROTEINS: Structure, Function & Genetics, 1998, 32: 52-66
[37] Irb?ck A. Monte Carlo approach to biopolymers and protein folding. Singapore: World Scientific, 1998. 98-109
[38]解伟,王翼飞.蛋白质折叠的计算机模拟.上海大学学报(自然科学版),2000, 6(2): 145-149
[39]解伟,王翼飞.蛋白质折叠的三维计算机模拟.上海大学学报(自然科学版), 2000, 6(6):548-550
[40]王敞,陈增强,袁著社.基于并行遗传算法的蛋白质空间结构预测.计算机科学,2003, 30(7): 147-149
[41]方茜,朱正佑,王翼飞.应用于蛋白质折叠模拟的三种新蒙特卡罗方法的比较.上海大学学报(自然科学版), 2004, 10(5): 526-530
[42] Huang J, Shi F, Zhou H B. Mixed search algorithm for protein folding. Wuhan University Journal of Natural Science. 2003, 8(3A):765-768
[43] Rainer K, Thomas D. Improving genetic algorithms for protein folding simulations by systematic crossover. Biosystems, 1999, 50:17-25
[44] Chou C I, Han R S, Li S P, et al. Guided simulated annealing method for optimization problem. Physical Review E, 2003, 67: 066704
[45] Faming L, Wing H W. Evolutionary Monte Carlo for protein folding simulations. Journal of Chemical Physics, 2001, 115(7):3374-3380
[46] Iba Y, Chikenji G, Kikuchi M. Simulation of lattice polymers with Multi-Self-Overlap ensemble. Journal Physics Society Japan, 1998, 67(10): 3327-3330
[47] Chikenji G, Kikuchi M, Iba Y. Mutlti-Self-Overlap ensemble for protein folding: ground state search and thermodynamics. Physical Review Letters, 1999, 83(9): 1886-1889
[48] Beutler T C. Dill K A. A fast conformational search strategy for finding low energy structures of model proteins. Protein Science, 1996, 5(10): 2037-2043
[49] Junni L Z, Jun S L. A new sequential importance sampling method and its application to the two-dimensional hydrophobic-hydrophilic model. Journal of Chemical Physics, 2002, 117(7): 3492-3498
[50] Grassberger P. Recursive sampling of random-walks: self-avoiding walks in disordered media. Journal of Physics. A. 1993, 26: 1023
[51] Grassberger P, Hegger R. Simulations of three-dimensional Theta polymers. Journal of Chemical Physics, 1995, 102(17): 6881-6899
[52] Grassberger P. Pruned-enriched Rosenbluth method: simulations ofθpolymers of chain length up to 1000000. Physical Review E, 1997, 56(3): 3682-3693
[53] Hsu H P, Mehra V, Nadler W, et al. Growth algorithms for lattice heteropolymers at low temperatures. Journal of Chemical Physics, 2003, 118(1): 444-452
[54] Hsu H P, Mehra V, Nadler W, et al. A Growth-based optimization algorithm for lattice heteropoiymers. Physical Review E, 2003, 68(2): 037703
[55] Huang W, LüZ. Personification algorithm for protein folding problem: improvements in PERM. Chinese Science Bulletin, 2004, 49 (19):2092-2096
[56] Huang W, LüZ, Shi H. Growth algorithm for finding low energy configurations of simple latticeproteins. Physical Review E, 2005, 72: 016704
[57] Stillinger F H, Gordon T H, Hirshfeld C L. Toy model for protein folding. Physical Review E, 1993, 48(2):1469 -1477
[58] Head-Gordon T, Stillinger F H. Optimal neural networks for protein-structure prediction. Physical Review E, 1993, 48: 1502-1515
[59] Stillinger F H. Collective aspects of protein folding illustrated by a toy model. Physical Review E, 1995, 52(3): 2872-2877
[60] Liang F. Annealing contour Monte Carlo algorithm for structure optimization in an off-lattice protein model. Journal of Chemical Physics, 2004, 120(14): 6756-6763
[61] Irb?ck A, Peterson C, Potthast F, et al. Local interactions and protein folding: a three-dimensional off-lattice approach. Journal of Chemical Physics, 1997, 107:273-282.
[62] Irb?ck A, Peterson C, Potthast F. Identification of amino acid sequences with good folding properties in an off-lattice model. Physical Review E, 1997, 55(1): 860-867
[63] Irb?ck A, Peterson C, Potthast F. Studies of an off-lattice model for protein folding: sequence dependence and improved sampling at finite temperature. Journal of Chemical Physics, 1995, 103: 10298-10305
[64] Torcini A, Livi R, Politi A. A dynamical approach to protein folding. The Journal of Biological Physics, 2001, 27: 181-187
[65] Gorse D. Global minimization of an off-lattice potential energy function using a chaperone-based refolding method. Biopolymers, 2001, 59: 411-426
[66] Gorse D. Application of chaperone-based refolding method to two-and three-dimensional off-lattice protein models. Biopolymers, 2002, 64: 146-160
[67] Hsu H P, Vishal M, Grassberger P. Structure optimization in an off-lattice protein model. Physical Review E, 2003, 68: 037703
[68] Bachmann M, Arkin H, Janke W. Multicanonical study of coarse-grained off-lattice models for folding heteropolymers. Physical Review E, 2005, 71:031906
[69] Lee J, Scheraga H A, Rackovsky S. New optimization method for conformational energy calculations on polypeptides: conformational space annealing. Journal of Computational Chemistry, 1997, 18: 1222-1232
[70] Lee J, Scheraga H A. Conformational space annealing by parallel computations: extensive conformational search of Metenkephalin and of the 20-residue membrane-bound portion of melittin. International Journal of Quantum Chemistry, 1999, 75:255-265
[71] Lee J, Liwo A, Scheraga H A. Energy-based de novo protein folding by conformational space annealing and an off-lattice united-residue force field: Application to the 10-55 fragment of staphylococcal protein A and to apo calbindin D9K. Proceedings of the National Academy ofSciences of USA, 1999, 96: 2025-2030
[72] Kim S Y, Lee S J, Lee J. The energy landscape of a BLN protein with beta hairpin shape, Journal of the Korean Physical Society, 2004, 44: 589-593
[73]黄文奇,詹叔浩.求解Packing问题的拟物方法.应用数学学报, 1979, 2 (2): 176-180
[74]黄文奇,许如初.支持求解圆形Packing的两个拟人策略中国科学(E辑), 1999,27(2): 347-353
[75]张鸣华.可计算性理论.北京:清华大学出版社,1984. 15-42
[76]罗敏霞.可计算理论的研究内容及应用.运城学院学报, 2003, 21(5): 5-7
[77]王晓东.计算机算法设计与分析.北京:电子工业出版社, 2001
[78]徐云. SAT问题的随机算法及其相变现象研究[博士学位论文].中国科技技术大学图书馆. 2002
[79]王凌.智能优化算法及其应用.北京:清华大学出版社, 2001
[80]杨东屏,李昂生.可计算理论.北京:科学出版社,1999
[81]贲可荣,孙宁.计算机科学中的待解问题综述.计算机工程与科学, 2005, 27(10): 3-4
[82]王凌.智能优化算法及其应用.北京:清华大学出版社, 2003
[83]徐成贤,陈志平,李乃成.近代优化方法.北京:科学出版社, 2002
[84]曾玉华.全局最优化的随机型方法综述.宁波工程学院学报, 2006, 18(2): 9-12
[85] Zbigniew M, David B. F著,曹宏庆,李艳,董红斌,吴志健译.如何求解问题—现代启发式方法.北京:中国水利水电出版社, 2003
[86] Kirkpartick S, Gelatt C D, Vecchi M P. Optimization by simulated annealing. Science, 1983, 220: 671-680
[87]周明,孙树栋.遗传算法原理及应用.北京:国防工业出版社,1999
[88] Holland J H. Adaptation in natural and artificial systems. Boston: MIT Press, 1992
[89] Fogel D B. An introduction to simulated evolutionary optimization. IEEE Transactions on Neural Networks, 1994, 5(1):3-14
[90] Fogel D B. Applying evolutionary programming to selected traveling salesman problems. Cybernetics and System, 1993, 24: 27-36
[91] Kennedy J, Eberhart R C. Particle swarm optimization. In: Proceedings of IEEE International Conference on Neural Networks, IV. Piscataway, NJ: IEEE Service Center, 1995. 1942-1948
[92] Eberhart R C, Shi Y. Particle swarm optimization: developments, applications and resources. In: Proceedings of Congress on Evolutionary Computation 2001. Piscataway, NJ: IEEE Press, 2001. 81-86
[93]陈冬芳,薛继伟,张漫.全局最优化算法及其应用.大庆石油学院学报, 2005, 29(1): 89-93
[94] Nourani Y, Andresen B. A comparison of simulated annealing cooling strategies. Journal ofPhysics A: Mathematical and General, 1998, 41: 8373-8385
[95] Ali M, T?rn A, Viitanen S. A direct search simulated annealing algorithm for optimization involving continuous variables. Computers & Operations Research, 2002, 29(1): 87-102
[96] Wah B W, Chang Y-J. Trace-based methods for solving nonlinear global optimization and satisfiability problems. Journal of Global Optimization, 1997, 10(2): 107-141
[97] Varanelli J M, Cohoon J P. A two-stage simulated annealing methodology. In: Proceedings of the 5th Great Lakes Symposium on VLSI. USA: Buffalo, 1995. 50-53
[98] Varanelli J M. On the acceleration of simulated annealing. USA: University of Virginia, 1996
[99] Diekmann R, Lüling R, Simon J. Problem independent distributed simulated annealing and its applications. Applied Simulated Annealing, Lecture Notes in Economics and Mathematical Systems LNEMS 396, Springer Verlag, 1993. 17-44
[100] Glover F. Tabu search—Part I. ORSA Journal on Computing, 1989, 1: 190-206
[101] Tan P H, Rasmussen L K. Tabu search multi-user detection in CDMA. Radio Vetenskap och Kommunikation. Sweden: Stockholm, 2002. 744-748
[102] Tan P H, Rasmussen L K. A reactive Tabu search heuristic for multi-user detection in CDMA. ISIT2002. Switzerland: Lausanne, 2002. 472-478
[103] Niar S, Freville A. A parallel Tabu search algorithm for the 0-1 multidimensional knapsack problem. In: Proceedings of 11th International Parallel Processing Symposium (IPPS’97), Switzerland, Geneva, IEEE, 1997. 512-516
[104] Watson J P, Whitley L D, Howe A E. A dynamic model of tabu search for the job-shop scheduling problem. In: Proceedings of the 1st Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA2003). Netherlands: Kluwer Academic Publishers, 2003. 320-336
[105]黄文奇,许如初.近世计算理论导引--NP难度问题的背景、前景及其求解算法研究.北京:科学出版社, 2004.
[106]李未,黄文奇.一种求解合取范式可满足性问题的数学物理方法.中国科学(A辑), 1994, 24(11): 1208-1217
[107] Huang W, Li W. A hopeful CNF-SAT algorithm-its high efficiency, industrial application and limitation. Journal of Computer Science and Technology, 1998, 13(l): 9-12
[108]黄文奇,金人超.求解SAT问题的拟物拟人算法―Solar.中国科学(E辑), 1997, 27(2): 179-186
[109] Holland J H. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control and artificial intelligence. Ann Arbor, MI: University of Michigan Press, 1975
[110] Butz M V, Goldberg D E, Stolzmann W. The anticipatory classifier system and genetic generalization. Natural Computing, 2002, 1(4): 427-467
[111] De Jong K A, Spears W M. A formal analysis of the role of multi-point crossover in genetic algorithms. Annals of Mathematzcs and Artficzal, 1992, 5(1):1-26
[112] Grefenstette J. Optimization of control parameters for genetic algorithms. IEEE Transactions on System, Man, and Cybernetics, 1986, SMC-16 (1): 122-128
[113] Le Grand S M, Merz K M. The application of the genetic algorithm to the minimization of potential energy functions. The Journal of Global Optimization, 1993, 3: 49-66
[114] Dandekar T, Argos P. Folding the main chain of small proteins with the genetic algorithm. Journal of Molecular Biology, 1994, 236(3): 844-861
[115] Dorigo M, Maniezzo V, Colomi A. The ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics-Part B, 1996, 26(l): 29-41
[116] Dorigo M, Caro G D, Gambardella L. M. Ant algorithms for discrete optimization. artificial life, 1999, 5(2): 137-172
[117] Dorigo M, Gambardella L M. Ant colonies for the traveling salesman problem. BioSystems, 1997, 43(2): 73-81
[118] Gambardella L M, Taillard E, Dorigo M. Ant colonies for the quadratic assignment problem. Journal of the Operational Research Society, 1999, 50(2): 167-176
[119] Colorni A, Dorigo M, Trubian M. Ant system for job-shop scheduling. JORBEL Belgian Journal of Operations Research, Statistics and Computer Science 1994, 34(1): 3953
[120] Costa D, Hertz A. Ants can color graphs. Journal of the Operational Research Society, 1997, 48(3): 295.305
[121] Huang W, Kang Y. A heuristic quasi-physical strategy for solving disks packing problem. Simulation Modelling Practice and Theory, 2002, 10: 195-207
[122] Huang W, Kang Y. A short note on a simple search heuristic for the disks packing problem. Annals of Operations Research, 2004, 131: 101-108
[123] Huang W Q, Li Y, Akeb H, et al. Greedy algorithms for packing unequal circles into a rectangular container. Journal of the Operational Research Society, 2005, 56: 539-548
[124] Huang W, Li Y, Li C, et al. New heuristic for packing unequal circles into a circular container. Computers & Operations Research, 2006, 33: 2125-2142
[125]陈矛,黄文奇.求解VLSI布局问题的启发式算法.计算机科学, 2006, 33(3): 197-199
[126]黄文奇.处理NP难度问题的拟物和拟人方法.国际离散数学与算法研讨会文集.广州:暨南大学出版社, 1994. 85-88
[127]赵孝武,黄文奇.关于SAT问题物理模型猜想的一个反例.华中理工大学学报. 2000, 28(11): 25-27
[128]黄文奇.求解Covering问题的拟物方法―NP难度问题的一个处理途径.计算机学报, 1989, (8): 610-616
[129]冯玉才,黄文奇,周旋.求解雷达群问题的拟物算法.中国科学(E辑), 1995, 25(9): 982-988
[130]黄文奇,吴玉清.另辟蹊径求解工厂作业调度问题.计算机应用, 2003, 23: 141-142
[131] Huang W, Chen M. Note on: an improved algorithm for the packing of unequal circles within a larger containing circle. Computers & Industrial engineering. 2006, 50:338~344
[132]钱志勤,腾弘飞,孙治国.人机交互的遗传算法及其在约束布局优化中的应用.计算机学报, 2001, 24 (5): 553-559
[133] Szykman S, Cagan J. Constrained three-dimensional component layout using simulated annealing. Journal of Mechanical Design, Transactions of the ASME, 1997, 119 (1): 28-35
[134] Schnecke V, Vornberger O. Hybrid genetic algorithms for constrained placement problems. IEEE Trans Evolutionary Computation, 1997, 1 (4): 266-277
[135] Chaudhary K, KuhErnest S. RITUAL: A performance-driven placement algorithm. IEEE Trans Circuits and System II: Analog and Digital Signal Processing, 1992, 39 (11): 825- 840
[136] Teng H F, Sun S L, Ge W H, et al. Layout optimization for the dishes installed on a rotating table. Science in China (Series A), 1994, 37 (10): 1272-1280
[137]唐飞,腾弘飞.一种改进的遗传算法及其在布局优化中的应用.软件学报, 1999, 10(10): 1096-1102
[138]李宁,刘飞,孙德宝.基于带变异算子粒子群优化算法的约束布局优化研究.计算机学报, 2004, 27 (7): 897-903
[139] Li M S, Klimov D K, Thirumalai D. Folding in lattice models with side chains. Computer Physics Communications, 2002, 147: 625-628
[140] Agarwala R, Batzoglon S, Dancik V, et al. Local rules for protein folding on a triangular lattice and generalized hydrophobicity in the HP model. Journal of Computational Chemistry, 1997, 4 (3): 275-296
[141] Chen M, Huang W. A branch and bound algorithm for the protein folding problem in the HP lattice model. Genomics, Proteomics & Bioinformatics. 2005, 3(4): 225-230
[142] Rosenbluth M N, Rosenbluth A W. Monte Carlo calculation of the average extension of molecular chains. Journal of Chemical Physics, 1955, 23(2): 356-359
[143] Wall F T, Erpenbeck J J. New method for the statistical computation of polymer dimensions. Journal of Chemical Physics, 1959, 30(10): 634-637
[144] Frauenkron H, Bastolla U, Gerstner E, et al. New Monte Carlo algorithm for protein folding Physical Review Letters, 1998, 80(14): 3149-3152
[145] Yue K, Fiebig K M, Thomas P D, et al. A test of lattice protein folding algorithms. Proceedingsof the National Academy of Sciences of USA, 1995, 92: 325-329
[146] M.阿佛里耳著,李元熹,陈开明,魏国华等译.非线性规划-分析与方法(下册).上海:上海科学技术出版社, 1980
[147]席少霖,赵凤治.最优化计算方法.上海:上海科学技术出版社, 1983
[148] Chen M, Huang W. Heuristic algorithm for off-lattice protein folding problem. Journal of Zhejiang University SCIENCE B. 2006, 7(1): 7-12
[149] Kang L. Non-numerical parallel algorithms: simulated annealing. Moscow: Science Press, 1998
[150] Kim S Y, Lee S B, Lee J. Structure optimization by conformational space annealing in an off-lattice protein model. Physical Review E, 2005, 72:011916
[151] Huang W, Chen M, LüZ. Energy optimization for off-lattice protein folding. Physical Review E. 2006, 74: 041907
[2]朱杰.生物信息学的研究现状及其发展问题的探讨.生物信息学, 2005, 3: 185-188
[3] Creighton T E. Protein folding. New York: Freeman, 1992
[4]邹承鲁.第二遗传密码:新生肤链及蛋白质折叠的研究,第一版.长沙:湖南科学技术出版社, 1997
[5]赵南明,周海梦.生物物理学,第一版.北京:高等教育出版社, 2000
[6]邹承餐,王志珍.立足国内走向世界从吴宪教授六十四年前一篇论文的重新发表谈起.生理科学进展, 1996, 27(1): 5-6
[7] Anfinsen C B. Principles that govern the folding of protein chains. Science, 1973, 181(96): 223-230
[8]阎隆飞,孙之荣.蛋白质分子结构.北京:清华大学出版社,1999
[9]刘东升,王金凤.结构基因组学研究与核磁共振.生物化学与生物物理进展, 2001, 28(6):827-831
[10] Swiss-Prot. Swiss-Prot protein knowledgebase release 49.5 statistics [EB/OL]. http://www. expasy.ch /sprot/relnotes/relstat.htm
[11] Cynthia G, Jambeck P. Developing bioinformatics computer skills, 1st edition. New York: O'Reilly Media, 2001
[12]靳利霞,唐焕文.蛋白质结构预测方法简述.自然杂志,2003, 23(4): 217-221
[13]殷志祥.蛋白质结构预测方法的研究进展.计算机工程与应用,2004,20:54-57
[14] Luo L F. The time scale of protein simple model of chaperones. Acta SNUN, 1994, 25:52-56
[15] Haknovich E I, Rutin A M. Formation of unique structure in polypeptide chains. Biophysical Chemistry, 1989, 34:187-193
[16] Ponnuswamy P K. Hydrophobic characteristics of folded protein. Progress in Biophysics & Molecular Biology, 1993, 59(1): 57-103
[17] Philip E B, Helge W. Structural bioinformatics. Chichester: John Wiley & Sons, 2003
[18] Tsai C S. An Introduction to computational biochemistry. New York: Wiley-Liss, 2002
[19]宁正元,林世强.蛋白质结构的预测及其应用.福建农林大学学报(自然科学版), 2006, 35(3):308-313
[20] Dill K A. Theory for the folding and stability of globular proteins. Biochemistry, 1985, 24: 1501-1509
[21] Dill K A, Bromberg S, Yue K, et al. Principles of protein folding: A perspective from simple exactmodels. Protein Science, 1995, 4: 561-602
[22] Dill K A, Fiebig K M, Chan H S. Cooperativity in protein folding Kinetics. Proceedings of the National Academy of Sciences of USA, 1993, 90: 1942-1946
[23] Hunt N G, Gregoret L M, Cohen F E. The origin of protein secondary structure: effects of packing density and hydrogen bonding studies by a fast conformational search. Journal of Molecular Biology, 1994, 241: 214-225
[24] Sali A, Shakhnovich E I, Karplus M. Kinetics of protein folding. A lattice model study of the requirements for folding to the native state. Journal of Molecular Biology, 1994, 235: 1614-1636
[25] Yee D P, Chan H S, Havel T F, et al. Does compactness induce secondary structure in proteins? Journal of Molecular Biology, 1994, 241:557-573
[26] Gutin A M, Abkevich V I, Shakhnovich E I. Evolution like selection of fast folding model proteins. Proceedings of the National Academy of Sciences of USA, 1995, 92: 1282-1286
[27] Gutin A M, Abkevich V I, Shakhnovich E I. Is burst hydrophobic collapse necessary for protein folding? Biochemistry, 1995, 34: 3066-3076
[28] Dill K A. Dominant forces in protein folding. Biochemistry, 1990, 29(31):7133-7155
[29] Shih C T, Su Z Y, Gwan J F, et al. The HP model, designability, and alpha-helices in protein structures. Physical Review Letters, 2000, 84(2): 384-389
[30] Bonnie B, Tom L. Protein folding in the hydrophobic-hydrophilic model is NP-complete. RECOMB 98. New York. 1998. 30-39
[31] Garey M R, Johnson D S. Computer and intractability: a guide to the theory of NP-Completeness. San Francisco: Freeman, 1978
[32] Hochbaum D S, Maass W. Approximation schemes for covering and packing problems in image processing and VLSI, Journal of the Association for Computing Machinery, 1985, 32 (1):130–136
[33] Unger R, Moult J. Genetic algorithms for protein folding simulations. Journal of Molecular Biology, 1993, 231: 75-81
[34] Beutler T, Dill K. A fast conformational search strategy for finding low energy structures of model proteins. Protein Science, 1996, 5: 2037- 2043
[35] Toma L, Toma S. Contact interactions method: A new algorithm for protein folding simulations. Protein Science, 1996, 5: 147- 153
[36] Bastolla U, Frauenkron H, Gerstner E, et al. Testing a new Monte Carlo algorithm for protein folding. PROTEINS: Structure, Function & Genetics, 1998, 32: 52-66
[37] Irb?ck A. Monte Carlo approach to biopolymers and protein folding. Singapore: World Scientific, 1998. 98-109
[38]解伟,王翼飞.蛋白质折叠的计算机模拟.上海大学学报(自然科学版),2000, 6(2): 145-149
[39]解伟,王翼飞.蛋白质折叠的三维计算机模拟.上海大学学报(自然科学版), 2000, 6(6):548-550
[40]王敞,陈增强,袁著社.基于并行遗传算法的蛋白质空间结构预测.计算机科学,2003, 30(7): 147-149
[41]方茜,朱正佑,王翼飞.应用于蛋白质折叠模拟的三种新蒙特卡罗方法的比较.上海大学学报(自然科学版), 2004, 10(5): 526-530
[42] Huang J, Shi F, Zhou H B. Mixed search algorithm for protein folding. Wuhan University Journal of Natural Science. 2003, 8(3A):765-768
[43] Rainer K, Thomas D. Improving genetic algorithms for protein folding simulations by systematic crossover. Biosystems, 1999, 50:17-25
[44] Chou C I, Han R S, Li S P, et al. Guided simulated annealing method for optimization problem. Physical Review E, 2003, 67: 066704
[45] Faming L, Wing H W. Evolutionary Monte Carlo for protein folding simulations. Journal of Chemical Physics, 2001, 115(7):3374-3380
[46] Iba Y, Chikenji G, Kikuchi M. Simulation of lattice polymers with Multi-Self-Overlap ensemble. Journal Physics Society Japan, 1998, 67(10): 3327-3330
[47] Chikenji G, Kikuchi M, Iba Y. Mutlti-Self-Overlap ensemble for protein folding: ground state search and thermodynamics. Physical Review Letters, 1999, 83(9): 1886-1889
[48] Beutler T C. Dill K A. A fast conformational search strategy for finding low energy structures of model proteins. Protein Science, 1996, 5(10): 2037-2043
[49] Junni L Z, Jun S L. A new sequential importance sampling method and its application to the two-dimensional hydrophobic-hydrophilic model. Journal of Chemical Physics, 2002, 117(7): 3492-3498
[50] Grassberger P. Recursive sampling of random-walks: self-avoiding walks in disordered media. Journal of Physics. A. 1993, 26: 1023
[51] Grassberger P, Hegger R. Simulations of three-dimensional Theta polymers. Journal of Chemical Physics, 1995, 102(17): 6881-6899
[52] Grassberger P. Pruned-enriched Rosenbluth method: simulations ofθpolymers of chain length up to 1000000. Physical Review E, 1997, 56(3): 3682-3693
[53] Hsu H P, Mehra V, Nadler W, et al. Growth algorithms for lattice heteropolymers at low temperatures. Journal of Chemical Physics, 2003, 118(1): 444-452
[54] Hsu H P, Mehra V, Nadler W, et al. A Growth-based optimization algorithm for lattice heteropoiymers. Physical Review E, 2003, 68(2): 037703
[55] Huang W, LüZ. Personification algorithm for protein folding problem: improvements in PERM. Chinese Science Bulletin, 2004, 49 (19):2092-2096
[56] Huang W, LüZ, Shi H. Growth algorithm for finding low energy configurations of simple latticeproteins. Physical Review E, 2005, 72: 016704
[57] Stillinger F H, Gordon T H, Hirshfeld C L. Toy model for protein folding. Physical Review E, 1993, 48(2):1469 -1477
[58] Head-Gordon T, Stillinger F H. Optimal neural networks for protein-structure prediction. Physical Review E, 1993, 48: 1502-1515
[59] Stillinger F H. Collective aspects of protein folding illustrated by a toy model. Physical Review E, 1995, 52(3): 2872-2877
[60] Liang F. Annealing contour Monte Carlo algorithm for structure optimization in an off-lattice protein model. Journal of Chemical Physics, 2004, 120(14): 6756-6763
[61] Irb?ck A, Peterson C, Potthast F, et al. Local interactions and protein folding: a three-dimensional off-lattice approach. Journal of Chemical Physics, 1997, 107:273-282.
[62] Irb?ck A, Peterson C, Potthast F. Identification of amino acid sequences with good folding properties in an off-lattice model. Physical Review E, 1997, 55(1): 860-867
[63] Irb?ck A, Peterson C, Potthast F. Studies of an off-lattice model for protein folding: sequence dependence and improved sampling at finite temperature. Journal of Chemical Physics, 1995, 103: 10298-10305
[64] Torcini A, Livi R, Politi A. A dynamical approach to protein folding. The Journal of Biological Physics, 2001, 27: 181-187
[65] Gorse D. Global minimization of an off-lattice potential energy function using a chaperone-based refolding method. Biopolymers, 2001, 59: 411-426
[66] Gorse D. Application of chaperone-based refolding method to two-and three-dimensional off-lattice protein models. Biopolymers, 2002, 64: 146-160
[67] Hsu H P, Vishal M, Grassberger P. Structure optimization in an off-lattice protein model. Physical Review E, 2003, 68: 037703
[68] Bachmann M, Arkin H, Janke W. Multicanonical study of coarse-grained off-lattice models for folding heteropolymers. Physical Review E, 2005, 71:031906
[69] Lee J, Scheraga H A, Rackovsky S. New optimization method for conformational energy calculations on polypeptides: conformational space annealing. Journal of Computational Chemistry, 1997, 18: 1222-1232
[70] Lee J, Scheraga H A. Conformational space annealing by parallel computations: extensive conformational search of Metenkephalin and of the 20-residue membrane-bound portion of melittin. International Journal of Quantum Chemistry, 1999, 75:255-265
[71] Lee J, Liwo A, Scheraga H A. Energy-based de novo protein folding by conformational space annealing and an off-lattice united-residue force field: Application to the 10-55 fragment of staphylococcal protein A and to apo calbindin D9K. Proceedings of the National Academy ofSciences of USA, 1999, 96: 2025-2030
[72] Kim S Y, Lee S J, Lee J. The energy landscape of a BLN protein with beta hairpin shape, Journal of the Korean Physical Society, 2004, 44: 589-593
[73]黄文奇,詹叔浩.求解Packing问题的拟物方法.应用数学学报, 1979, 2 (2): 176-180
[74]黄文奇,许如初.支持求解圆形Packing的两个拟人策略中国科学(E辑), 1999,27(2): 347-353
[75]张鸣华.可计算性理论.北京:清华大学出版社,1984. 15-42
[76]罗敏霞.可计算理论的研究内容及应用.运城学院学报, 2003, 21(5): 5-7
[77]王晓东.计算机算法设计与分析.北京:电子工业出版社, 2001
[78]徐云. SAT问题的随机算法及其相变现象研究[博士学位论文].中国科技技术大学图书馆. 2002
[79]王凌.智能优化算法及其应用.北京:清华大学出版社, 2001
[80]杨东屏,李昂生.可计算理论.北京:科学出版社,1999
[81]贲可荣,孙宁.计算机科学中的待解问题综述.计算机工程与科学, 2005, 27(10): 3-4
[82]王凌.智能优化算法及其应用.北京:清华大学出版社, 2003
[83]徐成贤,陈志平,李乃成.近代优化方法.北京:科学出版社, 2002
[84]曾玉华.全局最优化的随机型方法综述.宁波工程学院学报, 2006, 18(2): 9-12
[85] Zbigniew M, David B. F著,曹宏庆,李艳,董红斌,吴志健译.如何求解问题—现代启发式方法.北京:中国水利水电出版社, 2003
[86] Kirkpartick S, Gelatt C D, Vecchi M P. Optimization by simulated annealing. Science, 1983, 220: 671-680
[87]周明,孙树栋.遗传算法原理及应用.北京:国防工业出版社,1999
[88] Holland J H. Adaptation in natural and artificial systems. Boston: MIT Press, 1992
[89] Fogel D B. An introduction to simulated evolutionary optimization. IEEE Transactions on Neural Networks, 1994, 5(1):3-14
[90] Fogel D B. Applying evolutionary programming to selected traveling salesman problems. Cybernetics and System, 1993, 24: 27-36
[91] Kennedy J, Eberhart R C. Particle swarm optimization. In: Proceedings of IEEE International Conference on Neural Networks, IV. Piscataway, NJ: IEEE Service Center, 1995. 1942-1948
[92] Eberhart R C, Shi Y. Particle swarm optimization: developments, applications and resources. In: Proceedings of Congress on Evolutionary Computation 2001. Piscataway, NJ: IEEE Press, 2001. 81-86
[93]陈冬芳,薛继伟,张漫.全局最优化算法及其应用.大庆石油学院学报, 2005, 29(1): 89-93
[94] Nourani Y, Andresen B. A comparison of simulated annealing cooling strategies. Journal ofPhysics A: Mathematical and General, 1998, 41: 8373-8385
[95] Ali M, T?rn A, Viitanen S. A direct search simulated annealing algorithm for optimization involving continuous variables. Computers & Operations Research, 2002, 29(1): 87-102
[96] Wah B W, Chang Y-J. Trace-based methods for solving nonlinear global optimization and satisfiability problems. Journal of Global Optimization, 1997, 10(2): 107-141
[97] Varanelli J M, Cohoon J P. A two-stage simulated annealing methodology. In: Proceedings of the 5th Great Lakes Symposium on VLSI. USA: Buffalo, 1995. 50-53
[98] Varanelli J M. On the acceleration of simulated annealing. USA: University of Virginia, 1996
[99] Diekmann R, Lüling R, Simon J. Problem independent distributed simulated annealing and its applications. Applied Simulated Annealing, Lecture Notes in Economics and Mathematical Systems LNEMS 396, Springer Verlag, 1993. 17-44
[100] Glover F. Tabu search—Part I. ORSA Journal on Computing, 1989, 1: 190-206
[101] Tan P H, Rasmussen L K. Tabu search multi-user detection in CDMA. Radio Vetenskap och Kommunikation. Sweden: Stockholm, 2002. 744-748
[102] Tan P H, Rasmussen L K. A reactive Tabu search heuristic for multi-user detection in CDMA. ISIT2002. Switzerland: Lausanne, 2002. 472-478
[103] Niar S, Freville A. A parallel Tabu search algorithm for the 0-1 multidimensional knapsack problem. In: Proceedings of 11th International Parallel Processing Symposium (IPPS’97), Switzerland, Geneva, IEEE, 1997. 512-516
[104] Watson J P, Whitley L D, Howe A E. A dynamic model of tabu search for the job-shop scheduling problem. In: Proceedings of the 1st Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA2003). Netherlands: Kluwer Academic Publishers, 2003. 320-336
[105]黄文奇,许如初.近世计算理论导引--NP难度问题的背景、前景及其求解算法研究.北京:科学出版社, 2004.
[106]李未,黄文奇.一种求解合取范式可满足性问题的数学物理方法.中国科学(A辑), 1994, 24(11): 1208-1217
[107] Huang W, Li W. A hopeful CNF-SAT algorithm-its high efficiency, industrial application and limitation. Journal of Computer Science and Technology, 1998, 13(l): 9-12
[108]黄文奇,金人超.求解SAT问题的拟物拟人算法―Solar.中国科学(E辑), 1997, 27(2): 179-186
[109] Holland J H. Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control and artificial intelligence. Ann Arbor, MI: University of Michigan Press, 1975
[110] Butz M V, Goldberg D E, Stolzmann W. The anticipatory classifier system and genetic generalization. Natural Computing, 2002, 1(4): 427-467
[111] De Jong K A, Spears W M. A formal analysis of the role of multi-point crossover in genetic algorithms. Annals of Mathematzcs and Artficzal, 1992, 5(1):1-26
[112] Grefenstette J. Optimization of control parameters for genetic algorithms. IEEE Transactions on System, Man, and Cybernetics, 1986, SMC-16 (1): 122-128
[113] Le Grand S M, Merz K M. The application of the genetic algorithm to the minimization of potential energy functions. The Journal of Global Optimization, 1993, 3: 49-66
[114] Dandekar T, Argos P. Folding the main chain of small proteins with the genetic algorithm. Journal of Molecular Biology, 1994, 236(3): 844-861
[115] Dorigo M, Maniezzo V, Colomi A. The ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics-Part B, 1996, 26(l): 29-41
[116] Dorigo M, Caro G D, Gambardella L. M. Ant algorithms for discrete optimization. artificial life, 1999, 5(2): 137-172
[117] Dorigo M, Gambardella L M. Ant colonies for the traveling salesman problem. BioSystems, 1997, 43(2): 73-81
[118] Gambardella L M, Taillard E, Dorigo M. Ant colonies for the quadratic assignment problem. Journal of the Operational Research Society, 1999, 50(2): 167-176
[119] Colorni A, Dorigo M, Trubian M. Ant system for job-shop scheduling. JORBEL Belgian Journal of Operations Research, Statistics and Computer Science 1994, 34(1): 3953
[120] Costa D, Hertz A. Ants can color graphs. Journal of the Operational Research Society, 1997, 48(3): 295.305
[121] Huang W, Kang Y. A heuristic quasi-physical strategy for solving disks packing problem. Simulation Modelling Practice and Theory, 2002, 10: 195-207
[122] Huang W, Kang Y. A short note on a simple search heuristic for the disks packing problem. Annals of Operations Research, 2004, 131: 101-108
[123] Huang W Q, Li Y, Akeb H, et al. Greedy algorithms for packing unequal circles into a rectangular container. Journal of the Operational Research Society, 2005, 56: 539-548
[124] Huang W, Li Y, Li C, et al. New heuristic for packing unequal circles into a circular container. Computers & Operations Research, 2006, 33: 2125-2142
[125]陈矛,黄文奇.求解VLSI布局问题的启发式算法.计算机科学, 2006, 33(3): 197-199
[126]黄文奇.处理NP难度问题的拟物和拟人方法.国际离散数学与算法研讨会文集.广州:暨南大学出版社, 1994. 85-88
[127]赵孝武,黄文奇.关于SAT问题物理模型猜想的一个反例.华中理工大学学报. 2000, 28(11): 25-27
[128]黄文奇.求解Covering问题的拟物方法―NP难度问题的一个处理途径.计算机学报, 1989, (8): 610-616
[129]冯玉才,黄文奇,周旋.求解雷达群问题的拟物算法.中国科学(E辑), 1995, 25(9): 982-988
[130]黄文奇,吴玉清.另辟蹊径求解工厂作业调度问题.计算机应用, 2003, 23: 141-142
[131] Huang W, Chen M. Note on: an improved algorithm for the packing of unequal circles within a larger containing circle. Computers & Industrial engineering. 2006, 50:338~344
[132]钱志勤,腾弘飞,孙治国.人机交互的遗传算法及其在约束布局优化中的应用.计算机学报, 2001, 24 (5): 553-559
[133] Szykman S, Cagan J. Constrained three-dimensional component layout using simulated annealing. Journal of Mechanical Design, Transactions of the ASME, 1997, 119 (1): 28-35
[134] Schnecke V, Vornberger O. Hybrid genetic algorithms for constrained placement problems. IEEE Trans Evolutionary Computation, 1997, 1 (4): 266-277
[135] Chaudhary K, KuhErnest S. RITUAL: A performance-driven placement algorithm. IEEE Trans Circuits and System II: Analog and Digital Signal Processing, 1992, 39 (11): 825- 840
[136] Teng H F, Sun S L, Ge W H, et al. Layout optimization for the dishes installed on a rotating table. Science in China (Series A), 1994, 37 (10): 1272-1280
[137]唐飞,腾弘飞.一种改进的遗传算法及其在布局优化中的应用.软件学报, 1999, 10(10): 1096-1102
[138]李宁,刘飞,孙德宝.基于带变异算子粒子群优化算法的约束布局优化研究.计算机学报, 2004, 27 (7): 897-903
[139] Li M S, Klimov D K, Thirumalai D. Folding in lattice models with side chains. Computer Physics Communications, 2002, 147: 625-628
[140] Agarwala R, Batzoglon S, Dancik V, et al. Local rules for protein folding on a triangular lattice and generalized hydrophobicity in the HP model. Journal of Computational Chemistry, 1997, 4 (3): 275-296
[141] Chen M, Huang W. A branch and bound algorithm for the protein folding problem in the HP lattice model. Genomics, Proteomics & Bioinformatics. 2005, 3(4): 225-230
[142] Rosenbluth M N, Rosenbluth A W. Monte Carlo calculation of the average extension of molecular chains. Journal of Chemical Physics, 1955, 23(2): 356-359
[143] Wall F T, Erpenbeck J J. New method for the statistical computation of polymer dimensions. Journal of Chemical Physics, 1959, 30(10): 634-637
[144] Frauenkron H, Bastolla U, Gerstner E, et al. New Monte Carlo algorithm for protein folding Physical Review Letters, 1998, 80(14): 3149-3152
[145] Yue K, Fiebig K M, Thomas P D, et al. A test of lattice protein folding algorithms. Proceedingsof the National Academy of Sciences of USA, 1995, 92: 325-329
[146] M.阿佛里耳著,李元熹,陈开明,魏国华等译.非线性规划-分析与方法(下册).上海:上海科学技术出版社, 1980
[147]席少霖,赵凤治.最优化计算方法.上海:上海科学技术出版社, 1983
[148] Chen M, Huang W. Heuristic algorithm for off-lattice protein folding problem. Journal of Zhejiang University SCIENCE B. 2006, 7(1): 7-12
[149] Kang L. Non-numerical parallel algorithms: simulated annealing. Moscow: Science Press, 1998
[150] Kim S Y, Lee S B, Lee J. Structure optimization by conformational space annealing in an off-lattice protein model. Physical Review E, 2005, 72:011916
[151] Huang W, Chen M, LüZ. Energy optimization for off-lattice protein folding. Physical Review E. 2006, 74: 041907
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |