臺灣博碩士論文加值系統

過去二十年以來，不論是學界或是製藥界，結構化藥物設計（structure-based
drug design）這門科學都越來越受到重視。傳統上，從開發一種新藥，到將該新
藥推上市場，通常需要六至十二年的時間。而需要這麼長時間的理由是，從開發
新藥到該新藥成熟，必須經過數個不同的步驟，包括：『發現適合做進一步精製
的初始分子結構』；『精製分子結構以產生新藥』；對產生的新藥進行『生化測
試』（biological test）以及對藥物進行『臨床測試』（clinical test）等等。倘
若使用傳統的技術，上述的每個步驟，往往各需花費一至三年的時間。值得注意
的是：第一個步驟『發現適合做進一步精製的初始分子結構』是改善藥物設計流
程的重要關鍵之一。因為這個步驟的效率可藉由電腦的輔助而有所改善。事實
上，結構化藥物設計便是結合電腦繪圖（computer graphics）與演算法
（computational algorithms）技術以發現適合精製的初始分子結構之劃時代的革
命技術。

結構化藥物設計中最重要的問題之一：分子結合問題（molecular binding
problem）可以用分子力學（molecular mechanics）加以描述。基本上，分子結
合問題是一個能量最佳化的問題（energy optimization problem）。可惜的是，分
子結合問題經過量化之後，卻變成一個NP的問題，而且其評估函數（scoring
function）的複雜度（complexity）極高；因此，不論使用什麼演算法，都難以
有效率的找出不錯的解答。在過去，研究人員提出了數種方法來解答分子結合問
題；這些方法不外乎人機互動技術（human-machine interaction approach）（即
利用虛擬實境（virtual reality）技術設計輔助工具）；結構與活性之關連性定量
分析（quantitative structure-activity relationship, QSAR）以及純計算式的分析技
術（computational approach）；其中，近年來又以純計算式的分析有越來越受
重視的趨勢。因此在本論文中，我們試著提出數種新的演算法來解答分子結合問
題。我們的演算法稱為『族群式退火遺傳演算法』（population-based annealing
genetic algorithms, PAG）；該演算法結合遺傳演算法（genetic algorithms）與模
擬退火法（simulated annealing）的優點並加以發揚光大。而不論是理論分析或
是實驗的結果，都在在支持我們的『族群式退火遺傳演算法』具備相當解答最佳
化問題的能力。我們嘗試使用『族群式退火遺傳演算法』來解分子結合問題。實
驗的對象包括三組不同的『藥物與蛋白質』的分子結合系統。其中，三組蛋白質
分別是dihydrofolate reductase（DHFR），thermolysin（TLN）以及Human
Immunodeficiency Virus-1 Protease（HIV-1）。而與DHFR相結合的藥物包括，
抗癌藥物methotrexate（MTX）與兩種抗菌藥物 trimethoprim的衍生物。至於
後兩組蛋白質則分別搭配取自『蛋白質資料銀行』（Protein Data Bank, PDB）
的藥物。實驗所得的分子結合結構不僅具有極佳的能量表現，也有十分密合的幾
何形狀。

In the past two decades, structure-based drug design has received increasing
attention from research institutions and the pharmaceutical industry.
Traditionally, each new drug requires 6-12 years to bring it from discovery
to market. Such a lengthy drug discovery process is actually composed of
several steps. These steps include finding good starting molecular
structures for optimization, refining the starting molecular structures
to generate potential drugs, biologically testing potential drugs
generated from previous steps and testing new drugs clinically. Each step
mentioned above needs 1-3 years to complete by traditional techniques. It is
worth mentioning that the first step, finding good starting molecular
structures for optimization is one of the key issues to improve drug
discovery process and can be assisted by computers. Actually,
structure-based drug design is one of the revolutionary
approaches that help to find
good starting molecular structures of potential drugs using computer
graphics techniques and computational algorithms.

Molecular binding problem, one of the most important problems in
structure-based drug design, can be formulated as a global energy optimization
problem of molecular mechanics. Nevertheless, the formulated problem is an
NP problem with a very complicated scoring function, and so it is hard to find
feasible solutions efficiently no matter what methods are
applied. Therefore, in
the past, many researchers proposed various approaches to address the
molecular binding problem, including human-machine interaction approach
(virtual reality), quantitative structure-activity relationship(QSAR) and
computational approach. In this proposal, various novel computational
algorithms different from previous works are proposed to address the molecular
binding problem.
The algorithms are derived from genetic algorithms(GA) plus simulated
annealing(SA) hybrid techniques, namely population-based annealing genetic
algorithms(PAG).
GA and SA are two powerful stochastic techniques for solving
global optimization problems approximately. However, both
techniques suffer from efficiency or solution quality problems. PAG combines
SA with GA in order to reduce the weaknesses and incorporates the strengths
of both methods. Both empirical and analytical evidence show that PAG is an
efficient method to solve global optimization problems.
We have applied PAG to find binding structures for three drug-protein
molecular complex.
The proteins examined are dihydrofolate reductase enzyme(DHFR),
thermolysin(TLN)
and Human Immunodeficiency Virus-1 Protease(HIV-1).
One of the three drugs docking with DHFR is an anti-cancer drug
methotrexate(MTX)
and the other two are analogue of antibacterial drug trimethoprim.
In the latter two proteins, the crystal ligands, getting from Protein Data
Bank(PDB), are redocked.
All of the binding results
not only keep the energy low, but also have a promising
binding geometrical structure.

COVER
CONTENTS
LIST OF TABLES
LIST OF FIGURE
ABSTRACT
CHAPTER 1 Introduction
1.1 Introduction to the structure-based drug design
1.2 Introduction to the molecular binding problem
1.3 Genetic algorithms and simulated annealing
1.4 Thesis statement
1.5 The organization of the thesis
CHAPTER 2 The Population-based Annealing Genetic Algorithms(PAG)
2.1 Genetic algorithms/simulated annealing hybrids
2.2 Definition of PAG
2.3 The proposed algorithms
CHAPTER 3 Solving Molecular Binding Problem
3.1 The computational model
3.2 Test molecules and algorithm settings
3.3 Experimental results
3.3.1 Preliminary results
3.3.2 The correctness of experimental results
3.3.3 Experimental results of general cases
3.3.4 Discussion of PAG
CHAPTER 4 The Analysis of PAG
4.1 Asymptotic analysis of global convergence
4.2 The search behavior of the PA operator
CHAPTER 5 Conclusion and Future Work
5.1 Contribution
5.2 Conclusion and future works
REFERENCES