[MUSIC] Previously, we discussed how to compare two sequences with each other. This is pairwise alignment. And now, let's discuss how to find multiple sequence alignment. So how to compare multiple sequences at once. Why do we need this? Statistically significant similarities between two sequences becomes more significant if it presents in many other sequences. So if you compare a lot of similar species and you find very conservative domain in this species, it is very significant. While, when you compare these species pairwise, this conservative sequence may be not so obvious. For example, when you align three A-domains, which we discussed previously in this lesson. You can find many pairwise similarities between these three A-domains, but when you're trying to compare all of them at once, you will find that similarity, which present between all of these three sequences, and which can say you something about what makes this sequences behave similarly in a cell. So let's generalize pairwise alignment to multiple alignment. Previously we used two row matrix for alignment of two sequences. Now, when they want to represent alignment of three sequences, let's use three-row matrix. And we will need to design our scoring function to score alignments with more conserved columns higher than other ones. And our pairwise alignment was a path in a two dimensional Manhattan grid. And alignment between three sequences, actually it's a path in three dimensional grid. For example, let's take a look on alignment of ATGC, AATC, and ATGC. Here you can see the number of symbols up to given position written in a separate vector, and for first sequence, it's, it's 0, 1, 1, 2, 3, 4. Then for a second sequence, it's 0 1 2 3 3 4. And 0 0 1 2 3 4 for the last sequence. And we can take columns. The first column of this vector. The second column of this vectors. And so on and so forth as a points in three dimensional space. And our alignment paths will move from 0,0,0 point, which is source in our three dimensional Manhattan grid, to 1,1,0, to 1,2,1, and so on and so forth. And it will finish at the opposite corner of this three dimensional grid as it started, and this opposite corner, we will also call it, is a sim similarly to our two dimensional Manhattan grid. And two dimensional alignment during each step we took maximum of three values, which were vertically, diagonally, and horizontally opposite on this alignment cell. But in multiple dimension space, you will have more neighbors for each cell. For example, for three dimensional alignment cell, you will need to take a maximum of seven values. And here is dynamic programming equations for aligning three sequences. You will need to find a maximum among all seven neighbors plus score of moving from this neighbor to the current node. And how about run time of such algorithm? So for three sequences of length n, run time is proportional to the number of edges in this grid. Similar as before, but the number of edges now is much larger. So it's 7 times n cubed, because each of n cubed node, you'll have seven neighbors to choose from. So ky alignment, where you want to find alignment between k sequences, will build a k dimensional Manhattan graph, with n To the power of k nodes, because it's a k-dimensional cube, or k-dimensional rectangle. And most nodes, except of border ones, will have 2 to the power of k minus 1 incoming edges. So overall run time is proportional to the 2 to the power of k times n to the power of k. And this is really large, so this algorithm will work for a small sequences, small number of sequences, or many sequences of small length. But it won't work in a feasible time for many long sequences. For example, to find a multiple alignment of 18 sequences of lengths 18 each, you will need more time than the age of universe. And biologists usually use fast heuristic algorithms. They, they don't guarantee the find optimal solutions, but they guarantee that this algorithm will finish at a meaningful time. Let's discuss few heuristics which will help us to find multiple alignment in more feasible way. Every multiple alignment in use pairwise alignment, you can take two rows by any way you want, and you will get pairwise alignment of these two sequences, which is induced from this mul, multiple alignment. But can we find multiple alignment from pairwise alignments? In generally, no, because given a set of arbitrary pairwise alignments, we cannot construct multiple alignment that induces them. For example if we have sequences AAATTT, TTTGGG, and GGGAAA, we have this three pairwise alignments, which have, four matches each, but we cannot construct multiple alignment of this three sequences which will induce all these three pairwise alignment. But what can we do? Let's consider profile representation of multiple alignment. We had profiles before in this course. And profile is usually a probability for each letter to occur in each column. So for these sequences, you can see that first column contains 0 A's, 1 T, 3 C, and 1 gap. And probabilities of C is 0.6. Probability of T and the gap is 0.2. So how can we align sequence against sequence? You already know this. This is what Pavel told before in this lecture. But can we align sequence against profile? Or can we align profile against profile? yes, actually, we can. So aligning sequence against sequence requires you to build this Manhattan graph and write down one sequence horizontally, and one sequence vertically, but you can replace the sequence with a profile and you can use values proportional to the values in the profile to score each edge in a graph. Also, you can use profile as a second sequence. And you can align these two profiles in a very similar way that you aligned two sequences with each other. But for scoring function, you need to also consider probabilities, to have a certain letter in certain sequence at certain place. So how we can use this fact to find multiple alignment. We can construct simple greedy algorithm. We will calculate all pairwise alignments between all sequences. For example, we have k sequences, as a start, we will calculate all pairwise alignments of these k sequences, which is quadratic number of, which is proportional to the quadratic number of these sequences, and we will find two closest sequences among all of them. And we will join these two sequences into our file. After this step, we will have k minus 1 sequences. Well, actually we will have k minus two sequences in one profile, but we know that we can align profile in the same way as we align sequences. And we will iterate, so on each iteration will reduce number of sequences and profiles to align between each other by one. For example, let's take these four sequences, GATTCA, GTCTGA, GATATT, and GTCAGC. We'll find six pairwise alignments to the sequences and the best one is alignment between second and fourth sequences and it has score two. So we will join this two sequences into one profile and it will add to our pool of sequences we will want to align. And now, we have new set of three sequences to align, sequence one, which is originally sequence one, sequence three, and new profile. And we can iterate. We can construct pairwise alignments between each of these three sequences, and find closest and join them and so on and so forth, and at the last step, we will get to a single profile of multiple alignment. This greedy algorithm is not optimal. It may find not optimal solution, but it will work fast. And it will work on most of the real world cases. So today we learned a lot about sequence alignment. We learned how to find pairwise alignment in quadratic time and linear space. We learned how to use a find get analysis, which represent real world better for biological problems. We learned how to find global and local alignments. We learned how to find multiple alignment between many sequences at once. But can you find all similarities between human, mouse, and rat genomes, given that these genomes contain billions of nucleotides? Can you rapidly find alignments between human genome and millions of short reads? Which usually obtain by sequences as genome. And are alignment algorithms with quadratic time practical when we analyze entire genomes? Because as I said mammal genomes are really large. And when you try to analyze these genomes, quadratic time usually not works. And these questions we will discuss in future chapters.
