Needleman-Wunsch Algoritması

Algoritma,  Protein ve DNA sekanslarının hizalanması için bulundu. 1970 yılında büyük dizilerin hizalanması için ilk defa kullanılan ilk Dinamik Programdır. İki dizi içindeki benzerlikler ve benzer olmayan durumlar puanlandırılır ve bir tabloya yerleştirilir. Puanlama işlemi bittikten sonra sağ alt köşeden başlayarak en az penaltı puanına sahip olan yol optimum hizalamayı verir. 

Elimizde

GCATGCU
GATTACA

şeklinde iki adet nükleotid dizisi olsun. Bu iki dizinin onlarca hizalanma ihtimali mevcut fakat bize en optimum olanı lazım. Bunun için dizi elemanlarını yatay ve dikey olarak tabloya yerleştiriyoruz. Tablonun üzt kısmında bir satır boş bırakılıyor.

Dah sonra bu tabloyu en üst satırdan başlayarak dolduruyoruz.
Birbirinin aynı olan harfler (G/G gibi) +1 ile
Uyumsuzlar (G/A gibi) -1 ile
Boşluk harf kombinasyonları (G/"-" gibi) -1 ile puanlandırılsın.

Bu algoritmada komşu olan karelerden en yüsek değerli olanı alınır ve puanlama onun üzerine eklenerek yapılır. İlk satırı doldurduğumuza aşağıdaki gibi olacaktır;

Görüldüğü gibi en üstteki sıra 0 dan başlayarak ceza puanı olan -1 eklenerek devam etti. Yatay ve dikey sıralartamandık tan sonra G ile başlayan ilk yatay sıraya geliyor. Burada G-G uyumu +1 ile puanlandıracak, komşu karelerde en büyük değer 0 olduğu için + eklenecek ve o kare +1 olacak;

Şimdi ikinci satırdaki G-C için -1 değeri vermeliyiz. Komşu karelerdeki en büyük değer +1 dolayısı ile -1 ile toplandığında bu karedeki değer 0 olacaktır;

Bu şekilde tüm tabloyu dolduruyoruz. Tüm değerler yazıldıktan sonra sağ alt köşeden başlayarak en yüksek puan değerine ulaşan hizalamalar optimum oluyor.

Bu tabloda çeşitli optimum hizalamalar mevcut, mavi ve kırmızı oklarla köşegen geçişler harf karşılıklarını belirtirken yatay ve dikey geçişler (siyah okla belirtilenler) "-" indel boşluk karakterini ifade eder.

Tabloya göre olası ihtimaller şöyle olacaktır;

GCATGCU      GCATG-CU      GCA-TGCU      GCAT-GCU
GATTACA      G-ATTACA      G-ATTACA      G-ATTACA