求解蛋白质结构预测问题及矩形packing问题的启发式算法
|
摘要
求解NP难度问题一直是计算机科学技术的一个瓶颈任务。近年来的研究表明,对于NP难度问题可能根本不存在既完整严格又不太慢的求解算法。因此,这类问题的求解方法多为启发式方法。蛋白质结构预测问题和矩形packing问题都是NP难度问题。设计求解它们的快速而有效的算法具有深刻的理论意义和普遍的实用价值。受自然界和人类社会中智慧的启发,提出了求解这两类NP难度问题的有效的启发式算法,所做的主要工作有:
对于一个具有两种氨基酸(疏水氨基酸和亲水氨基酸)的三维非格点的蛋白质AB模型,受物理世界物体间相互作用的规律的启发,提出了该模型的蛋白质结构预测问题的拟物算法。结合本问题的一些启发式知识,获得了高效的启发式策略,包括初始构形的产生和跳坑策略,使得搜索过程尽量避免过早陷入局部极小点,即使到了局部极小点,能够使搜索过程跳出,将其引向前景更好的区域。结合这些启发式策略以及拟物算法得到了启发式拟物算法。该算法对文献中的氨基酸序列进行了实算,所得构形的最低能量比PERM+算法(即非格点的PERM(Pruned-Enriched Rosenbluth method)结合共轭梯度法)所得构形的最低能量更低。
提出了AB模型的蛋白质结构预测问题的启发式共轭梯度(HCG)算法。算法在三维欧氏空间中利用启发式的方法产生初始构形,然后用共轭梯度法优化低能状态,一旦计算陷入极小值的陷阱,则采用启发式的跳坑策略跳出局部极小点。将HCG算法应用到蛋白质AB模型中去预测和发现蛋白质结构。计算结果表明,对于链长为55的序列,HCG算法所得结果比当今国际文献中最先进的几个算法所得结果更好。
受PERM+算法的启发,给出了AB模型的基于面心立方体(FCC)格点的PERM++算法。该算法利用基于FCC格点的PERM算法产生初始构形,然后用共轭梯度法进一步优化低能状态。数值实验表明,PERM++算法的计算结果优于PERM+算法。
ELP方法在应用中存在一些缺陷,针对这些缺陷提出了基于拟物策略的局部搜索方法,将此方法同ELP方法相结合得到了改进的ELP算法(ELP+)。计算结果表明,对于部分氨基酸序列,ELP+算法找到了比PERM+算法、多正则(MUCA)Monte Carlo方法、势能曲面变平(ELP)方法、构形空间退火(CSA)算法等国际上最先进的一些算法给出的最低能量状态具有更低能量的构形。
使用拟人的策略,提出了基于欧氏距离的占角最大穴度优先的放置方法,为矩形packing问题的快速求解提供了一种高性能的启发式算法。算法的高效性通过应用于标准电路MCNC和GSRC得到了验证,其计算结果优于当今国际上已公开发表了的最先进的几个算法的结果。
基于拟人的思想,提出了带有预放置模块的布局问题的穴度算法及其改进的穴度算法。用标准电路MCNC对算法性能进行了测试,实算结果表明,改进的穴度算法比基于角模块表(CBL)和B*树型结构(B*-tree)表示的随机优化算法的计算结果都要好。
简而言之,我们对两类NP难度问题——蛋白质结构预测问题和矩形packing问题进行了分析和研究。受自然界、人类社会和具体问题的启发,为它们提出了一系列的有效求解算法。实践证明,这种模仿自然界物质运动和人类行为的方法是一个寻求高效算法的有效途径。这些方法对于研究其它NP难度问题的现实求解具有普遍的实际意义。然而求解蛋白质结构预测问题和矩形packing问题是复杂的开放性课题,其中还有很多问题有待于进一步研究和讨论。
Solving NP-hard problems is always the bottleneck task in the field of computer science and technology. In recent years, investigations show that for NP-hard problems, there may not exist an algorithm that is both complete and rigorous and not too slow. So its solution methods are generally heuristic. The protein structure prediction problem and the rectangles packing problem are NP-hard problems. Solving them has profound theoretical significance and universal practical value. Inspired by the wisdom of nature and human being, we proposed some effective heuristic algorithms to solve these two NP-hard problems. The main works are as follows:
A three-dimensional off-lattice protein AB model was studied, where two species of amino acids, hydrophobic and hydrophilic, were considered. Enlightened by the law of forces among things in the physical world, a corresponding quasi-physical algorithm was put forward for the protein structure prediction problem. By observing and learning from problem structure, high efficient heuristic strategies were presented, including producing the initial configurations and jumping out of traps. These approaches could effectively avoid falling into local minima, and even if the search fell into local minima, the calculation could get out of them and reached better prospects positions. The heuristic quasi-physical algorithm was proposed by integrating the heuristic strategies into the quasi-physical algorithm. For all instances in literature, the proposed algorithms found the configurations with lower energy than those obtained by PERM+, which integrated the off-lattice PERM (Pruned-Enriched Rosenbluth method) and conjugate gradient minimization.
A heuristic conjugate gradient (HCG) algorithm was presented for the protein structure prediction problem of the AB model. The algorithm firstly produced initial configurations in three-dimensional Euclidian space by the heuristic method, and the conjugate gradient minimization was then used to optimize low-energy configurations. Once the computation fell into the local minima, the heuristic off-trap strategy was used to get out of the predicament. The HCG algorithm was applied to the AB protein model to predict protein structure. The computing results showed that for sequence with length n=55, the HCG algorithm found the configurations with lower energy than those nowadays given in literature.
Inspired by the PERM+ algorithm, a so-called PERM++ algorithm based on face-centered-cubic (FCC) lattice was put forward to solve the protein structure prediction problem of the AB model. In PERM++, the initial configurations were produced by applying the PERM to the FCC lattice, and conjugate gradient minimization was then used to reach the minimum energy states. The numerical results showed that the performance of the PERM++ algorithm outperformed that of the PERM+.
A technical shortcoming in ELP was revealed. In order to overcome it, a local search method based on the quasi-physical strategy was presented. An improved ELP algorithm (ELP+) was proposed as the integration of the local search method and the ELP method. The calculating results showed that for several of amino acids chains studied, the ELP+ algorithm found the configurations with lower energy than those by PERM+, by multicanonical (MUCA) Monte Carlo method, by energy landscape paving (ELP) method, and by conformational space annealing (CSA) algorithm, respectively.
Based on the quasi-human strategy, we proposed the so-called corner-occupying and the largest hole degree first placement policy based on Euclidian distance. An effective heuristic algorithm was presented, and this algorithm could obtain the solution to the rectangles packing problem quickly. Experimental results on MCNC and GSRC benchmark circuits showed promising performance. As compared with other public algorithms, the proposed algorithms could get better results.
Finally, based on the quasi-human strategy, the hole degree algorithm and the improved hole degree algorithm were proposed to solve the modules placement problem with pre-placed modules. Experimental results on MCNC benchmark circuits demonstrated that the proposed heuristic deterministic algorithm was quite effective in solving the problem and outperformed the stochastic optimization placement algorithms based on corner block list (CBL) and B*-tree type representations, respectively.
In a word, two NP-hard problems, the protein structure prediction problem and the rectangles packing problem were studied in this dissertation. Inspired by nature, human being and problem structure, we put forward some effective algorithms to solve them. Experimental results showed that simulating the moves of things in nature and the actions of human being was an effective way of designing high-performance algorithms. These approaches have universal practical value for studying and solving other NP-hard problems. Since the protein structure prediction problem and the rectangles packing problem are open problems, there are still some other questions need to study.
对于一个具有两种氨基酸(疏水氨基酸和亲水氨基酸)的三维非格点的蛋白质AB模型,受物理世界物体间相互作用的规律的启发,提出了该模型的蛋白质结构预测问题的拟物算法。结合本问题的一些启发式知识,获得了高效的启发式策略,包括初始构形的产生和跳坑策略,使得搜索过程尽量避免过早陷入局部极小点,即使到了局部极小点,能够使搜索过程跳出,将其引向前景更好的区域。结合这些启发式策略以及拟物算法得到了启发式拟物算法。该算法对文献中的氨基酸序列进行了实算,所得构形的最低能量比PERM+算法(即非格点的PERM(Pruned-Enriched Rosenbluth method)结合共轭梯度法)所得构形的最低能量更低。
提出了AB模型的蛋白质结构预测问题的启发式共轭梯度(HCG)算法。算法在三维欧氏空间中利用启发式的方法产生初始构形,然后用共轭梯度法优化低能状态,一旦计算陷入极小值的陷阱,则采用启发式的跳坑策略跳出局部极小点。将HCG算法应用到蛋白质AB模型中去预测和发现蛋白质结构。计算结果表明,对于链长为55的序列,HCG算法所得结果比当今国际文献中最先进的几个算法所得结果更好。
受PERM+算法的启发,给出了AB模型的基于面心立方体(FCC)格点的PERM++算法。该算法利用基于FCC格点的PERM算法产生初始构形,然后用共轭梯度法进一步优化低能状态。数值实验表明,PERM++算法的计算结果优于PERM+算法。
ELP方法在应用中存在一些缺陷,针对这些缺陷提出了基于拟物策略的局部搜索方法,将此方法同ELP方法相结合得到了改进的ELP算法(ELP+)。计算结果表明,对于部分氨基酸序列,ELP+算法找到了比PERM+算法、多正则(MUCA)Monte Carlo方法、势能曲面变平(ELP)方法、构形空间退火(CSA)算法等国际上最先进的一些算法给出的最低能量状态具有更低能量的构形。
使用拟人的策略,提出了基于欧氏距离的占角最大穴度优先的放置方法,为矩形packing问题的快速求解提供了一种高性能的启发式算法。算法的高效性通过应用于标准电路MCNC和GSRC得到了验证,其计算结果优于当今国际上已公开发表了的最先进的几个算法的结果。
基于拟人的思想,提出了带有预放置模块的布局问题的穴度算法及其改进的穴度算法。用标准电路MCNC对算法性能进行了测试,实算结果表明,改进的穴度算法比基于角模块表(CBL)和B*树型结构(B*-tree)表示的随机优化算法的计算结果都要好。
简而言之,我们对两类NP难度问题——蛋白质结构预测问题和矩形packing问题进行了分析和研究。受自然界、人类社会和具体问题的启发,为它们提出了一系列的有效求解算法。实践证明,这种模仿自然界物质运动和人类行为的方法是一个寻求高效算法的有效途径。这些方法对于研究其它NP难度问题的现实求解具有普遍的实际意义。然而求解蛋白质结构预测问题和矩形packing问题是复杂的开放性课题,其中还有很多问题有待于进一步研究和讨论。
Solving NP-hard problems is always the bottleneck task in the field of computer science and technology. In recent years, investigations show that for NP-hard problems, there may not exist an algorithm that is both complete and rigorous and not too slow. So its solution methods are generally heuristic. The protein structure prediction problem and the rectangles packing problem are NP-hard problems. Solving them has profound theoretical significance and universal practical value. Inspired by the wisdom of nature and human being, we proposed some effective heuristic algorithms to solve these two NP-hard problems. The main works are as follows:
A three-dimensional off-lattice protein AB model was studied, where two species of amino acids, hydrophobic and hydrophilic, were considered. Enlightened by the law of forces among things in the physical world, a corresponding quasi-physical algorithm was put forward for the protein structure prediction problem. By observing and learning from problem structure, high efficient heuristic strategies were presented, including producing the initial configurations and jumping out of traps. These approaches could effectively avoid falling into local minima, and even if the search fell into local minima, the calculation could get out of them and reached better prospects positions. The heuristic quasi-physical algorithm was proposed by integrating the heuristic strategies into the quasi-physical algorithm. For all instances in literature, the proposed algorithms found the configurations with lower energy than those obtained by PERM+, which integrated the off-lattice PERM (Pruned-Enriched Rosenbluth method) and conjugate gradient minimization.
A heuristic conjugate gradient (HCG) algorithm was presented for the protein structure prediction problem of the AB model. The algorithm firstly produced initial configurations in three-dimensional Euclidian space by the heuristic method, and the conjugate gradient minimization was then used to optimize low-energy configurations. Once the computation fell into the local minima, the heuristic off-trap strategy was used to get out of the predicament. The HCG algorithm was applied to the AB protein model to predict protein structure. The computing results showed that for sequence with length n=55, the HCG algorithm found the configurations with lower energy than those nowadays given in literature.
Inspired by the PERM+ algorithm, a so-called PERM++ algorithm based on face-centered-cubic (FCC) lattice was put forward to solve the protein structure prediction problem of the AB model. In PERM++, the initial configurations were produced by applying the PERM to the FCC lattice, and conjugate gradient minimization was then used to reach the minimum energy states. The numerical results showed that the performance of the PERM++ algorithm outperformed that of the PERM+.
A technical shortcoming in ELP was revealed. In order to overcome it, a local search method based on the quasi-physical strategy was presented. An improved ELP algorithm (ELP+) was proposed as the integration of the local search method and the ELP method. The calculating results showed that for several of amino acids chains studied, the ELP+ algorithm found the configurations with lower energy than those by PERM+, by multicanonical (MUCA) Monte Carlo method, by energy landscape paving (ELP) method, and by conformational space annealing (CSA) algorithm, respectively.
Based on the quasi-human strategy, we proposed the so-called corner-occupying and the largest hole degree first placement policy based on Euclidian distance. An effective heuristic algorithm was presented, and this algorithm could obtain the solution to the rectangles packing problem quickly. Experimental results on MCNC and GSRC benchmark circuits showed promising performance. As compared with other public algorithms, the proposed algorithms could get better results.
Finally, based on the quasi-human strategy, the hole degree algorithm and the improved hole degree algorithm were proposed to solve the modules placement problem with pre-placed modules. Experimental results on MCNC benchmark circuits demonstrated that the proposed heuristic deterministic algorithm was quite effective in solving the problem and outperformed the stochastic optimization placement algorithms based on corner block list (CBL) and B*-tree type representations, respectively.
In a word, two NP-hard problems, the protein structure prediction problem and the rectangles packing problem were studied in this dissertation. Inspired by nature, human being and problem structure, we put forward some effective algorithms to solve them. Experimental results showed that simulating the moves of things in nature and the actions of human being was an effective way of designing high-performance algorithms. These approaches have universal practical value for studying and solving other NP-hard problems. Since the protein structure prediction problem and the rectangles packing problem are open problems, there are still some other questions need to study.
引文
[1] Turing A M. On computable numbers with an application to the entscheidungs problem. Proceedings of the London Mathematical Society, 1936, 42 (2): 230~265
[2] Garey M R, Jonhson D S著.计算机和难解性(NP完全理论导论).张立昂,沈泓,毕源章译.北京:科学出版社, 1987. 1~603
[3] Papadimitrion C H, Steiglitz K. Combinatorial optimization: Algorithms and complexity. New Jersey: Prentice Hall Inc, 1982. 1~298
[4] Hochbaum D S, Maass W. Approximation schemes for covering and packing problem in image processing and VLSI. Journal of the Association for Computing Machinery, 1985, 23 (1): 130~136
[5] Nilsson N J. Problem-solving methods in artificial intelligence. New York: McGraw-Hill, 1971. 1~14
[6] Osman H I. Metaheuristics: A bibliography. Annals of Operations Research, 1996, 63 (3): 513~623
[7] Manner R, Manderick B. Parallel problem solving from nature. North-Holland: Elsevier, 1992. 219~228
[8] Holland J H. Adaptation in natural and artificial systems. Ann Arbor: The University of Michigan Press, 1975. 1~34
[9] Goldberg D E. Genetic algorithms in search, optimization and machine learning. Addison: Wesley, 1989. 1~30
[10] Metropolis N, Rosenbluth A, Rosenbluth M A, et al. Equation of state calculations by fast computing machines. Journal of the Chemical Physics, 1953, 21 (6): 1087~1092
[11] Kirkpatrick S, Gelatt C D, Vecchi M P. Optimization by simulated annealing. Science, 1983, 220 (5): 671~689
[12] Van Luarhoven P J M, Aarts E H L. Simulated annealing: Theory and applications. Holland:Reidel D Publishing Company, 1987. 1~130
[13] Hopfield J, Tank D. Neural computation of decisions in optimization problems. Biological Cybernetics, 1985, 52 (3): 141~152
[14] Glover F, Greenberg H J. New approaches for heuristic search: A bilateral linkage with artificial intelligence. European Journal of Operational Research, 1989, 39 (2): 119~130
[15] Darrell W. An overview of evolutionary algorithms: Practical issues and common pitfalls. Information and Software Technology, 2001, 43 (14): 817~831
[16] Colorni A, Dorigo M, Maniezzo V. Distributed optimization by ant colonies. in: Varela F and Bourgings P, eds. Proceedings of the first European Conference on Artificial Life. Paris, France. 1991. Amsterdam: Elsevier Publishing, 1991. 134~142
[17]黄文奇,詹叔浩.求解packing问题的拟物方法.应用数学学报, 1979, 2 (2): 176~180
[18]黄文奇.求解packing问题的拟物方法——NP难问题的一个处理途径.计算机学报, 1989, 12 (8): 610~616
[19]黄文奇,陈亮.求解有关空间利用的调度问题的拟物方法.中国科学(A辑), 1991, 21 (3): 325~331
[20]李未,黄文奇.一种求解合取范式可满足问题的数学物理方法.中国科学(A辑), 1994, 24 (11): 1208~1217
[21]黄文奇,许如初.支持求解圆形packing问题的两个拟人策略.中国科学(E辑), 1999, 29 (4): 347~353
[22]黄文奇,金人超.求解SAT问题的拟物拟人算法——Solar.中国科学(E辑), 1997, 27 (2): 179~186
[23]黄文奇.处理NP难度问题的拟物和拟人方法.见:苏运霖主编.国际离散数学和算法研讨会议论文集.广州. 1994.广州:暨南大学出版社. 1994. 89~91
[24]黄文奇,许如初,陈卫东等.求解Packing及CNF-SAT问题的拟物拟人方法.华中理工大学学报, 1998, 26 (9): 5~7
[25]黄文奇,赵孝武.求解正交数组问题的拟物拟人算法.计算机研究与发展, 2002, 39 (2): 205~212
[26] Metropolis W, Ulam S. Monte Carlo method. Journal of the American Statistical Association, 1949, 44 (247): 335~341
[27] Li G J. Computational intelligent: An important field of research. Basic Study of Intelligent Computer’94. Beijing: Press of Tsinghua University, 1994. 9~12
[28] Linderoth J L, Savelsbergh M W. A computational study of search strategies for mixed integer programming. INFORMS Journal on Computing, 1998, 11 (2): 173~187
[29] Polya G. How to solve it. Princeton: Princeton University Press, 1948. 1~72
[30] Reeves C R. Model heuristic techniques for combinatorial problems. Oxford: Blackwell Scientific Publications, 1993. 1~55
[31]邢文训,谢金星.现代优化计算方法(第一版).北京:清华大学出版社, 1999. 1~293
[32]徐钟济.蒙特卡罗方法.上海:上海科学技术出版社, 1985. 1~28
[33] Huang W Q, Kang Y. A heuristic quasi-physical strategy for solving disks packing problem. Simulation Modeling Practice and Theory, 2002, 10 (4): 195~207
[34] Wang H Q, Huang W Q, Zhang Q, et al. An improved algorithm for the packing of unequal circles within a larger containing circle. European Journal of Operational Research, 2002, 141 (2): 440~453
[35]黄文奇,李庆华,余向东.求解空间Packing问题的拟物方法.应用数学学报, 1986, 9 (4): 443~453
[36] Miller R E, Thatcher J W. Complexity of computer computations. New York: Plenum Press, 1972. 1~105
[37] Cook S. The complexity of theorem proving procedures. in: Minker J, ed. Proceedings of the 3rd Annual ACM Symposium on the Theory of Computing. Shake heights: Ohio. 1971. New York: ACM Press, 1971. 151~158
[38] Karp R M. Reducibility among combinatorial problems. New York: Plenum Press, 1972. 2~6
[39]邹啸,陆祖宏,谢建明.生物信息学基础.北京:清华大学出版社, 2005. 1~77
[40] Anfinsen C B. Principles that govern the folding of protein chains. Science, 1973, 181(96): 223~230
[41]阎隆飞,孙之荣.蛋白质分子结构.北京:清华大学出版社. 1999. 1~100
[42] Michael J, Sternberg E. Progress in protein structure prediction: Assessment of CASP3. Current Opinion in Structure Biology, 1999, 9 (3): 368~373
[43]赵善荣,陈凯先.基于知识的蛋白质结构预测.生物化学与生物物理进展, 1995, 23 (5): 422~426
[44] Altshul A F, Gish W, Miller W. Basic local alignment search tool. Journal of Molecular Biology, 1990, 215 (3): 403~410
[45] Gribskov M, Mclachlan A. Profile analysis: Detection of distantly related proteins. Proceedings of the National Academy of Sciences, 1987, 84 (13): 4355~4358
[46] Krogh A, Brown M, Mian I. Hidden Markov models in computational biology: Application to protein modeling. Journal of Molecular Biology, 1996, 235 (5): 1501~1531
[47] Altshul S. Madden T. Gapped BLAST and PSI-BLAST: A new generation of protein database search programs. Nucleic Acids Research, 1997, 25 (17): 3389~3402
[48] Karplus K, Barrett C. Hidden Markov models for detecting remote protein homologies. Bioinformatics, 1998, 14 (10): 846~856
[49] Koehl P, Levitt M. Improved recognition of native-like protein structures using a family of designed sequences. Proceedings of the National Academy of Sciences, 2002, 99 (2): 691~696
[50] Koehl P, Levitt M. Protein topology and stability define the space of allowed sequences. Proceedings of the National Academy of Sciences, 2002, 99 (3): 1280~1285
[51] Murzin A, Brenner S. SCOP: A structural classification of protein database for the investigation of sequences and structures. Journal of Molecular Biology, 1995, 247 (4): 536~540
[52] Finkelstein A V, Ptitsyn O B. Why do globular proteins fit the limited set of folding patterns. Progress in Biophysics and Moleclar Biology, 1987, 50 (3): 171-190
[53] Chothia C. One thousand families for the molecular biologist. Nature, 1992, 357 (6379): 543~544
[54] Wang Z X. A re-estimation for the total numbers of protein folds and superfamilies. Protein Engineering, 1998, 11 (8): 621~626
[55] Lathrop R. The protein folding threading problem with sequence amino acid interaction preferences is NP-complete. Protein Engineering, 1994, 7 (9): 1059~1068
[56] Lathrop R. Global optimum protein threading with gapped alignment and empirical pair score functions. Journal of Molecular Biology, 1996, 255 (4): 641~665
[57]邹承鲁.第二遗传密码——新生肽链及蛋白质折叠的研究.长沙:湖南科学技术出版社, 1997. 1~187
[58] Hao M H, Scheraga H A. Optimizing potential function for protein folding. Journal of Physical Chemistry, 1996, 100 (34): 14540~14548
[59] Scheraga H A. Some approaches to the multiple-minima problem in the calculation of polypeptide and protein structures. International Journal of Quantum Chemistry, 1992, 42 (2): 1529~1536
[60] Klepeis J L, Ploudas C A, Morikis D M, et al. Predicting peptide structures using NMR data and deterministic global optimization. Journal of Computational Chemistry, 1999, 20 (13): 1354~1370
[61] Saunders M. Stochastic exploration of molecular energy surfaces hunting for the global minimum. Journal of the American Chemical Society, 1987, 109 (10): 3150~3152
[62] Li Z Q, Scheraga H A. Monte Carlo-minimization approach to the multiple-mimima problem in protein folding. Proceedings of the National Academy of Sciences, 1987, 84 (19): 6611~6615
[63] Brodmeier T, Presetsch E. Appplication of genetic algorithms in molecular modeling. Journal of Computational Chemistry, 1994, 15 (6): 588~595
[64] Rabow A A, Scheraga H A. Improved genetic algorithm for the protein folding problem by use of a Cartesian combination operator. Protein Science, 1996, 5 (9): 1800~1815
[65] 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 (9): 1222~1232
[66] Lee J, Scheraga H A, Rochovsky S. Conformational analysis of the 20-residue membrane-bound protein of melittin by conformational space annealing. Biopolymers, 1998, 46 (1): 103~115
[67]靳利霞,唐焕文.蛋白质结构预测的一种优化模型及算法.应用数学与计算数学学报, 2000, 20 (2): 1527~1532
[68] Pieia L, Kostrowicki J, Scheraga H A. The Multiple-minima problem in the conformational analysis of molecular: Deformation of the potential energy hyper-surface by the diffusion equation method. Journal of Physical Chemistry, 1989, 93 (2): 3339~3346
[69] Foreman K W, Phillips A T, Rosen J B, et al. Comparing search strategies for finding global optima on energy landscapes. Journal of Computational Chemistry, 1999, 20 (14): 1527~1532
[70] Senderowitz H, Still W C. Sampling potential energy surface of glycyl clycine peptide: Comparison of Metropolis Monte Carlo and stochastic dynamics. Journal of Computational Chemistry, 1998, 19 (11): 1294~1299
[71] Paternoster E R, Sweehey P E. Cutting and packing problems: A categorized application-orientated research bibliography. Journal of the Operational Research Society, 1992, 43 (7): 691~706
[72] Wang P Y, Wascher G. Cutting and packing. European Journal of Operational Research, 2002, 141 (2): 239~240
[73] Brooks R L, Smith C A B, Tutte W T. The dissection of rectangles into squares. Duke Mathematical Journal, 1940, 7 (1): 312~340
[74] Conway J H. Mrs. Perking’s quilt. Proceedings of the Cambridge Philosophical Society, 1964, 60 (2): 363~368
[75] Kantorovich L V. Mathematical methods of organising and planning production. Management Science, 1960, 6 (4): 366~422
[76] Eilon E. Optimizing the shearing of steel bars. Journal of Mechanical Engineering Science, 1960, 2 (1): 129~142
[77] Gilmore P C, Gomory R E. A linear programming approach to the cutting-stock problem (Part 1). Operations Research, 1961, 9 (6): 849~859
[78] Gilmore P C, Gomory R E. A linear programming approach to the cutting-stock problem(Part 2). Operations Research, 1963, 11 (6): 863~888
[79] Lodi A, Martello S, Monaci M. Two-dimensional packing problems: A survey. European Journal of Operational Research, 2002, 141 (2): 241~252
[80] Kenyon C, Remila E. A near-optimal solution to a two-dimensional cutting stock problem. Mathematics of Optimizations Research, 2002, 25 (4): 645~656
[81] Loris F. A global optimizations algorithm for the three-dimensional packing problem. European Journal of Operational Research, 2000, 126 (2): 340~354
[82] Martello S, Pisinger D, Vigo D. The three-dimensional bin packing problem. Operations Research, 2000, 48 (2): 256~267
[83] Lenstra J K, Rinnooy Kan A H G. Complexity of packing, covering, and partitioning problems. in: Schrijver A, ed. Packing and covering in combinatorics. Amsterdam: Elsevier science, 1979. 275~291
[84] Kr?ger B, Schwenderling P, Vornberger O. Parallel genetic packing of rectangles parallel problem solving from nature. in: Scwefel H P and M?nner R, eds. Lecture Notes in Computer Science. 1991. Berlin: Springer Verlag Press, 1991. 160~164
[85] Bortfeldt A, Gehring H. A hybrid genetic algorithm for the container loading problem. European Journal of Operational Research, 2001, 131 (1): 143~161
[86] K?mpke T. Simulated annealing: use of a new tool in bin-packing. Annals of Operations Research, 1988, 16 (1): 327~332
[87] Faina L. An application of simulated annealing to the cutting stock problem. European Journal of Operational Research, 1999, 114 (3): 542~556
[88] Lodi A, Martello S, Vigo D. Approximation algorithms for the oriented two-dimensional bin packing problem. European Journal of Operational Research, 1999, 112 (1): 158~166
[89] Chazelle B. The bottom-left bin-packing heuristic: An efficient implementation. IEEE Transactions on Computers, 1983, 32 (8): 697~707
[90] Albano A, Sappupo D. A heuristic solution of the rectangular cutting stock problem. The Computer Journal, 1980, 23 (4): 338~343
[91] Lodi A, Martello S, Vigo D. Heuristic and meta-heuristic approaches for a class oftwo-dimensional bin packing problems. INFORMS Journal on Computing, 1999, 11 (4): 345~357
[92] Hopper E, Turton B C H. An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem. European Journal of Operational Research, 2000, 128 (1): 34~57
[93]王金敏,陈东祥,查建中等.关于约束底盘装载问题的一种启发式算法.软件学报, 1996, 7 (10): 606~620
[94]袁苗龙,周济,张新访.三维几何布局的一类启发式求解算法.计算机学报, 1999, 22 (9): 923~930
[95]滕弘飞,孙守林,葛文海等.转动圆桌平衡摆盘——带平衡性能约束的Packing问题.中国科学, A辑, 1994, 24 (7): 754~760
[96] Teng H F, Sun S L, Liu D Q, et al. Layout optimization for the objects located within a rotating vessel—A three-dimensional packing problem with behavioral constriants. Computers & Operations Research, 2001, 28 (6): 521~535
[97] Joseph L, Tommy T, Wong C S, et al. Packing squares into square. Journal of Parallel and Distributed Computing, 1990, 10 (3): 274~275
[98] Lipniskii A A. Use of genetic algorithm for solution of the rectangle packing problem. Cybernetics and Systems Analysis, 2002, 38 (6): 943~946
[99] Leung T W, Chan C K, Troutt M D. Application of a mixed simulated annealing-genetic algorithm heuristic for the two-dimensional orthogonal packing problem. European Journal of Operational Research, 2003, 145 (3): 530~542
[100] Chan H H, Markov I L. Practical slicing and non-slicing block-packing without simulated annealing. in: Proccedings of Great Lakes Symposium on VLSI. Boston, Massachusetts, USA. 2004. New York: ACM Press, 2004. 282~287
[101] Dong S Q, Hong X L, Wu Y L, et al. VLSI block placement using less Flexibility First Principles. in: Lenaerts T, ed. Proceedings of the 2001 conference on Asia South Pacific design automation. Yokohama, Japan. 2001. New York: ACM Press, 2001. 601~604
[102] Murata H, Fujiyoshi K, Nakatake S, et al. VLSI module placement based on rectangle-packing bythe sequence pair. IEEE Transaction on Computer-Aided Design of Integrated Circuits and Systems, 1996, 15 (12): 1518~1524
[103] Murata H, Fujiyoshi K, Watanabe T, et al. A mapping from sequence-pair to rectangular dissection. in: Proceedings of Asia and Sound Pacific Design Automation Conference. Chiba, Japan. 1997. Piscataway, New Jersey: IEEE Press, 1997. 625~633
[104] Tang X P, Wong D F. FAST-SP: A fast algorithm for block placement based on sequence pair. in: Proceedings of Asia Sounth Pacific Design Automation Conference. Yokohama, Japan. 2001. New York: ACM Press, 2001. 521~526
[105] Nakatake S, Murata H, Fujiyoshi K, et al. Module placement on BSG-struture and IC layout application. in: Proceedings of International Conference on Computer Aided Design. Santa Clara, California, USA. 1996. Washington: IEEE Computer Society, 1997. 484~491
[106] Hong X L, Huang G, Dong S Q, et al. Corner block list: An effective and efficient topological representation of non-slicing floorplan. in: Proceedings of international conference on Computer-Aided Design. San Jose, California, USA. 2000. Piscataway, New Jersey: IEEE Press, 2000. 8~12
[107] Ma Y C, Hong X L, Dong S Q, et al. Floorplanning with abutment constraints and L-shaped/T-shaped blocks based on Corner Block List. in: Proceedings of the 38th Design Automation Conference. Las Vegas, Nevads, USA. 2001. New York: ACM Press, 2001. 770~775
[108] Dong S Q, Zhou S, Hong X L, et al. An optimum placement search algorithm based on extended corner block list. Journal of Computer Science & Technology, 2002, 17 (6): 699~707
[109] Lin J M, Chang Y W, Lin S P. Corner sequence——A P-admissible floorplan representation with a worst case linear-time packing scheme. IEEE Transactions on VLSI Systems, 11 (4): 679~686
[110] Guo P N, Cheng C K. An o-tree representation of non-slicing floorplan and its application. in: Proceedings of the 36th Design Automation Conference. New Orleans, Louisiana, USA. 1999. New York: ACM Press, 1999. 268~273
[111] Balasa F. Modeling non-slicing floorplans with binary trees. in: Proceedings of the IEEE/ACMInternational Conference on Computer-Aided Design. San Jose, California, USA. 2000. Piscataway, New Jersey: IEEE Press, 2000. 13~16
[112] Chang Y C, Chang Y W, Wu G M, et al. B*-Tree: A new representation for non-slicing floor-plans. in: Proceedings of the 37th Design Automation Conference. Los Angeles, California, USA. 2000. New York: ACM Press, 2000. 458~463
[113]黄文奇,许如初.近世计算理论导引——NP难度问题的背景、前景及其求解算法研究.北京:科学出版社, 2004. 1~80
[114] Wu Y L, Huang W Q, Lau S C, et al. An effective quasi-human based heuristic for solving the rectangles packing problem. European Journal of Operation Research, 2002 , 141 (2): 341~358
[115] 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 frament of staphylococcal protein A and to apo calbindin D9K. Proceedings of the National Academy of Sciences, 1999, 96 (5): 2025~2030
[116] Unger R, Moult J. Genetic algorithms for protein folding simulations. Journal of Molecular Biology, 1993, 231 (1): 75~81
[117] Dill K A. Theory for the folding and stability of globular proteins. Biochemistry, 1985, 24 (6): 1501~1509
[118] Camacho C J, Thirumalai D. Kinetics and thermodynamics of folding in model proteins. Proceedings of the National Academy of Sciences, 1993, 90 (13): 6369~6372
[119] Shakhnovich E I. Proteins with selected sequences fold into a unique native configuration. Physical Review Letters, 1994, 72 (24): 3907~3911
[120] Dill K A. Bromberg S, Yue K, et al. Principles of protein folding: A perspective from simple exact model. Protein Science, 1995, 4 (4): 561~602
[121] Honeycutt J D, Thirvmalai D. The nature of folding states of globular proteins. Biopolymers, 1992, 32 (6): 695~709
[122] Fukugita M, Lancaster D, Mitchard M G. Kinematics and thermodynamics of a folding heteropolymer. Proceedings of the National Academy of Sciences, 1993, 90 (13): 6365~6368
[123] Chikenji G, Kikuchi M, Iba Y. Malti-Self-Overlap ensemble for protein folding: Ground state search and thermodynamics. Physical Review Letters, 1999, 83 (9): 1886~1889
[124] Zhang J L, Liu J S. 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
[125] 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
[126] Hsu H P, Mehra W, Grassberger P. Growth-based optimization algorithm for lattice heteropolymers. Physical Review E, 2003, 68 (2): 021113
[127] Grassberger P. Pruned-Enriched Rosenbluth methed: Simulations of Theta polymers of chain length up to 1000000. Physical Review E, 1997, 56 (3): 3682~3693
[128]黄文奇,吕志鹏.求解蛋白质折叠问题的拟人算法:对PERM的改进.科学通报, 2004, 49 (17): 1801~1477
[129] Stillinger F H, Head-Gordon T, Hirshfeld C L. Toy model for protein folding. Physical Review E, 1993, 48 (2): 1469~1477
[130] Stillinger F H, Head-Gordon T. Collective aspects of protein folding illustrated by a toy model. Physical Review E, 1995, 52 (32): 2872~2877
[131] Hsu H P, Mehra V, Grassberger P. Structure optimization in an off-lattice protein model. Physical Review E, 2003, 68 (3): 037703
[132] Irb?ck A, Pottast F. Study of an off-lattice model for protein folding: Sequence dependence and improved sampling at finite temperature. Journal of Chemical Physics, 1995, 103 (23): 10298~10305
[133] Irb?ck A, Pottast F, Pottast F, et al. Local interactions and protein folding: A three-dimensional off-lattice approach. Journal of Chemical Physics, 1997, 107 (1): 273~282
[134] Liang F M. Annealing contour Monte Carlo algorithm for structure optimization in an off-lattice protein model. Journal of Chemical Physics, 2004, 120 (14): 6756~6763
[135] Gorse D. Application of a chaperone-based refolding method to two-and three-dimensionaloff-lattice protein models. Biopolymers, 2002, 64 (3): 146~160
[136] Gorse D. Global minimization of an off-lattice potential energy function using a chaperone-based refolding method. Biopolymers, 2001, 59 (6): 411~426
[137] Bachmann M, Arkin H, Janke W. Multicanonical study of coarse-grained off-lattice models for folding heteropolymers. Physical Review E, 2005, 71 (3): 031906
[138] 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 (1): 011916
[139]裴鹿成,张孝泽.蒙特卡罗方法及其在粒子输运问题中的应用.北京:科学出版社, 1980. 1~50
[140] Alder B, Fernach S, Rotenbery M. Methods in computation physics. Beijing: Academic Press, 1963. 1~100
[141] Freibergar W, Grenander U. A short course in computation probability and statistics. New York: Springer Verlay, 1971. 1~120
[142] Grenander U. Computation probability and statistics. SIAM Review, 1973, 15 (1): 134~192
[143] Irb?ck A. Hybrid Monte Carlo simulation of polymer chains. Journal of Chemical Physics, 1991, 101 (2): 1661~1667
[144] Liang F, Wong W H. Evolutionary Monte Carlo for protein folding simulations. Journal of Chemical Physics, 2001, 115 (7): 3374~3380
[145]唐焕文,靳利霞,计明军.蛋白质结构预测的优化模型与方法.工程数学学报, 2002, 19 (2): 13~22
[146] Hansmann U H E, Okamoto Y. Prediction of peptide conformation by multicanonical algorithm: A new approach to multi-minima problem. Journal of Computational Chemistry, 1993, 14 (11): 1333~1338
[147] Lyubartsev A P, Martsinovski A A, Shevkunov S V, et al. New method to Monte Carlo calculation of the free energy: Method of expanded ensembles. Journal of Chemical Physics, 1992, 96 (3): 1776~1783
[148] Hansmann U H E. Parallel tempering algorithm for conformation studies of biological molecules.Chemical Physics Letters, 1997, 281 (4): 140~150
[149] Vasquez M, Meirovitch E, Meirovitch H. A free energy based Monte Carlo minimization procedure for biomolecules. Journal of Physical Chemistry, 1994, 98 (38): 9380~ 9382
[150] Derreumaux P. Finding the low-energy forms of avian pancreatic polypeptide with the diffusion process-controlled Monte Carlo Method. Journal of Chemical Physics, 1998, 109 (4): 1567~1574
[151] Chan H S, Dill K A. Energy landscapes and the collapse dynamics of homopolymers. Journal of Chemical Physics, 1989, 99 (3): 2116~2127
[152] Hansmann U H E, Wille L T. Global optimization by energy landscape paving. Physical Review Letters, 2002, 88 (6): 068105
[153] Arkin H. A combination of replica exchange Monte Carlo and energy landscape paving algorithms to increase the effectiveness of conformational sampling. International Journal of Model Physics C, 2004, 15 (7): 933~937
[154] Arkin H, Celik T. Comparison of the ELP and multicanonical methods in simulation of the heptapetide deltorphin. The European Physical Journal B, 2002, 30 (3): 577~584
[155] Schug A, Wenzel W, Hansmann U H E. Energy landscape paving simulation of the trp-cage protein. Journal of Chemical Physics, 2005, 122 (19): 194711
[156] Zhan L, Chen J Z Y, Liu W K. Monte Carlo basin paving: An improved global optimization method. Physical Review E, 2006, 73 (3): 015701
[157] Besold G, Risbo J, Mouritsen O G. Efficient Monte Carlo sampling by direct flattening of free energy barriers. Computational Materials Science, 1999, 15 (3): 311~340
[158] Glover F. Tabu search-Part I. ORSA Journal of Computing, 1989, 1 (3): 190~206
[159] Cvijovic D, Klinowski J. Taboo search: An approach to the multiple minima problem. Science, 1995, 267 (3): 664~666
[160] Liu J M. Chang Y W. TCG-S: Orthogonal coupling of P*-admissible representation for general floorplans. in: Proceedings of the 39th Design Automation Conference. New Orleans, Louisiana, USA. 2002. New York: ACM Press, 2002. 842~847
[161] Murata H, Fujiyoshi K, Kaneko M. VLSI/PCB placement with obstacles based on sequence-pair. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1998, 17 (1): 60~68
[162] Nakatake S, Furuya M, Kajitani Y. Module placement on BSG-structure with pre-placed modules and rectilinear modules. in: Proceedings of Asia Sounth Pacific Design Automation Conference. Yokohama, Japan. 1998. Piscataway, New Jersey: IEEE Press, 1998. 571~576
[163] Dhamdhere S, Zhou N Y, Wang T C. Module placement with pre-placed modules using the corner block list representation. in: Proceedings of IEEE International Symposium on Circuits and System. Scottsdale, Arizona, USA. 2002. Piscataway, New Jersey: IEEE Press, 2002. 349~352
[164] Jiang Y H, Lai J B, Wang T C. Module placement with pre-placed modules using the B*-tree representation. in: Proceedings of IEEE International Symposium on Circuits and System. Sydney, Australia. 2001. Piscataway, New Jersey: IEEE Press, 2001. 347~350
[2] Garey M R, Jonhson D S著.计算机和难解性(NP完全理论导论).张立昂,沈泓,毕源章译.北京:科学出版社, 1987. 1~603
[3] Papadimitrion C H, Steiglitz K. Combinatorial optimization: Algorithms and complexity. New Jersey: Prentice Hall Inc, 1982. 1~298
[4] Hochbaum D S, Maass W. Approximation schemes for covering and packing problem in image processing and VLSI. Journal of the Association for Computing Machinery, 1985, 23 (1): 130~136
[5] Nilsson N J. Problem-solving methods in artificial intelligence. New York: McGraw-Hill, 1971. 1~14
[6] Osman H I. Metaheuristics: A bibliography. Annals of Operations Research, 1996, 63 (3): 513~623
[7] Manner R, Manderick B. Parallel problem solving from nature. North-Holland: Elsevier, 1992. 219~228
[8] Holland J H. Adaptation in natural and artificial systems. Ann Arbor: The University of Michigan Press, 1975. 1~34
[9] Goldberg D E. Genetic algorithms in search, optimization and machine learning. Addison: Wesley, 1989. 1~30
[10] Metropolis N, Rosenbluth A, Rosenbluth M A, et al. Equation of state calculations by fast computing machines. Journal of the Chemical Physics, 1953, 21 (6): 1087~1092
[11] Kirkpatrick S, Gelatt C D, Vecchi M P. Optimization by simulated annealing. Science, 1983, 220 (5): 671~689
[12] Van Luarhoven P J M, Aarts E H L. Simulated annealing: Theory and applications. Holland:Reidel D Publishing Company, 1987. 1~130
[13] Hopfield J, Tank D. Neural computation of decisions in optimization problems. Biological Cybernetics, 1985, 52 (3): 141~152
[14] Glover F, Greenberg H J. New approaches for heuristic search: A bilateral linkage with artificial intelligence. European Journal of Operational Research, 1989, 39 (2): 119~130
[15] Darrell W. An overview of evolutionary algorithms: Practical issues and common pitfalls. Information and Software Technology, 2001, 43 (14): 817~831
[16] Colorni A, Dorigo M, Maniezzo V. Distributed optimization by ant colonies. in: Varela F and Bourgings P, eds. Proceedings of the first European Conference on Artificial Life. Paris, France. 1991. Amsterdam: Elsevier Publishing, 1991. 134~142
[17]黄文奇,詹叔浩.求解packing问题的拟物方法.应用数学学报, 1979, 2 (2): 176~180
[18]黄文奇.求解packing问题的拟物方法——NP难问题的一个处理途径.计算机学报, 1989, 12 (8): 610~616
[19]黄文奇,陈亮.求解有关空间利用的调度问题的拟物方法.中国科学(A辑), 1991, 21 (3): 325~331
[20]李未,黄文奇.一种求解合取范式可满足问题的数学物理方法.中国科学(A辑), 1994, 24 (11): 1208~1217
[21]黄文奇,许如初.支持求解圆形packing问题的两个拟人策略.中国科学(E辑), 1999, 29 (4): 347~353
[22]黄文奇,金人超.求解SAT问题的拟物拟人算法——Solar.中国科学(E辑), 1997, 27 (2): 179~186
[23]黄文奇.处理NP难度问题的拟物和拟人方法.见:苏运霖主编.国际离散数学和算法研讨会议论文集.广州. 1994.广州:暨南大学出版社. 1994. 89~91
[24]黄文奇,许如初,陈卫东等.求解Packing及CNF-SAT问题的拟物拟人方法.华中理工大学学报, 1998, 26 (9): 5~7
[25]黄文奇,赵孝武.求解正交数组问题的拟物拟人算法.计算机研究与发展, 2002, 39 (2): 205~212
[26] Metropolis W, Ulam S. Monte Carlo method. Journal of the American Statistical Association, 1949, 44 (247): 335~341
[27] Li G J. Computational intelligent: An important field of research. Basic Study of Intelligent Computer’94. Beijing: Press of Tsinghua University, 1994. 9~12
[28] Linderoth J L, Savelsbergh M W. A computational study of search strategies for mixed integer programming. INFORMS Journal on Computing, 1998, 11 (2): 173~187
[29] Polya G. How to solve it. Princeton: Princeton University Press, 1948. 1~72
[30] Reeves C R. Model heuristic techniques for combinatorial problems. Oxford: Blackwell Scientific Publications, 1993. 1~55
[31]邢文训,谢金星.现代优化计算方法(第一版).北京:清华大学出版社, 1999. 1~293
[32]徐钟济.蒙特卡罗方法.上海:上海科学技术出版社, 1985. 1~28
[33] Huang W Q, Kang Y. A heuristic quasi-physical strategy for solving disks packing problem. Simulation Modeling Practice and Theory, 2002, 10 (4): 195~207
[34] Wang H Q, Huang W Q, Zhang Q, et al. An improved algorithm for the packing of unequal circles within a larger containing circle. European Journal of Operational Research, 2002, 141 (2): 440~453
[35]黄文奇,李庆华,余向东.求解空间Packing问题的拟物方法.应用数学学报, 1986, 9 (4): 443~453
[36] Miller R E, Thatcher J W. Complexity of computer computations. New York: Plenum Press, 1972. 1~105
[37] Cook S. The complexity of theorem proving procedures. in: Minker J, ed. Proceedings of the 3rd Annual ACM Symposium on the Theory of Computing. Shake heights: Ohio. 1971. New York: ACM Press, 1971. 151~158
[38] Karp R M. Reducibility among combinatorial problems. New York: Plenum Press, 1972. 2~6
[39]邹啸,陆祖宏,谢建明.生物信息学基础.北京:清华大学出版社, 2005. 1~77
[40] Anfinsen C B. Principles that govern the folding of protein chains. Science, 1973, 181(96): 223~230
[41]阎隆飞,孙之荣.蛋白质分子结构.北京:清华大学出版社. 1999. 1~100
[42] Michael J, Sternberg E. Progress in protein structure prediction: Assessment of CASP3. Current Opinion in Structure Biology, 1999, 9 (3): 368~373
[43]赵善荣,陈凯先.基于知识的蛋白质结构预测.生物化学与生物物理进展, 1995, 23 (5): 422~426
[44] Altshul A F, Gish W, Miller W. Basic local alignment search tool. Journal of Molecular Biology, 1990, 215 (3): 403~410
[45] Gribskov M, Mclachlan A. Profile analysis: Detection of distantly related proteins. Proceedings of the National Academy of Sciences, 1987, 84 (13): 4355~4358
[46] Krogh A, Brown M, Mian I. Hidden Markov models in computational biology: Application to protein modeling. Journal of Molecular Biology, 1996, 235 (5): 1501~1531
[47] Altshul S. Madden T. Gapped BLAST and PSI-BLAST: A new generation of protein database search programs. Nucleic Acids Research, 1997, 25 (17): 3389~3402
[48] Karplus K, Barrett C. Hidden Markov models for detecting remote protein homologies. Bioinformatics, 1998, 14 (10): 846~856
[49] Koehl P, Levitt M. Improved recognition of native-like protein structures using a family of designed sequences. Proceedings of the National Academy of Sciences, 2002, 99 (2): 691~696
[50] Koehl P, Levitt M. Protein topology and stability define the space of allowed sequences. Proceedings of the National Academy of Sciences, 2002, 99 (3): 1280~1285
[51] Murzin A, Brenner S. SCOP: A structural classification of protein database for the investigation of sequences and structures. Journal of Molecular Biology, 1995, 247 (4): 536~540
[52] Finkelstein A V, Ptitsyn O B. Why do globular proteins fit the limited set of folding patterns. Progress in Biophysics and Moleclar Biology, 1987, 50 (3): 171-190
[53] Chothia C. One thousand families for the molecular biologist. Nature, 1992, 357 (6379): 543~544
[54] Wang Z X. A re-estimation for the total numbers of protein folds and superfamilies. Protein Engineering, 1998, 11 (8): 621~626
[55] Lathrop R. The protein folding threading problem with sequence amino acid interaction preferences is NP-complete. Protein Engineering, 1994, 7 (9): 1059~1068
[56] Lathrop R. Global optimum protein threading with gapped alignment and empirical pair score functions. Journal of Molecular Biology, 1996, 255 (4): 641~665
[57]邹承鲁.第二遗传密码——新生肽链及蛋白质折叠的研究.长沙:湖南科学技术出版社, 1997. 1~187
[58] Hao M H, Scheraga H A. Optimizing potential function for protein folding. Journal of Physical Chemistry, 1996, 100 (34): 14540~14548
[59] Scheraga H A. Some approaches to the multiple-minima problem in the calculation of polypeptide and protein structures. International Journal of Quantum Chemistry, 1992, 42 (2): 1529~1536
[60] Klepeis J L, Ploudas C A, Morikis D M, et al. Predicting peptide structures using NMR data and deterministic global optimization. Journal of Computational Chemistry, 1999, 20 (13): 1354~1370
[61] Saunders M. Stochastic exploration of molecular energy surfaces hunting for the global minimum. Journal of the American Chemical Society, 1987, 109 (10): 3150~3152
[62] Li Z Q, Scheraga H A. Monte Carlo-minimization approach to the multiple-mimima problem in protein folding. Proceedings of the National Academy of Sciences, 1987, 84 (19): 6611~6615
[63] Brodmeier T, Presetsch E. Appplication of genetic algorithms in molecular modeling. Journal of Computational Chemistry, 1994, 15 (6): 588~595
[64] Rabow A A, Scheraga H A. Improved genetic algorithm for the protein folding problem by use of a Cartesian combination operator. Protein Science, 1996, 5 (9): 1800~1815
[65] 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 (9): 1222~1232
[66] Lee J, Scheraga H A, Rochovsky S. Conformational analysis of the 20-residue membrane-bound protein of melittin by conformational space annealing. Biopolymers, 1998, 46 (1): 103~115
[67]靳利霞,唐焕文.蛋白质结构预测的一种优化模型及算法.应用数学与计算数学学报, 2000, 20 (2): 1527~1532
[68] Pieia L, Kostrowicki J, Scheraga H A. The Multiple-minima problem in the conformational analysis of molecular: Deformation of the potential energy hyper-surface by the diffusion equation method. Journal of Physical Chemistry, 1989, 93 (2): 3339~3346
[69] Foreman K W, Phillips A T, Rosen J B, et al. Comparing search strategies for finding global optima on energy landscapes. Journal of Computational Chemistry, 1999, 20 (14): 1527~1532
[70] Senderowitz H, Still W C. Sampling potential energy surface of glycyl clycine peptide: Comparison of Metropolis Monte Carlo and stochastic dynamics. Journal of Computational Chemistry, 1998, 19 (11): 1294~1299
[71] Paternoster E R, Sweehey P E. Cutting and packing problems: A categorized application-orientated research bibliography. Journal of the Operational Research Society, 1992, 43 (7): 691~706
[72] Wang P Y, Wascher G. Cutting and packing. European Journal of Operational Research, 2002, 141 (2): 239~240
[73] Brooks R L, Smith C A B, Tutte W T. The dissection of rectangles into squares. Duke Mathematical Journal, 1940, 7 (1): 312~340
[74] Conway J H. Mrs. Perking’s quilt. Proceedings of the Cambridge Philosophical Society, 1964, 60 (2): 363~368
[75] Kantorovich L V. Mathematical methods of organising and planning production. Management Science, 1960, 6 (4): 366~422
[76] Eilon E. Optimizing the shearing of steel bars. Journal of Mechanical Engineering Science, 1960, 2 (1): 129~142
[77] Gilmore P C, Gomory R E. A linear programming approach to the cutting-stock problem (Part 1). Operations Research, 1961, 9 (6): 849~859
[78] Gilmore P C, Gomory R E. A linear programming approach to the cutting-stock problem(Part 2). Operations Research, 1963, 11 (6): 863~888
[79] Lodi A, Martello S, Monaci M. Two-dimensional packing problems: A survey. European Journal of Operational Research, 2002, 141 (2): 241~252
[80] Kenyon C, Remila E. A near-optimal solution to a two-dimensional cutting stock problem. Mathematics of Optimizations Research, 2002, 25 (4): 645~656
[81] Loris F. A global optimizations algorithm for the three-dimensional packing problem. European Journal of Operational Research, 2000, 126 (2): 340~354
[82] Martello S, Pisinger D, Vigo D. The three-dimensional bin packing problem. Operations Research, 2000, 48 (2): 256~267
[83] Lenstra J K, Rinnooy Kan A H G. Complexity of packing, covering, and partitioning problems. in: Schrijver A, ed. Packing and covering in combinatorics. Amsterdam: Elsevier science, 1979. 275~291
[84] Kr?ger B, Schwenderling P, Vornberger O. Parallel genetic packing of rectangles parallel problem solving from nature. in: Scwefel H P and M?nner R, eds. Lecture Notes in Computer Science. 1991. Berlin: Springer Verlag Press, 1991. 160~164
[85] Bortfeldt A, Gehring H. A hybrid genetic algorithm for the container loading problem. European Journal of Operational Research, 2001, 131 (1): 143~161
[86] K?mpke T. Simulated annealing: use of a new tool in bin-packing. Annals of Operations Research, 1988, 16 (1): 327~332
[87] Faina L. An application of simulated annealing to the cutting stock problem. European Journal of Operational Research, 1999, 114 (3): 542~556
[88] Lodi A, Martello S, Vigo D. Approximation algorithms for the oriented two-dimensional bin packing problem. European Journal of Operational Research, 1999, 112 (1): 158~166
[89] Chazelle B. The bottom-left bin-packing heuristic: An efficient implementation. IEEE Transactions on Computers, 1983, 32 (8): 697~707
[90] Albano A, Sappupo D. A heuristic solution of the rectangular cutting stock problem. The Computer Journal, 1980, 23 (4): 338~343
[91] Lodi A, Martello S, Vigo D. Heuristic and meta-heuristic approaches for a class oftwo-dimensional bin packing problems. INFORMS Journal on Computing, 1999, 11 (4): 345~357
[92] Hopper E, Turton B C H. An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem. European Journal of Operational Research, 2000, 128 (1): 34~57
[93]王金敏,陈东祥,查建中等.关于约束底盘装载问题的一种启发式算法.软件学报, 1996, 7 (10): 606~620
[94]袁苗龙,周济,张新访.三维几何布局的一类启发式求解算法.计算机学报, 1999, 22 (9): 923~930
[95]滕弘飞,孙守林,葛文海等.转动圆桌平衡摆盘——带平衡性能约束的Packing问题.中国科学, A辑, 1994, 24 (7): 754~760
[96] Teng H F, Sun S L, Liu D Q, et al. Layout optimization for the objects located within a rotating vessel—A three-dimensional packing problem with behavioral constriants. Computers & Operations Research, 2001, 28 (6): 521~535
[97] Joseph L, Tommy T, Wong C S, et al. Packing squares into square. Journal of Parallel and Distributed Computing, 1990, 10 (3): 274~275
[98] Lipniskii A A. Use of genetic algorithm for solution of the rectangle packing problem. Cybernetics and Systems Analysis, 2002, 38 (6): 943~946
[99] Leung T W, Chan C K, Troutt M D. Application of a mixed simulated annealing-genetic algorithm heuristic for the two-dimensional orthogonal packing problem. European Journal of Operational Research, 2003, 145 (3): 530~542
[100] Chan H H, Markov I L. Practical slicing and non-slicing block-packing without simulated annealing. in: Proccedings of Great Lakes Symposium on VLSI. Boston, Massachusetts, USA. 2004. New York: ACM Press, 2004. 282~287
[101] Dong S Q, Hong X L, Wu Y L, et al. VLSI block placement using less Flexibility First Principles. in: Lenaerts T, ed. Proceedings of the 2001 conference on Asia South Pacific design automation. Yokohama, Japan. 2001. New York: ACM Press, 2001. 601~604
[102] Murata H, Fujiyoshi K, Nakatake S, et al. VLSI module placement based on rectangle-packing bythe sequence pair. IEEE Transaction on Computer-Aided Design of Integrated Circuits and Systems, 1996, 15 (12): 1518~1524
[103] Murata H, Fujiyoshi K, Watanabe T, et al. A mapping from sequence-pair to rectangular dissection. in: Proceedings of Asia and Sound Pacific Design Automation Conference. Chiba, Japan. 1997. Piscataway, New Jersey: IEEE Press, 1997. 625~633
[104] Tang X P, Wong D F. FAST-SP: A fast algorithm for block placement based on sequence pair. in: Proceedings of Asia Sounth Pacific Design Automation Conference. Yokohama, Japan. 2001. New York: ACM Press, 2001. 521~526
[105] Nakatake S, Murata H, Fujiyoshi K, et al. Module placement on BSG-struture and IC layout application. in: Proceedings of International Conference on Computer Aided Design. Santa Clara, California, USA. 1996. Washington: IEEE Computer Society, 1997. 484~491
[106] Hong X L, Huang G, Dong S Q, et al. Corner block list: An effective and efficient topological representation of non-slicing floorplan. in: Proceedings of international conference on Computer-Aided Design. San Jose, California, USA. 2000. Piscataway, New Jersey: IEEE Press, 2000. 8~12
[107] Ma Y C, Hong X L, Dong S Q, et al. Floorplanning with abutment constraints and L-shaped/T-shaped blocks based on Corner Block List. in: Proceedings of the 38th Design Automation Conference. Las Vegas, Nevads, USA. 2001. New York: ACM Press, 2001. 770~775
[108] Dong S Q, Zhou S, Hong X L, et al. An optimum placement search algorithm based on extended corner block list. Journal of Computer Science & Technology, 2002, 17 (6): 699~707
[109] Lin J M, Chang Y W, Lin S P. Corner sequence——A P-admissible floorplan representation with a worst case linear-time packing scheme. IEEE Transactions on VLSI Systems, 11 (4): 679~686
[110] Guo P N, Cheng C K. An o-tree representation of non-slicing floorplan and its application. in: Proceedings of the 36th Design Automation Conference. New Orleans, Louisiana, USA. 1999. New York: ACM Press, 1999. 268~273
[111] Balasa F. Modeling non-slicing floorplans with binary trees. in: Proceedings of the IEEE/ACMInternational Conference on Computer-Aided Design. San Jose, California, USA. 2000. Piscataway, New Jersey: IEEE Press, 2000. 13~16
[112] Chang Y C, Chang Y W, Wu G M, et al. B*-Tree: A new representation for non-slicing floor-plans. in: Proceedings of the 37th Design Automation Conference. Los Angeles, California, USA. 2000. New York: ACM Press, 2000. 458~463
[113]黄文奇,许如初.近世计算理论导引——NP难度问题的背景、前景及其求解算法研究.北京:科学出版社, 2004. 1~80
[114] Wu Y L, Huang W Q, Lau S C, et al. An effective quasi-human based heuristic for solving the rectangles packing problem. European Journal of Operation Research, 2002 , 141 (2): 341~358
[115] 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 frament of staphylococcal protein A and to apo calbindin D9K. Proceedings of the National Academy of Sciences, 1999, 96 (5): 2025~2030
[116] Unger R, Moult J. Genetic algorithms for protein folding simulations. Journal of Molecular Biology, 1993, 231 (1): 75~81
[117] Dill K A. Theory for the folding and stability of globular proteins. Biochemistry, 1985, 24 (6): 1501~1509
[118] Camacho C J, Thirumalai D. Kinetics and thermodynamics of folding in model proteins. Proceedings of the National Academy of Sciences, 1993, 90 (13): 6369~6372
[119] Shakhnovich E I. Proteins with selected sequences fold into a unique native configuration. Physical Review Letters, 1994, 72 (24): 3907~3911
[120] Dill K A. Bromberg S, Yue K, et al. Principles of protein folding: A perspective from simple exact model. Protein Science, 1995, 4 (4): 561~602
[121] Honeycutt J D, Thirvmalai D. The nature of folding states of globular proteins. Biopolymers, 1992, 32 (6): 695~709
[122] Fukugita M, Lancaster D, Mitchard M G. Kinematics and thermodynamics of a folding heteropolymer. Proceedings of the National Academy of Sciences, 1993, 90 (13): 6365~6368
[123] Chikenji G, Kikuchi M, Iba Y. Malti-Self-Overlap ensemble for protein folding: Ground state search and thermodynamics. Physical Review Letters, 1999, 83 (9): 1886~1889
[124] Zhang J L, Liu J S. 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
[125] 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
[126] Hsu H P, Mehra W, Grassberger P. Growth-based optimization algorithm for lattice heteropolymers. Physical Review E, 2003, 68 (2): 021113
[127] Grassberger P. Pruned-Enriched Rosenbluth methed: Simulations of Theta polymers of chain length up to 1000000. Physical Review E, 1997, 56 (3): 3682~3693
[128]黄文奇,吕志鹏.求解蛋白质折叠问题的拟人算法:对PERM的改进.科学通报, 2004, 49 (17): 1801~1477
[129] Stillinger F H, Head-Gordon T, Hirshfeld C L. Toy model for protein folding. Physical Review E, 1993, 48 (2): 1469~1477
[130] Stillinger F H, Head-Gordon T. Collective aspects of protein folding illustrated by a toy model. Physical Review E, 1995, 52 (32): 2872~2877
[131] Hsu H P, Mehra V, Grassberger P. Structure optimization in an off-lattice protein model. Physical Review E, 2003, 68 (3): 037703
[132] Irb?ck A, Pottast F. Study of an off-lattice model for protein folding: Sequence dependence and improved sampling at finite temperature. Journal of Chemical Physics, 1995, 103 (23): 10298~10305
[133] Irb?ck A, Pottast F, Pottast F, et al. Local interactions and protein folding: A three-dimensional off-lattice approach. Journal of Chemical Physics, 1997, 107 (1): 273~282
[134] Liang F M. Annealing contour Monte Carlo algorithm for structure optimization in an off-lattice protein model. Journal of Chemical Physics, 2004, 120 (14): 6756~6763
[135] Gorse D. Application of a chaperone-based refolding method to two-and three-dimensionaloff-lattice protein models. Biopolymers, 2002, 64 (3): 146~160
[136] Gorse D. Global minimization of an off-lattice potential energy function using a chaperone-based refolding method. Biopolymers, 2001, 59 (6): 411~426
[137] Bachmann M, Arkin H, Janke W. Multicanonical study of coarse-grained off-lattice models for folding heteropolymers. Physical Review E, 2005, 71 (3): 031906
[138] 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 (1): 011916
[139]裴鹿成,张孝泽.蒙特卡罗方法及其在粒子输运问题中的应用.北京:科学出版社, 1980. 1~50
[140] Alder B, Fernach S, Rotenbery M. Methods in computation physics. Beijing: Academic Press, 1963. 1~100
[141] Freibergar W, Grenander U. A short course in computation probability and statistics. New York: Springer Verlay, 1971. 1~120
[142] Grenander U. Computation probability and statistics. SIAM Review, 1973, 15 (1): 134~192
[143] Irb?ck A. Hybrid Monte Carlo simulation of polymer chains. Journal of Chemical Physics, 1991, 101 (2): 1661~1667
[144] Liang F, Wong W H. Evolutionary Monte Carlo for protein folding simulations. Journal of Chemical Physics, 2001, 115 (7): 3374~3380
[145]唐焕文,靳利霞,计明军.蛋白质结构预测的优化模型与方法.工程数学学报, 2002, 19 (2): 13~22
[146] Hansmann U H E, Okamoto Y. Prediction of peptide conformation by multicanonical algorithm: A new approach to multi-minima problem. Journal of Computational Chemistry, 1993, 14 (11): 1333~1338
[147] Lyubartsev A P, Martsinovski A A, Shevkunov S V, et al. New method to Monte Carlo calculation of the free energy: Method of expanded ensembles. Journal of Chemical Physics, 1992, 96 (3): 1776~1783
[148] Hansmann U H E. Parallel tempering algorithm for conformation studies of biological molecules.Chemical Physics Letters, 1997, 281 (4): 140~150
[149] Vasquez M, Meirovitch E, Meirovitch H. A free energy based Monte Carlo minimization procedure for biomolecules. Journal of Physical Chemistry, 1994, 98 (38): 9380~ 9382
[150] Derreumaux P. Finding the low-energy forms of avian pancreatic polypeptide with the diffusion process-controlled Monte Carlo Method. Journal of Chemical Physics, 1998, 109 (4): 1567~1574
[151] Chan H S, Dill K A. Energy landscapes and the collapse dynamics of homopolymers. Journal of Chemical Physics, 1989, 99 (3): 2116~2127
[152] Hansmann U H E, Wille L T. Global optimization by energy landscape paving. Physical Review Letters, 2002, 88 (6): 068105
[153] Arkin H. A combination of replica exchange Monte Carlo and energy landscape paving algorithms to increase the effectiveness of conformational sampling. International Journal of Model Physics C, 2004, 15 (7): 933~937
[154] Arkin H, Celik T. Comparison of the ELP and multicanonical methods in simulation of the heptapetide deltorphin. The European Physical Journal B, 2002, 30 (3): 577~584
[155] Schug A, Wenzel W, Hansmann U H E. Energy landscape paving simulation of the trp-cage protein. Journal of Chemical Physics, 2005, 122 (19): 194711
[156] Zhan L, Chen J Z Y, Liu W K. Monte Carlo basin paving: An improved global optimization method. Physical Review E, 2006, 73 (3): 015701
[157] Besold G, Risbo J, Mouritsen O G. Efficient Monte Carlo sampling by direct flattening of free energy barriers. Computational Materials Science, 1999, 15 (3): 311~340
[158] Glover F. Tabu search-Part I. ORSA Journal of Computing, 1989, 1 (3): 190~206
[159] Cvijovic D, Klinowski J. Taboo search: An approach to the multiple minima problem. Science, 1995, 267 (3): 664~666
[160] Liu J M. Chang Y W. TCG-S: Orthogonal coupling of P*-admissible representation for general floorplans. in: Proceedings of the 39th Design Automation Conference. New Orleans, Louisiana, USA. 2002. New York: ACM Press, 2002. 842~847
[161] Murata H, Fujiyoshi K, Kaneko M. VLSI/PCB placement with obstacles based on sequence-pair. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1998, 17 (1): 60~68
[162] Nakatake S, Furuya M, Kajitani Y. Module placement on BSG-structure with pre-placed modules and rectilinear modules. in: Proceedings of Asia Sounth Pacific Design Automation Conference. Yokohama, Japan. 1998. Piscataway, New Jersey: IEEE Press, 1998. 571~576
[163] Dhamdhere S, Zhou N Y, Wang T C. Module placement with pre-placed modules using the corner block list representation. in: Proceedings of IEEE International Symposium on Circuits and System. Scottsdale, Arizona, USA. 2002. Piscataway, New Jersey: IEEE Press, 2002. 349~352
[164] Jiang Y H, Lai J B, Wang T C. Module placement with pre-placed modules using the B*-tree representation. in: Proceedings of IEEE International Symposium on Circuits and System. Sydney, Australia. 2001. Piscataway, New Jersey: IEEE Press, 2001. 347~350
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |