Canal-U

Mon compte

Résultats de recherche

Nombre de programmes trouvés : 307
Label UNT Vidéocours

le (3m30s)

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 ...
Voir la vidéo
Label UNT Vidéocours

le (7m8s)

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 ...
Voir la vidéo
Label UNT Vidéocours

le (5m16s)

5.4. L’algorithme UPGMA

L'algorithme, que nous allons étudier pour la reconstruction d'arbres phylogénétiques à partir des distances, s'appelle UPGMA. Un nom plutôt compliqué pour une méthode qui est plutôt simple. Et même, on le verra trop simple. UPGMA signifie Unweighted Pair Group Method with Arithmetic Mean. Nous allons voir au fur et à mesure, la signification dans l'exécution de l'algorithme de chacun de ces termes. Le point de départ de cet algorithme est donc un tableau de distances, tel que nous avons pu le remplir dans la session précédente. Voilà l'exemple que nous allons traiter. C'est un exemple simple. Nous avons sept espèces ...
Voir la vidéo
Label UNT Vidéocours

le (3m2s)

4.3. Quantifier la similarité de deux séquences

Le principe est donc de rechercher, dans les bases de données, des séquences similaires à celles que nous sommes en train d'étudier. Nous faisons aussi l'hypothèse que plus les séquences sont similaires, meilleure est la pertinence de l'information attachée à la séquence retrouvée dans la base de données. Nous allons donc chercher un moyen de quantifier le niveau de similarité entre 2 séquences. Le premier moyen très simple, c'est d'utiliser la distance dite de Hamming. De quoi s'agit-il ? Très simple, en effet. Prenez ces 2 séquences ici. Vous pouvez très rapidement à l'oeil voir qu'elles diffèrent par 2 substitutions, ...
Voir la vidéo
Label UNT Vidéocours

le (4m40s)

4.7. Coûts et alignement

Nous avons vu l'ébauche de notre algorithme d'alignement optimal en considérant la possibilité de calculer le coût optimal, ou score optimal, de ce dernier noeud. Et nous avons vu que le coût de ce dernier noeud, si les coûts de ces trois noeuds-là étaient connus comme étant optimaux, eh bien le coût optimal de ce noeud était la plus petite de ces trois valeurs-là. C'est-à-dire la plus petite des 3 valeurs des chemins de longueur 1, ou celui-ci, ou celui-là, ou celui-là. Il nous faut maintenant regarder d'un peu plus près ce que sont ces coûts qui figurent sur le ...
Voir la vidéo
Label UNT Vidéocours

le (5m53s)

5.5. Quand les différences sont trompeuses

Il y a plusieurs raisons pour lesquelles la méthode UPGMA, que nous venons de voir, se révèle simpliste. L'une des raisons par exemple, c'est pourquoi quand on recalcule les distances, quand on a groupé deux espèces et construit un nouveau noeud, pourquoi recalcule-t-on les distances sur la base d'une moyenne ? Difficile à justifier d'un point de vue biologique, mais la méthode est simple. Mais peut-être que la critique la plus forte provient du fait que nous nous appuyons sur des distances qui sont calculées sur les séquences, et nous allons voir que ce calcul-là tend à sous-estimer le nombre ...
Voir la vidéo
Label UNT Vidéocours

le (4m10s)

4.4. L’alignement de séquences devient un problème d’optimisation

La distance de Hamming nous donne une première possibilité de mesurer la similarité entre 2 séquences. Mais elle ne reflète pas suffisamment la réalité biologique. Qu'est-ce que j'entends par là ? On a parlé de mutations et nous avons vu qu'il y avait 3 types de mutation : les substitutions et les insertions délétions. Insertion dans une séquence, délétion dans l'autre et vice versa. Il faut tenir compte de cette catégorie de mutation, c'est pourquoi il nous faut changer notre manière effectivement d'évaluer la différence et à l'inverse la similarité entre 2 séquences. Prenons cet exemple de 2 séquences ici ...
Voir la vidéo
Label UNT Vidéocours

le (6m18s)

4.8. Un algorithme récursif

Nous avons désormais en main tous les éléments pour écrire notre algorithme de détermination d'un alignement optimal, ici d'un chemin optimal.Avec les notations que nous avons introduites, je vous rappelle que nous savons, à priori, déterminer le coût de ce noeud-là, autrement dit le coût du chemin aboutissant sur ce noeud, en faisant l'hypothèse que nous connaissons les coûts optimaux de ces trois noeuds-là. Avant de poursuivre, il convient de comprendre que ce schéma de calcul, qu'on utilise pour calculer le coût de ce noeud-là, est aussi utilisable pour calculer le coût de ce noeud-là, à partir des coûts de ...
Voir la vidéo
Label UNT Vidéocours

le (3m12s)

5.2. L’arbre, objet abstrait

Vous l'aurez compris un arbre phylogénétique est un arbre abstrait qui n'a qu'un lointain rapport métaphorique avec un véritable arbre. L'arbre des bio-informaticiens et des informaticiens se dessinent du reste dans l'autre sens. C'est-à-dire que si on retrouve bien effectivement des branches qui connectent des noeuds, on a un noeud qui est la racine et qui est situé tout en haut et on situe en bas généralement par convention, les feuilles qu'on appelle également noeuds terminaux. Pour décrire un arbre, on peut utiliser une expression parenthésée, dont la logique s'impose assez rapidement. Voilà ici l'expression parenthésée correspondant à cette structure ...
Voir la vidéo

 
FMSH
 
Facebook Twitter
Mon Compte