Table of Contents
DNA1: Last week's take-home lessons
DNA2: Today's story and goals
DNA 2
Applications of Dynamic Programming
Alignments & Scores
Increasingly complex (accurate) searches
"Hardness" of (multi-) sequence alignment
Testing search & classification algorithms
Comparisons of homology scores
Switch to protein searches when possible
A Multiple Alignment of Immunoglobulins
Scoring matrix based on large set of distantly related blocks: Blosum62
Scoring Functions and Alignments
Calculating Alignment Scores
DNA2: Today's story and goals
What is dynamic programming?
Recursion of Optimal Global Alignments
Recursion of Optimal Local Alignments
Computing Row-by-Row
Traceback Optimal Global Alignment
Local and Global Alignments
Time and Space Complexity of Computing Alignments
Time and Space Problems
Time & Space Improvement for w-band Global Alignments
Summary
DNA2: Today's story and goals
A Multiple Alignment of Immunoglobulins
A multiple alignment <=> Dynamic programming on a hyperlattice
Multiple Alignment vs Pairwise Alignment
Computing a Node on Hyperlattice
Challenges of Optimal Multiple Alignments
Methods and Heuristics for Optimal Multiple Alignments
ClustalW: Progressive Multiple Alignment
Star Alignments
DNA2: Today's story and goals
Accurately finding genes & their edges
Annotated "Protein" Sizes in Yeast & Mycoplasma
Predicting small proteins (ORFs)
Small coding regions
Motif Matrices
Protein starts
Motif Matrices
DNA2: Today's story and goals
Why probabilistic models in sequence analysis?
A Basic idea
Sequence recognition
Database search
Plausible sources of mono, di, tri, & tetra- nucleotide biases
CpG Island + in a ocean of - First order Markov Model
Estimate transistion probabilities -- an example
Estimated transistion probabilities from 48 "known" islands
Viterbi: dynamic programming for HMM
DNA2: Today's story and goals
|