隨著 DNA 定序技術的不斷提升以及各種基因體計畫的進行，越來越多的生物序列資料被建構成資料庫，並置於網際網路上免費供人使用。例如存放核酸序列資料的 GenBank、EMBL-Bank 和 DDBJ 等，以及存放蛋白質序列資料的 Swiss-Prot、TrEMBL 和 PIR 等。據估計，平均每 15 個月這些資料庫的內容就會增加一倍。利用這些資料，生物學家再藉由生物資訊和計算生物的分析工具，便可以了解許多生物問題。
在諸多生物資訊和計算生物的分析工具中，序列比對（sequence alignment）是一個基本且相當重要的研究工具，它可以比較及分析出兩條或多條序列之間的相似程度。相似度高的序列彼此間會有相似的結構及功能，這意味著它們可能源自共同的祖先。因此，生物學家一旦拿到未知功能的 DNA 或蛋白質序列時，最常做的事情就是利用序列比對工具搜尋資料庫，看看是否有已知註解功能的序列與手中未知功能的序列相似者，藉此推測手中序列的生物功能。
事實上，任何利用電腦從事研究的人或多或少都會用到演算法。通常我們會用執行時間複雜度來衡量一個演算法是否有效率。演算法的時間複雜度往往表示成一個與 n 有關的函數，n 是輸入資料的大小。若時間複雜度是一個多項式函數，例如 nk，其中 k 是常數，那麼這個演算法就被稱為有效率的演算法。反之若只能表示成非多項式函數，例如指數函數 kn，其中 k 是常數，則稱為沒有效率的演算法。
一般而言，我們會把 DNA 和蛋白質分別看成是由 4 和 20 個英文字母所組成的序列或字串，因為他們分別是由 4 種核酸和 20 種胺基酸所組成的。對 DNA 而言，突變是非常平常的事情，也是自然的演化過程。藉由基因的突變，生物可以適應自然環境的改變。
常見的 DNA 突變有 3 種，分別是取代、插入及刪除。所謂取代，是指把一個字母（即核酸）用另外一個字母取代，而插入或刪除，是指在 DNA 序列的某一個位置插入或刪除一個新的或舊的字母。譬如我們把 DNA 序列 AAGT 的第一個字母 A 用 T 取代，然後把第三個字母 G 刪除，接著在序列的尾巴插入新的字母 C，最後便可以得到一個新的 DNA 序列 TATC。這整個突變的過程就如同大自然在對 DNA 序列進行編輯一般，所以上述 3 種突變又稱為 DNA 的編輯運算。
通常生物學家會利用所謂的編輯距離，來衡量兩條 DNA 序列之間的相異程度。生命總是朝著最短路徑進行演化，所以兩條序列之間的編輯距離被定義為：把其中一條序列編輯轉成另外一條序列，所需最少的編輯運算個數。兩條 DNA 序列之間的編輯距離越小，代表它們之間的相似程度越高。從演化的觀點來說，這意味著它們演化自同一個祖先（即所謂的同源），所以彼此間應該會有相似的結構及功能。
通常生物學家會比較喜歡利用比對來衡量兩條序列之間的相似程度。拿 GACGGATAG 和 GATCGGAATAG 這兩條 DNA 序列來說，乍看之下這兩條長度不同的 DNA 序列似乎不太相似。但是，當我們把它們重疊在一起，並在第一條序列的第二個和第三個字母之間與第六個和第七個字母之間分別插入一個空白字，就可發現其實這兩條 DNA 序列還蠻相像的。這種序列重疊的方式，就稱為序列的比對。
事實上，每一種序列對齊方式都對應著一組編輯運算，可以把一條序列編輯轉成另外一條序列。以下舉例說明我們可以用 3 個編輯運算，把 AGGACTA 序列轉成 ACGTATA 序列。首先用一個取代編輯把第一個 G 轉成 C（對應第二個欄位），然後再用一個插入編輯把 T 插在第三個與第四個字母之間（對應第四個欄位），最後再利用一個刪除編輯把 C 拿掉（對應第六個欄位）。正因為如此，我們把第二個欄位稱為配錯，第四個欄位稱為插入，第六個欄位稱為刪除，其他欄位稱為配對。
首先我們定義一些符號，以便能夠簡單及清楚地介紹兩條序列比對問題的動態規劃演算法。令 A ＝ a1a2 … am 和 B ＝ b1b2 … bn 分別表示長度各為 m 和 n 的兩條序列；令 Align（i,j）表示兩條序列片段 Ai ＝ a1a2 … ai 和 Bj ＝ b1b2 … bj 之間分數（或相似度）最高的對齊方式，其中 i 和 j 的範圍分別是 1 ≦ i ≦ m 與 1 ≦ j ≦ n；令 S（i,j）表示 Align（i,j）的分數。我們的目的就是要求得兩條序列之間最佳的分數 S（m,n）及對齊方式 Align（m,n）。
在這之前，先把焦點放在 S（i,j）和 Align（i,j）的身上，因為若有辦法對任意的 i 和 j 都能計算出 S（i,j）和 Align（i,j），自然就可以求得 S（m,n）和 Align（m,n）。首先，我們把 Align（i,j）切成左右兩半：右半部只含 Align（i,j）的最後一個欄位，左半部則包含剩下的欄位。在這種情況之下，S（i,j）等於左半部的分數加上右半部的分數。不管 Align（i,j）的對齊方式為何，最後一個欄位的對齊方式就只有 3 種：字母對齊字母（即 ai 對齊 bj）、字母對齊空白字（即 ai 對齊 － ）、以及空白字對齊字母（即 － 對齊 bj）。
