Dynamic Programming Sequence aligment动态规划序列比对.pptVIP

Dynamic Programming: Sequence alignment CS 466 Saurabh Sinha DNA Sequence Comparison: First Success Story Finding sequence similarities with genes of known function is a common approach to infer a newly sequenced gene’s function In 1984 Russell Doolittle and colleagues found similarities between cancer-causing gene and normal growth factor (PDGF) gene A normal growth gene switched on at the wrong time causes cancer ! Cystic Fibrosis Cystic fibrosis (CF) is a chronic and frequently fatal genetic disease of the bodys mucus glands. CF primarily affects the respiratory systems in children. Search for the CF gene was narrowed to ~1 Mbp, and the region was sequenced. Scanned a database for matches to known genes. A segment in this region matched the gene for some ATP binding protein(s). These proteins are part of the ion transport channel, and CF involves sweat secretions with abnormal sodium content! Role for Bioinformatics Gene similarities between two genes with known and unknown function alert biologists to some possibilities Computing a similarity score between two genes tells how likely it is that they have similar functions Dynamic programming is a technique for revealing similarities between genes Motivating Dynamic Programming Dynamic programming example:Manhattan Tourist Problem Dynamic programming example:Manhattan Tourist Problem Manhattan Tourist Problem: Formulation MTP: An Example MTP: Greedy Algorithm Is Not Optimal MTP: Simple Recursive Program Here’s what’s wrong M(n,m) needs M(n, m-1) and M(n-1, m) Both of these need M(n-1, m-1) So M(n-1, m-1) will be computed at least twice Dynamic programming: the same idea as this recursive algorithm, but keep all intermediate results in a table and reuse MTP: Recurrence Manhattan Is Not A Perfect Grid Manhattan Is Not A Perfect Grid (cont’d) Traveling in the Grid Traversing the Manhattan Grid Traversing a DAG Alignment Aligning DNA Sequences Longest Common Subsequence (LCS) – Alignment without Mismatch