#!/usr/bin/ruby -w ################################################################################# # File : zuker.rb # # Author : Jean-Eudes Duchesne (duchesnj@iro.umontreal.ca) # # Created : March 22, 2004 # # Last updated : March 22, 2004 # # Description : Simle implementation of the Zuker's algorithm for the # # minimization of free energy. # # # # Usage : zuker.rb S # # S is the string for which's structure needs to be predicted # # the minimization of free energy. The script is pretty # # basic, so try not to use extreme cases. For exemple, output # # formatting is pretty simple, using strings that are too long # # might give unexpected results ! Also, only works for sequences # # in lower case. # # # ################################################################################# ### Libs ### ### Globals ### ### Classes & Methods ### class Array2D def initialize @data = [[]] end def [](i,j) # Want i to be the rows and j the columns if @data[j] == nil || @data[j][i] == nil return nil else return @data[j][i] end end def []=(i,j,x) @data[j] = [] if @data[j] == nil @data[j][i] = x end end class PondMatrix def initialize # Not very pretty, but I need the values ! @data = Array2D.new @data[0,0] = @data[1,1] = @data[2,2] = @data[3,3] = 1 @data[0,1] = @data[1,0] = @data[0,2] = @data[2,0] = @data[1,3] = @data[3,1] = @data[2,3] = @data[3,2] = 1 @data[0,3] = @data[3,0] = @data[1,2] = @data[2,1] = -1 end def [](a,b) case a when "a" i = 0 when "c" i = 1 when "g" i = 2 when "t" i = 3 end case b when "a" j = 0 when "c" j = 1 when "g" j = 2 when "t" j = 3 end return @data[i,j] end end def MIN(x,y) unless(y == nil || x == nil) if(y < x) return y else return x end end if(y == nil) return x else return y end end ### Main ### S = ARGV[0] n = S.length # Initialisation of ponderation matrix p = PondMatrix.new # Initialisation of array W = Array2D.new for i in 0 ... n for j in 0 ... i+4 W[i,j] = 0 end end # calculate every other cell for j in 4 ... n for i in 0 ... n-j unless (W[i+1,j+i-1] == nil) W[i,j+i] = W[i+1,j+i-1] + p[S[i..i],S[j+i..j+i]] # Because of the initial conditions, D[] is of size +1 compared to string S and T. This is why we need to refer to S at i-1 or T at j-1 rather than the espected i,j based on an algorithmic standpoint. end W[i,j+i] = MIN(W[i,j+i],W[i,j+i-1]) W[i,j+i] = MIN(W[i,j+i],W[i+1,j+i]) for k in i+1 ... j+i W[i,j+i] = MIN(W[i,j+i],W[i,k]+W[k+1,j+i]) end end end #Print dynamic table and minimal nb of operations #printf("\n - ") printf("\n ") for j in 0 ... n printf(" %s ", S[j..j]) end #printf("\n- ") for i in 0 ... n printf("\n%s ", S[i..i]) for j in 0 ... n printf("%3d ", W[i,j]) end end printf("\n\nMinimized free energy : %d\n\n", W[0,n-1])