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

ประวัติ

ในครั้งแรกที่นำเสนอขั้นตอนวิธีนี้ นีเดอมาน–วานซ์ได้อธิบายขั้นตอนวิธีของพวกเขา โดยคิดเฉพาะกรณีที่ลำดับนั้น ตรงกัน และ ไม่ตรงกัน แต่ไม่ได้อธิบายถึง กรณีที่มี ช่องว่าง ไว้ด้วย (ไม่ได้คิดถึง gap penalty) (d=0). การตีพิมพ์ครั้งแรก  จากปี 1970 ได้นำเสนอ รูปแบบการเรียกซ้ำไว้ดังนี้ F_{ij} = \max_{h<i,k<j} \{ F_{h,j-1}+S (A_{i},B_{j}), F_{i-1,k}+S (A_i,B_j) \}. จะสามารถเขียนโปรแกรมเชิงพลวัตออกมาได้ O (n³)
ภายหลังมีการพัฒนาขั้นตอนวิธีการเขียนโปรแกรมกำหนดการพลวัตที่ดีกว่าสามารถทำงานอยู่ในช่วงเวลากำลังสองในปัญหาเดียวกัน (ไม่มี gap penalty) ได้ถูกนำเสนอใน  ปี ค.ศ. 1972 โดย David Sankoff และยังมีขั้นตอนวิธีที่ถูกคิดขึ้นโดย T. K. Vintsyuk ก็สามารถทำงานในช่วงเวลากำลังสองได้เช่นกัน  ในปี ค.ศ. 1968 ในการบรรยายเรื่อง processing ("time warping") และโดย Robert A. Wagner and Michael J. Fischer ในปี ค.ศ. 1974
นีเดอมาน และ วานซ์กำหนดปัญหาของพวกเขาในกรณีที่ลำดับทั้งสอง เหมือนกันมากที่สุด ยังมีความเป็นไปได้ที่จะลดขนาด edit distance ระหว่างสองลำดับ ถูกนำเสนอโดย Vladimir Levenshtein ต่อมา Peter H. Sellers ได้แสดงให้เห็นถึง  ในปี ค.ศ. 1974 ว่าการแก้ปัญหาด้วยขั้นตอนวิธีทั้งสองนั้นต่างมีผลเท่ากัน
นิยามสมัยปัจจุบัน "นีเดอมาน–วานซ์" หมายถึง ขั้นตอนวิธี global alignment ที่ใช้เวลาการทำงานเป็นกำลังสอง

ขั้นตอนวิธี

การให้คะแนนการเรียงตัวอักษรจะอยู่ในรูปแบบ เมตริกซ์สมมาตร โดย S (a, b)  จะเป็นคะแนนความเหมือนกันของ a และ b และ d เป็น linear gap penalty.
ยกตัวอย่างเช่นเมตริกซ์สมมาตรด้านล่าง

จะมีการเรียงตัวเป็น
ตัวอย่างการจัดเรียง
ATCG
-TCG
ในการหาการเรียงตัวที่มีคะแนนสูงสุด ทำได้โดยกำหนด F เป็น อาเรย์ (หรือ เมตริกซ์) โดยมี แถว i และสดมภ์ j เป็น F_{ij} จะมีหนึ่งสดมภ์สำหรับแต่ละอักขระใน A และหนึ่งแถวสำหรับแต่ละอักขระใน B ดังนั้นหากเราต้องการทำ sequence alignment ที่มีขนาด n และ m จำเป็นต้องใช้เมโมรี่ที่มีขนาด O (nm) . เราสามารถหาการเรียงที่ดีที่สุดได้โดยใช้ (Hirschberg's algorithm จะใช้เวลาเป็น \Theta (\min \{n,m\}) )
การทำงานของขั้นตอนวิธีนี้คือจะให้ F_{ij} เป็นคะแนนสูงที่สุดของอักขระ i=0,...,n แรกในลำดับ A และ j=0,...,m แรกในลำดับ B และใช้ principle of optimality ดังนี้ Basis: F_{0j} = d*j F_{i0} = d*i Recursion, based on the principle of optimality: F_{ij} = \max (F_{i-1,j-1} + S (A_{i}, B_{j}), \; F_{i,j-1} + d, \; F_{i-1,j} + d) 
รหัสเทียมของขั้นตอนวิธีในการหา เมตริกซ์ 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 (Aᵢ, Bⱼ)
      Delete ← F (i-1, j) + d
      Insert ← F (i, j-1) + d
      F (i,j) ← max (Match, Insert, Delete)
    }
เมื่อเราหาเมตริกซ์ F ได้แล้ว F_{nm} จะเป็นคะแนนสูงที่สุดของการเรียงที่เป็นไปได้ ในการเติมเมตริกซ์ F นี้ ทำได้โดยเริ่มจากการเติมช่องล่างขวา และทำการเปรียบเทียบระหว่าง 3 กรณีที่เป็นไปได้หาว่ากรณีไหนได้คะแนนสูงสุด (กรณีเท่ากัน, แทรก, ลบ) ถ้า เท่ากัน นั่นคือ A_i และ B_j นั้นตรงกัน, ถ้า ลบหมายความว่า A_i นั้นตรงกับช่องว่าง, และถ้า แทรก หมายความว่า B_jนั้นตรงกับช่องว่าง (การเติมเมตริกซ์ 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 (Aᵢ, Bⱼ))
    {
      AlignmentA ← Aᵢ + AlignmentA
      AlignmentB ← Bⱼ + AlignmentB
      i ← i - 1
      j ← j - 1
    }
    else if (Score == ScoreLeft + d)
    {
      AlignmentA ← Aᵢ + AlignmentA
      AlignmentB ← "-" + AlignmentB
      i ← i - 1
    }
    otherwise (Score == ScoreUp + d)
    {
      AlignmentA ← "-" + AlignmentA
      AlignmentB ← Bⱼ + AlignmentB
      j ← j - 1
    }
  }
  while (i > 0)
  {
    AlignmentA ← Aᵢ + AlignmentA
    AlignmentB ← "-" + AlignmentB
    i ← i - 1
  }
  while (j > 0)
  {
    AlignmentA ← "-" + AlignmentA
    AlignmentB ← Bⱼ + AlignmentB
    j ← j - 1
  }