4.5. Un alignement de séquences vu comme un chemin dans une grille
- document 1 document 2 document 3
- niveau 1 niveau 2 niveau 3
- audio 1 audio 2 audio 3
Descriptif
Pour comparer deux séquences entre elles, il faut donc les aligner. Aligner ces deux séquences suppose faire des hypothèses d'insertion, délétion, aux bons endroits. Ça signifie, d'un point de vue séquence de caractères, insérer des caractères "blank", le tiret, aux endroits appropriés. Approprié dans quel sens ? Au sens que la distance entre les deux séquences soit minimale. On appliquera le même processus pour toute perte de séquence, et systématiquement, on retiendra comme étant la mesure de similarité, la distance minimale entre cette paire de séquences. Comment déterminer ces endroits d'insertion, de délétion, comment émettre ces hypothèses d'insertion, délétion et obtenir un alignement de coût minimal ? Pour ce faire, nous allons raisonner sur une grille. Ici, telle qu'elle est figurée là, où on a la première séquence en ligne et la seconde séquence à aligner comparée en colonne. Ceci nous définit une grille avec des noeuds numérotés 00 ici, 6-7 ici, dans le cas de deux séquences extrêmement courtes, mais vous l'avez bien vu, de longueurs différentes. Que va être un alignement de ces deux séquences ? Un alignement de ces deux séquences va être un chemin dans la grille qui relie le noeud d'origine au noeud extrémité, ici au noeud de coordonnée 6-7...
Intervenants
Thèmes
Notice
Documentation
Dans la même collection
-
4.8. Un algorithme récursifRechenmannFrançoisParmentelatThierry
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
-
4.4. L’alignement de séquences devient un problème d’optimisationRechenmannFrançoisParmentelatThierry
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
-
4.7. Coûts et alignementRechenmannFrançoisParmentelatThierry
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
-
4.10. Cet algorithme est-il efficace ?RechenmannFrançoisParmentelatThierry
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
-
4.3. Quantifier la similarité de deux séquencesRechenmannFrançoisParmentelatThierry
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
-
4.6. Si un chemin est optimal, tous ses chemins partiels sont optimauxRechenmannFrançoisParmentelatThierry
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
-
4.2. Évolution et similarité de séquencesRechenmannFrançoisParmentelatThierry
Avant de chercher à quantifier ce qu'est la similarité de séquence, on peut se poser la question même de savoir pourquoi des séquences de génome sont similaires entre organismes. La réponse tient dans
-
4.1. Comment prédire les fonctions des gènes/protéines ?RechenmannFrançoisParmentelatThierry
Après avoir regardé dans les yeux, les semaines précédentes, l'ADN, vu comment cet ADN par séquençage produisait des textes, des séquences génomiques, étudié la relation entre gènes et protéines,
-
4.9. Éviter la récursivité : une version itérativeRechenmannFrançoisParmentelatThierry
La fonction récursive que nous avons obtenue est d'un code assez compact et plutôt élégant, mais effectivement peu efficace. Pourquoi ? Rappelons son fonctionnement. Cette fonction est d'abord appelée
Avec les mêmes intervenants
-
5.6. La diversité des algorithmes informatiquesRechenmannFrançoisParmentelatThierry
Nous n'avons vu dans ce cours qu'un exemple extrêmement réduit d'algorithme bio informatique. Il existe en effet une très grande diversité de ces algorithmes bio informatiques qui sont motivés par l
-
4.8. Un algorithme récursifRechenmannFrançoisParmentelatThierry
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
-
5.2. L’arbre, objet abstraitRechenmannFrançoisParmentelatThierry
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
-
5.1. L’arbre des espècesRechenmannFrançoisParmentelatThierry
Dans cette cinquième et dernière partie de notre cours sur le génome et les algorithmes, qui se veut une introduction à l'analyse informatique de l'information génétique, nous regarderons de plus près
-
5.5. Quand les différences sont trompeusesRechenmannFrançoisParmentelatThierry
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
-
4.7. Coûts et alignementRechenmannFrançoisParmentelatThierry
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
-
4.4. L’alignement de séquences devient un problème d’optimisationRechenmannFrançoisParmentelatThierry
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
-
5.4. L’algorithme UPGMARechenmannFrançoisParmentelatThierry
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,
-
4.3. Quantifier la similarité de deux séquencesRechenmannFrançoisParmentelatThierry
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
-
4.10. Cet algorithme est-il efficace ?RechenmannFrançoisParmentelatThierry
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
-
4.6. Si un chemin est optimal, tous ses chemins partiels sont optimauxRechenmannFrançoisParmentelatThierry
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
-
5.3. Remplir un tableau de distancesRechenmannFrançoisParmentelatThierry
Pour tenter de construire l'arbre phylogénétique d'un ensemble d'espèces, nous allons utiliser les données et génotypique ou des données génotypiques disponibles sur ces espèces. Plus clairement, nous
Sur le même thème
-
Une minute avec Emmanuelle SaillardSaillardEmmanuelle
1 une minute avec ... met à l'honneur les scientifiques et les personnels d'appuis à la recherche du Centre Inria de l'université de Bordeaux. Grâce à ce nouveau format, le monde de la recherche n
-
Une minute avec Clément FoyerFoyerClément
1 une minute avec ... met à l'honneur les scientifiques et les personnels d'appuis à la recherche du Centre Inria de l'université de Bordeaux. Grâce à ce nouveau format, le monde de la recherche n
-
Désassemblons le numérique - #Episode1 : plongée au cœur des donnéesProuzeauArnaud
Ce premier épisode de Désassemblons le numérique part à la rencontre d'Arnaud Prouzeau, chercheur au sein de l'équipe-projet Potioc du Centre Inria de l'université de Bordeaux. Arnaud oriente ses
-
Opinion polarization and network segregation. Modelling a complex RelationshipFlacheAndreas
Recently, many societies seem to shift towards more polarization and volatility in opinions, for example in attitudes about immigration, climate policy, or the best policy response to Covid-19. A
-
21 Molecular Algorithms Using Reprogrammable DNA Self-AssemblyWoodsDamien
The history of computing tells us that computers can be made of almost anything: silicon, gears and levers, neurons, flowing water, interacting particles or even light. Although lithographically
-
Topological insights in neuroscienceHess BellwaldKathryn
Over the past decade, and particularly over the past five years, research at the interface of topology and neuroscience has grown remarkably fast. Topology has, for example, been successfully applied
-
Quelques algorithmes de calcul d'enveloppe convexe en 2DGiraultAlain
Le calcul de l'enveloppe convexe d'un nuage de points est un des problèmes fondamentaux en informatique, avec des applications multiples : traitement d'images, reconstruction 3D, détection de
-
Modélisation de la croissance des micro-organismesJongHidde de
La croissance microbienne peut être formulée comme un problème d'optimisation : comment allouer les ressources nutritives extraites de l'environnement aux différentes fonctions cellulaires afin de
-
Les mathématiques et la physique dans les effets spéciaux et les jeux vidéoNeyretFabrice
La synthèse d’images (parfois appelée « la 3D ») permet de créer dans l’ordinateur des mondes fictifs, ultra-réalistes ou de style cartoon selon l’envie des graphistes, des réalisateurs, des
-
Caches, montrez-vous !DurandMarie
Les processeurs actuels permettent de l'ordre de quelques tera-opérations par seconde. Puissance nécessaire pour soutenir les besoins en simulation numérique, qui constitue, après la théorie et l
-
Théorie de l’appariement et applications actuelles
Pourquoi y a-t-il tant de personnes sans emploi alors qu’au même moment un grand nombre de postes sont disponibles ? La théorie de l’appariement analyse ces problèmes où un certain nombre de
-
Self-Supervised Visual Learning and SynthesisEfrosAlexei A.
Computer vision has made impressive gains through the use of deep learning models, trained with large-scale labeled data. However, labels require expertise and curation and are expensive to collect.
