fbpx
วิกิพีเดีย

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

ขั้นตอนวิธีของนีเดอมาน–วานซ์ เป็นการทำ 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 } 


อ้างอิง

  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)
  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.CS1 maint: multiple names: authors list (link)
  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.

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

  • 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) โดยสมชาย ประสิทธิ์จูตระกูล

นตอนว, ของน, เดอมาน, วานซ, งก, ามภาษา, ในบทความน, ไว, ให, านและผ, วมแก, ไขบทความศ, กษาเพ, มเต, มโดยสะดวก, เน, องจากว, เด, ยภาษาไทยย, งไม, บทความด, งกล, าว, กระน, ควรร, บสร, างเป, นบทความโดยเร, วท, เป, นการทำ, global, alignment, บนลำด, บสองลำด, global, alignmen. lingkkhamphasa inbthkhwamni miiwihphuxanaelaphurwmaekikhbthkhwamsuksaephimetimodysadwk enuxngcakwikiphiediyphasaithyyngimmibthkhwamdngklaw krann khwrribsrangepnbthkhwamodyerwthisudkhntxnwithikhxngniedxman wans epnkartha global alignment bnladbsxngladb global alignment khuxkarhaladbthidithisudinkarcderiyngihladb A aela B trngkninthuktaaehnngihidmakthisudethathicaepnipid mikarichknthwipin chiwsarsnethssastr ephuxeriyngladbkhxng oprtin hrux niwkhlioxithd khntxnwithinithuktiphimphinpi 1970 ody Saul B Needleman aela Christian D Wunsch 1 khntxnwithikhxngniedxman wans epnhnungintwxyangkhxngkarekhiynopraekrmodyichethkhnikh kahndkarphlwt aelaepnkarichkahndkarphlwtkhrngaerkinkarepriybethiybladbchiwphaphinpraethsithykmikarsuksaekiywkbkhntxnwithinidwyechnkn odycaehnidcakokhrngnganwicy thngcakmhaly aelacakexkchnmakmay yktwxyangechn okhrngngankartrwcsxbphuichdwyrhsphanaelakhxmulrupaebbkarphimph okhrngnganniepnkartrwcsxbphuichkhxmphiwetxrdwyrabbkarwiekhraahcnghwakarphimph Keystroke Verification sahrbichesrimkhwamplxdphyihkbrabbtrwcsxbrhsphan cakwithikarepriybethiyb radbkrd ebs DNA dwywithi Needleman Wunsch Algorithm aelabbSmith Waterman Algorithm 1 enuxha 1 prawti 2 khntxnwithi 3 xangxing 4 aehlngkhxmulxun 5 nganwicythiprayuktichinpraethsithy 6 duephim 7 suksaephimetimprawti aekikhinkhrngaerkthinaesnxkhntxnwithini niedxman wansidxthibaykhntxnwithikhxngphwkekha odykhidechphaakrnithiladbnn trngkn aela imtrngkn aetimidxthibaythung krnithimi chxngwang iwdwy imidkhidthung gap penalty d 0 kartiphimphkhrngaerk 1 cakpi 1970 idnaesnx rupaebbkareriyksaiwdngni F i j max h lt i k lt j F h j 1 S A i B j F i 1 k S A i B j displaystyle F ij max h lt i k lt j F h j 1 S A i B j F i 1 k S A i B j casamarthekhiynopraekrmechingphlwtxxkmaid O n3 phayhlngmikarphthnakhntxnwithikarekhiynopraekrmkahndkarphlwtthidikwasamarththanganxyuinchwngewlakalngsxnginpyhaediywkn immi gap penalty idthuknaesnxin 2 pi kh s 1972 ody David Sankoff aelayngmikhntxnwithithithukkhidkhunody T K Vintsyuk ksamarththanganinchwngewlakalngsxngidechnkn 3 inpi kh s 1968 inkarbrryayeruxng processing time warping aelaody Robert A Wagner and Michael J Fischer 4 inpi kh s 1974niedxman aela wanskahndpyhakhxngphwkekhainkrnithiladbthngsxng ehmuxnknmakthisud yngmikhwamepnipidthicaldkhnad edit distance rahwangsxngladb thuknaesnxody Vladimir Levenshtein txma Peter H Sellers idaesdngihehnthung 5 inpi kh s 1974 wakaraekpyhadwykhntxnwithithngsxngnntangmiphlethaknniyamsmypccubn niedxman wans hmaythung khntxnwithi global alignment thiichewlakarthanganepnkalngsxngkhntxnwithi aekikhkarihkhaaennkareriyngtwxksrcaxyuinrupaebb emtrikssmmatr ody S a b displaystyle S a b caepnkhaaennkhwamehmuxnknkhxng a aela b aela d epn linear gap penalty yktwxyangechnemtrikssmmatrdanlangcamikareriyngtwepnATCG TCGinkarhakareriyngtwthimikhaaennsungsud thaidodykahnd F epn xaery hrux emtriks odymi aethw i aelasdmph j epn F i j displaystyle F ij camihnungsdmphsahrbaetlaxkkhrain A aelahnungaethwsahrbaetlaxkkhrain B dngnnhakeratxngkartha sequence alignment thimikhnad n aela m caepntxngichemomrithimikhnad O n m displaystyle O nm erasamarthhakareriyngthidithisudidodyich Hirschberg s algorithm caichewlaepn 8 min n m displaystyle Theta min n m karthangankhxngkhntxnwithinikhuxcaih F i j displaystyle F ij epnkhaaennsungthisudkhxngxkkhra i 0 n displaystyle i 0 n aerkinladb A aela j 0 m displaystyle j 0 m aerkinladb B aelaich principle of optimality dngni Basis F 0 j d j displaystyle F 0j d j F i 0 d i displaystyle F i0 d i Recursion based on the principle of optimality F i j max F i 1 j 1 S A i B j F i j 1 d F i 1 j d displaystyle F ij max F i 1 j 1 S A i B j F i j 1 d F i 1 j d rhsethiymkhxngkhntxnwithiinkarha emtriks F midngni 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 emuxerahaemtriks F idaelw F n m displaystyle F nm caepnkhaaennsungthisudkhxngkareriyngthiepnipid inkaretimemtriks F ni thaidodyerimcakkaretimchxnglangkhwa aelathakarepriybethiybrahwang 3 krnithiepnipidhawakrniihnidkhaaennsungsud krniethakn aethrk lb tha ethakn nnkhux A i displaystyle A i aela B j displaystyle B j nntrngkn tha lbhmaykhwamwa A i displaystyle A i nntrngkbchxngwang aelatha aethrk hmaykhwamwa B j displaystyle B j nntrngkbchxngwang karetimemtriks F odythwipnn xacmichxngthimikhaaennethaknidhlaychxng nnkhuxmithangeluxkthidithisudidhlaythang AlignmentA AlignmentB i length A j length B while i gt 0 and j gt 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 gt 0 AlignmentA Ai AlignmentA AlignmentB AlignmentB i i 1 while j gt 0 AlignmentA AlignmentA AlignmentB Bj AlignmentB j j 1 xangxing aekikh 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 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 aehlngkhxmulxun aekikhNW align A protein sequence to sequence alignment program by Needleman Wunsch algorithm online server amp 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 othersnganwicythiprayuktichinpraethsithy aekikhkhntxnwithiechingwiwthnddaeplngsahrbkarcderiyngladbebshlayladbduephim aekikhSmith Waterman algorithm BLAST Levenshtein distance Dynamic time warpingsuksaephimetim aekikhokhrngsrangkhxmul chbbwacacawa odysmchay prasiththicutrakul karxxkaebbxlkxrithum Algorithm Design odysmchay prasiththicutrakulekhathungcak https th wikipedia org w index php title khntxnwithikhxngniedxman wans amp oldid 9234183, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,

บทความ

, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม