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/2ev9-7932
Citer cette ressource :
François Rechenmann. Inria. (2015, 5 février). 4.7. Alignment costs , in 4. Sequences comparison. [Vidéo]. Canal-U. https://doi.org/10.60527/2ev9-7932. (Consultée le 20 juillet 2024)

# 4.7. Alignment costs

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 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 cost of the gap that is an insertion cost. If we come from that node, the situation is similar, the cost of that node will be the cost of thatone plus the same insertion cost. If we come from that node, thecost here will be the sum of the cost of that node plus the code of the substitution of the letter N of the sequence by letter M of the second sequence. And this cost is known withinthe substitution matrix, here, which tells for each pair of characters, here in the four letter alphabet, the cost of substituting oneletter, one nucleotide by another one. So, now since we want to havehere the minimal cost what we do is we take, we return as the value of the cost here the minimum of these three expressions.

Intervention
Thème
Documentation

## Dans la même collection

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

### 4.8. A recursive algorithm

Rechenmann
François

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

• 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

• 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

## Avec les mêmes intervenants et intervenantes

• 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

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

### 1.1. The cell, atom of the living world

Rechenmann
François

Welcome to this introduction to bioinformatics. We will speak of genomes and algorithms. More specifically, we will see how genetic information can be analysed by algorithms. In these five weeks to

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

### 1.9. Predicting the origin of DNA replication?

Rechenmann
François

We have seen a nice algorithm to draw, let's say, a DNA sequence. We will see that first, we have to correct a little bit this algorithm. And then we will see how such as imple algorithm can provide

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

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

### 5.5. Differences are not always what they look like

Rechenmann
François

The algorithm we have presented works on an array of distance between sequences. These distances are evaluated on the basis of differences between the sequences. The problem is that behind the