Sequence Alignment Algorithms

In this section you will optimally align two short protein sequences using pen and paper, then search for homologous proteins by using a computer program to align several, much longer, sequences.

Dynamic programming algorithms are recursive algorithms modified to store intermediate results, which improves efficiency for certain problems. The Smith-Waterman (Needleman-Wunsch) algorithm uses a dynamic programming algorithm to find the optimal local (global) alignment of two sequences -- $a$ and $b$. The alignment algorithm is based on finding the elements of a matrix $H$ where the element $H_{i,j}$ is the optimal score for aligning the sequence ($a_1$,$a_2$,...,$a_i$) with ($b_1$,$b_2$,.....,$b_j$). Two similar amino acids (e.g. arginine and lysine) receive a high score, two dissimilar amino acids (e.g. arginine and glycine) receive a low score. The higher the score of a path through the matrix, the better the alignment. The matrix $H$ is found by progressively finding the matrix elements, starting at $H_{1,1}$ and proceeding in the directions of increasing $i$ and $j$. Each element is set according to:

$$H_{i,j} = \textrm{max} \left\{ \begin{array}{l} H_{i-1,j-1} ... ...\ H_{i-1,j} - d \\ H_{i,j-1} - d \\ \end{array} \right.$$

where $S_{i,j}$ is the similarity score of comparing amino acid $a_i$ to amino acid $b_j$ (obtained here from the BLOSUM40 similarity table) and $d$ is the penalty for a single gap. The matrix is initialized with $H_{0,0} = 0$. When obtaining the local Smith-Waterman alignment, $H_{i,j}$ is modified:

$$H_{i,j} = \textrm{max} \left\{ \begin{array}{l} 0\\ H_{i-1... ...\\ H_{i-1,j} - d \\ H_{i,j-1} - d \\ \end{array} \right.$$

The gap penalty can be modified, for instance, $d$ can be replaced by $(d \times k)$, where $d$ is the penalty for a single gap and $k$ is the number of consecutive gaps.

Once the optimal alignment score is found, the ``traceback'' through $H$ along the optimal path is found, which corresponds to the the optimal sequence alignment for the score. In the next set of exercises you will manually implement the Needleman-Wunsch alignment for a pair of short sequences, then perform global sequence alignments with a computer program developed by Anurag Sethi, which is based on the Needleman-Wunsch algorithm with an affine gap penalty, $d + e (k-1)$, where $e$ is the extension gap penalty. The output file will be in the GCG format, one of the two standard formats in bioinformatics for storing sequence information (the other standard format is FASTA).

Manually perform a Needleman-Wunsch alignment

In the first exercise you will test the Smith-Waterman algorithm on a short sequence parts of hemoglobin (PDB code 1AOW) and myoglobin 1 (PDB code 1AZI).

• Here you will align the sequence HGSAQVKGHG to the sequence KTEAEMKASEDLKKHGT.

• The two sequences are arranged in a matrix in Table 3. The sequences start at the upper right corner, the initial gap penalties are listed at each offset starting position. With each move from the start position, the initial penalty increase by our single gap penalty of 8.

Table 3: The empty matrix with initial gap penalties.

		H	G	S	A	Q	V	K	G	H	G
	0	-8	-16	-24	-32	-40	-48	-56	-64	-72	-80
K	-8
T	-16
E	-24
A	-32
E	-40
M	-48
K	-56
A	-64
S	-72
E	-80
D	-88
L	-96
K	-104
K	-112
H	-120
G	-128
T	-136

• The first step is to fill in the similarity scores S$_{i,j}$ from looking up the matches in the BLOSUM40 table, shown here labeled with 1-letter amino acid codes:

A  5 
R -2  9
N -1  0  8  
D -1 -1  2  9 
C -2 -3 -2 -2 16 
Q  0  2  1 -1 -4  8 
E -1 -1 -1  2 -2  2  7 
G  1 -3  0 -2 -3 -2 -3  8 
H -2  0  1  0 -4  0  0 -2 13 
I -1 -3 -2 -4 -4 -3 -4 -4 -3  6  
L -2 -2 -3 -3 -2 -2 -2 -4 -2  2  6 
K -1  3  0  0 -3  1  1 -2 -1 -3 -2  6 
M -1 -1 -2 -3 -3 -1 -2 -2  1  1  3 -1  7 
F -3 -2 -3 -4 -2 -4 -3 -3 -2  1  2 -3  0  9 
P -2 -3 -2 -2 -5 -2  0 -1 -2 -2 -4 -1 -2 -4 11 
S  1 -1  1  0 -1  1  0  0 -1 -2 -3  0 -2 -2 -1  5 
T  0 -2  0 -1 -1 -1 -1 -2 -2 -1 -1  0 -1 -1  0  2  6 
W -3 -2 -4 -5 -6 -1 -2 -2 -5 -3 -1 -2 -2  1 -4 -5 -4 19 
Y -2 -1 -2 -3 -4 -1 -2 -3  2  0  0 -1  1  4 -3 -2 -1  3  9 
V  0 -2 -3 -3 -2 -3 -3 -4 -4  4  2 -2  1  0 -3 -1  1 -3 -1  5 
B -1 -1  4  6 -2  0  1 -1  0 -3 -3  0 -3 -3 -2  0  0 -4 -3 -3  5 
Z -1  0  0  1 -3  4  5 -2  0 -4 -2  1 -2 -4 -1  0 -1 -2 -2 -3  2  5
X  0 -1 -1 -1 -2 -1 -1 -1 -1 -1 -1 -1  0 -1 -2  0  0 -2 -1 -1 -1 -1 -1  
   A  R  N  D  C  Q  E  G  H  I  L  K  M  F  P  S  T  W  Y  V  B  Z  X

• We fill in the BLOSUM40 similarity scores for you in Table 4.

• To turn this $S$ matrix intro the dynamic programming $H$ matrix requires calculation of the contents of all 170 boxes. We've calculated the first 4 here, and encourage you to calculate the contents of at least 4 more. The practice will come in handy in the next steps. As described above, a matrix square cannot be filled with its dynamic programming value until the squares above, to the left, and to the above-left diagonal are computed. The value of a square is

  
  

  $$H_{i,j} = \textrm{max} \left\{ \begin{array}{l} H_{i-1,j-1} ... ...\ H_{i-1,j} - d \\ H_{i,j-1} - d \\ \end{array} \right.$$
  
  

  , using the convention that $H$ values appear in the top part of a square in large print, and $S$ values appear in the bottom part of a square in small print. Our gap penalty $d$ is 8.

• Example: In the upper left square in Table 4, square (1,1), the similarity score $S_{1,1}$ is -1, the number in small type at the bottom of the box. The value to assign as $H_{1,1}$ will be the greatest (``max'') of these three values: $( H_{0,0} + S_{1,1} ), (H_{0,1} - d), (H_{1,0} - d) )$. That is, the greatest of: $(0 + -1), (-8 -8), (-8 -8)$ which just means the greatest of: -1, -16, and -16. This is -1, so we write -1 as the value of $H_{1,1}$ (the larger number in the top part of the box). The same reasoning in square (2,1) leads us to set $H_{2,1}$ as -9, and so on.

  Note: we consider $H_{0,0}$ to be the ``predecessor'' of $H_{1,1}$, since it helped decided $H_{1,1}$'s value. Later, predecessors will qualify to be on the traceback path.

• Again, just fill in 4 or 5 boxes in Table 4 until you get a feel for gap penalties and similarity scores S vs. alignment scores H. In the next step, we provide the matrix with all values filled in as Table 5. Check that your 4 or 5 calculations match.

• Now we move to Table 5, with all 170 $H_{i,j}$ values are shown, to do the ``alignment traceback''. To find the alignment requires one to trace the path through from the end of the sequence (the lower right box) to the start of the sequence (the upper left box). This job looks complicated, but should only take about 5 -7 minutes.

• We are tracing a path in Table 5, from the lower right box to the upper left box. You can only move to a square if it could have been a ``predecessor'' of your current square - that is, when the matrix was being filled with $H_{i,j}$ values, the move from the predecessor square to your current square would have followed the mathematical rules we used to find H$_{i,j}$ above. Circle each square you move to along your path.

• Example: we start at the lower right square (10,17), where $H_{10,17}$ is -21 and $S_{10,17}$ is -2. We need to test for 3 possible directions of movement: diagonal (up + left), up, and left. The condition for diagonal movement given above is: $H_{i,j} = H_{i-1,j-1} + S_{i,j}$, so for the diagonal box (9,16) to have contributed to (10,17), $H_{9,16} + S_{10,17}$ would have to equal the H value of our box, -21. Since (-29 + -2) does not equal -21, the diagonal box is not a ``predecessor'', so we can't move in that direction. We try the rule for the box to the left: $H_{i,j} = H_{i-1,j} - d$ Since -37 - 8 does not equal -21, we also can't move left. Our last chance is moving up. We test $H_{i,j} = H_{i,j-1} - d$. Since -21 = (-13 - 8) we can move up! Draw an arrow from the lower right box, ( $H_{10,17}=-21, S_{10,17}= -2$) to the box just above it, ( $H_{10,16}=-13, S_{10,16} =8$) .

• Continue moving squares, drawing arrows, and circling each new square you land on, until you have reached the upper right corner of the matrix If the path branches, follow both branches.

• Write down the alignment(s) that corresponds to your path(s) by writing the the letter codes on the margins of each position along your circled path. Aligned pairs are at the boxes at which the path exits via the upper-left corner. When there are horizontal or vertical movements movements along your path, there will be a gap (write as a dash, ``-'') in your sequence.

Table 4: Alignment score worksheet. In all alignment boxes, the similarity score $S_{i,j}$ from the BLOSUM40 matrix lookup is supplied (small text, bottom of square). Four alignment scores are provided as examples (large text, top of square), try and calculate at least four more, following the direction provided in the text for calculating $H_{i,j}$.

		H	G	S	A	Q	V	K	G	H	G
	0	-8	-16	-24	-32	-40	-48	-56	-64	-72	-80
K	-8	$\begin{array}{c} \mathbf{-1}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{-9}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{6}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$
T	-16	$\begin{array}{c} \mathbf{-9}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{-3}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$
E	-24	$\begin{array}{c} \mathbf{}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-3}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-3}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-3}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-3}}\\ \end{array}$
A	-32	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{5}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{1}}\\ \end{array}$
E	-40	$\begin{array}{c} \mathbf{}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-3}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-3}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-3}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-3}}\\ \end{array}$
M	-48	$\begin{array}{c} \mathbf{}\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$
K	-56	$\begin{array}{c} \mathbf{}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{6}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$
A	-64	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{5}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{1}}\\ \end{array}$
S	-72	$\begin{array}{c} \mathbf{}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{5}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{0}}\\ \end{array}$
E	-80	$\begin{array}{c} \mathbf{}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-3}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-3}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-3}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-3}}\\ \end{array}$
D	-88	$\begin{array}{c} \mathbf{}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-3}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$
L	-96	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-4}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-3}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-4}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-4}}\\ \end{array}$
K	-104	$\begin{array}{c} \mathbf{}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{6}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$
K	-112	$\begin{array}{c} \mathbf{}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{6}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$
H	-120	$\begin{array}{c} \mathbf{}\\ {_{13}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-4}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{13}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$
G	-128	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{8}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-4}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{8}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{8}}\\ \end{array}$
T	-136	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{}\\ {_{-2}}\\ \end{array}$

