以2D HP 模型對蛋白質摺疊問題之研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：31

、訪客IP：18.226.222.12

姓名

呂永志(Yung-chih Lu) 查詢紙本館藏

畢業系所

數學系

論文名稱

以2D HP 模型對蛋白質摺疊問題之研究
(A Study on the Protein Folding Problem in the 2D HP Model)

相關論文

★ 圓環面網路上的病毒散播	★ On Steiner centers of graphs
★ On the Steiner medians of a block graph	★ 圖形列表著色
★ 秩為5的圖形	★ Some results on distance-two labeling of a graph
★ 關於非奇異線圖的樹	★ On Minimum Strictly Fundamental Cycle Basis
★ 目標集選擇問題	★ 路徑圖與格子圖上的目標集問題
★ 超立方體圖與格子圖上的目標集問題	★ 圖形環著色數的若干等價定義
★ 網格圖上有效電阻計算方法的比較	★ 數樹：方法綜述
★ 拉普拉斯居中度研究概述	★ 信息居中度研究簡要回顧

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

蛋白質在生物化學中扮演非常重要的角色，蛋白質的化學構造非常複雜，然而大多數生物學家相信蛋白質的摺疊方式是唯一的：將蛋白質拆解拉成一長串胺機酸序列後，蛋白質會在數微秒到數毫秒間恢復原狀。這個問題也一直是生物學家、化學家、物理學家爭論的焦點，然而一直得不到令各方信服的說法。近年來，數學家想以數學模型來模擬此一問題：”蛋白質摺疊的唯一性”。
本論文採用Dill於1985年依據能量觀點所提出的二維HP模型為基礎，討論蛋白質摺疊的唯一性的問題(Crescenzi等人已於1998年證明此一問題在二維HP模型下為NP-complete)。本論文分為三章：第一章，簡介蛋白質構造及摺疊問題。第二章，針對Norman於2002年所提出的演算法做出細部修正。第三章，討論由Brian Hayes於1998年所提出的問題：在二維HP模型下，什麼樣的蛋白質序列有唯一摺疊？本文以迥異於Brian Hayes的想法，提出並證明長度為4k+5時的序列型態。並推測長度為4k+3時，具唯一摺疊的序列。

摘要(英)

There are three chapters in this paper.
In chapter1, we introduce the structures of proteins and the HP model suggest by Dill in 1985. In chapter2, we consider a algorithm suggested by Alanthan Newman in 2002: It is a 1/3-approximation linear-time algorithm for the protein folding problem on the 2D square lattice. Unfortunately his proof was not sound and had gaps. We claim that there are a few blemishes in his analysis of the algorithm, and we are going to fix it.
In chapter3, we consider a problem suggested by Brian Hayes in 1998: what proteins in the two-dimensional HP model have unique optimal foldings? In particular, we prove that there are (open chains) with the property for all lengths of the form 4k+5.

關鍵字(中)

★ 蛋白質摺疊

關鍵字(英)

★ uniqueness of protein folding

論文目次

Contents I
List of Figures II
Abstract 1
Chapter 1. Introduction 2
1.1 Protein Structure 2
1.2 Dill's HP-model 3
1.3 Folding Rules and Upper Bound 4
Chapter 2. Note for Newman's Approximation Algorithm 6
2.1 Notations and Definitions 6
2.2 Newman's Algorithm for Protein Foldings 8
Chapter 3. Proteins with Unique Optimal Foldings in the 2D HP Model 12
3.1 Definitions and Some Simple Facts 13
3.2 Main Results 17
3.3 Some Relative Results for the Uniqueness of Protein Folding 40
Future Work 43
Acknowledgments 43
Bibliography 44

參考文獻

O. Aichholzer, D. Bremner, E. D. Demaine, H. Meijer, V. Sacristan and M. Soss,
Long Proteins with Unique Uptimal Foldings in the HP-model,
Computational Geometry, 25 (2003), 139-159.
B. Berger and T. Leighton,
Protein Folding in the Hydrophobic-hydrophilic (HP) Model is NP-complete,
Journal of Computational Biology, 5(1) 1998, 27-40.
H. S. Chan and K. A. Dill,
The Protein Folding Problem,
Physic Today, (1993), 24-32.
P. Crescenzi, D. Goldman, C. Papadimitriou, A. Piccoboni, and M. Yannakais
On the Complexity of Protein Folding,
In Proceedings of the Second International Conference on Computational Molecular Biology(RECOMB), New York, NY, March 22-25, 1998.
K. A. Dill,
Theory for the Folding and Stability of Globular Proteins,
Biochemistry, 24 (1985), p.1501.
K. A. Dill,
Dominant Forces in Protein Folding,
Biochemistry, 29(31) (1990), 7133-7155.
B. Hayes,
Prototeins,
American Scientist, 86 (1998), 216-221.
W. E. Hart and S. Istrail,
Fast Protein Folding in the Hydrophobic-hydrophilic
Model within Three-eights of Optimal, In Proceedings of the 27th Annual ACM Symposium on the Theory of Computing, (1995), 157-168.
G. Mauri, A. Piccolboni, and G. Pavesi
Approximation Algoritms for Protein Folding Prediction,
Proceedings of the 10th ACM-SIAM Symposium on Discrete Algoritms(SODA'99).
A. Newman,
A new algorithm for protein folding in the HP model
In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms, (2002), 287-296.

指導教授

葉鴻國(Hong-Gwa Yeh)

審核日期

2004-8-3

推文