Needleman Wunsch Algoritması

Yazan : Şadi Evren ŞEKER

Bu yazının amacı, bir dizgi (string) işleme algoritması olan Needleman-Wunsch algoritmasını açıklamaktır. Algoritma, basitçe iki dizgi (string) arasındaki yaslama durumunu bulmayı amaçlar. Buna göre iki dizgiden oluşturulan bir ölçüm değeri ile (metric) dizgiler karşılaştırılır ve farklılıklar bulunur.

Algoritma yapısal olarak, Smith-Waterman algoritmasına benzemektedir. İki algoritma arasındaki temel farklılık Smith-Waterman algoritmasında tutulan masfuf (matrix) üzerinde eksi değerlerin olamaması ancak Needleman-Wunsch algoritmasında, eksi değerlere izin verilmesidir. Algoritmanın en belirgin özelliklerinden birisi de dinamik programlama (dynamic programming) kullanıyor olmasıdır. Yani iki dizginin karşılaştırıldığı noktaya kadar olan bilgileri bir masufuf (matrix) üzerinde tutularak bu değerler her seferinde yeniden hesaplanmaz.

Algoritmanın çalışmasını örnek olarak kabul edeceğimiz iki dizgi üzerinden gösterelim.

Örnek olarak karşılaştırmak istediğimiz iki dizgi aşağıdaki şekilde verilmiş olsun :

a= G CACGCTG

b= GA CGCGCG

İki dizginin karşılaştırılacağı algoritmada öncelikle algoritmanın sayısal değerlerini belirtmemiz gerekiyor. Bu değerler parametrik olarak değişebilmekle beraber, örneğimizde kullanacağımız ceza değerlerini -1 alalım ve ödül değerlerini de +2 olarak kabul edelim. Bu durumda ceza değeri olan aşağıdaki durumlarda -1 alınacaktır:

• w(boşluk ) = -1

• w(a,-) = -1

• w(-,b) = -1

• w(uymaz) -1

Bütün iyi durumları da +2 olarak alalım ki tek durum uyma durumudur:

• w(uyar) = 2

Bu iki dizgi (string) için aşağıdaki şekilde bir tablo oluşturmak mümkündür:

Öncelikle, yukarıda görüldüğü üzere, boş bir tablonun satır ve kolon başlıklarına birer harf gelecek şekilde iki dizgi de (string) yerleştiriliyor.

Ardından, w(a,-) ve w(-,b) şartlarının -1 olmasından dolayı bu durumu tablomuza yerleştiriyoruz. Görüldüğü üzere ceza değeri bütün durumlar için uygulanmıştır.

İlk satırın çıkarılışını adım adım görelim. Öncelikle satır başlığımız G olduğu için sütunlarda bu harf ile eşleşmeler kontrol edilecektir. İlk kontrolümüz G-G kontrolü ve bu yüzden +2 değeri gelecek. Ancak hücrenin komşularından en büyük değer -1 olduğu için -1 + 2 = 1 sonucunu bularak hücreye yazıyoruz. Devamında ikinci kolonda G-C uyuşmazılığı söz konusu. Bu durumda -1 ceza uygulanacak ve en büyük komşumuz biraz önce bulduğumuz 1 olduğu için 1 – 1 = 0 değerini bu hücreye yazıyoruz. Ardından G-A uyuşmazlığından dolayı en büyük komşumuz olan 0 -1 = -1 sonucunu hücreye yazıyoruz. Hemen ardından G-C uyuşmazlığından dolayı bütün komşuları -1 olan hücremize -1 -1 = -2 sonucu yazılıyor. Bir sonraki kolonda ise G-G uyuşması var ve en büyük komşumuz olan -1 + 2 = 1 değeri hücreye yazılıyor. Çalışma bu şekilde devam ediyor yani o hücreye geldiğimizde satır ve sütun karşılaştırması yapılarak uyuşma halinde +2 diğer durumlarda ise -1 yazılıyor değeri en yüksek komşu değerine ekleniyor.

Yukarıda, tablonun tamamının doldurulmuş hali verilmiştir. Bu tabloda netice olarak iki dizginin birbirine yaslanması durumunda skoru gösterilmektedir. Ayrıca tablodaki herhangi bir hücre seçildiğinde, iki dizginin bu noktaya kadar olan halleri de bulunabilir. Örneğin GACG ile GCACG dizgilerini karşılaştırmak isteyelim, bu iki dizginin karşılaştırılması yukarıdaki tabloda 3 olara değerlendirilmiştir ve en yüksek değerdeki komşuları, yukarı ve sola doğru izlenirse aşağıdaki gibi bir yol ortaya çıkar:

Yukarıdaki yol, sol üst köşeye kadar giden en yüksek değerlere sahip yoldur. Bu yolu okuyacak olursak:

GCACG

G-ACG

şeklinde arada bir boşluk bırakarak iki dizginin birleştirildiği görülebilir.