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

จากวิกิพีเดีย สารานุกรมเสรี

ขั้นตอนวิธีสมิธ-วอเตอร์แมน (อังกฤษ: Smith-Waterman algorithm) นำเสนอโดย 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 \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\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 = 
\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)