le (4m23s)

# Résultats de recherche

**304**

le (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 (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)

## 4.9. Recursion can be avoided: an iterative version

We have written a recursive function to compute the optimal path that is an optimal alignment between two sequences. Here all the examples I gave were onDNA sequences, four letter alphabet. OK. The writing of this recursive function is very elegant but unfortunately we will see now that it isnot very efficient in execution time. Let's see why. Remember the computing schema weapply during the recursion, for example here, to compute the cost of this node, we saw that it was required to computerecursively the cost of that node, that node and that node. OK but to compute the cost of that node here, you need to compute the cost ... Voir la vidéole (7m40s)

## 5.5. Differences are not always what they look like

The algorithm we have presented works on an array of distance between sequences. These distances are evaluated on the basis of differences between the sequences. The problem is that behind the differences we observed on the set of sequences, there may beother mutations which cannot be observed and we should modify the distances. We will have a look at some simple cases of these observed differences which may correspond to hidden differences and then we will see how the evaluation, computationof the number of differences may be affected. The simple case is this one, aunique substitution between, in the sequence One we have a Cand it turns out that in ... Voir la vidéole (4m46s)

## 5.2. The tree, an abstract object

When we speak of trees, of species,of phylogenetic trees, of course, it's a metaphoric view of a real tree. Our trees are abstract objects. Here is a tree and the different components of this tree. Here is what we call an edge or a branch. We have nodes, a particular nodeis the root and other nodes are the leaves here terminal nodesand we see that when we draw a tree as an abstract object, we put the root upside and the leaves downside so it's the reverse of a classical natural tree. We need an expression to describe a tree and we will use this kind of expression, how ... Voir la vidéole (4m50s)

## 5.3. Building an array of distances

So using the sequences of homologous gene between several species, our aim is to reconstruct phylogenetic tree of the corresponding species. For this, we have to comparesequences and compute distances between these sequences and we have seen last week how we were able to measure the similarity between sequences and we can use this similarity as a measureof distance between sequences. So we will compare pairs of sequences, measure the similarity and store the value of distance, of similarity into what we could call a matrix or an array. Before going further, let's makemore explicit the use of these two terms, they are not equivalentbut some people mix them. The ... Voir la vidéole (5m0s)

## 5.4. The UPGMA algorithm

We know how to fill an array with the values of the distances between sequences, pairs of sequences which are available in the file. This array of distances will be the input of our algorithm for reconstructing phylogenetic trees. The name of this algorithm israther complicated but the method itself is rather simple,too simple indeed. We will see that. The name standsfor Unweighted Pair Group Method with Arithmetic Mean, wewill understand these terms along the presentationof the algorithm. The algorithm starts withan array of distances. Let's take this very simpleexample, it implies seven species and here we have the values of thedistances between these different sequences associated with a species. As you ... Voir la vidéole (7m26s)