Sequence Alignment 2 Part II (PDF)

Introduction to Bioinformatics Introduction to Bioinformatics Notes on Sequence Alignments Part II Chi-Cheng Lin, Ph.D. Department of Computer Science...

Introduction to Bioinformatics Introduction to Bioinformatics Notes on Sequence Alignments Part II Chi-Cheng Lin, Ph.D. Department of Computer Science Winona State University [email protected] Introduction to Bioinformatics Dynamic Programming Dynamic programming is the technique used to perform sequence alignment. It is a technique for solving optimization problems that works as follows: – Find and memorize solutions for subproblems – Use those solutions to build solutions for larger subproblems – Continue until the final solution is found It is basically a recursive computation of cost function in a non-recursive fashion 2 Introduction to Bioinformatics Dynamic Programming Example – Solving Fibonacci number f(n) = f(n-1) + f(n-2) recursively takes exponential time – Because many numbers are recalculated 3 Introduction to Bioinformatics Recursive Fibonacci int f(int n) { // 1, 1, 2, 3, 5, 8, 13, … if (n