7.91- Lecture #2 Michael Yaffe More Pairwise Sequence Comparisons ARDE SHGLLENKLLGCDSMRWE :..:::: GRDYKMALLEQWIIGCD-MRWD and Multiple sequence Alignment ARDESHGLLENKLLGCDSMRWE GRDYKMALLEQWILGCD-MRWD sR--元 IEDCMV-CNFFR而 Reading This lecture: Mount pp.8-9,65-89,96-115,140-155,161-170
7.91 – Lecture #2 More Pairwise Sequence Comparisons ARDFSHGLLENKLLGCDSMRWE .::. .:::. .:::: :::. GRDYKMALLEQWILGCD-MRWD - and – Multiple Sequence Alignment ARDFSHGLLENKLLGCDSMRWE .::. .:::. .:::: :::. GRDYKMALLEQWILGCD-MRWD .::. ::.: .. :. .::: SRDW--ALIEDCMV-CNFFRWD Reading: This lecture: Mount pp. 8-9, 65-89, 96-115, 140-155, 161-170 Michael Yaffe
Outline Recursion and dynamic programming Applied dynamic programming: global alignments: Needleman-Wunsch Applied dynamic programming: local alignments Smith -Waterman Substitution matrices PAM. blosUM, Gonnet Gaps- linear and affine · Alignment statistics What you need to know to optimize an alignment
Outline • Recursion and dynamic programming • Applied dynamic programming: global alignments: Needleman-Wunsch • Applied dynamic programming: local alignments – Smith-Waterman • Substitution matrices: PAM, BLOSUM, Gonnet • Gaps - linear and affine • Alignment statistics • What you need to know to optimize an alignment
Outline(cont) Multiple sequence alignments: MSA, Clustal Block analysis Position-Specific Scoring Matrices(PSSM)
Outline (cont) • Multiple sequence alignments: MSA, Clustal • Block analysis • Position-Specific Scoring Matrices (PSSM)
Examples o(n)is“ polynomial time” as long as K<3 tractable Consider our un-gapped dot matrix Global alignment 12345678 12345678. 12345678 12345678 12345678 12345678 essentially an o(mn) problem
Examples O(nk) is “polynomial time” as long as K<3 …..tractable Consider our un-gapped dot matrix Global alignment: 1 n 1 12345678…. 12345678…. 12345678…. 12345678…. 12345678…. m 12345678…. ….essentially an O(mn) problem
O.K. Examples o(n)better than o(n log(n)), better than O(n), better than o(n3) Terrible Examples o(kn =exponential time. horrible!!!! NP problems-no known polynomial time Solutions non-deterministic polynomial Problems
O.K. Examples O(n) better than O(n log(n)), better than O(n2), better than O(n3) Terrible Examples O(kn) = exponential time….horrible!!!! NP problems- no known polynomial time Solutions = non-deterministic polynomial Problems