Multiple Sequence Alignment Using Dynamic Programming Technique

论文摘要

多重序列比对（MSA）是在现代生物学领域应用中的最重要方法之一。MSA被应用于生物信息学中的不同领域,譬如功能和结构预测以及基因的进化。不过MSA是一个NP-hard问题,因此启发式方法可在合理的时间内完成大量的数据比对。当进行比对时,我们有许多不同的方法如动态规划法、启发性方法、渐进法等。在现有的探索性方法中,CLUSTALW被认为是一种优越的应用软件,其能够提供较优势的序列分析法。虽然有着许多不同方法,但我们不能确定哪种方法是最好的,因为它们都具有不同的优势.本论文将介绍多重序列比对理论和现有的MSA应用程序。此后本文将基于动态规划法进行分析及提出解决方案。本文逐渐完成双序列比对、三序列比对和多中心比对（MCSA）。在每次测试中,选取不同长度的序列,并对结果进行了分析。本论文的主要工作是在动态规划法基础上改进了矩阵分析方法。本论文使用最低分数构成矩阵并会按由下而上方向填入数据,序列比对结果取决于“打分矩阵、差距、方法”。同时本论文还对动态规划法和渐进法进行实验分析。

论文目录

• ABSTRACT
• 摘要
• CHAPTER 1: INTRODUCTION
• 1.1 Statement problem
• 1.2 The power of alignment system
• 1.3 Necessity of Sequence Alignment Adjustments
• 1.4 The Structure of thesis
• CHAPTER 2: BACKGROUND
• 2.1 Basic of biology
• 2.1.1 DNA
• 2.1.2 RNA
• 2.1.3 Proteins
• 2.2 Multiple alignment concept overviews
• 2.2.1 Definition of sequence alignment
• 2.2.2 Classification
• 2.2.2.1 Evolutionary Mutations
• 2.2.3 Other concepts
• 2.2.3.1 Scoring Matrix
• 2.2.3.2 Gap and penalties
• 2.2.3.3 Scoring Method
• 2.3 Sequence alignment and Biology
• 2.3.1 Determine Function from Structure
• 2.3.2 Phylogenetic tree
• CHAPTER 3: SEQUENCES ALIGNMENT
• 3.1 Pairwise Sequence Alignment
• 3.1.1 Scoring Sequence Align
• 3.2 Pairwise Sequence Alignment Method
• 3.2.1 Dot matrix analysis
• 3.2.2 Dynamic programming algorithm
• 3.2.3 Word or K-tupe methods
• 3.2.4 Compare Pairwise Sequence Alignment Method
• 3.3 Multiple Sequence Alignment
• 3.3.1 Dynamic Programming
• 3.3.2 Progressive algorithm
• 3.3.3 Interactive algorithm
• 3.3.4 Compare Interactive, Progressive algorithm and Dynamic
• CHAPTER 4: ALGORITHM & IMPLEMENTATION
• 4.1 Dynamic programming algorithm
• 4.1.1 Pairwise algorithm and implementation
• 4.1.1.1 Pairwise Algorithm
• 4.1.1.2 Implementation
• 4.1.2 Three sequences alignment
• 4.1.2.1 Algorithm
• 4.1.2.2 Implementation
• 4.2 Multiple Center Star
• 4.2.1 Implementation
• CHAPTER 5: EXPERIMENT AND RESULTS
• 5.1 Pairwise Alignment result
• 5.2 Three alignment result
• 5.3 Compare Pairwise and Three sequences alignment
• 5.4 Multiple Center Star Alignment
• 5.5 Compare Three - Multiple Center Star Alignment
• CONCLUSION
• REFERENCE
• APPENDIX
• ACKNOWLEDGEMENTS