-
- Label UNT : UNIT
-
- Date de réalisation : 1 Juin 2015
- Durée du programme : 8 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és 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.
Dans la même collection















4.10. Cet algorithme est-il efficace ?
La version itérative de notre algorithme d'alignement optimal de séquences est indéniablement beaucoup plus efficace que sa version récursive, puisque nous avons vu qu'il permettait d'éviter que le coût d'un même nœud soit réévalué plusieurs fois.
Mais qu'en est-il véritablement de l'efficacité de cet algorithme ? Eh bien encore une fois, pour mesurer les performances en temps d'un algorithme, les informaticiens ne font pas de chronométrage, ils calculent le nombre d'opérations qui doivent être effectuées pour que l'algorithme aboutisse à son résultat.
Ici dans le cadre de cet algorithme de Needleman et Wunsch qu'ils ont proposé en 1970, on voit vite que le nombre d'opérations à exécuter - comparaisons et calculs qui vont autour - est de l'ordre de N fois M où N est la longueur de la première séquence et M la longueur de la seconde. On dira que la complexité algorithmique est quadratique, on oublie la différence entre N et M et on dit tout simplement que quoi ? La complexité est quadratique de l'ordre de N au carré où N est la longueur des séquences, peu importe qu'elle soit la même ou différente...
commentaires
Ajouter un commentaire Lire les commentaires