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/pnsj-q734
Citer cette ressource :
François Rechenmann. Inria. (2015, 5 février). 4.8. A recursive algorithm , in 4. Sequences comparison. [Vidéo]. Canal-U. https://doi.org/10.60527/pnsj-q734. (Consultée le 13 juillet 2024)

# 4.8. A recursive algorithm

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

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 atthe position of the first sequence. The interesting point here is tounderstand that this scheme can also be applied for that node. If you make the hypothesis, you know the costs at that node, at that node and that node, then using the same schema you can compute the cost at that node. The same cost which will be used to compute the cost at the ending node. So this is the scheme at the basis of our recursive function. What is a recursive function? A recursive function is something which may appear a bit magic the first time because it's a function which is called within its own execution. You call the function, it begins the execution and at one or several points the function is called again, that's why it's called recursive.

Intervention
Thème
Documentation

## Dans la même collection

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

### 4.6. A path is optimal if all its sub-paths are optimal

Rechenmann
François

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

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

### 4.4. Aligning sequences is an optimization problem

Rechenmann
François

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

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

### 4.5. A sequence alignment as a path

Rechenmann
François

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

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

## 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: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: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:04:22

### 4.4. Aligning sequences is an optimization problem

Rechenmann
François

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

• 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:05:13

### 3.2. A simple algorithm for gene prediction

Rechenmann
François

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

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