Home ] Description ] Instructions ] [ Source Code ] Samples ] Applet ]

 

Note: This utility may be used and distributed freely. However, please contact the author
          (michael.rasiej@yale.edu) if you would like to modify the source code and/or use it
          for other than academic purpose.

//===========================================================================
// Title:         SequenceShop 1.0b: Sequence Alignment (SequenceShop.java)
// Author:        Michael J. Rasiej
// Date:          December 1999
// Class:         Yale University; Bioinformatics 452a; Prof. Mark Gerstein
// Description:   Implementation of a modified version of the 
//                Needleman-Wunsch dynamic programming algorithm with gap 
//                penalty and local sensitivity options (Smith and
//                Waterman methods for local sensitivity)
//===========================================================================
// Test Sequence 1: TTGACACCCTCCCAATTGTA
// Test Sequence 2: ACCCCAGGCTTTACACAT
import java.applet.Applet;
import java.awt.*;
import java.awt.event.*;
//========================================================================
// SequenceShop is the main class which controls the entire applet
//========================================================================
public class SequenceShop extends Applet {
// These variables store the parameters to be used for initializing the
// Matrix class
   private String Seq1;
   private String Seq2;
   private float Gop;
   private float Gep;
   private float Ms;
   private float Mp;
   private Label SEQ1_l = new Label("Sequence 1:");
   private Label SEQ2_l = new Label("Sequence 2:");
   private Label GOP_l = new Label ("Gap Opening Penalty:");
   private Label GEP_l = new Label ("Gap Extension Penalty:");
   private Label MP_l = new Label ("Mismatch Penalty:");
   private Label MS_l = new Label ("Match Score:");
// Define parameter input fields   
   private TextField SEQ1 = new TextField(50);
   private TextField SEQ2 = new TextField(50);
   private TextField GOP = new TextField (2);
   private TextField GEP = new TextField (2);
   private TextField MP = new TextField (2);
   private TextField MS = new TextField (2);
   
   private TextArea log = new TextArea (10,40); // Output component of the applet
   private Button button = new Button("CASE SENSITIVE ALIGN");
   private Button button2 = new Button("ALL UPPERCASE ALIGN");
// Event listeners associated with various applet components   
   private SSListener listener0 = new SSListener(this, 0);
   private SSListener listener1 = new SSListener(this, 1);
   private SSInputsListener inputListener0 = new SSInputsListener (this, 0);
   private SSInputsListener inputListener1 = new SSInputsListener (this, 1);
   private SSInputsListener inputListener2 = new SSInputsListener (this, 2);
   private SSInputsListener inputListener3 = new SSInputsListener (this, 3);
   private SSInputsListener inputListener4 = new SSInputsListener (this, 4);
   private SSInputsListener inputListener5 = new SSInputsListener (this, 5);
   private CheckboxGroup Method = new CheckboxGroup();
   private Checkbox Global = new Checkbox("GLOBAL optimization",Method,true);
   private Checkbox Local = new Checkbox("LOCAL optimization",Method,false);
   private Checkbox Custom = new Checkbox("CUSTOM alignment",Method,false);
// Listeners associated with choosing the alignment method   
   private SSItemListener itemListener0 = new SSItemListener (this, 0);  // Global
   private SSItemListener itemListener1 = new SSItemListener (this, 1);  // Local
   private SSItemListener itemListener2 = new SSItemListener (this, 2);  // Custom
// Grouping various applet components into more managable clusters
   private Panel Sequences = new Panel();
   private Panel CheckMethod = new Panel();
   private Panel ParameterL = new Panel();
   private Panel ParameterS = new Panel();
   private Panel Control = new Panel();
   private Panel Buttons = new Panel();
// This method initializes the Applet and pastes the different components
// on the screen
                                                                                                                                                              
