Question

Write a Matlab script to solve. Output the aligned sequences with the maximum alignment score.

We would like to align two DNA sequences: (v) C G A T A C T, and (w) G A T T C G T based on the following scoring scheme

i) s(i, j) = 1.5 if vi = wj (matches);

ii) s(i, j) = -1.0 if vi != wj (mismatches);

iii) d = 0.25 (indels: insertions or deletions). D is the gap penality

What would be the maximum alignment score? Explain how you get the result.

Answer 1

Answer:

Scoring systems in pairwise alignments
In order to align a pair of sequences, a scoring system is required to score matches and mismatches. The scoring system can be as simple as “+1” for a match and “-1” for a mismatch between the pair of sequences at any given site of comparison. However substitutions, insertions and deletions occur at different rates over evolutionary time. This variation in rates is the result of a large number of factors, including the mutation process, genetic drift and natural selection. For protein sequences, the relative rates of different substitutions can be empirically determined by comparing a large number of related sequences. These empirical measurements can then form the basis of a scoring system for aligning subsequent sequences. Many scoring systems have been developed in this way. These matrices incorporate the evolutionary preferences for certain substitutions over other kinds of substitutions in the form of log-odd scores. Popular matrices used for protein alignments are BLOSUM and PAM1 matrices.
Note: The BLOSUM and PAM matrices are substitution matrices. The number of a BLOSUM matrix indicates the threshold (%) similarity between the sequences originally used to create the matrix. BLOSUM matrices with higher numbers are more suitable for aligning closely related sequences. For PAM, the lower numbered tables are for closely related sequences and higher numbered PAMs are for more distant groups.
When aligning protein sequences in Geneious, a number of BLOSUM and PAM matrices are available.
Algorithms for pairwise alignments
Once a scoring system has been chosen, we need an algorithm to find the optimal alignment of two sequences. This is done by inserting gaps in order to maximize the alignment score. If the sequences are related along their entire sequence, a global alignment is appropriate. However, if the relatedness of the sequences is unknown or they are expected to share only small regions of similarity, (such as a common domain) then a local alignment is more appropriate.
An efficient algorithm for global alignment was described by Needleman and Wunsch 1970, and their algorithms was later extended by Gotoh 1982 to model gaps more accurately. For local alignments, the Smith-Waterman algorithm is the most commonly used. See the references at the links provided for further information on these algorithms.
Number of alignments
• There are many ways to align two sequences • Consider the sequence fragments below: a simple alignment shows some conserved portions
• Number of possible alignments for 2 sequences of length 1000 residues: ! more than 10600 gapped alignments (Avogadro 1024, estimated number of atoms in the universe 1080)