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

ขั้นตอนวิธีของนีเดอมาน–วานซ์ เป็นการทำ global alignment บนลำดับสองลำดับ global alignment คือการหาลำดับที่ดีที่สุดในการจัดเรียงให้ลำดับ A และ B ตรงกันในทุกตำแหน่งให้ได้มากที่สุดเท่าที่จะเป็นไปได้ มีการใช้กันทั่วไปใน ชีวสารสนเทศศาสตร์ เพื่อเรียงลำดับของ โปรตีน หรือ นิวคลีโอไทด์ ขั้นตอนวิธีนี้ถูกตีพิมพ์ในปี 1970 โดย Saul B. Needleman และ Christian D. Wunsch.

ขั้นตอนวิธีของนีเดอมาน–วานซ์ เป็นหนึ่งในตัวอย่างของการเขียนโปรแกรมโดยใช้เทคนิค กำหนดการพลวัต และเป็นการใช้กำหนดการพลวัตครั้งแรกในการเปรียบเทียบลำดับชีวภาพ

ในประเทศไทยก็มีการศึกษาเกี่ยวกับขั้นตอนวิธีนี้ด้วยเช่นกัน โดยจะเห็นได้จากโครงงานวิจัย ทั้งจากมหาลัย และจากเอกชนมากมาย ยกตัวอย่างเช่น โครงงานการตรวจสอบผู้ใช้ด้วยรหัสผ่านและข้อมูลรูปแบบการพิมพ์ โครงงานนี้เป็นการตรวจสอบผู้ใช้คอมพิวเตอร์ด้วยระบบการวิเคราะห์จังหวะการพิมพ์ (Keystroke Verification) สำหรับใช้เสริมความปลอดภัยให้กับระบบตรวจสอบรหัสผ่าน จากวิธีการเปรียบเทียบ ระดับกรด-เบส DNA ด้วยวิธี Needleman-Wunsch Algorithm และบบSmith-Waterman Algorithm [1] เก็บถาวร 2012-05-28 ที่ เวย์แบ็กแมชชีน

ประวัติ

ในครั้งแรกที่นำเสนอขั้นตอนวิธีนี้ นีเดอมาน–วานซ์ได้อธิบายขั้นตอนวิธีของพวกเขา โดยคิดเฉพาะกรณีที่ลำดับนั้น ตรงกัน และ ไม่ตรงกัน แต่ไม่ได้อธิบายถึง กรณีที่มี ช่องว่าง ไว้ด้วย (ไม่ได้คิดถึง gap penalty) (d=0). การตีพิมพ์ครั้งแรก จากปี 1970 ได้นำเสนอ รูปแบบการเรียกซ้ำไว้ดังนี้ ${\displaystyle 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 ที่ใช้เวลาการทำงานเป็นกำลังสอง

ขั้นตอนวิธี

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

ยกตัวอย่างเช่นเมตริกซ์สมมาตรด้านล่าง

จะมีการเรียงตัวเป็น

ATCG

-TCG

ในการหาการเรียงตัวที่มีคะแนนสูงสุด ทำได้โดยกำหนด F เป็น อาเรย์ (หรือ เมตริกซ์) โดยมี แถว i และสดมภ์ j เป็น ${\displaystyle F_{ij}}$ จะมีหนึ่งสดมภ์สำหรับแต่ละอักขระใน A และหนึ่งแถวสำหรับแต่ละอักขระใน B ดังนั้นหากเราต้องการทำ sequence alignment ที่มีขนาด n และ m จำเป็นต้องใช้เมโมรี่ที่มีขนาด ${\displaystyle O(nm)}$. เราสามารถหาการเรียงที่ดีที่สุดได้โดยใช้ (Hirschberg's algorithm จะใช้เวลาเป็น ${\displaystyle \Theta (\min\{n,m\})}$)

การทำงานของขั้นตอนวิธีนี้คือจะให้ ${\displaystyle F_{ij}}$ เป็นคะแนนสูงที่สุดของอักขระ ${\displaystyle i=0,...,n}$ แรกในลำดับ A และ ${\displaystyle j=0,...,m}$ แรกในลำดับ B และใช้ principle of optimality ดังนี้ Basis: ${\displaystyle F_{0j}=d*j}$ ${\displaystyle F_{i0}=d*i}$ Recursion, based on the principle of optimality: ${\displaystyle 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 (Ai, Bj)
      Delete ← F (i-1, j) + d
      Insert ← F (i, j-1) + d
      F (i,j) ← max (Match, Insert, Delete)
    }

เมื่อเราหาเมตริกซ์ F ได้แล้ว ${\displaystyle F_{nm}}$ จะเป็นคะแนนสูงที่สุดของการเรียงที่เป็นไปได้ ในการเติมเมตริกซ์ F นี้ ทำได้โดยเริ่มจากการเติมช่องล่างขวา และทำการเปรียบเทียบระหว่าง 3 กรณีที่เป็นไปได้หาว่ากรณีไหนได้คะแนนสูงสุด (กรณีเท่ากัน, แทรก, ลบ) ถ้า เท่ากัน นั่นคือ ${\displaystyle A_{i}}$ และ ${\displaystyle B_{j}}$ นั้นตรงกัน, ถ้า ลบหมายความว่า ${\displaystyle A_{i}}$ นั้นตรงกับช่องว่าง, และถ้า แทรก หมายความว่า ${\displaystyle 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 (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
  }

แหล่งข้อมูลอื่น

• NW-align: A protein sequence-to-sequence alignment program by Needleman-Wunsch algorithm (online server & source code)
• Needleman-Wunsch Algorithm as Ruby Code เก็บถาวร 2006-11-01 ที่ เวย์แบ็กแมชชีน
• Java Implementation of the Needleman-Wunsch Algorithm เก็บถาวร 2007-03-28 ที่ เวย์แบ็กแมชชีน
• B.A.B.A. — an applet (with source) which visually explains the algorithm.
• A clear explanation of NW and its applications to sequence alignment เก็บถาวร 2011-05-15 ที่ เวย์แบ็กแมชชีน
• Sequence Alignment Techniques at Technology Blog
• OPAL เก็บถาวร 2011-08-23 ที่ เวย์แบ็กแมชชีน JavaScript implementation of algorithms: Needleman-Wunsch, Needleman-Wunsch-Sellers and Smith-Waterman
• Biostrings เก็บถาวร 2009-11-06 ที่ เวย์แบ็กแมชชีน R package implementing Needleman-Wunsch algorithm among others

งานวิจัยที่ประยุกต์ใช้ในประเทศไทย

• ขั้นตอนวิธีเชิงวิวัฒน์ดัดแปลงสำหรับการจัดเรียงลำดับเบสหลายลำดับ

ดูเพิ่ม

• Smith-Waterman algorithm
• BLAST
• Levenshtein distance
• Dynamic time warping

ศึกษาเพิ่มเติม

• โครงสร้างข้อมูล (ฉบับวาจาจาวา) โดยสมชาย ประสิทธิ์จูตระกูล
• การออกแบบอัลกอริทึม (Algorithm Design) โดยสมชาย ประสิทธิ์จูตระกูล