ขั้นตอนวิธีของนีเดอมาน–วานซ์

ขั้นตอนวิธีของนีเดอมาน–วานซ์ เป็นการทำ บนลำดับสองลำดับ คือการหาลำดับที่ดีที่สุดในการจัดเรียงให้ลำดับ A และ B ตรงกันในทุกตำแหน่งให้ได้มากที่สุดเท่าที่จะเป็นไปได้ มีการใช้กันทั่วไปใน ชีวสารสนเทศศาสตร์ เพื่อเรียงลำดับของ โปรตีน หรือ นิวคลีโอไทด์ ขั้นตอนวิธีนี้ถูกตีพิมพ์ในปี 1970 โดย และ .
ขั้นตอนวิธีของนีเดอมาน–วานซ์ เป็นหนึ่งในตัวอย่างของการเขียนโปรแกรมโดยใช้เทคนิค กำหนดการพลวัต และเป็นการใช้กำหนดการพลวัตครั้งแรกในการเปรียบเทียบลำดับชีวภาพ
ในประเทศไทยก็มีการศึกษาเกี่ยวกับขั้นตอนวิธีนี้ด้วยเช่นกัน โดยจะเห็นได้จากโครงงานวิจัย ทั้งจากมหาลัย และจากเอกชนมากมาย ยกตัวอย่างเช่น โครงงานการตรวจสอบผู้ใช้ด้วยรหัสผ่านและข้อมูลรูปแบบการพิมพ์ โครงงานนี้เป็นการตรวจสอบผู้ใช้คอมพิวเตอร์ด้วยระบบการวิเคราะห์จังหวะการพิมพ์ (Keystroke Verification) สำหรับใช้เสริมความปลอดภัยให้กับระบบตรวจสอบรหัสผ่าน จากวิธีการเปรียบเทียบ ระดับกรด-เบส DNA ด้วยวิธี Needleman-Wunsch Algorithm และบบSmith-Waterman Algorithm 
ประวัติ.
ในครั้งแรกที่นำเสนอขั้นตอนวิธีนี้ นีเดอมาน–วานซ์ได้อธิบายขั้นตอนวิธีของพวกเขา โดยคิดเฉพาะกรณีที่ลำดับนั้น "ตรงกัน" และ "ไม่ตรงกัน" แต่ไม่ได้อธิบายถึง กรณีที่มี "ช่องว่าง" ไว้ด้วย (ไม่ได้คิดถึง gap penalty) ("d"=0). การตีพิมพ์ครั้งแรก จากปี 1970 ได้นำเสนอ รูปแบบการเรียกซ้ำไว้ดังนี้
<math>F_{ij} = \max_{h.
จะสามารถเขียนโปรแกรมเชิงพลวัตออกมาได้ O (n3)
ภายหลังมีการพัฒนาขั้นตอนวิธีการเขียนโปรแกรมกำหนดการพลวัตที่ดีกว่าสามารถทำงานอยู่ในช่วงเวลากำลังสองในปัญหาเดียวกัน (ไม่มี gap penalty) ได้ถูกนำเสนอใน ปี ค.ศ. 1972 โดย David Sankoff
และยังมีขั้นตอนวิธีที่ถูกคิดขึ้นโดย T. K. Vintsyuk ก็สามารถทำงานในช่วงเวลากำลังสองได้เช่นกัน ในปี ค.ศ. 1968 ในการบรรยายเรื่อง processing
 และโดย Robert A. Wagner and ในปี ค.ศ. 1974
นีเดอมาน และ วานซ์กำหนดปัญหาของพวกเขาในกรณีที่ลำดับทั้งสอง เหมือนกันมากที่สุด ยังมีความเป็นไปได้ที่จะลดขนาด ระหว่างสองลำดับ ถูกนำเสนอโดย ต่อมา Peter H. Sellers ได้แสดงให้เห็นถึง ในปี ค.ศ. 1974 ว่าการแก้ปัญหาด้วยขั้นตอนวิธีทั้งสองนั้นต่างมีผลเท่ากัน
นิยามสมัยปัจจุบัน "นีเดอมาน–วานซ์" หมายถึง
ขั้นตอนวิธี ที่ใช้เวลาการทำงานเป็นกำลังสอง
ขั้นตอนวิธี.
การให้คะแนนการเรียงตัวอักษรจะอยู่ในรูปแบบ เมตริกซ์สมมาตร โดย <math>S (a, b) </math> จะเป็นคะแนนความเหมือนกันของ "a" และ "b" และ "d" เป็น linear .
ยกตัวอย่างเช่นเมตริกซ์สมมาตรด้านล่าง
จะมีการเรียงตัวเป็น
ATCG
-TCG
ในการหาการเรียงตัวที่มีคะแนนสูงสุด ทำได้โดยกำหนด "F" เป็น อาเรย์ (หรือ เมตริกซ์) โดยมี แถว "i" และสดมภ์ "j" เป็น
<math>F_{ij}</math> จะมีหนึ่งสดมภ์สำหรับแต่ละอักขระใน "A" และหนึ่งแถวสำหรับแต่ละอักขระใน "B" ดังนั้นหากเราต้องการทำ sequence alignment ที่มีขนาด "n" และ "m" จำเป็นต้องใช้เมโมรี่ที่มีขนาด <math>O (nm) </math>. เราสามารถหาการเรียงที่ดีที่สุดได้โดยใช้ (จะใช้เวลาเป็น <math>\Theta (\min \{n,m\}) </math>)
การทำงานของขั้นตอนวิธีนี้คือจะให้ <math>F_{ij}</math> เป็นคะแนนสูงที่สุดของอักขระ <math>i=0...,n</math> แรกในลำดับ "A" และ <math>j=0...,m</math> แรกในลำดับ "B" และใช้ ดังนี้
Basis:
<math>F_{0j} = d*j</math>
<math>F_{i0} = d*i</math>
Recursion, based on the principle of optimality:
<math>F_{ij} = \max (F_{i-1,j-1} + S (A_{i}, B_{j}), \; F_{i,j-1} + d, \; F_{i-1,j} + d) </math>
รหัสเทียมของขั้นตอนวิธีในการหา เมตริกซ์ F มีดังนี้
 for i=0 to length (A)
 F (i,0) ← d*i
 for j=0 to length (B)
 F (0,j) ← d*j
 for i=1 to length (A)
 for j = 1 to length (B)
 Match ← F (i-1,j-1) + S (Ai, Bj)
 Delete ← F (i-1, j) + d
 Insert ← F (i, j-1) + d
 F (i,j) ← max (Match, Insert, Delete)
เมื่อเราหาเมตริกซ์ F ได้แล้ว <math>F_{nm}</math> จะเป็นคะแนนสูงที่สุดของการเรียงที่เป็นไปได้ ในการเติมเมตริกซ์ F นี้ ทำได้โดยเริ่มจากการเติมช่องล่างขวา และทำการเปรียบเทียบระหว่าง 3 กรณีที่เป็นไปได้หาว่ากรณีไหนได้คะแนนสูงสุด (กรณีเท่ากัน, แทรก, ลบ) ถ้า เท่ากัน นั่นคือ <math>A_i</math> และ <math>B_j</math> นั้นตรงกัน, ถ้า ลบหมายความว่า <math>A_i</math> นั้นตรงกับช่องว่าง, และถ้า แทรก หมายความว่า <math>B_j</math>นั้นตรงกับช่องว่าง (การเติมเมตริกซ์ F โดยทั่วไปนั้น อาจมีช่องที่มีคะแนนเท่ากันได้หลายช่อง นั่นคือมีทางเลือกที่ดีที่สุดได้หลายทาง)
 AlignmentA ← "
 AlignmentB ← "
 i ← length (A)
 j ← length (B)
 while (i > 0 and j > 0)
 Score ← F (i,j)
 ScoreDiag ← F (i - 1, j - 1)
 ScoreUp ← F (i, j - 1)
 ScoreLeft ← F (i - 1, j)
 if (Score == ScoreDiag + S (Ai, Bj))
 AlignmentA ← Ai + AlignmentA
 AlignmentB ← Bj + AlignmentB
 i ← i - 1
 j ← j - 1
 else if (Score == ScoreLeft + d)
 AlignmentA ← Ai + AlignmentA
 AlignmentB ← "-" + AlignmentB
 i ← i - 1
 otherwise (Score == ScoreUp + d)
 AlignmentA ← "-" + AlignmentA
 AlignmentB ← Bj + AlignmentB
 j ← j - 1
 while (i > 0)
 AlignmentA ← Ai + AlignmentA
 AlignmentB ← "-" + AlignmentB
 i ← i - 1
 while (j > 0)
 AlignmentA ← "-" + AlignmentA
 AlignmentB ← Bj + AlignmentB
 j ← j - 1