   public void init() {
      this.setFont(new Font("Helvetica",Font.PLAIN,14));
      Sequences.setLayout(new GridLayout(4,1));
      Sequences.add(SEQ1_l);
      SEQ1_l.setFont(new Font("Helvetica",Font.BOLD,16));
      Sequences.add(SEQ1);
      Sequences.add(SEQ2_l);
      SEQ2_l.setFont(new Font("Helvetica",Font.BOLD,16));
      Sequences.add(SEQ2);
      Sequences.setVisible(true);
      ParameterS.setLayout(new GridLayout(4,1));
      ParameterL.setLayout(new GridLayout(4,1));
      ParameterL.add(GOP_l);
      ParameterS.add(GOP);
      ParameterL.add(GEP_l);
      ParameterS.add(GEP);
      ParameterL.add(MP_l);
      ParameterS.add(MP);
      ParameterL.add(MS_l);
      ParameterS.add(MS);
      ParameterS.setVisible(true);
      ParameterL.setVisible(true);
      CheckMethod.setLayout(new GridLayout(3,1));
      CheckMethod.add(Global);
      CheckMethod.add(Local);
      CheckMethod.add(Custom);
      CheckMethod.setVisible(true);
      Control.setLayout(new GridLayout(1,2));
      Control.add(ParameterL);
      Control.add(ParameterS);
      Control.setVisible(true);
      
      Buttons.setLayout(new GridLayout(1,2));
      Buttons.add(button);
      Buttons.add(button2);
      Buttons.setVisible(true);
      this.setLayout(new FlowLayout(FlowLayout.LEFT,10,10));
      add(Sequences);
      add(CheckMethod);
      add(Control);
      add(log);
      add(Buttons);
      log.setEditable(false);
      log.setFont(new Font("Courier",Font.BOLD, 16));
      button.addActionListener(listener0);
      button2.addActionListener(listener1);
      SEQ1.addActionListener(inputListener0);
      SEQ2.addActionListener(inputListener1);
      GOP.addActionListener(inputListener2);
      GEP.addActionListener(inputListener3);
      MP.addActionListener(inputListener4);
      MS.addActionListener(inputListener5);
      Global.addItemListener(itemListener0);
      Local.addItemListener(itemListener1);
      Custom.addItemListener(itemListener2);
      setVisible(true);
   } // method init
// execute() creates and computes the matrix (when align button pressed)   
   public void execute(int chois) {
      
      if (chois == 1) {
         Seq1 = Seq1.toUpperCase();   // Convert sequence strings to UPPERcase
         Seq2 = Seq2.toUpperCase();
      }
      if (chois == 2) {
// Cleanup/applet close procedure could be placed here in the future
      }
      
      Matrix Grid = new Matrix(Seq1, Seq2, Gop, Gep, Mp, Ms);
      log.append("Score: " + Grid.PrintStats(0) + "\nLength 1: " + Grid.PrintStats(1) +
      "\nLength 2: " + Grid.PrintStats(2) + "\n\n");
      log.append(Grid.PrintStringBuffers(0));
      log.append(Grid.PrintStringBuffers(1));
      log.append(Grid.PrintStringBuffers(2));
   } // method execute
// Select GLOBAL, LOCAL or CUSTOM alignment
   public void methodChoice(int type) {
      switch (type) {
         case 0: Gop = 1.2f; Gep = 0.6f; Mp = 0.0f; Ms = 1.0f; break;
         case 1: Gop = 1.2f; Gep = 0.6f; Mp = -0.6f; Ms = 1.0f; break;
         case 2: break;
         default: log.append("ERROR in methodChoice()!");
      }
   } // methodChoice
// Function to alter alignment parameters 
   public void choose(int input) {
      switch (input) {
         case 0: Seq1 = SEQ1.getText(); break;
         case 1: Seq2 = SEQ2.getText(); break;
         case 2: Gop = (new Float(GOP.getText())).floatValue(); break;
         case 3: Gep = (new Float(GEP.getText())).floatValue(); break;
         case 4: Mp = (new Float(MP.getText())).floatValue(); break;
         case 5: Ms = (new Float(MS.getText())).floatValue(); break;
         default: log.append("ERROR in choose()!");
      }
   } // method choose
} // class SequenceShop
// Listener for buttons
class SSListener implements ActionListener {
   private SequenceShop applet;
   private int choice;
   
   public SSListener (SequenceShop listening_applet, int mychoice) {
      applet = listening_applet;
      choice = mychoice;
   } // constructor SSListener
   
