SequenceAlignment-Application-Lirq.pptVIP

– the foundation of bioinformatics analysis 李瑞强 lirq@ Beijing Genomics Institute 2006-03-17 Types of Alignment - Algorithm Dot Plots Dynamic programing (blast, fasta) Global - Needelman-Wunsch Local - Smith-Waterman Profile based (HMM, Psi-blast) Structure based - Object DNA ?? DNA DNA ?? Protein Protein ?? Protein Protein ?? Structure Structure ?? Structure Dynamic programing in equation form Align sequence x and y. F is the DP matrix; s is the substitution matrix; d is the linear gap penalty. DP in equation form A simple example A simple example A simple example A simple example Traceback Start from the lower right corner and trace back to the upper left. Each arrow introduces one character at the end of each aligned sequence. A horizontal move puts a gap in the left sequence. A vertical move puts a gap in the top sequence. A diagonal move uses one character from each sequence. A simple example A simple example Gap penalties If low enough, can align anything Penalties associated with a scoring matrix Two common varieties: Gap opening cost same as gap extension cost Opening and extension costs different (extension much smaller than opening) BLOSUM62 - Scoring matrix for protein sequences Local alignment Smith-Waterman (1981) Another dynamic programming solution Local alignment Application of DP to search sequence databases. BLAST - Basic Local Alignment Search Tool. finds regions of local similarity between sequences. BLAST Algorithm Extension criteria: one-hit ? two-hit Blast Word Size Right tool for right job NCBI Blast Program Selection Guide /BLAST/ NCBI protein sequence databases NCBI Nucleotide sequence databases NCBI genome databases Program Selection for Nucleotide Queries Program Selection for Protein Queries View of blast result Matched hits – sorted according to scores Detailed alignments Low complexity region Search against Organism Specific or Genome Databases Function of Special BLAST Pages under Special/Meta Sections PSI