-
- Label UNT : UNIT
-
- Date de réalisation : 1 Juin 2015
- Durée du programme : 4 min
- Classification Dewey : biologie application informatique
-
- Catégorie : Vidéocours
- Niveau : Tous publics / hors niveau, 1er cycle, L1
- Disciplines : Outils, méthode et techniques scientifiques, Informatique
- Collections : 4. Comparaison de séquences
- ficheLom : Voir la fiche LOM
-
- Auteur(s) : RECHENMANN Francois, PARMENTELAT Thierry
-
- Langue : Français
- Mots-clés : génomique, algorithmique, bioinformatique, biologie cellulaire et moléculaire, modélisation
- Conditions d’utilisation / Copyright : 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.
4.6. Si un chemin est optimal, tous ses chemins partiels sont optimaux
Copier le code pour partager la vidéo :
4.10. Cet algorithme est-il efficace ?
4.9. Éviter la récursivité : une version itérative
4.8. Un algorithme récursif
4.7. Coûts et alignement
4.5. Un alignement de séquences vu comme un chemin dans une grille
4.4. L’alignement de séquences devient un problème ...
4.3. Quantifier la similarité de deux séquences
4.2. Évolution et similarité de séquences
4.1. Comment prédire les fonctions des gènes/protéines ?
4.6. Si un chemin est optimal, tous ses chemins partiels sont optimaux
Nous cherchons à concevoir un algorithme capable de déterminer l'alignement optimal de 2 séquences. Et nous avons vu que ça revient à chercher un algorithme qui recherche un chemin optimal dans une grille. Chemin optimal, c'est-à-dire de coût de score minimal.
Pour bâtir cet algorithme, nous allons nous appuyer sur une propriété de ce chemin optimal qui est la suivante : si un chemin de longueur l est optimal, alors le chemin de longueur l-1 l'est aussi. Comment prouver cette propriété ? Très simplement en fait par l'absurde. C'est-à-dire qu'on va faire l'hypothèse contraire. C'est-à-dire que si le chemin de longueur L est optimal, il se peut que le chemin de longueur L-1, qu'il existe un chemin de longueur L-1 qui ne le soit pas. Et on arrivera à une contradiction. Ce qui va montrer par l'absurde, la véracité de cette affirmation-là. On voit également qu’un chemin de longueur L-1 correspond sur l'alignement à un alignement de longueur L-1 également. Correspondance, on l'avait vu, entre alignement et chemin...
commentaires
Ajouter un commentaire Lire les commentaires