   public void actionPerformed(ActionEvent action) {
         applet.execute(choice);
   } // method actionPerformed
} // class SSListener
// Listener for "method choice" radio buttons
class SSItemListener implements ItemListener {
   private SequenceShop applet;
   private int choice;
   
   public SSItemListener (SequenceShop listen_applet, int mychoice) {
      applet = listen_applet;
      choice = mychoice;
   } // constructor SSItemListener
   
   public void itemStateChanged (ItemEvent event) {
      
      applet.methodChoice(choice);
      
   } // method itemStateChanged
} // class SSItemListener
// Listener for other input items   
class SSInputsListener implements ActionListener {
   private SequenceShop applet;
   private int choice;
   
   public SSInputsListener (SequenceShop listen_applet, int mychoice) {
      applet = listen_applet;
      choice = mychoice;
   } // constructor SSInputsListener
   
   public void actionPerformed(ActionEvent action) {
      applet.choose(choice);
   } // method actionPerformed
} // class SSInputsListener
//========================================================================
// Class Matrix defines an object which corresponds to the computation
// grid used in the sequence alignment and includes all matrix
// processing methods.
//========================================================================
class Matrix {
   private String Seq1;    // Top sequence
   private String Seq2;    // Side sequence
   private int CL;         // Number of columns
   private int RL;         // Number of rows
   private int Score = 0;  // Number of matches
   public StringBuffer Top = new StringBuffer(0);     // Seq1 processed sequence
   public StringBuffer Middle = new StringBuffer(0);  // Middle "connecting" processed sequence
   public StringBuffer Bottom = new StringBuffer(0);  // Seq2 processed sequence
   private float GOP;      // Gap Opening Penalty
   private float GEP;      // Gap extension Penalty
   private float MS;       // Match score
   private float MP;       // Mismatch penalty (use 0 for global alignment)         
                     
   private float[][] CG;   // CG = Computation Grid
                           // CG[rows][columns]
                           
