Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Tp arbre Arbres de su ?xes Le problème est dans une séquence de trouver e ?cacement les occurences d ? une autre séquence en utilisant des arbres de su ?xes Pour les exemples on pourra utiliser la séquence du ?-phage au format fasta à l ? adresse http pbi

Arbres de su ?xes Le problème est dans une séquence de trouver e ?cacement les occurences d ? une autre séquence en utilisant des arbres de su ?xes Pour les exemples on pourra utiliser la séquence du ?-phage au format fasta à l ? adresse http pbil univ-lyon fr members gueguen lib TPAlgo lambda fa lisible gr? ce à la fonction dans le ?chier http pbil univ- lyon fr members gueguen lib TPAlgo litfasta py Dans la suite on va appeler s la séquence sur laquelle on cherche des occurences du mot m En outre m i j fait référence à la sous-séquence de m de i inclus à j exclus On dit que m est en position p sur s si ?? i len m m i s i p On appelle pré ?xe resp su ?xe d ? une séquence un début resp une ?n de longueur quelconque de cette séquence Algorithme direct Écrire une fonction maxpref s m qui prend en entrée une séquence s et un mot m et qui retourne le plus long pré ?xe de m qui est aussi dans s Évaluer la complexité temporelle de cette fonction avec pour s la séquence du phage ? Arbre de su ?xes simple Récupérer le ?chier http pbil univ-lyon fr members gueguen lib TPAlgo noeudlettre py Ce ?chier contient la dé ?nition de la classe Noeud qui correspond au n ?ud d ? un arbre Un Noeud est un dictionnaire dont les clefs sont des mots et les valeurs d ? autres Noeuds Les arêtes qui partent d ? un Noeud ont toutes des labels di ?érents Le principe d ? un arbre de mots est de représenter sous forme d ? arbre un ensemble de mots Pour que n ? importe quel ensemble de mots puisse être représenté de cette manière il faut ajouter une lettre supplémentaire à l ? alphabet initial qui corresponde aux ?ns de mots notée Ainsi dans l ? exemple ci-dessous les mots représentés sont A TC TCA TA C C A C T A A C Le format d ? écriture d ? un arbre est le suivant mot mot arbre Ainsi par exemple A T C A A C correspond à l ? arbre ci-dessus Un autre exemple est dans le ?chier ex arbre txt La méthode read de Noeud permet de lire une telle ligne Construction Écrire une méthode a mot self m de Noeud qui retourne True si l ? arbre représente le mot m Écrire une méthode prend mot self m qui complète un arbre pour qu ? il représente le mot m Un arbre des su ?xes d ? une séquence de lettres est un arbre qui représente tous les su ?xes de cette séquence Par exemple pour la séquence ACATAC A C A TA T A C CT A T A C C C A Écrire un algorithme su ? seq self s qui considère successivement tous les su ?xes de la séquence et