|
Note: This utility may be used and distributed
freely. However, please contact the author //=========================================================================== // 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
|