Practical Sections on Pairwise Alignments

Dynamic Programming in Java

• Prepare and tune in

  Obtain the file JAlignment.tar.gz save it in your home directory, decompress and detar it:

  
  $ gtar xvzf JAlignment.tar.gz

  
  change into the JAlignment-directory, compile and load the class Align.class (which contains the main-method) into the Java Runtime Environment:

  
  $ cd JAlignment
  $ javac *.java
  $ java Align hxk_yeast.fasta

  
  A meaningless alignment of two sequences is performed and a meaningless alignment score is output. Inspect the main-method in the file Align.java to get an overview of program execution:
  
  

  1.

  some command-line arguments are read

  2.

  two sequences of a fasta-file are read

  3.

  a new alignment object is created, the methods fillEditMatrix() and backTracking(int gapPenalty) are called and the alignment is output.

  
  
  

• Useful methods in JAlignment

  There are some useful methods provided by the follwing classes which will enable you to implement the dynamic programming algorithm (see below) very quickly. Just notice what they are for, you don't have to inspect the code.

  
  

  (a)

  class ScoreMatrix:
  public short sim(char letter1, char letter2)
  returns the similarity value of char letter1 and char letter2 given by the score matrix object.

  
  

  (b)

  class Sequence:
  public char getLetter(int index)
  returns as a char the letter (= amino acid residue) of the sequence object at index index-1.

  
  

  (c)

  class Alignment:
  public void align(char letter1, char letter2)
  inserts the chars letter1 and letter2 in a GappedSequence object.
  
  protected int max(int a, int b)
  protected int max(int a, int b, int c)
  protected int max(int a, int b, int c, int d)
  returns the maximum value of the integer numbers (a,b), (a,b,c) or (a,b,c,d) respectively.

  
  

• Global alignment with linear gap costs

  
  

  1.

  Write the method fillEditMatrix(int gapPenalty) in class Alignment (file Alignment.java) to fill in an edit matrix, which is used to compute an optimal global alignment with linear gap costs. Include the assignment of the optimal alignment score to the variable int alignmentScore.

  2.

  Write/change the method backTracking(int gapPenalty) in class Alignment.

  3.

  Edit file Align.java not to call fillEditMatrix() but to call fillEditMatrix(openGapPenalty) now.

  4.

  If you dealt with the above tasks properly, you should be able to compile the source files and to run Align again.

  
  
  theory
  
  solution:
  Alignment.java
  Align.java

  
  

• Variants

  
  

  Implement the following variants of the dynamic programming algorithm:

  1.

  Free end gaps

  2.

  Linear affine gap costs

  3.

  Smith-Waterman Algorithm

  
  
  theory
  
  solution for Smith-Waterman Alignment:
  Alignment.java
  Align.java