Table 5: Traceback worksheet. The completed alignment score matrix $H$ (large text, top of each square) with the BLOSUM40 lookup scores S$_{i,j}$ (small text, bottom of each square). To find the alignment, trace back starting from the lower right (T vs G, score -21) and proceed diagonally (to the left and up), left, or up. Only proceed, however, if the square in that direction could have been a predecessor, according to the conditions described in the text.

		H	G	S	A	Q	V	K	G	H	G
	0	-8	-16	-24	-32	-40	-48	-56	-64	-72	-80
K	-8	$\begin{array}{c} \mathbf{-1}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{-9}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -16}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{-24}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -31}\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{-39}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -42 }\\ {_{6}}\\ \end{array}$	$\begin{array}{c} \mathbf{-50 }\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -58 }\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{-66}\\ {_{-2}}\\ \end{array}$
T	-16	$\begin{array}{c} \mathbf{-9}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{-3}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -7}\\ {_{2}}\\ \end{array}$	$\begin{array}{c} \mathbf{-15}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -23}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{-30}\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -38 }\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{-44 }\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -52 }\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{-60}\\ {_{-2}}\\ \end{array}$
E	-24	$\begin{array}{c} \mathbf{ -16}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{-11}\\ {_{-3}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -3}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -8}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -13}\\ {_{2}}\\ \end{array}$	$\begin{array}{c} \mathbf{-21}\\ {_{-3}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -29 }\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{-37 }\\ {_{-3}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -44 }\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{-52}\\ {_{-3}}\\ \end{array}$
A	-32	$\begin{array}{c} \mathbf{-24}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{-15}\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -10}\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{ 2}\\ {_{5}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -6}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{-13}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -21 }\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{-28 }\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -36 }\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{-43}\\ {_{1}}\\ \end{array}$
E	-40	$\begin{array}{c} \mathbf{-32}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{-23}\\ {_{-3}}\\ \end{array}$	$\begin{array}{c} \mathbf{-15}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -6}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{ 4}\\ {_{2}}\\ \end{array}$	$\begin{array}{c} \mathbf{-4}\\ {_{-3}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -12 }\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{-20 }\\ {_{-3}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -28 }\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{-36}\\ {_{-3}}\\ \end{array}$
M	-48	$\begin{array}{c} \mathbf{-39}\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{-31}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -23}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{-14}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -4}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{ 5}\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -3 }\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{-11 }\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -19 }\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{-27}\\ {_{-2}}\\ \end{array}$
K	-56	$\begin{array}{c} \mathbf{-47}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{-39}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -31}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{-22}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -12 }\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{-3}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{ 11 }\\ {_{6}}\\ \end{array}$	$\begin{array}{c} \mathbf{ 3 }\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -5 }\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{-13}\\ {_{-2}}\\ \end{array}$
A	-64	$\begin{array}{c} \mathbf{-55}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{-46}\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -38}\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{-26}\\ {_{5}}\\ \end{array}$	$\begin{array}{c} \mathbf{-20}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -11}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{ 3}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{ 12}\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{ 4 }\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -4}\\ {_{1}}\\ \end{array}$
S	-72	$\begin{array}{c} \mathbf{-63 }\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{-54 }\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -41 }\\ {_{5}}\\ \end{array}$	$\begin{array}{c} \mathbf{-34}\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{-25 }\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{-19}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{-5 }\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{ 4 }\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{11 }\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{ 4 }\\ {_{0}}\\ \end{array}$
E	-80	$\begin{array}{c} \mathbf{-71 }\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{-62 }\\ {_{-3}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -49 }\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{-42}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{-32 }\\ {_{2}}\\ \end{array}$	$\begin{array}{c} \mathbf{-27}\\ {_{-3}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -13 }\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{-4}\\ {_{-3}}\\ \end{array}$	$\begin{array}{c} \mathbf{ 4 }\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{ 8}\\ {_{-3}}\\ \end{array}$
D	-88	$\begin{array}{c} \mathbf{-79 }\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{-70 }\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -57 }\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{-50}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{-40 }\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{-35}\\ {_{-3}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -21 }\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{-12 }\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{-4 }\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{ 2}\\ {_{-2}}\\ \end{array}$
L	-96	$\begin{array}{c} \mathbf{-87 }\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{-78 }\\ {_{-4}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -65 }\\ {_{-3}}\\ \end{array}$	$\begin{array}{c} \mathbf{-58}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{-48 }\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{-38}\\ {_{2}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -29 }\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{-20 }\\ {_{-4}}\\ \end{array}$	$\begin{array}{c} \mathbf{-12 }\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{-6}\\ {_{-4}}\\ \end{array}$
K	-104	$\begin{array}{c} \mathbf{-95 }\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{-86 }\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -73 }\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{-66}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{-56 }\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{-46}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -32 }\\ {_{6}}\\ \end{array}$	$\begin{array}{c} \mathbf{-28 }\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{-20 }\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{-14}\\ {_{-2}}\\ \end{array}$
K	-112	$\begin{array}{c} \mathbf{-103}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -94}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -81}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -74}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{-64}\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{-54}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -40}\\ {_{6}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -34}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{-28}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{-22}\\ {_{-2}}\\ \end{array}$
H	-120	$\begin{array}{c} \mathbf{-99}\\ {_{13}}\\ \end{array}$	$\begin{array}{c} \mathbf{-102}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -89}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -82}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{-72}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{-62}\\ {_{-4}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -48}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -42}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{-21}\\ {_{13}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -29 }\\ {_{-2}}\\ \end{array}$
G	-128	$\begin{array}{c} \mathbf{-107}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -91}\\ {_{8}}\\ \end{array}$	$\begin{array}{c} \mathbf{-97}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -88}\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{-80}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{-70}\\ {_{-4}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -56}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -40}\\ {_{8}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -29 }\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{-13}\\ {_{8}}\\ \end{array}$
T	-136	$\begin{array}{c} \mathbf{-115}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -99}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{-89}\\ {_{2}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -96}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{-88}\\ {_{-1}}\\ \end{array}$	$\begin{array}{c} \mathbf{-78}\\ {_{1}}\\ \end{array}$	$\begin{array}{c} \mathbf{ -64}\\ {_{0}}\\ \end{array}$	$\begin{array}{c} \mathbf{-48 }\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{-37}\\ {_{-2}}\\ \end{array}$	$\begin{array}{c} \mathbf{-21}\\ {_{-2}}\\ \end{array}$

