Notice
4.8. Un algorithme récursif
- document 1 document 2 document 3
- niveau 1 niveau 2 niveau 3
Descriptif
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 ce noeud et de ce noeud-là, à travers un des trois chemins possibles. De même, le coup de ce noeud-là peut être calculé avec le même schéma de calcul à partir du coût de ce noeud-là, celui-ci et celui-là, et ainsi de suite. Et ainsi de suite, en remontant jusqu'au noeud 00. Ceci nous donne un schéma de calcul récursif que nous allons implémenter dans une fonction récursive. Qu'est-ce qu'une fonction récursive ? Une fonction récursive est une fonction qui fait appel à elle-même, qui s'appelle elle-même, au cours même de son exécution. Elle s'exécute, et au cours de son exécution, elle s'appelle elle-même. Et donc, on va avoir une cascade d'appels. Elle est en train de s'exécuter, elle s'appelle, elle s'exécute, elle s'appelle et cetera...
Intervention
Dans la même collection
-
4.9. Éviter la récursivité : une version itérative
RechenmannFrançoisParmentelatThierryLa 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
-
4.3. Quantifier la similarité de deux séquences
RechenmannFrançoisParmentelatThierryLe 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 optimaux
RechenmannFrançoisParmentelatThierryNous 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.1. Comment prédire les fonctions des gènes/protéines ?
RechenmannFrançoisParmentelatThierryAprè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.10. Cet algorithme est-il efficace ?
RechenmannFrançoisParmentelatThierryLa 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.4. L’alignement de séquences devient un problème d’optimisation
RechenmannFrançoisParmentelatThierryLa 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 alignement
RechenmannFrançoisParmentelatThierryNous 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.2. Évolution et similarité de séquences
RechenmannFrançoisParmentelatThierryAvant 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.5. Un alignement de séquences vu comme un chemin dans une grille
RechenmannFrançoisParmentelatThierryPour 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
Avec les mêmes intervenants et intervenantes
-
1.6. GC and AT contents of DNA sequence
RechenmannFrançoisWe have designed our first algorithmfor counting nucleotides. Remember, what we have writtenin pseudo code is first declaration of variables. We have several integer variables that are variables which
-
2.5. Implementing the genetic code
RechenmannFrançoisRemember we were designing our translation algorithm and since we are a bit lazy, we decided to make the hypothesis that there was the adequate function forimplementing the genetic code. It's now time
-
3.2. A simple algorithm for gene prediction
RechenmannFrançoisBased on the principle we statedin the last session, we will now write in pseudo code a firstalgorithm for locating genes on a bacterial genome. Remember first how this algorithm should work, we first
-
3.10. Gene prediction in eukaryotic genomes
RechenmannFrançoisIf it is possible to have verygood predictions for bacterial genes, it's certainly not the caseyet for eukaryotic genomes. Eukaryotic cells have manydifferences in comparison to prokaryotic cells. You
-
4.8. A recursive algorithm
RechenmannFrançoisWe have seen how we can computethe optimal cost, the ending node of our grid if we know the optimal cost of the three adjacent nodes. This is this computation scheme we can see here using the notation
-
5.6. The diversity of bioinformatics algorithms
RechenmannFrançoisIn this course, we have seen a very little set of bioinformatic algorithms. There exist numerous various algorithms in bioinformatics which deal with a large span of classes of problems. For example,
-
1.1. The cell, atom of the living world
RechenmannFrançoisWelcome to this introduction to bioinformatics. We will speak of genomes and algorithms. More specifically, we will see how genetic information can be analysed by algorithms. In these five weeks to
-
1.9. Predicting the origin of DNA replication?
RechenmannFrançoisWe have seen a nice algorithm to draw, let's say, a DNA sequence. We will see that first, we have to correct a little bit this algorithm. And then we will see how such as imple algorithm can provide
-
2.8. DNA sequencing
RechenmannFrançoisDuring the last session, I explained several times how it was important to increase the efficiency of sequences processing algorithm because sequences arevery long and there are large volumes of
-
3.5. Making the predictions more reliable
RechenmannFrançoisWe have got a bacterial gene predictor but the way this predictor works is rather crude and if we want to have more reliable results, we have to inject into this algorithmmore biological knowledge. We
-
4.6. A path is optimal if all its sub-paths are optimal
RechenmannFrançoisA sequence alignment between two sequences is a path in a grid. So that, an optimal sequence alignmentis an optimal path in the same grid. We'll see now that a property of this optimal path provides
-
5.1. The tree of life
RechenmannFrançoisWelcome to this fifth and last week of our course on genomes and algorithms that is the computer analysis of genetic information. During this week, we will firstsee what phylogenetic trees are and how
Sur le même thème
-
Les machines à enseigner. Du livre à l'IA...
BruillardÉricQue peut-on, que doit-on déléguer à des machines ? C'est l'une des questions explorées par Éric Bruillard qui, du livre aux IA génératives, expose l'évolution des machines à enseigner...
-
Le projet dnarXiv : Stockage de données sur des molécules d'ADN
LavenierDominiqueDuprazElsaLeblancJulienCoatrieuxGouenouDominique Lavenier, Elsa Dupraz, Julien Leblanc et Gouenou Coatrieux nous présentent le projet dnarXiv, un projet porté par le LabEx CominLabs qui explore le stockage de données sur des molécules d
-
Projection methods for community detection in complex networks
LitvakNellyCommunity detection is one of most prominent tasks in the analysis of complex networks such as social networks, biological networks, and the world wide web. A community is loosely defined as a group
-
Lara Croft. doing fieldwork under surveillance
Dall'AgnolaJasminLara Croft. Doing Fieldwork Under Surveillance Intervention de Jasmin Dall'Agnola (The George Washington University), dans le cadre du Colloque coorganisé par Anders Albrechtslund, professeur en
-
Containing predictive tokens in the EU
CzarnockiJanContaining Predictive Tokens in the EU – Mapping the Laws Against Digital Surveillance, intervention de Jan Czarnocki (KU Leuven), dans le cadre du Colloque coorganisé par Anders Albrechtslund,
-
Ivan Murit - Processus de création d'images
MuritIvanJe vais présenter une manière décalée d'aborder les outils d'impression. Pour cela nous ne partirons pas de l'envie d'imprimer une image préexistante, mais d'avant cela : comment se crée une forme
-
Le Creativ’Lab, au cœur de la robotique et de l’intelligence artificielle (ASR N°18 - LORIA)
HénaffPatrickLefebvreSylvainLe 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
MathieuClaireL’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
RéveillèreLaurentMaveyraud-TricoireSamuelBlancXavierBertrandYvesMainguenéMarcL’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
TarissanFabienL’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
DorentRichardL’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 …
MerigouxDenisL’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
