ELE 4120 Bioinformatics Tutorial 1

ELE 4120 BioinformaticsTutorial 4 Content• Dynamic Programming– Global Alignment (Needleman and WunschAlgorithm)– Semiglobal Alignment– Local Alignment (Smith-Waterman Algorithm)Sequence Alignment• When the scoring method is defined, the best alignment can be found1. Exhaustive search – calculate the score of all possible alignments. This method is not feasible for modest length sequence, because there are huge number of possibilities.2. Dynamic Programming - an optimization method that can be applied to sequence alignment problem Dynamic Programming (1)• For example, we want to align the following 2 sequences: A C T CA T C• There are 3 possibilities for the first position in the alignment– 1. Add gap in the 1st sequence– 2. Add gap in the 2nd sequence– 3. not place gap in both sequences1st position Score Remaining Sequence---1 ACTCATCA-1 CTC--ATCA1 CTCATCDynamic Programming (2)• If we know the best 1st Score Remaining Sequencealignment of the remaining positionsequences, we can know ---1 ACTCthe best alignmentATC• Therefore, the problem A-1 CTCbecomes:--ATCA1 CTCAWhat is the best TCalignment of these sequences?Dynamic programming compute the optimal alignment by filling in a table of partial sequence alignment score in order to avoid recomputing. Global Alignment (1)• Example: Compute the best alignment for the following two sequences: (match score = 1, mismatch score = 0, gap penalty = -1)A C A C TA ...