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/gxjh-tq78
Citer cette ressource :
François Rechenmann. Inria. (2015, 5 février). 2.6. Algorithms + data structures = programs , in 2. Genes and proteins. [Vidéo]. Canal-U. https://doi.org/10.60527/gxjh-tq78. (Consultée le 13 juillet 2024)

# 2.6. Algorithms + data structures = programs

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

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, that is, doesit return the expected answer? The answer is yes, if you giveas an input a sequence of DNA, you will get as an output asequence of amino acids unless, of course, one of the tripletsis not one of the 64 expected triplets and then you will get, ofcourse, a nonsense protein sequence. Is it efficient? Well, for measuring the efficiency of an algorithm, you can ask the question, how manybasic operations you have to execute. In that case the critical operationis comparison of letters. In the best case if you are lucky,the algorithm for looking up a triplet needs three comparisons,if you're not lucky, in the worst case, it needs 64 comparisons. These are not high numbers, ofcourse, but you have to remember that you have to execute the Lookup Algorithm for every triplet of the sequence so a sequencemay be very very long so it may be a good idea to ask the question: can we do better? And the answer is yes. For doing better, what we can introduce is a data structure. Here is the data structure inthe left part of this slide.

Intervention
Thème
Documentation

## Dans la même collection

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

### 2.7. The algorithm design trade-off

Rechenmann
François

We saw how to increase the efficiencyof our algorithm through the introduction of a data structure. Now let's see if we can do even better. We had a table of index and weexplain how the use of these

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

### 2.1. The sequence as a model of DNA

Rechenmann
François

Welcome back to our course on genomes and algorithms that is a computer analysis ofgenetic information. Last week we introduced the very basic concept in biology that is cell, DNA, genome, genes

• 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:06:09

### 2.4. A translation algorithm

Rechenmann
François

We have seen that the genetic codeis a correspondence between the DNA or RNA sequences and aminoacid sequences that is proteins. Our aim here is to design atranslation algorithm, we make the

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

### 2.8. DNA sequencing

Rechenmann
François

During the last session, I explained several times how it was important to increase the efficiency of sequences processing algorithm because sequences arevery long and there are large volumes of

• 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:50

### 2.5. Implementing the genetic code

Rechenmann
François

Remember we were designing our translation algorithm and since we are a bit lazy, we decided to make the hypothesis that there was the adequate function forimplementing the genetic code. It's now time

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

### 2.9. Whole genome sequencing

Rechenmann
François

Sequencing is anexponential technology. The progresses in this technologyallow now to a sequence whole genome, complete genome. What does it mean? Well let'stake two examples: some twenty years ago,

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

### 2.3. The genetic code

Rechenmann
François

Genes code for proteins. What is the correspondence betweenthe genes, DNA sequences, and the structure of proteins? The correspondence isthe genetic code. Proteins have indeedsequences of amino acids.

## Avec les mêmes intervenants et intervenantes

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

### 1.3. DNA codes for genetic information

Rechenmann
François

Remember at the heart of any cell,there is this very long molecule which is called a macromolecule for this reason, which is the DNA molecule. Now we will see that DNA molecules support what is called

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

### 2.1. The sequence as a model of DNA

Rechenmann
François

Welcome back to our course on genomes and algorithms that is a computer analysis ofgenetic information. Last week we introduced the very basic concept in biology that is cell, DNA, genome, genes

• 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: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:03:59

### 4.3. Measuring sequence similarity

Rechenmann
François

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

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

### 5.3. Building an array of distances

Rechenmann
François

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

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

### 1.6. GC and AT contents of DNA sequence

Rechenmann
François

We have designed our first algorithmfor counting nucleotides. Remember, what we have writtenin pseudo code is first declaration of variables. We have several integer variables that are variables which

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

### 2.5. Implementing the genetic code

Rechenmann
François

Remember we were designing our translation algorithm and since we are a bit lazy, we decided to make the hypothesis that there was the adequate function forimplementing the genetic code. It's now time

• 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:04:54

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

Rechenmann
François

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

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

### 4.10. How efficient is this algorithm?

Rechenmann
François

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

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

### 5.7. The application domains in microbiology

Rechenmann
François

Bioinformatics relies on many domains of mathematics and computer science. Of course, algorithms themselves on character strings are important in bioinformatics, we have seen them. Algorithms and