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

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

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

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

ประวัติแก้ไข

ในครั้งแรกที่นำเสนอขั้นตอนวิธีนี้ นีเดอมาน–วานซ์ได้อธิบายขั้นตอนวิธีของพวกเขา โดยคิดเฉพาะกรณีที่ลำดับนั้น ตรงกัน และ ไม่ตรงกัน แต่ไม่ได้อธิบายถึง กรณีที่มี ช่องว่าง ไว้ด้วย (ไม่ได้คิดถึง gap penalty) (d=0). การตีพิมพ์ครั้งแรก ^[1] จากปี 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) ได้ถูกนำเสนอใน ^[2] ปี ค.ศ. 1972 โดย David Sankoff และยังมีขั้นตอนวิธีที่ถูกคิดขึ้นโดย T. K. Vintsyuk ก็สามารถทำงานในช่วงเวลากำลังสองได้เช่นกัน ^[3] ในปี ค.ศ. 1968 ในการบรรยายเรื่อง processing ("time warping") และโดย Robert A. Wagner and Michael J. Fischer^[4] ในปี ค.ศ. 1974

นีเดอมาน และ วานซ์กำหนดปัญหาของพวกเขาในกรณีที่ลำดับทั้งสอง เหมือนกันมากที่สุด ยังมีความเป็นไปได้ที่จะลดขนาด edit distance ระหว่างสองลำดับ ถูกนำเสนอโดย Vladimir Levenshtein ต่อมา Peter H. Sellers ได้แสดงให้เห็นถึง ^[5] ในปี ค.ศ. 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_i, B_j)
      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_i, B_j))
    {
      AlignmentA ← A_i + AlignmentA
      AlignmentB ← B_j + AlignmentB
      i ← i - 1
      j ← j - 1
    }
    else if (Score == ScoreLeft + d)
    {
      AlignmentA ← A_i + AlignmentA
      AlignmentB ← "-" + AlignmentB
      i ← i - 1
    }
    otherwise (Score == ScoreUp + d)
    {
      AlignmentA ← "-" + AlignmentA
      AlignmentB ← B_j + AlignmentB
      j ← j - 1
    }
  }
  while (i > 0)
  {
    AlignmentA ← A_i + AlignmentA
    AlignmentB ← "-" + AlignmentB
    i ← i - 1
  }
  while (j > 0)
  {
    AlignmentA ← "-" + AlignmentA
    AlignmentB ← B_j + AlignmentB
    j ← j - 1
  }

อ้างอิงแก้ไข

↑ ^1.0 ^1.1 Needleman, Saul B.; and Wunsch, Christian D. (1970). (70) 90057-4 "A general method applicable to the search for similarities in the amino acid sequence of two proteins". Journal of Molecular Biology. 48 (3): 443–53. doi:10.1016/0022-2836 (70) 90057-4. PMID 5420325. {{cite journal}}: ตรวจสอบค่า |doi= (help); ตรวจสอบค่า |url= (help)CS1 maint: multiple names: authors list (ลิงก์)
↑ Sankoff, D. (1972). "Matching sequences under deletion/insertion constraints". Proceedings of the National Academy of Sciences of the USA. 69 (1): 4–6. doi:10.1073/pnas.69.1.4. PMC 427531. PMID 4500555.
↑ Vintsyuk, T. K. (1968). "Speech discrimination by dynamic programming". Kibernetika. 4: 81–88.
↑ Wagner, R. A. and Fischer, M. J. (1974). "The string-to-string correction problem". Journal of the ACM. 21 (1): 168–173. doi:10.1145/321796.321811.{{cite journal}}: CS1 maint: multiple names: authors list (ลิงก์)
↑ Sellers, P. H. (1974). "On the theory and computation of evolutionary distances". SIAM Journal on Applied Mathematics. 26 (4): 787–793. doi:10.1137/0126070.

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

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

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

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

ดูเพิ่มแก้ไข

ศึกษาเพิ่มเติมแก้ไข

[Needleman-1] 1.0 ^1.1 Needleman, Saul B.; and Wunsch, Christian D. (1970). (70) 90057-4 "A general method applicable to the search for similarities in the amino acid sequence of two proteins". Journal of Molecular Biology. 48 (3): 443–53. doi:10.1016/0022-2836 (70) 90057-4. PMID 5420325. {{cite journal}}: ตรวจสอบค่า |doi= (help); ตรวจสอบค่า |url= (help)CS1 maint: multiple names: authors list (ลิงก์)

[Sankoff-2] Sankoff, D. (1972). "Matching sequences under deletion/insertion constraints". Proceedings of the National Academy of Sciences of the USA. 69 (1): 4–6. doi:10.1073/pnas.69.1.4. PMC 427531. PMID 4500555.

[Vintsyuk-3] Vintsyuk, T. K. (1968). "Speech discrimination by dynamic programming". Kibernetika. 4: 81–88.

[WagnerFischer-4] Wagner, R. A. and Fischer, M. J. (1974). "The string-to-string correction problem". Journal of the ACM. 21 (1): 168–173. doi:10.1145/321796.321811.{{cite journal}}: CS1 maint: multiple names: authors list (ลิงก์)

[Sellers-5] Sellers, P. H. (1974). "On the theory and computation of evolutionary distances". SIAM Journal on Applied Mathematics. 26 (4): 787–793. doi:10.1137/0126070.

[1]

[2]

[3]

[4]

[5]