ขั้นตอนวิธีของนีเดอมาน–วานซ์
ลิงก์ข้ามภาษาในบทความนี้ มีไว้ให้ผู้อ่านและผู้ร่วมแก้ไขบทความศึกษาเพิ่มเติมโดยสะดวก เนื่องจากวิกิพีเดียภาษาไทยยังไม่มีบทความดังกล่าว กระนั้น ควรรีบสร้างเป็นบทความโดยเร็วที่สุด |
ขั้นตอนวิธีของนีเดอมาน–วานซ์ เป็นการทำ global alignment บนลำดับสองลำดับ global alignment คือการหาลำดับที่ดีที่สุดในการจัดเรียงให้ลำดับ A และ B ตรงกันในทุกตำแหน่งให้ได้มากที่สุดเท่าที่จะเป็นไปได้ มีการใช้กันทั่วไปใน ชีวสารสนเทศศาสตร์ เพื่อเรียงลำดับของ โปรตีน หรือ นิวคลีโอไทด์ ขั้นตอนวิธีนี้ถูกตีพิมพ์ในปี 1970 โดย Saul B. Needleman และ Christian D. Wunsch.
ขั้นตอนวิธีของนีเดอมาน–วานซ์ เป็นหนึ่งในตัวอย่างของการเขียนโปรแกรมโดยใช้เทคนิค กำหนดการพลวัต และเป็นการใช้กำหนดการพลวัตครั้งแรกในการเปรียบเทียบลำดับชีวภาพ
ในประเทศไทยก็มีการศึกษาเกี่ยวกับขั้นตอนวิธีนี้ด้วยเช่นกัน โดยจะเห็นได้จากโครงงานวิจัย ทั้งจากมหาลัย และจากเอกชนมากมาย ยกตัวอย่างเช่น โครงงานการตรวจสอบผู้ใช้ด้วยรหัสผ่านและข้อมูลรูปแบบการพิมพ์ โครงงานนี้เป็นการตรวจสอบผู้ใช้คอมพิวเตอร์ด้วยระบบการวิเคราะห์จังหวะการพิมพ์ (Keystroke Verification) สำหรับใช้เสริมความปลอดภัยให้กับระบบตรวจสอบรหัสผ่าน จากวิธีการเปรียบเทียบ ระดับกรด-เบส DNA ด้วยวิธี Needleman-Wunsch Algorithm และบบSmith-Waterman Algorithm [1]
ประวัติ
ในครั้งแรกที่นำเสนอขั้นตอนวิธีนี้ นีเดอมาน–วานซ์ได้อธิบายขั้นตอนวิธีของพวกเขา โดยคิดเฉพาะกรณีที่ลำดับนั้น ตรงกัน และ ไม่ตรงกัน แต่ไม่ได้อธิบายถึง กรณีที่มี ช่องว่าง ไว้ด้วย (ไม่ได้คิดถึง gap penalty) (d=0). การตีพิมพ์ครั้งแรก จากปี 1970 ได้นำเสนอ รูปแบบการเรียกซ้ำไว้ดังนี้ . จะสามารถเขียนโปรแกรมเชิงพลวัตออกมาได้ O (n3)
ภายหลังมีการพัฒนาขั้นตอนวิธีการเขียนโปรแกรมกำหนดการพลวัตที่ดีกว่าสามารถทำงานอยู่ในช่วงเวลากำลังสองในปัญหาเดียวกัน (ไม่มี 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 ที่ใช้เวลาการทำงานเป็นกำลังสอง
ขั้นตอนวิธี
การให้คะแนนการเรียงตัวอักษรจะอยู่ในรูปแบบ เมตริกซ์สมมาตร โดย จะเป็นคะแนนความเหมือนกันของ a และ b และ d เป็น linear gap penalty.
ยกตัวอย่างเช่นเมตริกซ์สมมาตรด้านล่าง
จะมีการเรียงตัวเป็น
ATCG
-TCG
ในการหาการเรียงตัวที่มีคะแนนสูงสุด ทำได้โดยกำหนด F เป็น อาเรย์ (หรือ เมตริกซ์) โดยมี แถว i และสดมภ์ j เป็น จะมีหนึ่งสดมภ์สำหรับแต่ละอักขระใน A และหนึ่งแถวสำหรับแต่ละอักขระใน B ดังนั้นหากเราต้องการทำ sequence alignment ที่มีขนาด n และ m จำเป็นต้องใช้เมโมรี่ที่มีขนาด . เราสามารถหาการเรียงที่ดีที่สุดได้โดยใช้ (Hirschberg's algorithm จะใช้เวลาเป็น )
การทำงานของขั้นตอนวิธีนี้คือจะให้ เป็นคะแนนสูงที่สุดของอักขระ แรกในลำดับ A และ แรกในลำดับ B และใช้ principle of optimality ดังนี้ Basis: Recursion, based on the principle of optimality:
รหัสเทียมของขั้นตอนวิธีในการหา เมตริกซ์ 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 นี้ ทำได้โดยเริ่มจากการเติมช่องล่างขวา และทำการเปรียบเทียบระหว่าง 3 กรณีที่เป็นไปได้หาว่ากรณีไหนได้คะแนนสูงสุด (กรณีเท่ากัน, แทรก, ลบ) ถ้า เท่ากัน นั่นคือ และ นั้นตรงกัน, ถ้า ลบหมายความว่า นั้นตรงกับช่องว่าง, และถ้า แทรก หมายความว่า นั้นตรงกับช่องว่าง (การเติมเมตริกซ์ 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 }
อ้างอิง
- ↑ 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" Check
|url=
value (help). Journal of Molecular Biology. 48 (3): 443–53. doi:10.1016/0022-2836 (70) 90057-4 Check|doi=
value (help). PMID 5420325.CS1 maint: multiple names: authors list (link) - 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.CS1 maint: multiple names: authors list (link)
- 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
- Java Implementation of the Needleman-Wunsch Algorithm
- B.A.B.A. — an applet (with source) which visually explains the algorithm.
- A clear explanation of NW and its applications to sequence alignment
- Sequence Alignment Techniques at Technology Blog
- OPAL JavaScript implementation of algorithms: Needleman-Wunsch, Needleman-Wunsch-Sellers and Smith-Waterman
- Biostrings R package implementing Needleman-Wunsch algorithm among others
งานวิจัยที่ประยุกต์ใช้ในประเทศไทย
- ขั้นตอนวิธีเชิงวิวัฒน์ดัดแปลงสำหรับการจัดเรียงลำดับเบสหลายลำดับ
ดูเพิ่ม
- Smith-Waterman algorithm
- BLAST
- Levenshtein distance
- Dynamic time warping
ศึกษาเพิ่มเติม
- โครงสร้างข้อมูล (ฉบับวาจาจาวา) โดยสมชาย ประสิทธิ์จูตระกูล
- การออกแบบอัลกอริทึม (Algorithm Design) โดยสมชาย ประสิทธิ์จูตระกูล