动态规划法-双序列比对.pptxVIP

1 /55回顾Dynamic ProgrammingEdit Distance（编辑距离）Alignment（比对）Directed Acyclic GraphEdit GraphBacktracking- T G C A T - A - CA T - C - T G A T C第1页，共55页。 2 /55习题4，求两条序列的最长共同子序列。【作业】v = TACGGGTATw = GGACGTACG第2页，共55页。 3 /550123456789000000000001020304050607080905GGACGTACGTACGGGTAT第3页，共55页。 4Sequence Alignment第4页，共55页。 5 /55OutlineGlobal Alignment Scoring MatricesLocal AlignmentAlignment with Affine Gap Penalties第5页，共55页。 6 /55From LCS to Alignment: Change up the ScoringThe Longest Common Subsequence (LCS) problem—the simplest form of sequence alignment – allows only insertions and deletions (no mismatches). In the LCS Problem, we scored 1 for matches and 0 for indelsConsider penalizing indels and mismatches with negative scoresSimplest scoring schema: +1 : match premium -μ : mismatch penalty -σ : indel penalty- T G C A T - A - CA T - C - T G A T CAKRANR KAAANK-1 + (-1) + (-2) + 5 + 7 + 3 = 11第6页，共55页。 7 /55Simple ScoringWhen mismatches are penalized by –μ, indels are penalized by –σ, and matches are rewarded with +1, the resulting score is: #matches – μ(#mismatches) – σ (#indels)第7页，共55页。 8 /55The Global Alignment ProblemFind the best alignment between two strings under a given scoring schemaInput : Strings v and w and a scoring schemaOutput : Alignment of maximum scorem : mismatch penaltyσ : indel penalty第8页，共55页。 9 /55Scoring MatricesTo generalize scoring, consider a (4+1) x(4+1) scoring matrix δ. In the case of an amino acid sequence alignment, the scoring matrix would be a (20+1)x(20+1) size. The addition of 1 is to include the score for comparison of a gap character “-”.This will simplify the algorithm as follows:第9页，共55页。 10 /55The Blosum62 Scoring Matrix第10页，共55页。 11 /55Measuring SimilarityMeasuring the extent of similarity between two sequencesBased on percent sequence identityBased on conservation第11页，共55页。 12 /55Percent Sequence IdentityThe extent to which two nucleotide or amino acid seq