ขั้นตอนวิธีสมิธ-วอเตอร์แมน

แม่แบบ:ลิงก์ไปภาษาอื่น ขั้นตอนวิธีสมิธ-วอเตอร์แมน (แม่แบบ:Langx) นำเสนอโดย Temple F. Smith และ Michael S. Waterman ในปี 1981

เป็นขั้นตอนวิธีสำหรับการปรับแนวของลำดับเฉพาะที่ เพื่อหารูปแบบของลำดับให้เหมือนลำดับสองลำดับที่ต้องการ มากที่สุด

ขั้นตอนวิธีนี้มีชื่อเสียงเพื่อเรียงลำดับของ โปรตีน หรือ นิวคลีโอไทด์ โดยใช้ระบบให้คะแนนเมตริกซ์และ กำหนดพลวัตในการแก้ปัญหา

ขั้นตอนวิธี

1. สร้างเมตริกซ์สมมาตร H ขนาดใหญ่กว่าความยาวของลำดับ 1 ช่อง

2. ให้คะแนนเมตริกซ์แต่ละช่องด้วยเงื่อนไขดังนี้

-$H(i,0)=0,H(0,j)=0;0<i<=m,j<=n$ โดยที่ m,n=ความยาวของลำดับ 1และ2 ตามลำดับ

-ถ้าลำดับลำดับที่ i,j ของลำดับที่ 1 และ 2 ตรงกัน $w(a_i,b_j)=2$ถ้าไม่ตรงกัน$w(a_i,b_j)=-1$

-เติมช่องเมตริกซ์แต่ละช่องให้เป็นค่ามากที่สุดดังต่อไปนี้

$H(i,j)=\max \left\{\begin{array}{c}0\\ H(i-1,j-1)+w(a_i,b_j)& \text{Match/Mismatch}\\ H(i-1,j)-1\text{Deletion}\\ H(i,j-1)-1\text{Insertion}\end{array}\right\},1\le i\le m,1\le j\le n$

3. นำเมตริกซ์ที่ได้ไปคิดย้อนกลับเพื่อหาลำดับที่ได้ผลลัพธ์ค่ามากที่สุดโดยคิดดังนี้

-หาค่าจากเมตริกซ์ช่องก่อนหน้าที่มากที่สุด จนได้เมตริกซ์ช่องที่มีค่าเป็น 0

-นำพิกัดช่อง (i,j) ที่ย้อนไปจากขั้นตอนที่แล้วมาหาลำดับ โดย

-พิกัดที่เปลี่ยนแปลงทั้ง i,j หมายถึงกรณีที่ ลำดับ i,j ของลำดับสองตรงกัน หรือไม่ตรงกัน

-พิกัดที่เปลี่ยน i เพียงอย่างเดียว หมายถึงกรณีที่ คิดลำดับ i-1,j แทน i,j

-พิกัดที่เปลี่ยน j เพียงอย่างเดียว หมายถึงกรณีที่ คิดลำดับ j-1,j แทน i,j

4. พิจารณ์กรณีต่างๆ โดยดูจากเมตริกซ์และพิกัดที่เปลี่ยนไป จนเป็นลำดับที่ต้องการ

ตัวอย่าง

ลำดับแรก = ACACACTA

ลำดับที่สอง = AGCACACA

สร้างเมตริกซ์ H $H=\left(\begin{array}{cccccccccc}& -& A& C& A& C& A& C& T& A\\ -& 0& 0& 0& 0& 0& 0& 0& 0& 0\\ A& 0& 2& 1& 2& 1& 2& 1& 0& 2\\ G& 0& 1& 1& 1& 1& 1& 1& 0& 1\\ C& 0& 0& 3& 2& 3& 2& 3& 2& 1\\ A& 0& 2& 2& 5& 4& 5& 4& 3& 4\\ C& 0& 1& 4& 4& 7& 6& 7& 6& 5\\ A& 0& 2& 3& 6& 6& 9& 8& 7& 8\\ C& 0& 1& 4& 5& 8& 8& 11& 10& 9\\ A& 0& 2& 3& 6& 7& 10& 10& 10& 12\end{array}\right)$

คิดย้อนกลับเมตริกซ์ จะได้พิกัด (8,8), (7,7), (7,6), (6,5), (5,4), (4,3), (3,2), (2,1), (1,1), (0,0)

• จาก (8,8) ไป (7,7) แสดงถึง ตัวสุดท้ายมาจาก ตัวสุดท้ายของลำดับแรกและลำดับที่สอง โดย (7,7) จะชี้ถึงตำแหน่งของลำดับในพิกัดที่ 2 และ 1 ตามลำดับ

• จาก (7,7) ไป (7,6) แสดงถึง ตัวถัดไปของลำดับที่สองจะไม่ถูกไม่ใช้ โดย (7,6) จะชี้ถึงตำแหน่งของลำดับในพิกัดที่ 2 และ 1 ตามลำดับ ; เรียกว่า การสอดใส่ (อังกฤษ : Insertion)

...

• จาก (2,1) ไป (1,1) แสดงถึงตัวถัดไปของลำดับแรกจะไม่ถูกใช้ โดย (1,1) จะชี้ถึงตำแหน่งของลำดับในพิกัดที่ 2 และ 1 ตามลำดับ ; เรียกว่า การหลุดหาย (อังกฤษ : Deletion)

...

• คิดย้อนกลับไปจนถึงพิกัด (0,0) จะได้ลำดับดังนี้

ลำดับแรก = A-CACACTA

ลำดับที่สอง = AGCACAC-A

อ้างอิง

Smith, Temple F.; and Waterman, Michael S. (1981) แม่แบบ:Webarchive