Canal-U

Mon compte

Résultats de recherche

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

le (4m28s)

2.7. Les compromis de la conception d’algorithmes

La mise en oeuvre d'une structure de données appropriée permet, nous l'avons vu, d'améliorer les performances d'algorithmes. Nous en avons vu l'exemple sur la recherche d'un triplet dans un tableau de code génétique, quand nous avons ajouté ces tables d'index, nous avons vu que nous avons diminué de façon tout à fait significative, le nombre de comparaisons à effectuer. Je vous propose maintenant une autre approche où les index ne sont pas sous forme de table mais sont calculés. Il faut que vous vous souveniez de la manière dont le tableau est organisé. D'abord tous les triplets qui commencent par ...
Voir la vidéo
Label UNT Vidéocours

le (6m51s)

2.8. Les technologies de séquençage de l’ADN

Nous parlons beaucoup dans ce cours de séquences génomiques ou séquences d'ADN, que nous voyons pour des raisons algorithmiques sous forme de chaînes de caractères. Comment ces séquences, ces chaînes de caractères, sont-elles obtenues ? D'une manière très imagée, il s'agit de lire la succession des nucléotides le long d'un brin d'ADN. Je dis imagé parce que cette lecture n'est pas une opération extrêmement simple. Le résultat de cette opération, qu'on appelle séquençage, c'est le texte dans cet alphabet de 4 lettres. Les appareils qui servent à mener cette opération de séquençage sont appelés séquenceurs. Les technologies de séquençage peuvent ...
Voir la vidéo
Label UNT Vidéocours

le (4m47s)

3.1. Tous les gènes se terminent sur un codon stop

Une fois la séquence d'un génome complet obtenue, débute la phase d'annotation. L'annotation elle-même consiste tout d'abord à rechercher la localisation, c'est-à-dire la position des gènes sur cette séquence. Cette semaine, nous allons nous intéresser à la prédiction des gènes, nous allons étudier un algorithme de prédiction de gènes sur des séquences génomiques procaryotes, nous allons essayer d'améliorer la qualité de ces prédictions en ayant recours à des additifs à notre algorithme, recherches de certains motifs supplémentaires, éventuellement recours à des techniques probabilistes. Nous allons chercher à voir comment on peut comparer la qualité des prédictions de différentes méthodes, et ...
Voir la vidéo
Label UNT Vidéocours

le (5m50s)

3.7. Index et arbre des suffixes

Il y a donc deux approches pour améliorer la performance des algorithmes de recherche d'un motif dans une chaîne de caractères. La première approche consiste à pré-traiter le motif. On a vu un exemple de cette approche avec l'algorithme de Boyer-Moore. La deuxième approche consiste à pré-traiter le texte dans lequel nous recherchons les motifs. Et nous allons voir deux exemples de mise en oeuvre de cette approche. La première consiste à construire un index de mots de longueur fixe. De quoi s'agit-il ? Considérons cette chaîne de caractères, relativement courte ici, de longueur 14. Nous allons construire un index de tous les ...
Voir la vidéo
Label UNT Vidéocours

le (4m47s)

3.8. Des méthodes probabilistes à la rescousse

Nous avons vu comment la qualité des prédictions de gènes dans un génome bactérien, pouvait être améliorée à travers la recherche d'occurrences de motifs particuliers liés au site de fixation du ribosome, le fameux site RBS.Il n'en reste pas moins que ces prédictions de gènes, basée uniquement sur la recherche de motifs, sont insuffisantes pour produire des prédictions de qualité satisfaisante. Les bio informaticiens complètent donc cette approche-là par des approches probabilistes qui permettent de tester le caractère codant, ou non codant, de la région prédite. Voyons de plus près comment ces méthodes fonctionnent.Pour ce faire je vais prendre un ...
Voir la vidéo
Label UNT Vidéocours

le (5m44s)

3.6. L’algorithme de Boyer-Moore

Vous avez compris que la recherche de motifs, c'est-à-dire de sous-chaînes de caractères dans une chaîne plus importante, était un composant important de beaucoup d'algorithmes de bio-informatique. Les algorithmiciens ont toujours cette obsession de l'efficacité de leurs algorithmes. Pourquoi ? Parce qu'on travaille sur des textes qui sont assez longs, on en a vu des ordres de grandeur, et moins, on aura à faire de comparaison, plus rapide sera l'exécution de nos algorithmes. Donc, travailler sur l'efficacité des algorithmes de recherche de motifs est largement justifié. Regardons en effet, quelle est l'efficacité de l'algorithme qu'on appelle naïf ? Naïf au sens ...
Voir la vidéo
Label UNT Vidéocours

le (5m47s)

2.10. Comment trouver les gènes ?

L'obtention de la séquence complète d'un génome d'un organisme vivant est certes un beau résultat, mais c'est en fait le début d'une longue phase d'interprétation, d'annotations et de comparaisons. Par annotations, on entend quoi? On entend d'abord la prédiction des positions des gènes, où sont situés les gènes, où le gène commence-t-il, où se termine-t-il ? Une fois qu'on connaît cette position de début et de fin dans un gène bactérien, on est capable de prédire par traduction la protéine. De là, l'étape supplémentaire serait de dire quelle est la ou quelles sont les fonctions de la protéine codée par ...
Voir la vidéo
Label UNT Vidéocours

le (5m41s)

3.4. Prédiction de tous les gènes d’une séquence

En combinant de façon adéquate la recherche des triplés Stop et Start sur un brin d'ADN, nous avons obtenu un algorithme qui prédit les gènes sur ce brin, mais également sur une phase. C'est-à-dire en groupant les lettres en triplés d'une certaine manière. Nous avons vu qu'il existait 3 phases sur une séquence donnée. Nous allons donc dans un premier temps, avant de voir comment nous pouvons prédire tous les gènes d'un génome, modifier légèrement notre algorithme en le paramétrant au lieu de commencer systématiquement à la première position de la séquence nous commencerons sur la position iPhase et iPhase ...
Voir la vidéo
Label UNT Vidéocours

le (4m2s)

3.3. À la recherche des codons start et stop

Nous avons écrit la structure, l'ossature d'un algorithme de prédiction de gènes dans un génome bactérien, en utilisant les principes que nous avions énoncés précédemment. Cet algorithme est incomplet puisque pour l'instant, nous avons repoussé l'écriture des 2 fonctions nécessaires à la recherche des occurrences des triplets Stop et Start. C'est donc ce que nous allons faire maintenant. Comment faire pour rechercher l'occurrence d'un triplet ? En fait l'algorithme est très simple, très naïf, il consiste à comparer chaque lettre du triplet à chaque lettre de la séquence, et faire progresser, si aucune correspondance n'est trouvée, faire correspondre le motif ...
Voir la vidéo
Label UNT Vidéocours

le (4m21s)

3.2. Un algorithme simple de prédiction de gènes

Sur la base des principes énoncés précédemment, nous allons écrire un premier algorithme de prédiction de gènes sur un texte génomique procaryote. Je rappelle ces principes. L'idée est la suivante : de rechercher des triplets STOP consécutifs dans la même phase, consécutifs de telle façon qu'effectivement il n'y ait pas un stop qui vienne se mettre au milieu et qui casserait, en quelque sorte, la région codante qui doit être traduite dans son intégralité. Donc, recherche de deux triplets STOP consécutifs, suffisamment éloignés l'un de l'autre pour qu'il y ait de la place pour coder une protéine fonctionnelle. Ensuite, on recherche le ...
Voir la vidéo

 
FMSH
 
Facebook Twitter Google+
Mon Compte