Needleman Wunsch algoritmi

Needleman -Wunsch algoritmi bioinformatikada oqsil yoki nukleotidlar ketma - ketligini tekislash uchun ishlatiladigan algoritmdir . Bu biologik ketma-ketliklarni solishtirish uchun dinamik dasturlashning birinchi ilovalaridan biri edi . Algoritm Saul B. Needleman va Kristian D. Vunsh tomonidan ishlab chiqilgan va 1970 yilda nashr etilgan.  Algoritm mohiyatan katta muammoni (masalan, toʻliq ketma-ketlikni) kichikroq masalalar qatoriga ajratadi va u kichikroq masalalarning yechimlaridan foydalanadi. kattaroq muammoning optimal yechimini topish uchun muammolar.  U baʼzan optimal moslik deb ham ataladi algoritm va global hizalama texnikasi. Needleman-Wunsch algoritmi optimal global tekislash uchun hali ham keng qoʻllanadi, ayniqsa global tekislash sifati juda muhim bo'lsa. Algoritm har bir mumkin boʻlgan tekislash uchun ball beradi va algoritmning maqsadi eng yuqori ballga ega boʻlgan barcha mumkin boʻlgan tekislashlarni topishdir.
1-rasm: Needleman-Wunsch ketma-ketligini juftlik bilan tekislashSinfKetma-ketlikni tekislashEng yomon ishlashEng yomon holatda kosmik murakkablik