Recursion and dynamic Programming Aligning two protein sequences without gaps- roughly an o(mn)problem With gaps- becomes computationally astronomical, and cannot be done y direct comparison methods. (22/\(2L); L=sequence length) Alternative is to compare all possible pairs of characters(matches and mismatches, and also take gaps into account as well, while keeping the number of comparisons manageable. The approach is called dynamic programming. Mathematically proven to produce optimal alignment Need a substitution or similarity matrix and some way to account for gaps Example of how to score an alignment: Write down two sequences sequence#1 V D S C Y sequence#2 V E S L C Y Score from sub. Matrix 4 2 4 -119 7 Score=X(AA pair scores)-gap penalty =15Recursion and Dynamic Programming Aligning two protein sequences without gaps – roughly an O(mn) problem. With gaps – becomes computationally astronomical, and cannot be done by direct comparison methods. (= 22L / √(2 πL); L=sequence length) Alternative is to compare all possible pairs of characters (matches and mismatches, and also take gaps into account as well, while keeping the number of comparisons manageable. The approach is called dynamic programming. Mathematically proven to produce optimal alignment Need a substitution or similarity matrix and some way to account for gaps. Example of how to score an alignment: Write down two sequences: sequence#1 V D S – C Y sequence#2 V E S L C Y Score from sub. Matrix 4 2 4 -11 9 7 Score = Σ(AA pair scores) – gap penalty = 15