歐陽彥正臺灣大學:電機工程學研究所張天豪Chang, Tien-HaoTien-HaoChang2007-11-262018-07-062007-11-262018-07-062005http://ntur.lib.ntu.edu.tw//handle/246246/53566This thesis studies global optimization for simulation-based molecule docking. Such docking algorithms aim to mimic the binding process and typically generate more accurate binding modes than geometrics-based docking algorithms. Many simulation-based docking algorithms recognize the binding free energy landscape as an extreme complicated function and employ global optimization algorithms such as simulated anneling and genetic algorithm to find the global optimum of the energy function. However, as the flexibility of the molecules is taken into account, the complexity of the problem increases substantially. As a result, design of highly efficient mechanism is of great significance. This thesis proposes an efficient simulation-based docking mechanism. The proposed docking procedure employs a binding site prediction algorithm based on kernel density estimation prior to simulation of energy states. The process of binding site prediction extracts the amino acids located in the cavities of the protein tertiary structure with O(nlogn) time complexity, where n is the number of amino acids in the protein. Experimental results show that the prediction process is able to speed up the analysis by a factor ranging from 35.1 to 305.2 times. In the simulation phase, a novel optimization algorithm belonging to evolutionary algorithm category is proposed. The proposed optimization exploits the maximum entropy property of the Gaussian probability distribution in the context of information theory. Experimental results revel that the proposed optimization algorithm solves the genetic drift problem while keeping the search efficiency. Furthermore, it uses a very succinct model to process population communication and to control the population quality. As a result, the proposed optimization algorithm is significantly superior when dealing with very rugged energy landscapes, which usually have insurmountable barriers.Abstract i Contents iii List of Figures v List of Tables vi Chapter 1. Introduction - 1 - 1.1 Functional site location - 2 - 1.2 Functional site similarity - 3 - 1.3 Predicting ligand interactions by molecular docking - 4 - 1.4 Challenges of modern docking procedures - 6 - 1.5 Prediction framework of protein-ligand binding sites - 9 - 1.6 Thesis structure - 10 - Chapter 2. Related Work - 11 - 2.1 Protein structural alignment - 12 - 2.2 Site recognition based on library search - 14 - 2.3 Evolutionary algorithms for global optimization - 15 - 2.4 Simulation-based docking - 16 - 2.4.1 Lamarkian genetic algorithm (LGA) - 16 - 2.4.2 Generic Evolutionary Method for molecular DOCKing (GEMDOCK) - 17 - 2.4.3 Internal coordinate modeling (ICM) - 18 - Chapter 3. An Efficient Binding Site Prediction Algorithm Based on Kernel Density Estimation - 20 - 3.1 Overview of the binding site prediction algorithm - 20 - 3.2 The cavity recognition process - 21 - 3.3 The binding pattern search process - 26 - 3.3.1 Binding pattern database construction - 27 - 3.3.2 Protein tertiary sub-structure alignment - 28 - 3.4 Analysis of time complexity - 33 - Chapter 4. An Efficient Simulation Docking Method based on A Novel Maximum Entropy Optimization Algorithm - 34 - 4.1 Basic assumption - 35 - 4.2 Sampling procedure - 36 - 4.3 Sampling quality control - 39 - 4.4 Local search - 42 - 4.5 Prevent centralizing to a local optimum - 44 - Chapter 5. Experiments - 46 - 5.1 Performance of protein tertiary substructure comparison - 46 - 5.2 Parameter setting - 49 - 5.3 Optimization performance on highly rugged objective function - 60 - Chapter 6. Conclusion and Future Work - 68 - References: - 71 -en-US蛋白質結構嵌合proteinstructuredocking預測蛋白質反應區域之研究A Study on Prediction of Protein Binding Sitesthesis