ขั้นตอนวิธีสมิธ-วอเตอร์แมน
ลิงก์ข้ามภาษาในบทความนี้ มีไว้ให้ผู้อ่านและผู้ร่วมแก้ไขบทความศึกษาเพิ่มเติมโดยสะดวก เนื่องจากวิกิพีเดียภาษาไทยยังไม่มีบทความดังกล่าว กระนั้น ควรรีบสร้างเป็นบทความโดยเร็วที่สุด |
ขั้นตอนวิธีสมิธ-วอเตอร์แมน (อังกฤษ: Smith-Waterman algorithm) นำเสนอโดย Temple F. Smith และ Michael S. Waterman ในปี 1981
เป็นขั้นตอนวิธีสำหรับการปรับแนวของลำดับเฉพาะที่ เพื่อหารูปแบบของลำดับให้เหมือนลำดับสองลำดับที่ต้องการ มากที่สุด
ขั้นตอนวิธีนี้มีชื่อเสียงเพื่อเรียงลำดับของ โปรตีน หรือ นิวคลีโอไทด์ โดยใช้ระบบให้คะแนนเมตริกซ์และ กำหนดพลวัตในการแก้ปัญหา
ขั้นตอนวิธี
[แก้]1. สร้างเมตริกซ์สมมาตร H ขนาดใหญ่กว่าความยาวของลำดับ 1 ช่อง
2. ให้คะแนนเมตริกซ์แต่ละช่องด้วยเงื่อนไขดังนี้
- โดยที่ m,n=ความยาวของลำดับ 1และ2 ตามลำดับ
-ถ้าลำดับลำดับที่ i,j ของลำดับที่ 1 และ 2 ตรงกัน ถ้าไม่ตรงกัน
-เติมช่องเมตริกซ์แต่ละช่องให้เป็นค่ามากที่สุดดังต่อไปนี้
3. นำเมตริกซ์ที่ได้ไปคิดย้อนกลับเพื่อหาลำดับที่ได้ผลลัพธ์ค่ามากที่สุดโดยคิดดังนี้
-หาค่าจากเมตริกซ์ช่องก่อนหน้าที่มากที่สุด จนได้เมตริกซ์ช่องที่มีค่าเป็น 0
-นำพิกัดช่อง (i,j) ที่ย้อนไปจากขั้นตอนที่แล้วมาหาลำดับ โดย
-พิกัดที่เปลี่ยนแปลงทั้ง i,j หมายถึงกรณีที่ ลำดับ i,j ของลำดับสองตรงกัน หรือไม่ตรงกัน
-พิกัดที่เปลี่ยน i เพียงอย่างเดียว หมายถึงกรณีที่ คิดลำดับ i-1,j แทน i,j
-พิกัดที่เปลี่ยน j เพียงอย่างเดียว หมายถึงกรณีที่ คิดลำดับ j-1,j แทน i,j
4. พิจารณ์กรณีต่างๆ โดยดูจากเมตริกซ์และพิกัดที่เปลี่ยนไป จนเป็นลำดับที่ต้องการ
ตัวอย่าง
[แก้]ลำดับแรก = ACACACTA
ลำดับที่สอง = AGCACACA
สร้างเมตริกซ์ H
คิดย้อนกลับเมตริกซ์ จะได้พิกัด (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) เก็บถาวร 2012-07-17 ที่ เวย์แบ็กแมชชีน