• Now to check your results against a computer program. We have prepared a pairwise Needleman-Wunsch alignment program, pair, which you will apply to the same sequences which you have just manually aligned.

• Change your directory by typing at the Unix prompt:
  cd ~/tbss.work/Bioinformatics/pairData
  then start the pair alignment executable by typing:
  pair targlist
  . All alignments will be carried out using the BLOSUM40 matrix, with a gap penalty of 8. The paths to the input files and the BLOSUM40 matrix used are defined in the file targlist; the BLOSUM40 matrix is the first 25 lines of the file blosum40. (Other substitution matrices can be found at the NCBI/Blast website.)

  Note: In some installations, the pair executable is
  in ~/tbss.work/Bioinformatics/pairData and here you must
  type ./pair targlist to run it.
  If you cannot access the pair executable at all, you can see the output from this step in ~/tbss.work/Bioinformatics/pairData/example_output/

• After executing the program you will generate three output files namely align, scorematrix and stats. View the alignment in GCG format by typing less align. The file scorematrix is the 17x10 $H$ matrix. If there are multiple paths along the traceback matrix, the program pair will choose only one path, by following this precedence rule for existing potential traceback directions, listed in decreasing precedence: diagonal (left and up), up, left. In the file stats you will find the optimal alignment score and the percent identity of the alignment.

