4.7. Coûts et alignement
- document 1 document 2 document 3
- niveau 1 niveau 2 niveau 3
- audio 1 audio 2 audio 3
Descriptif
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 dessin, les coûts d'insertion Bêta, et les coûts de substitution Alpha de N,M. Pourquoi Alpha de N,M ? Eh bien parce que, Alpha de N,M, c'est le coût de substitution de la lettre qui est là par celle-ci. De la première séquence par la lettre de la deuxième séquence, à cette position-là de l'alignement. Ce coût Alpha de N,M, c'est en fait un élément d'une matrice qui donne les coûts de substitution d'une base par une autre, dans le cas de l'ADN, ou d'un acide aminé par un autre, dans le cas d'alignement de séquences protéiques...
Intervenant
Thème
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.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.5. Un alignement de séquences vu comme un chemin dans une grilleRechenmannFrançoisParmentelatThierry
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
-
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
-
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
-
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
-
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.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
-
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.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.7. Les applications en microbiologieRechenmannFrançoisParmentelatThierry
Une très grande diversité, on l'a vu, d'algorithmes en bio-informatique, motivé par la résolution de problèmes différents. Ces algorithmes, ces recherches en bio-informatique, s'appuient sur des
-
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
Sur le même thème
-
Le Creativ’Lab, au cœur de la robotique et de l’intelligence artificielle (ASR N°18 - LORIA)HénaffPatrickLefebvreSylvain
Le LORIA, laboratoire phare de la Grande Région dans le domaine de l’informatique, propose de rendre la recherche plus ouverte, plus collaborative, plus ambitieuse… en un mot, plus créative, à travers
-
Les algorithmes de Parcoursup
L’objectif de la journée « Algorithmes d’aide à la décision publique » était de sensibiliser le grand public aux rôles des algorithmes d’aide à la décision publique utilisés par exemple pour l
-
Algorithmes d'aide à la décision publique / Ouverture
L’objectif de la journée « Algorithmes d’aide à la décision publique » était de sensibiliser le grand public aux rôles des algorithmes d’aide à la décision publique utilisés par exemple pour l
-
Quelques enjeux autour des algorithmes d'aide à la décision publique
L’objectif de la journée « Algorithmes d’aide à la décision publique » était de sensibiliser le grand public aux rôles des algorithmes d’aide à la décision publique utilisés par exemple pour l
-
Un nouveau système de répartition des greffons cardiaques utilisant un algorithme
L’objectif de la journée « Algorithmes d’aide à la décision publique » était de sensibiliser le grand public aux rôles des algorithmes d’aide à la décision publique utilisés par exemple pour l
-
Règles, calcul et politique : investigation des choix de programmation inaperçus pour les aides au …
L’objectif de la journée « Algorithmes d’aide à la décision publique » était de sensibiliser le grand public aux rôles des algorithmes d’aide à la décision publique utilisés par exemple pour l
-
Algorithmes de décision publique : élaboration, évaluation et évolutions
L’objectif de la journée « Algorithmes d’aide à la décision publique » était de sensibiliser le grand public aux rôles des algorithmes d’aide à la décision publique utilisés par exemple pour l
-
La vérification déductive avec l'outil WHY3
L’objectif de la journée « Algorithmes d’aide à la décision publique » était de sensibiliser le grand public aux rôles des algorithmes d’aide à la décision publique utilisés par exemple pour l
-
Retour sur quelques effets juridiques modérément contrôlés de la règlementation sur les "algorithme…
L’objectif de la journée « Algorithmes d’aide à la décision publique » était de sensibiliser le grand public aux rôles des algorithmes d’aide à la décision publique utilisés par exemple pour l
-
Affelnet, APB, Parcoursup... : les algorithmes peuvent-ils présider aux destinées des élèves ?
L’objectif de la journée « Algorithmes d’aide à la décision publique » était de sensibiliser le grand public aux rôles des algorithmes d’aide à la décision publique utilisés par exemple pour l
-
Expliquer, justifier et contester le système d'attribution des greffons
L’objectif de la journée « Algorithmes d’aide à la décision publique » était de sensibiliser le grand public aux rôles des algorithmes d’aide à la décision publique utilisés par exemple pour l
-
Quelles perspectives pour l'acceptabilité des algorithmes ?
L’objectif de la journée « Algorithmes d’aide à la décision publique » était de sensibiliser le grand public aux rôles des algorithmes d’aide à la décision publique utilisés par exemple pour l
