使用遺傳演算法解多序列排比的問題

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：14

、訪客IP：18.119.139.59

姓名

林靜媚(Ching-mei Lin) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

使用遺傳演算法解多序列排比的問題
(Using Genetic Algorithms to Solve Multiple Sequence Alignments)

相關論文

★ 應用嵌入式系統於呼吸肌肉群訓練儀之系統開發	★ 勃起障礙與缺血性心臟病的雙向研究: 以台灣全人口基礎的世代研究
★ 基質輔助雷射脫附飛行時間式串聯質譜儀微生物抗藥性資料視覺化工具	★ 使用穿戴式裝置分析心律變異及偵測心律不整之應用程式
★ 建立一個自動化分析系統用來分析任何兩種疾病之間的關聯性透過世代研究設計以及使用承保抽樣歸人檔	★ 青光眼病患併發糖尿病,使用Metformin及Sulfonylurea治療得到中風之風險:以台灣人口為基礎的觀察性研究
★ 利用組成識別和序列及空間特性構成之預測系統來針對蛋白質交互作用上的特殊區段點位進行分析及預測辨識	★ 新聞語意特徵擷取流程設計與股價變化關聯性分析
★ 藥物與疾病關聯性自動化分析平台設計與實作	★ 建立財務報告自動分析系統進行股價預測
★ 建立一個分析疾病與癌症關聯性的自動化系統	★ 基於慣性感測器虛擬鍵盤之設計與實作
★ 一個醫療照護監測系統之實作	★ 應用手機開發手握球握力及相關資料之量測
★ 利用關聯分析全面性的搜索癌症關聯疾病	★ 全面性尋找類風濕性關節炎之關聯疾病

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

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

摘要(中)

多序列排比是分子序列分析上一個重要的工具。在演化的過程中，分子序列可能會發生許多的突變，例如插入、刪除、替代等突變事件；而這些突變造成分子列序間的各種差異。多序列排比是透過同時比較多個序列，以找出序列之間的相似區域，故可找出序列間的結構關係。
本論文提出一個遺傳演算法，來解決多序列排比的問題。我們使用十七個序列的資料集合來測試我們所提出的方法，並且將我們的實驗結果與其它方法做比較。我們發現我們的方法在大多數具有高相似性的測試資料中擁有不錯的表現。

摘要(英)

Multiple sequence alignment is an important tool in molecular
sequence analysis. In the evolutionary process, molecular sequences may have several mutations, such as insertion, deletion and substitution. These mutation events result in the diversified difference between sequences. Multiple sequences alignment can help compare the structure-relationship between sequences by simultaneously aligning multiple sequences to find the similar regions.
This thesis presents genetic algorithms to solve multiple sequence alignments. Several data sets are tested and the experimental results are compared with other methods. We find our approach could obtain good performance in the majority of data sets with high similarity and long sequences.

關鍵字(中)

★ 分子序列分析
★ 遺傳演數法
★ 多序列排比

關鍵字(英)

★ molecular sequence analysis
★ genetic algorithm
★ multiple sequence alignment

論文目次

1. Introduction
1.1 Motivation
1.2 Problem Description
1.3 Organization of The Thesis
2. Related Work
2.1 Optimal alignment of Two Sequences
2.2 The Sum-of-Pairs Measure For Multiple Sequences Alignment
2.3 Literature of Multiple Sequence Alignment
3. Method
3.1 Chromosomes
3.2 System Process Flow
3.3 Fitness
3.4 Crossover
3.5 Mutation
4. Experiments And Results
4.1 Environment of Implementation
4.2 Experiments
5. Conclusion
Bibliography
Appendix Data Set

參考文獻

