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

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

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

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

ขั้นตอนวิธี

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

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

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

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

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

${\displaystyle H(i,j)=\max {\begin{Bmatrix}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{Bmatrix}},\;1\leq i\leq m,1\leq j\leq 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 ${\displaystyle H={\begin{pmatrix}&-&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{pmatrix}}}$ 

คิดย้อนกลับเมตริกซ์ จะได้พิกัด (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)