Finding homologous pairs of ClassII tRNA synthetases

Homologous proteins are proteins derived from a common ancestral gene. In this exercise with the Needleman-Wunsch algorithm you will study the sequence identity of several class II tRNA synthetases, which are either from Eucarya, Eubacteria or Archaea or differ in the kind of aminoacylation reaction which they catalyze. Table 6 summarizes the reaction type, the organism and the PDB accession code and chain name of the employed Class II tRNA synthetase domains.

Table 6: Domain types, origins, and accession codes

Specificity	Organism	PDB code:chain	ASTRAL catalytic domain
Aspartyl	Eubacteria	1EQR:B	d1eqrb3
Aspartyl	Archaea	1B8A:A	d1b8aa2
Aspartyl	Eukarya	1ASZ:A	d1asza2
Glycl	Archaea	1ATI:A	d1atia2
Histidyl	Eubacteria	1ADJ:C	d1adjc2
Lysl	Eubacteria	1BBW:A	d1bbwa2
Aspartyl	Eubacteria	1EFW:A	d1efwa3

• We have have prepared a computer program multiple which will align multiple pairs of proteins.

• Change your directory by typing at the Unix prompt:
  cd ~/tbss.work/Bioinformatics/multipleData
  then start the alignment executable by typing:
  multiple targlist
  .

  Note: In some installations, the multiple executable is
  in ~/tbss.work/Bioinformatics/multipleData and here you must
  type ./multiple targlist to run it.
  If you cannot access the multiple executable at all, you can see the output from this step in ~/tbss.work/Bioinformatics/multipleData/example_output/

• In the align and stats files you will find all combinatorial possible pairs of the provided sequences. On a piece of paper, write the names of the the proteins, grouped by ther domain of life, as listed in Table 6. Compare sequence identities of aligned proteins from the same domain of a life, and of aligned proteins from different domains of life, to help answer the questions below.