[SOUND] So now we will discuss how to penalize insertions and deletions in sequence alignment in a more sophisticated way. Previously, we used naive scoring for indels, where we assigned fixed penalty sigma to each indel. However, this fixed penalty isn't good to represent series of hundreds of consecutive indels. And we will call this sequence of k consecutive indels as single evolutionary event gap rather than many evolutionary events of small insertions and deletions. To model this situation in sequence alignment algorithms, we'll use a find gap penalty, where we use two constants. One is sigma, which is a gap opening penalty, and the second one is epsilon, what, which is gap extension penalty. And usually sigma is more than epsilon. Since starting a gap should be penalized more than extending it, and the formula to calculate penalty for a gap of length k will be sigma plus epsilon times k minus 1. So let's take a look now how we can use this in our Manhattan grid. Previously we had a single edges with weight sigma to represent insertions and deletions, and these edges were horizontal and vertical edges in our Manhattan grid. Now, we can add more edges. For example, we can add an edge of a weight sigma plus epsilon, which will represent a gap, a single gap of length two. And for our Manhattan grid we actually need to add a lot of these edges. So we need to add a separate edge for all gaps of length two. Edges for all gaps of lengths 3 and more and more, and we will need to add it vertical and horizontally. How many edges have we added to our graph? Actually, we added edges proportionally to n cube, where n is a length of sequences which we are trying to compare. Since sequence alignment algorithms' run time is proportional to the number of edges, our algorithm will be quite slow. It will run proportionally to the n cube. How we can improve this running time of algorithm? We can split our Manhattan grid into three levels. Bottom level, middle level, and upper level. Bottom level will represent insertions, and will contain only edges, which goes vertically from node to node. Middle level will represent matches and mismatches, and will contain diagonal edges. Upper level will represent additions, and will contain only horizontal edges of our graph. And still, we need to find a path between top left corner to the bottom right corner. And we can move in our Manhattan grid, but we also can move between these layers of the grid. So for example, we can take one edge diagonally, and now if we want to make insertion, we need to move to the bottom level, take one edge there, and move back to the middle level. And these two edges will represent a single gap, where the sigma is a gap opening penalty and epsilon is a gap extension penalty. After that, we can continue moving on the middle level, for example, we found a match between our sequences. And then, if you want to represent deletion, we need to move to upper level, make some movements there, and go back to the middle level. And we can finish our path. To model this mathematically, we can have three different equations for dynamic programming for each level. And lower level will use information from lower level itself, and the middle level, middle level will use information from all three levels, and upper level will use information from upper level itself and the middle level. How many edges does this three level Manhattan grid have? Hint, is a degree of which node is quite small. So each node in this three layered Manhattan will have only one, two, or three neighbors. And the number of edges is proportional to the n square, so the run time of this algorithm will be the same as before. But currently we can use more sophisticated affine gap penalty than the native penalty which we used before.