Canal-U

Mon compte
Inria

4.9. Recursion can be avoided: an iterative version


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_9_recursion_can_be_avoided_an_iterative_version.35255?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

Producteur Canal-U :
Inria
Contacter le contributeur
J’aime
Imprimer
partager facebook twitter Google +

4.9. Recursion can be avoided: an iterative version

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 writing of this recursive function is very elegant but unfortunately we will see now that it isnot very efficient in execution time. Let's see why. Remember the computing schema weapply during the recursion, for example here, to compute the cost of this node, we saw that it was required to computerecursively the cost of that node, that node and that node. OK but to compute the cost of that node here, you need to compute the cost of that one, that oneand that one again that is this cost which was computed in order to compute the code of the ending node here has to be recomputed in the recursive function to compute the cost of that node. In a more general way, to computethe cost of a node like this one, you need to compute all of these nodes here but to compute the cost of that node, you need to compute all the costs of these nodes again and again and again. So the cost of one node in thiswriting of the function is computed many, many, many times. It's because we use this recursive function so it was nice but it was expensive in terms of execution time. So we can imagine a new version of the algorithm which is not recursive but iterative in two phases. Let's see how it works.

  •  
    Label UNT : UNIT
  •  
    Date de réalisation : 5 Février 2015
    Lieu de réalisation : Grenoble
    Durée du programme : 7 min
    Classification Dewey : biologie application informatique
  •  
    Catégorie : Vidéocours
    Niveau : 1er cycle, 2ieme cycle
    Disciplines : Biologie cellulaire, Informatique, Informatique, Mathématiques et informatique
    Collections : 4. Sequences comparison
    ficheLom : Voir la fiche LOM
  •  
    Auteur(s) : RECHENMANN Francois
  •  
    Langue : Anglais
    Mots-clés : DNA, Genome, algorithm, cell, bioinformatics
    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.
 

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 Google+
Mon Compte