Yazan : Şadi Evren ŞEKER

Bu yazının amacı, Smith Waterman algoritmasını açıklamaktır. Algoritma, dizgi yaslama (string alignment) işlemlerinde kullanılmaktadır.

Dizgi yaslama işlemi (string alignment), basitçe iki dizgiyi alıp bu iki dizgideki ortak alanları bulmayı amaçlar. Bu tip algoritmalar, özellikle gelişen biyobilişim (bioinformatics) çalışmaları ile, genler arasında benzerlik bulunmasının önem kazanmasıyla günümüzde hatırı sayılır bir öneme haizdir.

Algoritma Hakkında

Smith-Waterman algoritması, Needleman-Wunsch algoritmasına oldukça benzemektedir ve bir çeşidi olarak görülebilir. Algoritma 1981 yılında, algoritmaya ismini veren iki bilimadamı tarafından ortaya atılmıştır. Algoritmanın en önemli özelliği, dinamik programlama (dynamic programming) kullanan yapısıdır. Bu tip dinamik programlama kullanan algoritmaların ortak özelliği, ikame masfufu (substitution matrix, yer değiştirme matrisi) kullanmaları ve boşluk değerleri için bir boşluk fonksiyonu kullanmalarıdır (gap scoring function).

Needleman-Wunsch algoritmasından tek farkı, eksi değerli skorlar yerine 0 kullanıyor olmasıdır.

Algoritmanın Çalışması

Algoritma, bir masfuf (matrix) inşa ederek çalışmaya başları. Bu masfuf aşağıdaki özelliklerdedir:

H(i,0) = 0 , 0 <= i <= m

H(0,j) = 0 , 0 <= j <= n

if( ai == bj )

w(ai,bj) = w (uyar)

else

w(ai,bj) = w (uymaz)

Yukarıdaki matris tanımından anlaşılacağı üzere yaslama işlemi (alignment) yapılan iki dizgi a ve b olarak gösterilmiştir. Ayrıca m, a’nın boyutu ve n de b’nin boyutunu gösteren değerlerdir. i ve j değişkenleri ise, bu matristeki ve dolayısıyla dizgilerdeki kaçıncı elemanın işlendiğini tutan birer değişken sayıdır. H(i,j) değeri, matris üzerindeki bir sayıya işaret etmekte olup bu değer, a[1…i] ve b[1…j] şeklinde gösterilebilecek, a’nin i. ve b’nin j. elemanına kadar olan en yüksek benzerlik skorunu tutmaktadır.

w(x,y) şeklinde gösterilen fonksiyon ise, parametre olarak aldığı iki değer için boşluk skorunu (gap score) tutmaktadır.

Örnek

Örnek olarak, aşağıdaki iki dizgiyi (string) ele alalım:

a= G CACGCTG

b= GA CGCGCG

Bu iki dizgi için n = 8 ve m = 8 olarak hesaplanabilir. Şimdi matrisin oluşturulmasına geçelim:

Bütün ceza durumlarını -1 olarak verelim. Bu ceza durumları şunlardı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

Şimdi matrisimizi oluşturabiliriz:

Ö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 durumdaki satır ve sütuna 0 değeri yerleştiriliyor. Bu yerleştirmenin sebebi, değerin eksi değere düşmesi halinde 0 ile gösteriliyor olmasıdır.

Yukarıdaki ilk satır ile işe başlayalım. Burada seçtiğimiz satırın başlığı, G olarak atanmış. Bu durumda kolon başlığında da G olması halinde +2, farklı bir değer olması halinde ise -1 ekleyerek devam edeceğiz. İlk başlangıç değerimiz satırın ilk kolonunda yazan 0 değeri. O halde ikinci kolonda G-G uyması olduğu için +2 değer konuluyor. Ardından gelen 3. kolon başlığı C olduğu için ve uymadığı için -1 ekleniyor, yani bir önceki değer olan 2’den 1 çıkarılarak 1 bulunuyor. Ardından gelen A değeri yine G ile uymadığı için -1 eklenerek 0 bulunuyor. Sonra yine G-G uyumu bulunarak +2 ekleniyor ve 2 değeri yazılıyor ve işlem satır sonuna kadar bu şekilde devam ediyor.

