動態規劃算法(Dynamic Programming Algorithm)是壹種計算方法，它的主要思路是把壹個問題分成若幹個小問題來解決
在生物學中應用的兩種動態規劃算法：Needleman-Wunsch算法（全局比對）和Smith-Waterman算法（局部比對）
（1）全局序列比對：
1）兩條序列可以在壹個x- 和y-軸的矩陣中得到比對；
2）如果序列壹致，則可以得到壹條通過對角線的路徑；
3）尋找最佳的次路徑，然後將它們加起來得到最好的得分，
這包括：
需要時插入空隙（gap）
允許保守替代
選擇打分系統（簡單的或復雜的）
Needleman-Wunsch算法可以保證得到最佳的比對
（2）局部序列比對：局部比對的目標是尋找兩序列最優比對區（子序列），不需要延伸到序列的兩端；局部比對是數據庫搜索是最常用的算法，在尋找序列之間的結構域時相當有用。 1）Smith-Waterman 算法
1. 設置壹個矩陣，大小為（m+1, n+1）
2. 矩陣中的值必須不小於0。
3. 矩陣中的每個單元格的分值S是以下四者中的最大值：
1. 算法的目的是尋找矩陣中的最大值，這代表了比對中的結尾處（羧基端）。
2. 回溯過程從最大值的位置開始，沿著對角線向上向左直到碰到壹個零分值的單元格。
3. 算法需要的壹個條件是隨機匹配的期望分值為負，保證不相關的長序列不能得到高分值（大多打分矩陣滿足此條）