le (4m55s)

# Résultats de recherche

**536**

le (6m39s)

## 4.7. Alignment costs

We have seen how we can compute the cost of the path ending on the last node of our grid if we know the cost of the sub-path ending on the three adjacent nodes. It is time now to see more deeply why these costs are used to compute the cost in the last node. So again, we saw how we can compute the cost here of the path ending on that node if we know the cost of the sub-path ending on these three red nodes. Indeed, if we come from that node, the cost on that node will be the cost of that node plus the ... Voir la vidéole (4m12s)

## 4.6. A path is optimal if all its sub-paths are optimal

A sequence alignment between two sequences is a path in a grid. So that, an optimal sequence alignmentis an optimal path in the same grid. We'll see now that a property of this optimal path provides us with scanned lines for designing an optimization algorithm. The property is the following. A path which is optimal is made up of optimal sub-paths. To prove that, we can start byproving that if a path of length L is optimal then the path of length L minus one is also optimal. This can be proved quiteeasily ad arburdum. That is, you take the hypothesis that the path of length L is optimal ... Voir la vidéole (3m51s)

## 4.5. A sequence alignment as a path

Comparing two sequences and thenmeasuring their similarities is an optimization problem. Why? Because we have seen thatwe have to take into account substitution and deletion. During the alignment, the comparison of the two sequences, we haveto insert blank characters at a certain position in order tohave an optimal score that is we want the sequence to be themore similar as possible. So the problem is to find whereto locate the blank character. There are many solutions and wewant to find the best one, it is an optimization problem. How do we deal with thisoptimization problem? We will consider an alignmentbetween two sequences as a path in that kind of grid. Here ... Voir la vidéole (4m23s)

## 4.4. Aligning sequences is an optimization problem

We have seen a nice and a quitesimple solution for measuring the similarity between two sequences. It relied on the so-called hammingdistance that is counting the number of differencesbetween two sequences. But the real situation is a bitmore complex as we'll see now, it needs an adequatesolution and algorithm. Why is it a bit more complex? Let's have a look at thispair of two sequences. If we apply the hamming distance,compute the hamming between these two sequences,we find ten differences. OK. But you must remember thatmutation may be substitution, deletion and insertion. So if wetake into account the deletion and insertion, the situation isvery different in the case of these two sequences. ... Voir la vidéole (4m0s)

## 4.3. Measuring sequence similarity

So we understand why gene orprotein sequences may be similar. It's because they evolve togetherwith the species and they evolve in time, there aremodifications in the sequence and that the sequence may still besimilar, similar enough again to retrieve information on onesequence to transfer it to another sequence of interest. So thequestion now is how can we measure this similarity between twosequences for the moment. The first approach to similarityis a very simple one is to apply a distance which is calledhere the Editing System or the Hamming Distance.The idea is very basic. You would take two sequences likethese two sequences here and you look at the differences and youcount ... Voir la vidéole (4m30s)

## 4.2. Why gene/protein sequences may be similar?

Before measuring the similaritybetween the sequences, it's interesting to answer the question: why gene or protein sequences may be similar? It is indeed veryinteresting because the answer is related to the theory ofevolution which is due, as you all know, to Darwin. What Darwinsays is that species evolve in time and there is a creation ofnew species for existing ones. So there is an evolutionof species over time. He was a very thinking man, huh. This evolution can be also seenon the genomic sequences. Let's see this very small and partialtree of life and hypothetical tree of life. Here you have thespecies and you have this phenomenon of speciation giving ... Voir la vidéole (7m42s)

## 4.8. A recursive algorithm

We have seen how we can computethe optimal cost, the ending node of our grid if we know the optimal cost of the three adjacent nodes. This is this computation scheme we can see here using the notation of the pseudo code and not the mathematical notation we used in the previous sessions. So again we can compute the cost of this node if we know the cost of that node, that node and that node and we have to add respectively the insertion cost, the substitution cost orthe insertion cost. The substitution cost here depends on the letter at this position in the sequence and this letter ... Voir la vidéole (9m27s)

## 4.10. How efficient is this algorithm?

We have seen the principle of an iterative algorithm in two paths for aligning and comparing two sequences of characters, here DNA sequences. And we understoodwhy the iterative version is much more efficient than the recursive version. But, how efficient is reallythis iterative algorithm? You remember that in order to measure the efficiency of algorithms, the computer scientists do not use any mean of measuring the time or any other thing. They evaluate the number of timethe main operation inside the algorithm is executed. In the caseof this Needleman and Wunsch algorithm which has been published 40 years ago, the operation which is critical is the comparisonbetween two letters of ... Voir la vidéole (6m59s)