le (4m46s)

# Résultats de recherche

**745**

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éole (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éole (5m36s)

## 3.9. Benchmarking the prediction methods

It is necessary to underline that gene predictors produce predictions. Predictions mean that you have no guarantees that the coding sequences, the coding regions,the genes you get when applying your algorithm, are true genes, thatis genes which have a biological existence. Only experimental analysiscan confirm or infirm your predictions. Nevertheless it is interesting and also important to be able to evaluate your algorithm, thisis the role of benchmarking. Benchmarking means measuring the capacity of your algorithm to produce good predictions. How can we make thiskind of measurement? We need a reference, an idealreference would be a genome which is well annotated and for whichall of the annotations have been confirmed through ... Voir la vidéole (8m57s)

## 3.10. Gene prediction in eukaryotic genomes

If it is possible to have verygood predictions for bacterial genes, it's certainly not the caseyet for eukaryotic genomes. Eukaryotic cells have manydifferences in comparison to prokaryotic cells. You rememberthe existence of a nucleus and you also remember on one ofthe schemes in the first week that there are more structureswithin a eukaryotic cell. But the differences lie also inthe organization of the genomes. In eukaryotic genomes, the so-calledintergenic regions are very long. Intergenic regions are theregions which separate genes. A bacterial genome is very denseindeed, if you put your fingers somewhere on the genome, if itwas possible of course, it would be on the gene. If you do the ... Voir la vidéole (4m55s)

## 4.1. How to predict gene/protein functions?

Last week we have seen that annotating a genome means first locating the genes on the DNA sequences that is the genes, the region coding for proteins. But this is indeed the first step,the next very important step is to be able to predict thefunctions of the genes. That is more correctly, the function of the protein coded by the genes. How can we predict thisgene or function protein? It is essentially based on thefact that we will retrieve genes or protein for which the sequenceis similar and for which we know the function. So we will seehow we can measure and compute the similarity between DNA or protein ... Voir la vidéole (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)