Multiple Sequence Alignment Using Dynamic Programming Technique

摘要

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