Devoir 3-4
Date limite de remise: vendredi le 14 mars 2003, 18:00.
Recherche exacte (100 points)
Le but de cet exercice est d'utiliser l'algorithme Boyer et Moore ou Z
,
ainsi qu'un algorithme plus rapide. L'exercice utilise GenBank et manipulations des données
selon le format FASTA.
- En utilisant BLAST, trouvez des séquences similaires à
atgacaaagt tatagtcatg ggcagatctc catcgcatga atccaaaggg
- Calculez les P-valeurs pour les 5 meilleures paires de segments: identifiez les matches significants et choisissez la séquence la plus similaire.
- Donnez une brève description de la séquence à travers les champs de l'entrée: origin et type de la séquence, etc.
- Sauvegardez la séquence (T1) sous un format fasta sur votre compte.
- Identifiez la partie qui code la protéine dont les bornes sont données dans le champ CDS. Sauvegardez la séquence protéique (T2).
Dans T2, la séquence d'acide aminés HGYGVYGHPGYGG se répète deux fois. Si on coupe la séquence en deux donc HGYGVYG et HPGYGG, les deux se répéteront toujours deux fois de façon alternante. Le travail demandé sera de voir si au niveau des ARN, on retrouve la même chose. Plus précisement, on veut savoir si l'équivalent en ARN du pattern HGYGVYG se répète toujours deux fois tels que dans la protéine. Soit P2=HGYGVYG et soit P1 le sous-mot de T1 qui correspond à la première occurrence de P2 en T2.
- implantez l'algorithme
Z
ou celui de Boyer et Moore pour retrouver le nombre d'occurrences de P1 en T1, et celles de P2 en T2. - implantez encore un algorithme plus rapide (p.e., Turbo Boyer et Moore ou celui de Apostolico-Giancarlo) pour retrouver toujours les occurrences.
Les programmes doivent lire les Ti à partir d'un fichier de format FASTA. Après avoir testé vos programmes sur les deux séquences (une avec un alphabet de 20 et l'autre avec un de 4), dresser un tableau comparatif mettant en évidence la longueur des alphabets en utilisant les métriques de comparaisons: vitesse d'exécution et nombre de comparaisons. De ce travail doit ressortir l'influence de la taille de l'alphabet sur le déroulement des algorithmes dans les deux phases : de pré-traitement et de recherche proprement dite.
Remise du travail
Il faut remettre un rapport écrit, les fichiers de FASTA produits en étapes 4 et 5, et la source de votre code avec toute explication que vous trouvez nécessaire. Dans le rapport:
- donnez vos réponses aux questions des étapes 2 et 3.
- expliquez les étapes des algorithme choisis.
- montrez les tableaux comparatifs et analysez les résultats
Pour les fichiers: remettre par remise dift3290 tp3 fichier1 fichier2 ...
Cet exercice a été conçu par Ratiba Terbaoui.