Gelelim bir sonraki satıra. Bu satır, A ile başladığı için, kolon başlıklarını A ile karşılaştıracağız. A-G karşılaşması bir uyuşmama durumudur. Dolayısıyla -1 kuralını işletiriz. Bu hücrenin bir üst satırındaki hücrede 2 bir sol hücrede ise 0 olduğunu görüyoruz. Bu değerlerden en büyüğünü alıyoruz (ki bu 2’dir) ve -1 ekleyerek yazıyoruz, şu halde 1 olmuş oluyor.

Ardından A-C uyuşmazlığı gelir ve hem bir üst satırda hem bir sol kolonda 1 olduğu için -1 kuralıyla 0 bulunur. Ardından A-A uyuşması ile +2 işletilir ki hem satır hem sütundan 0 geldiği için hücre değeri 2 olmuş olur. Bu işlem satır sonuna kadar bu şekilde devam eder. Yani uyuşma durumunda +2 ve uyuşmama durumunda -1 eklenerek işlemeye devam edilir. Ekleme işlemi ise bir üst hücre veya bir sol hücredeki en büyük değer seçilerek devam eder.

Yukarıda, bu tablonun tamamının doldurulmuş hali gösterilmektedir. Buna göre tablodaki her hücre için, ilgili satır ve sütun başlıkları kontrol edilir, şayet eşitlerse bir üst hücre veya bir soldaki hücreden en büyük değerde olanı alınır ve +2 eklenir, şayet eşit değilse bu üst ve sol hücrelerin en büyüğünden 1 çıkarılır.

Sonuç olarak herhangi bir satır ve sütun için o ana kadarki en çok benzerlik durumunu veren bir ölçü geliştirilmiş olur.

Örneğin, GCACG ile GACG dizgilerinin (string) mesafesi tablodan 4 olarak okunabilir. Bunun anlamı iki dizgi arasındaki mesafeye en büyük değerlerin seçimi ile ulaşılması halinde, iki dizginin birbirine yaslanması mümkündür.

Tablodaki en yüksek değerler ile sol üst köşeye kadar dönecek olursak:

Yukarıdaki şekilde, iki dizginin birleştirildiği noktalarda tartışmasız tek seçenek olan durumlar kırmızı, aynı yere ulaşmayı sağlayan birden fazla alternatifin olduğu durumlar ise mavi olarak gösterilmiştir. Bu durumda iki dizginin alacağı değerlerin en yüksekleri seçilerek sol üst köşeye ulaşacak birden fazla alternatif bulunmuştur. Bu yolların hepsi aynı sonuca varmaktadır ancak örnek olarak aşağıdaki seçimi yapacak olursak (konunun anlaşılması için bir tanesini seçtiğimizi düşünelim)

Şekilde görüldüğü üzere, iki dizgi arasındaki bağlantı aşağıdaki şekilde kurulabilir:

GCACG

G-ACG

bağlantısı kurulabilir. Bu bağlantıda iki dizgi arasında kopan tek nokta bulunmuş olur.

 

Yorumlar

  1. Güney Kasper

    Şadi Hocam merhaba,

    Tüm emekleriniz için çok teşekkür ederim. Bu eser de diğerleri gibi şahane. Tam olarak anlayamadığım bir nokta var. Resimdeki daire içine aldığım hücre, CG karşılığında, dolayısı ile hücrenin yukarısında ve soluna bakılarak en yüksek değere sahip olandan, CG uyumu sağlanmadığı için -1 değeri ile işlem görecek. Yanlışım var ise lütfen düzeltin, işlem sonucunda hücre değeri 4 olması gerekmiyor muydu?

    https://s31.postimg.org/402xdwiiz/sadi_hoca.jpg

    Tüm emeklerinizden ötürü çok teşekkür ederim.

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir