Notice
3.6. L’algorithme de Boyer-Moore
- document 1 document 2 document 3
- niveau 1 niveau 2 niveau 3
Descriptif
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 de : on applique l'algorithme le plus basique auquel on pourrait penser. De quoi s'agit-il ? Vous avez un motif ici de taille 6, qui est le motif à rechercher dans un texte, dans une séquence plus longue de longueur M. Comment faites-vous ? Eh bien, vous placez votre motif au début de la séquence et vous comparez : ici ça correspond, ici ça ne correspond pas. Donc, ce n'est pas la peine de continuer, j'avance mon motif d'une position. Et je refais la comparaison avec la première lettre, il n'y a pas de correspondance. J'avance. Comparaison avec la première lettre, une correspondance. Par contre ici, G et A ne sont pas en correspondance. J'avance. Ici même chose, le A "match" comme on dit avec la position courante de la séquence. Par contre, pas la lettre suivante. Donc j'avance même chose, j'avance. Ici, correspondance, correspondance, pas de correspondance. Donc j'avance et ainsi de suite jusqu'à effectivement trouver ou pas une occurrence de mon motif dans la séquence complète...
Intervention
Dans la même collection
-
3.9. Comment évaluer la qualité de prédiction des méthodes ?
RechenmannFrançoisParmentelatThierryNous avons vu qu'il était possible, ou du moins nous le pensions, améliorer la qualité de prédiction des gènes sur un génome bactérien en introduisant des démarches supplémentaires, de recherches de
-
3.3. À la recherche des codons start et stop
RechenmannFrançoisParmentelatThierryNous 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
-
3.7. Index et arbre des suffixes
RechenmannFrançoisParmentelatThierryIl 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
-
3.1. Tous les gènes se terminent sur un codon stop
RechenmannFrançoisParmentelatThierryUne 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
-
3.10. La prédiction de gènes dans les génomes eucaryotes
RechenmannFrançoisParmentelatThierrySi nous disposons actuellement de prédicteurs de gènes dans les génomes procaryotes de très bonne efficacité, avec des prédictions relativement fiables, c'est en fait loin d'être le cas sur les
-
3.4. Prédiction de tous les gènes d’une séquence
RechenmannFrançoisParmentelatThierryEn 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
-
3.8. Des méthodes probabilistes à la rescousse
RechenmannFrançoisParmentelatThierryNous 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
-
3.2. Un algorithme simple de prédiction de gènes
RechenmannFrançoisParmentelatThierrySur 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 :
-
3.5. Comment améliorer la qualité des prédictions ?
RechenmannFrançoisParmentelatThierryIl faut toujours le répéter et le souligner, les algorithmes qui déterminent des gènes déterminent des gènes candidats. Ce sont des prédictions de gènes. Donc la question est de savoir s'il est
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
-
Désassemblons le numérique - #Episode11 : Les algorithmes façonnent-ils notre société ?
SchwartzArnaudLima PillaLaércioEstériePierreSalletFrédéricFerbosAudeRoumanosRayyaChraibi KadoudIkramUn an après le tout premier hackathon sur les méthodologies d'enquêtes journalistiques sur les algorithmes, ce nouvel épisode part à la rencontre de différents points de vue sur les algorithmes.
-
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...
-
Désassemblons le numérique - #Episode9 : Bientôt des supercalculateurs dans nos piscines ?
BeaumontOlivierBouzelRémiDes supercalculateurs feraient-ils bientôt leur apparition dans les piscines municipales pour les chauffer ? Réponses d'Olivier Beaumont, responsable de l'équipe-projet Topal, et Rémi Bouzel,
-
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
