Ressource pédagogique : 4.6. A path is optimal if all its sub-paths are optimal

Informations pratiques sur cette ressource

Description de la ressource pédagogique

Description (résumé)

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 and you say the path oflength L minus one is not optimal. And then, you arrive at a contradiction which means that this is proved. OK. So you can also make the samereasoning with the path of length L minus two, Lminus three and so on. And so, you arrive at the conclusionthat an optimal path is made up of optimal sub-paths. And this will explain how we candesign a schema of computation of the optimal path. The trick in this algorithm is to start with the last unitary path. That is, you remember our grid, thisis the last node of the grid. N and M are the lengths of the sequences. Here is the first sequence.

"Domaine(s)" et indice(s) Dewey

• biologie application informatique (570.285)

Thème(s)