Aligning Sequences

• What is the best alignment?




• Sequence to Structure


• Sequence to group of sequences


• Sequence to sequence




• How do you actually align two sequences?




• By eye


• Using a computer


• How does a computer align sequences?


• Needleman-Wunsch algorithm


• Dynamic Programing Alignment





• Needleman-Wunsch basics

	 AATGC                AATG     C
         |  ||        =       |  |  +  |
	 AG-GC                AG-G     C



• Needleman-Wunsch details

	 Si,j = Si,j + max Sk,l   

				(1<= k < i)
				(1<= l < j)



• Needleman-Wunsch scary

	Si,j = Si,j + max Si-1,j-1 

			max Si-x,j-1  +  Wx-1     
				(2<= x < i)
			max Si-1, j-y +  Wy-1	 
                                (2<= y < i)


 Wx is the score for making a gap of length x in sequence 1
 Wy is the score for making a gap of length y in sequence 2



• Needleman-Wunsch example

	A	A	T	G	C
A	1	1	0	0	0
G	0
G
C

S1,1=1 S1,2=1 Si,j = Si,j + max {} i<=4 j<=5

• Needleman-Wunsch example

	A	A	T	G	C
A	1	1	0	0	0
G	0	1	1	2	1
G	0	1	1	2
C

       Si,j = Si,j + max Si-1,j-1
                     max Si-x,j-1  + Wx-1  
                     max Si-1,j-y  + Wy-1             
           2<=x
     




	
	Needleman-Wunsch scary 

       Si,j = Si,j + max Si-1,j-1
 	             max Si-x,j-1  + Wx-1  
                     max Si-1,j-y  + Wy-1     
          2<=x



	
	Needleman-Wunsch example 


 
A
A
T
G
C
 
A
1
1
0
0
0
 
G
0
1
1
2
1
 
G
0
1
1
2
2
 
C
1
1
1
1
3
 




	
	Needleman-Wunsch example 


 
A
A
T
G
C
 
A
1
1
 
 
 
 
G
 
1
1
2
 
 
G
 
 
 
2
 
 
C
 
 
 
 
3
 



  

  .AGGC		AG.GC	A.CGC	A..GGC	.A.GGC
   | ||		|  ||	|  ||	|  | |   | | |
  AATGC		AATGC	AATGC	AATG.C	AATG.C