Canal-U

Mon compte
Inria

4.10. Cet algorithme est-il efficace ?


Copier le code pour partager la vidéo :
<div style="position:relative;padding-bottom:56.25%;padding-top:10px;height:0;overflow:hidden;"><iframe src="https://www.canal-u.tv/video/inria/embed.1/4_10_cet_algorithme_est_il_efficace.24660?width=100%&amp;height=100%" style="position:absolute;top:0;left:0;width:100%;height: 100%;" width="550" height="306" frameborder="0" allowfullscreen scrolling="no"></iframe></div> Si vous souhaitez partager une séquence, indiquez le début de celle-ci , et copiez le code : h m s
Auteur(s) :
RECHENMANN Francois
PARMENTELAT Thierry

Producteur Canal-U :
Inria
Contacter la chaine
J’aime
Imprimer
partager facebook twitter

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...

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

commentaires


Ajouter un commentaire Lire les commentaires
*Les champs suivis d’un astérisque sont obligatoires.
Aucun commentaire sur cette vidéo pour le moment (les commentaires font l’objet d’une modération)
 

Dans la même collection

FMSH
 
Facebook Twitter
Mon Compte