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.

  1. En utilisant BLAST, trouvez des séquences similaires à
    atgacaaagt tatagtcatg ggcagatctc catcgcatga atccaaaggg
    
  2. Calculez les P-valeurs pour les 5 meilleures paires de segments: identifiez les matches significants et choisissez la séquence la plus similaire.
  3. Donnez une brève description de la séquence à travers les champs de l'entrée: origin et type de la séquence, etc.
  4. Sauvegardez la séquence (T1) sous un format fasta sur votre compte.
  5. 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.

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:

Pour les fichiers: remettre par remise dift3290 tp3 fichier1 fichier2 ...

Cet exercice a été conçu par Ratiba Terbaoui.