[AvL87]E.H.L. Aart and P.J.M. van Laarhoven.
Simulated Annealing: a Review of Theory and Applications.
Kluwer Academic, Amsterdam, 1987.
[CF99]Kumar Chellapilla and Gary B. Fogel.
Multiple sequence alignment using evolutionary programming.
Congress on Evolutionary Computation, pages 445-452, 1999.
[CWC92]S. C. Chan, A. K. C. Wong, and D. K. Y. Chiu.
A survey of multiple sequence comparison methods.
Bulletin of Mathematical Biology, 54:563-598, 1992.
[FD87]Da-Fei Feng and Russell F. Doolittle.
Progressive sequence alignment as a prerequisite to correct phylogenetic trees.
Journal of Molecular Evolution, 25:351-360, 1987.
[Gol89]D. E. Goldberg.
Genetic Algorithms in Search, Optimization, and Machine Learning.
Addison-Wesley, New York, 1989.
[Got89] O. Gotoh.
An improved algorithm for matching biological sequences.
Journal of Molecular Biology, 162:705-708, 1989.
[HS88]D.G. Higgins and P.M. Sharp.
CLUSTAL: a package for performing multiple sequence alignments on a microcomputer.
Gene, 73:237-244, 1988.
[IWS96]M. Isokawa, M. Wayama, and T. Shimizu.
Multiple sequence alignment using a genetic algorithm.
Genome Informatics, 7:176-177, 1996.
[Jon88]K. De Jong.
Learning with genetic algorithms: An overview.
In Machine Learning 3, pages 121-138. Kluwer, Hingham, MA, 1988.
[JWD80]R. A. Jue, N. W. Woodbury, and R. F. Doolittle.
Sequence homologies among e. coli ribosomal proteins: evidence for evolutionary related groupings and internal duplications.
Journal of Molecular Evolution, 15:129-148, 1980.
[LAB+93]C.E. Lawrence, S.F. Altschul, M.S. Boguski, J.S. Liu, A.F. Neuwald, and J.C. Wootton.
Detecting subtle sequence signals: a gibbs sampling strategy for multiple alignment.
Science, pages 208-214, 1993.
[MM88]E. W. Myers and W. Miller.
Multiple sequence alignment using simulated annealing.
Computer Applications in the Biosciences, 4(1):11-17, 1988.
[Mor99]B. Morgenstern.
DIALIGN 2: improvement of the segment-to-segment approach to multiple sequence alignment.
Bioinformatics, 15:211-218, 1999.
[MRS85]M. Murata, J. S. Richardson, and J. L. Sussman.
Simultaneous comparison of three protein sequences.
In Proceedings of the National Academy of Science U. S. A., volume 82, pages 3073-3077, 1985.
[NH96]Cedric Notredame and Desmond G. Higgins.
SAGA: sequence alignment by genetic algorithm.
Nucleic Acids Research, 24(8):1515-1524, 1996.
[NOH97]Cedric Notredame, Emmet A. O'Brien, and Desmond G. Higgins.
Raga: Rna sequence alignment by genetic algorithm.
Nucleic Acids Research, 25(22):4570-4580, 1997.
[NW70]S. B. Needleman and C. D. Wunsch.
A general method applicable to the search for similarities in the amino acid sequences of two proteins.
Journal of Molecular Biology, 42:245-161, 1970.
[PW96]Sankar K. Pal and Paul P. Wang.
Genetic algorithms for pattern recognition.
CRC Press, Boca Raton, 1996.
[San72]D. Sankoff.
Matching sequence under deletion-insertion constraints.
In Proceedings of the National Academy of Science U. S. A., volume 64, pages 4-6, Washington, DC, 1972. Academy.
[SM97]Joao Setubal and Joao Meidanis.
Sequence comparison and database search.
In Introduction To Computational Molecular Biology, pages 47-103. PWS, 1997.
[Sto98]Jens Stoye.
Multiple sequence alignment with the divide-and-conquer method.
Gene, 211(2):GC45-GC56, 1998.
[THG94]J.D. Thompson, D.G. Higgins, and T.J. Gibson.
CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position specific gap penalties and weight matrix choice.
Nucleic Acids Research, 22(22):4673-4680, 1994.
[Wat84]M. S. Waterman.
General methods of sequence comparison.
Bulletin of Mathematical Biology, 46:473-500, 1984.
[Whi94]Darrell Whitley.
A genetic algorithm tutorial.
Statistics and Computing, 4:65-85, 1994.
[WJ94]L. Wang and T. Jiang.
On the complexity of multiple sequence alignment.
Journal of Computational Bioloby, 1(4):337-348, 1994.
[WTS95]M. Wayama, K. Takahashi, and T. Shimizu.
An approach to amino acid sequence alignment using a genetic algorithm.
Genome Informatics, 6:122-123, 1995.
[ZW97a]Ching Zhang and Andrew K. C. Wong.
A genetic algorithm for multiple molecular sequence alignment.
Computer Applications in the Biosciences, 13(6):565-581, 1997.
[ZW97b]Ching Zhang and Andrew K. C. Wong.
Toward efficient multiple molecular sequence alignment: A system of genetic algorithm and dynamic programming.
IEEE Transactions on Systems, Man, and Cybernetics-part B: Cybernetics, 27(6):918-932, 1997.

指導教授

洪炯宗(Jorng-Tzong Horng)

審核日期

2000-7-12

推文