Remerciez-le!

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

Arbres de suﬃxes Le problème est, dans une séquence, de trouver eﬃcacement les

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-lyon1.fr/members/gueguen/lib/TP_Algo/lambda.fa lisible grâce à la fonction dans le ﬁchier : http://pbil.univ-lyon1.fr/members/gueguen/lib/TP_Algo/lit_fasta.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 : ∀0 ⩽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. 1 Algorithme direct Écrire une fonction max_pref(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 λ. 2 Arbre de suﬃxes simple Récupérer le ﬁchier http://pbil.univ-lyon1.fr/members/gueguen/lib/TP_Algo/noeud_lettre.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. 1 A C C A T $ $ $ $ A $ 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. 2.1 Construction 1. Écrire une méthode a_mot(self, m) de Noeud qui retourne True si l’arbre représente le mot m. 2. É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 A C C A T T T A A T A C C C C A $ $ $ $ $ $ 3. Écrire un algorithme suff_seq(self, s) qui considère successivement tous les suﬃxes de la séquence, et les incorpore dans l’arbre. 4. En fonction de la longueur de la séquence, quelle est la complexité temporelle de cet algorithme ? Et la complexité spatiale (ie le nombre de nœuds) ? 5. Écrire un constructeur de Noeud __init__(self, s) qui construit automa- tiquement l’arbre des suﬃxes de la séquence s. 2.2 Utilisation En guise d’exemple, l’arbre de suﬃxes sera celui de la séquence des 1000 premières lettre du génome du phage-λ. Attention de ne pas construire l’arbre de suﬃxes de tout le génome, cela est trop gros pour la mémoire de l’ordinateur. 2 Le paquetage meliae permet de mesurer la mémoire occupée par des objets python. Pour cela, on peut faire : from meliae import scanner scanner.dump_all_objects("mem_suff.json") from meliae import loader om=loader.load("mem_suff.json") s=om.summarize() print s Construisez un arbre à partir des 1000 premières lettres du génome du phage-λ. — Combien de mémoire est utilisée globalement par python ? — Combien d’instances de Noeud ont-elles été construites, et combien de mémoire occupent-elles ? À laquelle il faut ajouter la mémoire prise par les dict dont hérite Noeud. Une utilisation des arbres de suﬃxe est de comparer les contenus en mots de deux séquences. 1. Programmer une méthode récursive de Noeud, rech_mot_rec(self, mot) qui retourne True si le mot mot est présent dans la séquence représentée par l’arbre de suﬃxes. 2. Proposer une version itérative rech_mot_iter(self,mot) de la fonction pré- cédente. 3. Avec un proﬁler, comparer leurs complexités temporelles. 4. Programmer une fonction max_pref(self, mot) qui retourne le plus grand préﬁxe commun entre un mot et un arbre de suﬃxes. 5. Comparer la complexité de cette fonction avec la fonction "simple" de la partie précédente. 6. Concevoir une méthode max_commun(self, seq) qui retourne le plus long mot commun à une séquence seq et celle représentée par l’arbre de suﬃxes. Quelle est la complexité de cet algorithme ? 3 Diminuer la complexité spatiale Dans un arbre, il peut y avoir une succession de nœuds qui n’ont qu’un ﬁls. Une telle succession est inutile, puisqu’elle peut être simpliﬁée par un seul nœud, dont le label est la succession des labels des nœuds supprimés. Par exemple, on peut remplacer A → C → G →par ACG − →. Seulement, assigner à chaque branche des mots (éventuellement longs) est aussi très demandeur de mémoire. Cependant, si l’arbre est un arbre de suﬃxes, on dispose de la séquence, donc de tous les mots présents dedans. Ainsi, il n’est pas besoin de les 3 réécrire dans les clefs de l’arbre, mais simplement des coordonnées correspondantes dans la séquence. Récupérer le ﬁchier : http://pbil.univ-lyon1.fr/members/gueguen/lib/TP_Algo/noeud_suff.py qui déﬁnit une nouvelle classe Noeud construite comme indiqué ci-dessus. 1. Comparer le temps de création d’un arbre de suﬃxes avec cette version, par rapport à la précédente. En outre, est-ce que la complexité en espace a radicalement dimininué ? 4 Vers le graphe Dans la fonction max_commun, chaque lettre de seq peut être comparée plusieurs fois, ce qui n’est pas optimal. Une solution pour palier ce problème est d’ajouter dans chaque nœud de l’arbre de suﬃxes, par exemple qui représente le mot m, un pointeur vers le nœud qui représente le plus long suﬃxe strict de m dans l’arbre, comme dans la ﬁgure ci-dessous. A A C C A T T T A A T A C C C C A $ $ $ $ $ $ Cette nouvelle arête correspondra à ce où aller en cas d’échec dans la lecture d’un mot. 1. Modiﬁer les classes et méthodes de Noeud du ﬁchier noeud_lettre.py pour qu’un arbre intègre cette information. En particulier, modiﬁer la méthode suff_seq pour que cette construction soit eﬃcace (ie elle ne nécessité qu’une lecture directe de la séquence). 2. Dans ce cas, quelle est la complexité de la recherche de plus long mot commun ? 4 uploads/Litterature/ tp-arbre.pdf