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

จากวิกิพีเดีย สารานุกรมเสรี

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

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


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

ประวัติ[แก้]

ในครั้งแรกที่นำเสนอขั้นตอนวิธีนี้ นีเดอมาน–วานซ์ได้อธิบายขั้นตอนวิธีของพวกเขา โดยคิดเฉพาะกรณีที่ลำดับนั้น ตรงกัน และ ไม่ตรงกัน แต่ไม่ได้อธิบายถึง กรณีที่มี ช่องว่าง ไว้ด้วย (ไม่ได้คิดถึง 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 (n3)

ภายหลังมีการพัฒนาขั้นตอนวิธีการเขียนโปรแกรมกำหนดการพลวัตที่ดีกว่าสามารถทำงานอยู่ในช่วงเวลากำลังสองในปัญหาเดียวกัน (ไม่มี 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 (Ai, Bj)
      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 (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
  }


อ้างอิง[แก้]

  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 Check |doi= value (help). PMID 5420325. 
  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. 
  3. Vintsyuk, T. K. (1968). "Speech discrimination by dynamic programming". Kibernetika 4: 81–88. 
  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. 
  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. 

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


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


ดูเพิ่ม[แก้]

ศึกษาเพิ่มเติม[แก้]