Canal-U

Mon compte

Résultats de recherche

Nombre de programmes trouvés : 307
Label UNT Vidéocours

le (7m7s)

3.7. Index and suffix trees

We have seen with the Boyer-Moore algorithm how we can increase the efficiency of spin searching through the pre-processing of the pattern to be searched. Now we will see that an alternative way of improving the performance is to pre-process the text itself,the searchable text itself and we will, for that, study two methods, the construction of indexes of fixed length words and the algorithm which uses prefix trees. An index of fixed lengthword, what does it mean? Imagine you have a text, a searchable text, that is a text in which you want to search a pattern,here is quite a short text, the sequence is 14 correctors. We will ...
Voir la vidéo
Label UNT Vidéocours

le (6m10s)

3.8. Probabilistic methods

Up to now, to predict our gene,we only rely on the process of searching certain strings or patterns. In order to further improve our gene predictor, the idea is to use, to rely onprobabilistic methods. What does it mean? I will firsttake an example, which is not related to genomic but I think it'sgood to understand the idea. Imagine you have a very long text which is known to be written in some human understandable language but you don't know which one but you know that some passages of this text only are written in a human understandable language,maybe English, maybe French and so on, whatever. You don't know. How ...
Voir la vidéo
Label UNT Vidéocours

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éo
Label UNT Vidéocours

le (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éo
Label UNT Vidéocours

le (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éo
Label UNT Vidéocours

le (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éo
Label UNT Vidéocours

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éo
Label UNT Vidéocours

le (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éo
Label UNT Vidéocours

le (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éo
Label UNT Vidéocours

le (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éo

 
FMSH
 
Facebook Twitter
Mon Compte