   private int GlobalMaxRow = 0;   // The row and the column of the maximum score
   private int GlobalMaxCol = 0;
   private float GlobalMaxScore = -3.0E+38f;   // Value of the maximum score for the matrix
   public Matrix (String seq1, String seq2, float gop, float gep, float mp, float ms) {
      Seq1 = this.StringOps(seq1);   // Immediate processing of the input string
      Seq2 = this.StringOps(seq2);
      CL = Seq1.length();            // Get column and row lengths
      RL = Seq2.length();
      CG = new float[RL][CL];        // Declare the actual computation grid
      GOP = gop;                   
      GEP = gep;                   
      MP = mp;                     
      MS = ms;
      this.IdentityFill();      // Reference to self -- execute these functions automatically
      this.ComputeMatrix();
      this.NormalizeMatrix();   // Turn negative matrix values to 0s
      this.AlignSequences();
   } // constructor Matrix
// Finds matches and mismatches in the matrix
   private void IdentityFill() {
      for (int r=0; r < RL; r++)
         for (int c=0; c < CL; c++) {
            if (Seq2.charAt(r) == Seq1.charAt(c))
               CG[r][c] = MS;
            else CG[r][c] = MP;
         }
   } // method IdentityFill
// Computes sum matrix based on the identity matrix
   private void ComputeMatrix () {
      for (int r = RL-1; r >= 0; r--)
         for (int c = CL-1; c >= 0; c--) {
            CG[r][c] = CG[r][c] + FindMax(r,c);
            if (CG[r][c] > GlobalMaxScore) {
               GlobalMaxScore = CG[r][c];
               GlobalMaxRow = r;
               GlobalMaxCol = c;
            }
         }
   } // method ComputeMatrix
// Remove all negative scores: essential for local alignment
   private void NormalizeMatrix() {
      for (int r=0; r < RL; r++)
         for (int c=0; c < CL; c++)
            if (CG[r][c] < 0)
               CG[r][c] = 0;
   } // method NormalizeMatrix
// Finds the maximum cell taking into account gap penalties
   private float FindMax(int row, int col) {
      float Max = 0.0f;   // Holds current maximum value
      if (row == RL-1 || col == CL-1)
         return 0.0f;                     
      
      Max = CG[row+1][col+1];
      for (int r = row+2; r <= RL-1; r++)
         if (CG[r][col+1]-(GOP + GEP*(r-row+2)) > Max) {
            Max = CG[r][col+1]-(GOP + GEP*(r-row+2)); // Dynamically computes and
         }                                            // subtracts Gap Penalty
      for (int c = col+2; c <= CL-1; c++)
         if (CG[row+1][c]-(GOP + GEP*(c-col+2)) > Max) {
            Max = CG[row+1][c]-(GOP + GEP*(c-col+2));
         }
      return Max;
   } // method FindMax
// Finds the maximum cell during traceback through the matrix
// "direction" of 0 = search to the bottom of global maximum
// "direction" of 1 = search to the top of global maximum
   private int FindMaxBack(int row, int col, int[] coord, int direction) {
      float Max = 0.0f;   // Holds current maximum value
      switch (direction) {
         case 0: {         
                    if (row == RL-1)
                       return -1;   // Return -1 means having hit "top" or 
                                    // "bottom" of matrix
                    if (col == CL-1)
                       return -2;   // Return -2 means having hit "side" of matrix            
      
                    coord[0] = row+1;
                    coord[1] = col+1;
                    Max = CG[row+1][col+1];
   
                    for (int r = row+2; r <= RL-1; r++)
                       if (CG[r][col+1]-(GOP + GEP*(r-row+2)) > Max) {                       
                          coord[0] = r;
                          coord[1] = col+1;
                          Max = CG[r][col+1]-(GOP + GEP*(r-row+2));
                       }                                            
                    for (int c = col+2; c <= CL-1; c++)
                       if (CG[row+1][c]-(GOP + GEP*(c-col+2)) > Max) {
                          coord[0] = row+1;
                          coord[1] = c;
                          Max = CG[row+1][col]-(GOP + GEP*(c-col+2));
                       }
                 } break;
        
         case 1: {
                    if (row == 0)
                       return -1;   // Return -1 means having hit "top" or 
                                    // "bottom" of the matrix        
                    if (col == 0)
                       return -2;   // Return -2 means having hit a "side" of
                                    // the matrix       
                    coord[0] = row-1;
                    coord[1] = col-1;
                    Max = CG[row-1][col-1];
                    for (int r = row-2; r >= 0; r--)
                       if (CG[r][col-1]-(GOP + GEP*(r-row+2)) > Max) {                       
                          coord[0] = r;
                          coord[1] = col-1;
                          Max = CG[r][col-1]-(GOP + GEP*(r-row+2));
                       }                                            
                    for (int c = col-2; c >= 0; c--)
                       if (CG[row-1][c]-(GOP + GEP*(c-col+2)) > Max) {
                          coord[0] = row-1;
                          coord[1] = c;
                          Max = CG[row-1][c]-(GOP + GEP*(c-col+2));
                       }
                 } break;
         default: System.out.println("ERROR in FindMaxBack()");
         
      } // switch statement
     
      return 0;
   } // method FindMaxBack
// Traces BACK through the Matrix and reads the results into StringBuffers
   private void AlignSequences() {
   
      int[] Coord = {GlobalMaxRow, GlobalMaxCol}; // Stores [r,c] of maximum score
      int wallvar = 0; // Allows to detect sides of the matrix
      int CurrMaxRow = GlobalMaxRow;
      int CurrMaxCol = GlobalMaxCol;
      int PrevMaxRow = 0;
      int PrevMaxCol = 0;
      int RowDiff = 0;  // Row difference
      int ColDiff = 0;
// Initial matching of the global top score in the matrix            
      Top.append(Seq1.charAt(CurrMaxCol));
      Bottom.append(Seq2.charAt(CurrMaxRow));
      if (Seq1.charAt(CurrMaxCol) == Seq2.charAt(CurrMaxRow)) {
         Middle.append('|');
         Score++;
      }
      else Middle.append(' ');
// "While" loop for the bottom part of the matrix      
      while (true) {
         wallvar = FindMaxBack(CurrMaxRow, CurrMaxCol, Coord, 0);
         RowDiff = Coord[0]-CurrMaxRow;
         ColDiff = Coord[1]-CurrMaxCol;
         if (wallvar == -1) {
            for (int c=CurrMaxCol+1; c < CL; c++) {
               Top.append(Seq1.charAt(c));
               Bottom.append('.');
               Middle.append(' ');
            }
            break;
         }
         if (wallvar == -2) {
            for (int r=CurrMaxRow+1; r < RL; r++) {
               Bottom.append(Seq2.charAt(r));
               Top.append('.');
               Middle.append(' ');
            }
            break;
         }
         PrevMaxRow = CurrMaxRow;
         PrevMaxCol = CurrMaxCol;
         CurrMaxRow = Coord[0];
         CurrMaxCol = Coord[1];
         for (int i = RowDiff-1; i > 0; i--) {
            Top.append('-');
            Bottom.append(Seq2.charAt(++PrevMaxRow));
            Middle.append(' ');
         }
         for (int j = ColDiff-1; j > 0; j--) {
            Bottom.append('-');
            Top.append(Seq1.charAt(++PrevMaxCol));
            Middle.append(' ');
         }
         Top.append(Seq1.charAt(CurrMaxCol));
         Bottom.append(Seq2.charAt(CurrMaxRow));
         if (Seq1.charAt(CurrMaxCol) == Seq2.charAt(CurrMaxRow)) {
            Middle.append('|');
            Score++;
         }
         else Middle.append(' ');
         
      } // while loop for "bottom"
      CurrMaxRow = GlobalMaxRow;
      CurrMaxCol = GlobalMaxCol;
// "While" loop for the top of the matrix
      while (true) {
         wallvar = FindMaxBack(CurrMaxRow, CurrMaxCol, Coord, 1);
         RowDiff = CurrMaxRow-Coord[0];
         ColDiff = CurrMaxCol-Coord[1];
         if (wallvar == -1) {
            for (int c=CurrMaxCol-1; c >= 0; c--) {
               Top.insert(0,Seq1.charAt(c));
               Bottom.insert(0,'.');
               Middle.insert(0,' ');
            }
            break;
         }
         if (wallvar == -2) {
            for (int r=CurrMaxRow-1; r >= 0; r--) {
               Bottom.insert(0,Seq2.charAt(r));
               Top.insert(0,'.');
               Middle.insert(0,' ');
            }
            break;
         }
         PrevMaxRow = CurrMaxRow;
         PrevMaxCol = CurrMaxCol;
         CurrMaxRow = Coord[0];
         CurrMaxCol = Coord[1];
         for (int i = RowDiff-1; i > 0; i--) {
            Top.insert(0,'-');
            Bottom.insert(0,Seq2.charAt(--PrevMaxRow));
            Middle.insert(0,' ');
         }
         for (int j = ColDiff-1; j > 0; j--) {
            Bottom.insert(0,'-');
            Top.insert(0,Seq1.charAt(--PrevMaxCol));
            Middle.insert(0,' ');
         }
         Top.insert(0,Seq1.charAt(CurrMaxCol));
         Bottom.insert(0,Seq2.charAt(CurrMaxRow));
         if (Seq1.charAt(CurrMaxCol) == Seq2.charAt(CurrMaxRow)) {
            Middle.insert(0,'|');
            Score++;
         }
         else Middle.insert(0,' ');
      } // while loop for "top"
  
   } // method AlignSequences
// Cleans up the input string before alignment
   private String StringOps (String str) {
      str = str.trim();
      return str;
   } // method StringOps
// Used for output of aligned sequences
   public String PrintStringBuffers(int input) {
      String string;
      switch (input) {
         case 0: string = (Top.toString() + "\n"); break;
         case 1: string = (Middle.toString() + "\n"); break;
         case 2: string = (Bottom.toString() + "\n\n"); break;
         default: return ("ERROR in PrintStringBuffers!");
      }
      return string;
   } // method PrintStringBuffer
// Used for output of other alignment statistics
   public int PrintStats(int input) {
      int Input;
      switch (input) {
         case 0: Input = Score; break;
         case 1: Input = CL; break;
         case 2: Input = RL; break;
         default: return -1;
      }
      return Input;
   } // method PrintStats
   
} // class Matrix