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

ขั้นตอนวิธีสมิธ-วอเตอร์แมน  () นำเสนอโดย 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) 

หมวดหมู่:ขั้นตอนวิธีชีวสารสนเทศศาสตร์
หมวดหมู่:กำหนดการพลวัต