การให้คะแนนการเรียงตัวอักษรจะอยู่ในรูปแบบ เมตริกซ์สมมาตร โดย S ( a , b ) {\displaystyle S(a,b)} จะเป็นคะแนนความเหมือนกันของ a และ b และ d เป็น linear gap penalty.

ยกตัวอย่างเช่นเมตริกซ์สมมาตรด้านล่าง

จะมีการเรียงตัวเป็น

ไฟล์:DwATT565.png

ATCG

-TCG

ในการหาการเรียงตัวที่มีคะแนนสูงสุด ทำได้โดยกำหนด F เป็น อาเรย์ (หรือ เมตริกซ์) โดยมี แถว i และสดมภ์ j เป็น F i j {\displaystyle F_{ij}} จะมีหนึ่งสดมภ์สำหรับแต่ละอักขระใน A และหนึ่งแถวสำหรับแต่ละอักขระใน B ดังนั้นหากเราต้องการทำ sequence alignment ที่มีขนาด n และ m จำเป็นต้องใช้เมโมรี่ที่มีขนาด O ( n m ) {\displaystyle O(nm)} . เราสามารถหาการเรียงที่ดีที่สุดได้โดยใช้ (Hirschberg's algorithm จะใช้เวลาเป็น Θ ( min { n , m } ) {\displaystyle \Theta (\min\{n,m\})} )

การทำงานของขั้นตอนวิธีนี้คือจะให้ F i j {\displaystyle F_{ij}} เป็นคะแนนสูงที่สุดของอักขระ i = 0 , . . . , n {\displaystyle i=0,...,n} แรกในลำดับ A และ j = 0 , . . . , m {\displaystyle j=0,...,m} แรกในลำดับ B และใช้ principle of optimality ดังนี้Basis: F 0 j = d ∗ j {\displaystyle F_{0j}=d*j} F i 0 = d ∗ i {\displaystyle F_{i0}=d*i} Recursion, based on the principle of optimality: F i j = max ( F i − 1 , j − 1 + S ( A i , B j ) , F i , j − 1 + d , F i − 1 , j + d ) {\displaystyle F_{ij}=\max(F_{i-1,j-1}+S(A_{i},B_{j}),\;F_{i,j-1}+d,\;F_{i-1,j}+d)}

รหัสเทียมของขั้นตอนวิธีในการหา เมตริกซ์ F มีดังนี้

  for i=0 to length (A)    F (i,0) ← d*i  for j=0 to length (B)    F (0,j) ← d*j  for i=1 to length (A)    for j = 1 to length (B)    {      Match ← F (i-1,j-1) + S (Ai, Bj)      Delete ← F (i-1, j) + d      Insert ← F (i, j-1) + d      F (i,j) ← max (Match, Insert, Delete)    }

เมื่อเราหาเมตริกซ์ F ได้แล้ว F n m {\displaystyle F_{nm}} จะเป็นคะแนนสูงที่สุดของการเรียงที่เป็นไปได้ ในการเติมเมตริกซ์ F นี้ ทำได้โดยเริ่มจากการเติมช่องล่างขวา และทำการเปรียบเทียบระหว่าง 3 กรณีที่เป็นไปได้หาว่ากรณีไหนได้คะแนนสูงสุด (กรณีเท่ากัน, แทรก, ลบ) ถ้า เท่ากัน นั่นคือ A i {\displaystyle A_{i}} และ B j {\displaystyle B_{j}} นั้นตรงกัน, ถ้า ลบหมายความว่า A i {\displaystyle A_{i}} นั้นตรงกับช่องว่าง, และถ้า แทรก หมายความว่า B j {\displaystyle B_{j}} นั้นตรงกับช่องว่าง (การเติมเมตริกซ์ F โดยทั่วไปนั้น อาจมีช่องที่มีคะแนนเท่ากันได้หลายช่อง นั่นคือมีทางเลือกที่ดีที่สุดได้หลายทาง)

  AlignmentA ← ""  AlignmentB ← ""  i ← length (A)  j ← length (B)  while (i > 0 and j > 0)  {    Score ← F (i,j)    ScoreDiag ← F (i - 1, j - 1)    ScoreUp ← F (i, j - 1)    ScoreLeft ← F (i - 1, j)    if (Score == ScoreDiag + S (Ai, Bj))    {      AlignmentA ← Ai + AlignmentA      AlignmentB ← Bj + AlignmentB      i ← i - 1      j ← j - 1    }    else if (Score == ScoreLeft + d)    {      AlignmentA ← Ai + AlignmentA      AlignmentB ← "-" + AlignmentB      i ← i - 1    }    otherwise (Score == ScoreUp + d)    {      AlignmentA ← "-" + AlignmentA      AlignmentB ← Bj + AlignmentB      j ← j - 1    }  }  while (i > 0)  {    AlignmentA ← Ai + AlignmentA    AlignmentB ← "-" + AlignmentB    i ← i - 1  }  while (j > 0)  {    AlignmentA ← "-" + AlignmentA    AlignmentB ← Bj + AlignmentB    j ← j - 1  }