Vidéo pédagogique
Notice
Lieu de réalisation
Grenoble
Sous-titrage
Sous-titre
Langue :
Anglais
Crédits
François Rechenmann (Intervention)
Conditions d'utilisation
Ces ressources de cours sont, sauf mention contraire, diffusées sous Licence Creative Commons. L’utilisateur doit mentionner le nom de l’auteur, il peut exploiter l’œuvre sauf dans un contexte commercial et il ne peut apporter de modifications à l’œuvre originale.
DOI : 10.60527/b733-qa95
Citer cette ressource :
François Rechenmann. Inria. (2015, 5 février). 3.2. A simple algorithm for gene prediction , in 3. Gene prediction. [Vidéo]. Canal-U. https://doi.org/10.60527/b733-qa95. (Consultée le 20 juillet 2024)

# 3.2. A simple algorithm for gene prediction

Réalisation : 5 février 2015 - Mise en ligne : 9 mai 2017
• document 1 document 2 document 3
• niveau 1 niveau 2 niveau 3
Descriptif

Based on the principle we statedin the last session, we will now write in pseudo code a firstalgorithm for locating genes on a bacterial genome. Remember first how this algorithm should work, we first need to find two consecutive stop triplets in the same phase, same phase meansthe number of letters between these two stop triplets might bea multiple of three so that this sequence here can be divided into triplets. This is called an open reading frame. Once we have an open reading framewe look for the start triplet which is situated leftmost onthe open reading frame and we declare, we make the hypothesis that thisis a coding region, that is a gene. OK. Let's see that in more details. So our algorithms start withthe declaration of variable we need, some counter indexes here integer and here I have an array of integer with two columns and as many rows as necessary. A row will allow to record the beginning of the gene as a position in the sequence and the end ofthe gene as another position in the sequence normally, this number mustof course be greater than this one. They are integers because theyare positioned in the sequence. We initialized some index andthen what do we have to do?

Intervention
Thème
Documentation

## Dans la même collection

• Vidéo pédagogique
00:06:09

### 3.8. Probabilistic methods

Rechenmann
François

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

• Vidéo pédagogique
00:04:45

### 3.3. Searching for start and stop codons

Rechenmann
François

We have written an algorithm for finding genes. But you remember that we arestill to write the two functions for finding the next stop codonand the next start codon. Let's see how we can do that. We

• Vidéo pédagogique
00:05:58

### 3.6. Boyer-Moore algorithm

Rechenmann
François

We have seen how we can make gene predictions more reliable through searching for all the patterns,all the occurrences of patterns. We have seen, for example, howif we locate the RBS, Ribosome

• Vidéo pédagogique
00:05:35

### 3.9. Benchmarking the prediction methods

Rechenmann
François

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

• Vidéo pédagogique
00:06:22

### 3.4. Predicting all the genes in a sequence

Rechenmann
François

We have written an algorithm whichis able to locate potential genes on a sequence but only on one phase because we are looking triplets after triplets. Now remember that the genes maybe located on

• Vidéo pédagogique
00:07:06

### 3.7. Index and suffix trees

Rechenmann
François

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

• Vidéo pédagogique
00:05:41

### 3.1. All genes end on a stop codon

Rechenmann
François

Last week we studied genes and proteins and so how genes, portions of DNA, are translated into proteins. We also saw the very fast evolutionof the sequencing technology which allows for producing

• Vidéo pédagogique
00:08:56

### 3.10. Gene prediction in eukaryotic genomes

Rechenmann
François

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

• Vidéo pédagogique
00:04:45

### 3.5. Making the predictions more reliable

Rechenmann
François

We have got a bacterial gene predictor but the way this predictor works is rather crude and if we want to have more reliable results, we have to inject into this algorithmmore biological knowledge. We

## Avec les mêmes intervenants et intervenantes

• Vidéo pédagogique
00:05:48

### 1.4. What is an algorithm?

Rechenmann
François

We have seen that a genomic textcan be indeed a very long sequence of characters. And to interpret this sequence of characters, we will need to use computers. Using computers means writing program.

• Vidéo pédagogique
00:04:58

### 2.2. Genes: from Mendel to molecular biology

Rechenmann
François

The notion of gene emerged withthe works of Gregor Mendel. Mendel studied the inheritance on some traits like the shape of pea plant seeds,through generations. He stated the famous laws of inheritance

• Vidéo pédagogique
00:05:37

### 2.10. How to find genes?

Rechenmann
François

Getting the sequence of the genome is only the beginning, as I explained, once you have the sequence what you want to do is to locate the gene, to predict the function of the gene and maybe study the

• Vidéo pédagogique
00:05:35

### 3.9. Benchmarking the prediction methods

Rechenmann
François

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

• Vidéo pédagogique
00:04:29

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

Rechenmann
François

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

• Vidéo pédagogique
00:04:59

### 5.4. The UPGMA algorithm

Rechenmann
François

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

• Vidéo pédagogique
00:06:06

### 1.7. DNA walk

Rechenmann
François

We will now design a more graphical algorithm which is called "the DNA walk". We shall see what does it mean "DNA walk". Walk on to DNA. Something like that, yes. But first, just have a look again at

• Vidéo pédagogique
00:05:47

### 2.6. Algorithms + data structures = programs

Rechenmann
François

By writing the Lookup GeneticCode Function, we completed our translation algorithm. So we may ask the question about the algorithm, does it terminate? Andthe answer is yes, obviously. Is it pertinent,

• Vidéo pédagogique
00:06:22

### 3.4. Predicting all the genes in a sequence

Rechenmann
François

We have written an algorithm whichis able to locate potential genes on a sequence but only on one phase because we are looking triplets after triplets. Now remember that the genes maybe located on

• Vidéo pédagogique
00:06:38

### 4.7. Alignment costs

Rechenmann
François

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

• Vidéo pédagogique
00:06:58

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

Rechenmann
François

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

• Vidéo pédagogique
00:04:52

### 1.2. At the heart of the cell: the DNA macromolecule

Rechenmann
François

During the last session, we saw how at the heart of the cell there's DNA in the nucleus, sometimes of cells, or directly in the cytoplasm of the bacteria. The DNA is what we call a macromolecule, that