30  Needleman-Wunsch Algoritması

Bu algoritma, iki nükleotit dizisini baştan sona en uygun şekilde eşleştirmek için Dinamik Programlama yöntemini kullanır.

Süreç iki ana aşamadan oluşmaktadır:

İlk olarak değişkenlerimizi tanımlayalım:

d1_vektor <- c("A","A","C","G")
d2_vektor <- c("A","A","T","G","C","T")

match <- 1
mismatch <- -1
gap <- -2

# matrisin satır ve sütun sayılarını
rows <- length(d2_vektor) + 1
cols <- length(d1_vektor) + 1

Skorlama matrisini ve yön matrisini (point matris) oluşturalım:

matris <- matrix(NA, nrow = rows, ncol = cols) 
points <- matrix(NA, nrow = rows, ncol = cols)

matris [1, ] <- seq(0,length(d1_vektor)*gap, gap)
matris [ ,1] <- seq(0,length(d2_vektor)*gap, gap)

Matrisi inceleyelim:

print(matris)
     [,1] [,2] [,3] [,4] [,5]
[1,]    0   -2   -4   -6   -8
[2,]   -2   NA   NA   NA   NA
[3,]   -4   NA   NA   NA   NA
[4,]   -6   NA   NA   NA   NA
[5,]   -8   NA   NA   NA   NA
[6,]  -10   NA   NA   NA   NA
[7,]  -12   NA   NA   NA   NA

Matris doldurma aşamasına geçelim:

#--Matris Doldurma Aşaması

for(i in 2:rows ) {  
  for(j in 2:cols ) {
    if(d1_vektor[j-1] == d2_vektor[i-1]){
      skor1 <- matris[i-1, j-1] + match 
    }else {
      skor1 <- matris[i-1, j-1] + mismatch
    }
  skor2 <- matris[i-1, j] + gap
  skor3 <- matris[i, j-1] + gap
  # o pozisyonda elde edilmesi gereken max skor
  matris[i,j] <- max(skor1,skor2,skor3)
  # maksimum skor hangi kutucuktan geldi?
  position <- which.max(c(skor1,skor2,skor3))
  if(position == 1){
    points[i,j] <- "diag"
  } else if (position == 2) {  
    points[i,j]<- "up"
  } else{ 
    points[i,j]<-"left"
    }
  }
}

Oluşturduğumuz matrisi inceleyelim:

print(matris)
     [,1] [,2] [,3] [,4] [,5]
[1,]    0   -2   -4   -6   -8
[2,]   -2    1   -1   -3   -5
[3,]   -4   -1    2    0   -2
[4,]   -6   -3    0    1   -1
[5,]   -8   -5   -2   -1    2
[6,]  -10   -7   -4   -1    0
[7,]  -12   -9   -6   -3   -2

Şimdi de yön matrisimizi inceleyelim:

print(points)
     [,1] [,2]   [,3]   [,4]   [,5]  
[1,] NA   NA     NA     NA     NA    
[2,] NA   "diag" "diag" "left" "left"
[3,] NA   "diag" "diag" "left" "left"
[4,] NA   "up"   "up"   "diag" "diag"
[5,] NA   "up"   "up"   "diag" "diag"
[6,] NA   "up"   "up"   "diag" "up"  
[7,] NA   "up"   "up"   "up"   "diag"

Son olarak geri takip kodumuzu yazalım:

#--Geri İzleme (Traceback)
# inclediğimiz dizilerin hizalanmış versiyonları
aln1<-c()
aln2<-c()

i<-length(d2_vektor)+1  
j<-length(d1_vektor)+1  

while (i!=1 & j!=1) {
  if (points[i,j]=="diag"){ 
    i<-i-1
    j<-j-1
    print("diag") 
    aln1<-c (d1_vektor[j-1],aln1)
    aln2<-c (d2_vektor[i-1],aln2)
    
    print(aln1)
    print(aln2)
    
  } else if(points[i,j]=="up"){
      i<- i-1 
      aln1<-c("-",aln1)
      aln2<-c(d2_vektor[i-1],aln2)
      print("up")
      
      print(aln1)
      print(aln2)
  } else {
      j<-j-1
      aln1<-c(d1_vektor[j-1],aln1)
      aln2<-c("-",aln2)
      print("left")
      
      print(aln1)
      print(aln2)
    }
}
[1] "diag"
[1] "C"
[1] "C"
[1] "diag"
[1] "A" "C"
[1] "G" "C"
[1] "up"
[1] "-" "A" "C"
[1] "T" "G" "C"
[1] "up"
[1] "-" "-" "A" "C"
[1] "A" "T" "G" "C"
[1] "diag"
[1] "A" "-" "-" "A" "C"
[1] "A" "A" "T" "G" "C"
[1] "diag"
[1] "A" "-" "-" "A" "C"
[1] "A" "A" "T" "G" "C"
print(aln1)
[1] "A" "-" "-" "A" "C"
print(aln2)
[1] "A" "A" "T" "G" "C"