Consider the following alignment matrix a Write down all max

Consider the following alignment matrix:

(a) Write down all maximallyscoring alignments for the dynamic programming matrix shown above.

(b) Was this DP matrix generated by the Smith-Waterman or Needleman-Wunsch algorithm? How do you know?

(c) For this DP matrix, is the gap penalty linear or affine? Explain and give the value(s).

(d) What is the scoring matrix, based on the above DP matrix.Note that you can infer some comparisons precisely whereas for others you can only infer the bounds (i.e. score is < 0).

10 1-4 14 12 10 -6 2018 21 12 16 24 FT 8-22 801 E8 128-6 D-6 212-18 24 C-4 597 4-2 7531 0 -2 4 6 8 GHIK

Solution

It is commonly asked in molecular biology that whether two given sequences are related or not, in order to identify their structure or function. The simpler way to answer this question is to compare their sequences.

Sequence Alignment studies lay the foundation of bioinformatics. Bioinformatics describes the arrangement of DNA/RNA or protein sequences, in order to identify the regions of similarity among them. This information is used to infer structural, functional and evolutionary relationship between the sequences. Two types of alignments widely studied:

Global Alignment- In this the alignment is carried out from beginning till end of the sequence to find out the best possible alignment.

Local Alignment: It finds the local regions with high level of similarity.

Dynamic programming is used for optimal alignment of two sequences. It gives scores for matches and mismatches (Scoring matrices), rather than only applying dots. By searching for the highest scores in the matrix, alignment can be accurately obtained. Needleman-Wunsch and Smith-Waterman algorithms for sequence alignment are defined by dynamic programming approach.

Smith Waterman algorithm was first proposed by Temple F. Smith and Michael S. Waterman in 1981. With the help of this algorithm the local sequence alignment can be explained. The main advantage of Local Sequence Alignment is that it gives conserved regions between the two sequences.

M_i,j = Maximum (M_i-1,_j-1 + S_i,j M_i,j-1 + W, M_i-1,j + W, 0)

Variables used stands for; i,j describes row and columns, M is the matrix value of the required cell (stated as M_i,j) S is the score of the required cell (S_i,j) and W is the gap alignment.

One can fill the 1st row and 1st column with the scoring matrix as follows:

b) The main difference Smith Waterman algorithm to the Needleman–Wunsch algorithm is that negative scoring matrix cells are set to zero. Traceback procedure starts at the highest scoring matrix cell and proceeds until a cell with score zero is encountered, yielding the highest scoring local alignment. Therefore, the given DP matrix is generated by Needleman-Wunsch algorithm.

c) It is observed that sequence alignment can have gap penalties favoring larger(Affine gap penalty) or fewer gaps(Linear gap penalty).

The gap penalties affect the alignment result. High penalties suggests compact alignments and low ones the opposite. The aim of analysing data without a prior assumption of the \"true\" penalty and therefore favoring gaps of certain length is great but unfortunately there are no perfect solutions for doing this.

d) Scoring matrix: Needleman-Wunsch and Smith-Waterman algorithms procedures use scoring system. For nucleotide sequence alignment, the scoring matrices used are relatively simpler since the frequency of mutation for all the bases are equal. Positive or higher value is assigned for a match and a negative or a lower value is assigned for mismatch. These assumption can be used for scoring the matrices.