Dynamic programming
Global alignment- Needleman Wunsch algorithm
Local alignment- Smith Waterman
Introduction
• The most commonly asked question in molecular biology is
whether two given sequences are related or not, in order to
identify their structure or function. The most simpler way to
answer this question is to compare their sequences.
•
• Sequence is a collection of nucleotides or amino acid residues
which are connected with each other. Speaking biologically, a
typical DNA/RNA sequence consist of nucleotides while a protein
sequence consist of amino acids.
•
• Sequencing is the process to determine the nucleotide or amino
acid sequence of a DNA fragment or a protein. There are different
experimental methods for sequencing, and the obtained sequence
is submitted to different databases like NCBI, Genbank etc.
Method of sequencing
• Sequences stored in the database were obtained from different experimental methods. Most commonly
used methods for DNA sequencing are Sanger Method and Maxam-Gilbert Method. Similarly Edman
Degradation method and Mass Spectrometry technique are used for protein sequencing.
• Sanger Method (dideoxy chain termination method): Here 4 test tubes are taken labelled with A, T, G
and C. Into each of the test tubes, DNA has to be added in denatured form (single strands). Next a
primer is to be added which anneals to one of the strand in template. The 3' end of the primer
accomodates the dideoxy nucleotides [ddNTPs] (specific to each tube) as well as deoxy nucleotides
randomly. When the ddNTP's gets attached to the growing chain, the chain terminates due to lack of
3'OH which forms the phospho diester bond with the next nucleotide. Thus small strands of DNA are
formed. Electrophoresis is done and the sequence order can be obtained by analysing the bands in the
gel based on the molecular weight. The primer or one of the nucleotides can be radioactively or
fluorescently labeled also, so that the final product can be detected from the gel easily and the sequence
can be inferred.
• Maxam-Gilbert (Chemical degradation method): This method requires denatured DNA fragment whose
5' end is radioactively labeled. This fragment is then subjected to purification before proceeding for
chemical treatment which results in a series of labeled fragments. Electrophoresis technique helps in
arranging the fragments based on their molecular weight. To view the fragments, gel is exposed to X-ray
film for autoradiography. A series of dark bands will appear, each corresponding to a radio labeled DNA
fragment, from which the sequence can be inferred.
• Edman Degradation reaction: The reaction finds the order of amino acids in a protein by cleaving each
amino acid from the N-terminal without distrubing the bonds in the protein. After each clevage,
chromatography or electrophoresis is done to identify the amino acid.
• Mass Spectrometry: It is used to determine the mass of particle, composition of molecule and for
finding the chemical structures of molecules like peptides and other chemical compounds. Based on the
mass to charge ratio, one can identify the amino acids in a protein.
Sequence alignment and importance
• Sequence Alignment or sequence comparison lies at heart of the
bioinformatics, which describes the way of arrangement of
DNA/RNA or protein sequences, in order to identify the regions of
similarity among them. It is used to infer structural, functional and
evolutionary relationship between the sequences. Alignment finds
similarity level between query sequence and different database
sequences. The algorithm works by dynamic programming
approach which divides the problem into smaller independent sub
problems. It finds the alignment more quantitatively by assigning
scores.
•
• When a new sequence is found, the structure and function can be
easily predicted by doing sequence alignment. Since it is believed
that, a sequence sharing common ancestor would exhibit similar
structure or function. Greater the sequence similarity, greater is the
Methods of sequence alignment
• There are mainly two methods of Sequence Alignment:
•
• Global Alignment : Closely related sequences which are of same length are very much
appropriate for global alignment. Here, the alignment is carried out from beginning till end
of the sequence to find out the best possible alignment.
•
• The Needleman-Wunsch algorithm (A formula or set of steps to solve a problem) was
developed by Saul B. Needleman and Christian D. Wunsch in 1970, which is a dynamic
programming algorithm for sequence alignment. The dynamic programming solves the
original problem by dividing the problem into smaller independent sub problems. These
techniques are used in many different aspects of computer science. The algorithm explains
global sequence alignment for aligning nucleotide or protein sequences.
•
• Local Alignment : Sequences which are suspected to have similarity or even dissimilar
sequences can be compared with local alignment method. It finds local regions with high
level of similarity.
•
• These two methods of alignments are defined by different algorithms, which use scoring
matrices to align the two different series of characters or patterns (sequences). The two
different alignment methods are mostly defined by Dynamic programming approach for
Dynamic programming
• Dynamic programming is used for optimal alignment of two
sequences. It finds the alignment in a more quantitative
way by giving some scores for matches and mismatches
(Scoring matrices), rather than only applying dots. By
searching the highest scores in the matrix, alignment can be
accurately obtained.
• The Dynamic Programming solves the original problem by
dividing the problem into smaller independent sub
problems. These techniques are used in many different
aspects of computer science. Needleman-Wunsch and
Smith-Waterman algorithms for sequence alignment are
defined by dynamic programming approach.
• Then combine the solution of sub-problems to reach an
overall solution
Needleman wunsch algorithm for global
alignment
• Two sequences to be aligned are
• TCGCA
• TCCA
• Are written horizontally and vertically and a
matrix with one extra row and column is
made.
• A cell c is formed by intersection of row i and
column j with score mentioned as a[I, j].
• If we want to calculate score at any position a[i, j] in
the matrix we have to look at three adjacent cells
namely c[i-1,j], c[I, j-1], c[i-1, j-1]
• If the values of corresponding row and column are
matching +1 score is added diagonally, if it’s a
mismatch -1 is added diagonally.
• A gap penalty of -2 is added up and left.
• Out of the three scores the maximum is used to fill
the current cell.
• c[i, j-1] - 2
• C[i, j]=max c[i-1, j] - 2
• c[i-1, j-1] + p(i, j)
• Here p(i, j) is a function that returns +1 if c[i]=c[j] or
match and returns -1 if they do not match
T C G C A
0 -2 -4 -6 -8 -10
T -2
C -4
C -6
A -8
Step 1. initialization of alignment matrix. This is done by adding a gap penalty in each cell
vertically and across
Step 2. Matrix fill- the maximal score at each cell is filled according to formula already
discusses
Step 3.
Trace- back- the process of deduction of the best alignment from the
matrix.
The traceback always begins with the last cell to be filled
with the score, i.e. the bottom right cell.
One moves according to the traceback value written in the
cell.
There are three possible moves: diagonally (toward the
top-left corner of the matrix), up, or left.
The traceback is completed when the first, top-left cell of
the matrix is reached (”done” cell).
Trace back continued
• The alignment is deduced from the values of
cells along
• the traceback path, by taking into account the
values of the cell in the traceback matrix:
• diag – the letters from two sequences are
aligned
• left – a gap is introduced in the left sequence
• up – a gap is introduced in the top sequence
• Sequences are aligned backwards.
T C G C A
0 -2 -4 -6 -8 -10
T -2 1 -1 -3 -5 -7
C -4 -1 2 0 -2 -4
C -6 -3 0 1 1 -1
A -8 -5 -2 -1 0 2