Page TP IFT3295

Démonstrateur : Emmanuel Noutahi
Email : fmr.noutahi@umontreal.ca
Local : AA-3174 (laboratoire du LBIT)
Disponibilités : Lundi et Jeudi de 13h30 à 16h30 (ou prendre rendez-vous par email)

Comment remettre votre devoir ? cliquez-ici

En bref, connectez-vous à votre compte du DIRO, et en ligne de commande :
ssh remise
remise ift3295 tpX devoir.zip
,
où X désigne le numéro du TP.

Comment aller récupérer vos notes ? cliquez-ici

En bref, connectez-vous à votre compte du DIRO, et en ligne de commande :
ssh remise
notes ift3295


Page du cours IFT3295


Démo 1 [Lundi 18 Septembre]

La démo portera sur les séquences biologiques et la programmation dynamique. Étant donné qu'il n'y a pas encore assez de matière vue en classe, cette démo sera un peu spéciale. La démo est disponible ici ==> demo 1 et aborde les notions suivantes :
  1. Séquence biologique, code génétique, etc
  2. Distances entre séquences, Programmation dynamique pour l'alignement de deux séquences (distance d'édition)
  3. Base de données, clustalx
Vous trouverez les séquences protéiques de l'insuline chez quelques animaux ici : ==> insulin.fasta.
Et ci-dessous un alignement de ces séquences en présence d'un arbre phylogénétique. insulin tree

Voici une vidéo qui sur le séquençage qui illustre les progrès scientifiques sur le sujet en moins d'une décennie : https://www.youtube.com/watch?v=jFCD8Q6qSTM.


TP1 [Lundi 18 septembre]

L'énoncé du TP1 est disponible ici ==> TP1.pdf. Les fichiers supplémentaires (reads.fq, sequence.fasta, geneX.fasta) sont tous disponibles à ~dift3295/TP1.

Le TP est à faire en équipe de deux et vous avez deux semaines pour le finir. Je vous conseille de le commencer assez tôt pour avoir une idée des numéros difficiles afin de poser les questions à temps.


Aide TP1 [Jeudi 21 Septembre]

J'ai reçu quelques questions pour le TP1 et je voudrais donc préciser certains points

Démo 2 [Lundi 25 Septembre]

La démo portera sur les optimisation des algorithmes d'alignement de deux séquences. La démo est disponible ici ==> demo 2.

Question récurrence TP1 [Mardi 26 Septembre]

J'ai reçu quelques questions sur la matrice 20x20 demandée.

TP2 [Lundi 2 Octobre]

L'énoncé du TP2 est disponible ici ==> TP2.pdf. Les fichiers supplémentaires (sequences.fasta, BLOSUM62.txt) sont tous disponibles à ~dift3295/TP2.

Le TP est à faire en équipe de deux et vous avez deux semaines pour le finir. Je vous conseille de le commencer assez tôt (je ne serai pas toujours disponible pour répondre aux questions de dernières minutes la veille de la remise).


Démo 3 [Lundi 2 Octobre]

La démo 3 portera sur les structures secondaires d'ARNs, les automates/HMMs. Nous corrigerons aussi le TP1. L'énoncé de la démo est disponible ici ==> demo3.pdf.


TP2 update

Notez que la remise du TP1 a été reportée pour le 30 octobre. Vous avez donc pratiquement 1 mois pour le faire :).

Le lundi 9 octobre est férié. Il n'y aura donc pas de cours ou démo. Bonne fin de semaine


Démo 4 et Intra précédent [Mercredi 11 Octobre]

L'intra de l'année passée est mise à votre disposition ==> intra 2016. Nous le corrigerons le lundi prochain au cours de la démo 4.

L'énoncé de la démo 4 est également disponible ici ==> demo 4. Elle porte sur l'alignement multiple de séquence qui sera à l'examen. Notez que cette démo sera courte car plus de temps seront passé sur la révision pour l'examen.


Notes TP1 et retour [Mercredi 25 Octobre]

Vos notes pour le TP1 sont disponibles. Parce qu'il y a eu des changements sur le serveur, la commande notes ne fonctionne pas correctement. En attendant, utilisez la procédure suivante:

ssh remise
~dift3295/bin/getnotes $@ | /usr/bin/gawk -f /usr/local/lib/notes.aw $1

Aussi, quand vous remettez du code,

Pour chaque modification que je dois faire dans votre programme pour le faire fonctionner correctement, vous perdez des points !


TP2, séquence de test [Vendredi 26 Octobre]

Voici quelques séquences de test pour votre alignement avec pondération affine :

>seq1
MCAT
>seq2
MGACCT

Le résultat espéré est:

seq1: M--CAT
seq2: MGACCT

score: 7
		
Un autre exemple :
>seq1
MGAPWYTST
>seq2
MAHTYTT

Résultat attendu:

seq1: MGAPWYTST
seq2: M-AHTYT-T

score: 0
		
Un dernier exemple avec des séquences plus longues et l'ensemble des alignements équivalents :
>S1
MGEIGFTEKQEALVKESWEILKQDIPKYSLHFFSQILEIAPAAKGLFSFLRDSDEVPHNNPKLKAHAVKV
FKMTCETAIQLREEGKVVVADTTLQYLGSIHLKSGV

>S2
MEKVPGEMEIERRERSEELSEAERKAVQATWARLYANCEDVGVAILVRFFVNFPSAKQYFSQFKHMEEPL
EMERSPQLRKHACRVMGALNTVVENLHDPEKVS
L'ensemble des résultats se trouve dans seqtest.fasta et le score correspondant est score: 3

Démo 5 [Jeudi 26 Octobre]

L'énoncé de la demo5 est maintenant disponible ici ==> demo 5. Elle porte sur les sujets non-abordé pour les alignements multiples et commence à introduire les algos pour la recherche exacte

Au cours de la démo, nous corrigerons aussi le TP2, et je présenterai le TP3


TP3 [Samedi 4 Novembre]

L'énoncé du TP3 est disponible ici ==> TP3.pdf. Les fichiers supplémentaires (tRNAs.fasta, unknown.fasta) sont tous disponibles à ~dift3295/TP3.

Le TP est à faire en équipe de deux préférablement. Vous avez une semaine pour le faire. J'avais promis de le mettre en ligne le vendredi, mais suite à certaines complications ça n'a pas été possible. Je m'excuse, et pour cette raison, la remise est pour le mardi 14 Novembre avant le cours de 13h30 (~ ça reste négociable).

Le TP est très facile (pas de développement algorithmique) et il consiste à programmer une version très primitive de blast (~2/3h pour coder et répondre aux questions).


Démo 6 [Samedi 4 Novembre]

Au cours de la démo 6, je corrigerai l'examen intra. Vous aurez la possibilité de consulter vos copies au cours de la démo.

Je vais essayer de revenir sur KMP et parler brièvement de Aho-Corasick (Préparez vos questions sur le sujet). Il n'y a pas d'énoncé pour cette démo.


Complexité moyenne de Boyer-Moore-Horspool [Dimanche 5 Novembre]

J'ai reçu une question sur la complexité moyenne de BMH. Il y a un papier intéressant qui en parle: Baeza-Yates and Régnier, 1992.

TLDR: la complexité moyenne est linéaire, en fonction de la taille du texte.


Fusion de HSPs, TP3 [Jeudi 9 Novembre]

Comme expliqué en démo, certaines fusions de HSPs chevauchants ne sont pas possibles. Vous ne pouvez fusionner des HSPs chevauchants que si l'un représente la continuité de l'autre, ou s'ils sont identiques. Un exemple d'exception est illustré sur la figure suivante

Fusion de HSPs


Arbre des suffixes, Démo 7 [Lundi 13 Novembre]

L'énoncé (+ solutions/pistes de la démo 7 ) est disponibles à démo7.pdf.

Si vous désirez vous exercer pour les arbres de suffixes (qui seront probablement dans le final), j'avais fait ceci l'année passée pour les étudiants ==> SuffixTreeJS. Il s'agit d'une implémentation de l'algo de Ukkonen (donc linéaire) : détail sur le git-repo.


Exemple d'output de PLAST [Updaté]

Exemple 1
./plast -i 'GTCATGTTACGGCCATGAAAGTTGTGGGTTCAAGTCCTGCCA' -db tRNA.fasta -E 4 -ss 1e-3 --seed '111001101'

>R|acg|Chlorotetraedron_incus score: 42.0 ident: 100.0
GTCATGTTACGGCCATGAAAGTTGTGGGTTCAAGTCCTGCCA
GTCATGTTACGGCCATGAAAGTTGTGGGTTCAAGTCCTGCCA

# Best HSP:
id:R|acg|Chlorotetraedron_incus, score:210.00, bitscore:61.00, evalue: 5.72e-13
0   GTCATGTTACGGCCATGAAAGTTGTGGGTTCAAGTCCTGCCA  41
25  GTCATGTTACGGCCATGAAAGTTGTGGGTTCAAGTCCTGCCA  66 

----------------------------------------
total 1
Exemple 2
./plast -i 'GAAAATCCTCGTGTCACCAGTTCAAATCTGGTTCCTGGCA' -db tRNA.fasta -E 12 -ss 1e-1 --seed '110011' 


>F|gaa|Zea_mays_subsp_parviglumis score: 40.0 ident: 100.0
GAAAATCCTCGTGTCACCAGTTCAAATCTGGTTCCTGGCA
GAAAATCCTCGTGTCACCAGTTCAAATCTGGTTCCTGGCA

# Best HSP:
id:F|gaa|Zea_mays_subsp_parviglumis, score:200.00, bitscore:58.00, evalue: 4.36e-12
0   GAAAATCCTCGTGTCACCAGTTCAAATCTGGTTCCTGGCA  39
33  GAAAATCCTCGTGTCACCAGTTCAAATCTGGTTCCTGGCA  72 

----------------------------------------

>F|gaa|Mesostigma_viride score: 22.0 ident: 77.5
GAAAATCCTTGTGTCAGTGGTTCAAATCCACTTTCAGGCA
GAAAATCCTCGTGTCACCAGTTCAAATCTGGTTCCTGGCA

# Best HSP:
id:F|gaa|Mesostigma_viride, score:104.00, bitscore:31.00, evalue: 5.85e-04
0   GAAAATCCTCGTGTCACCAGTTCAAATC  27
33  GAAAATCCTTGTGTCAGTGGTTCAAATC  60 

----------------------------------------

>F|gaa|Marchantia_polymorpha score: 18.0 ident: 82.1428571429
GAAAATCCTTGTGTCAGTGGTTCGAATC
GAAAATCCTCGTGTCACCAGTTCAAATC

# Best HSP:
id:F|gaa|Marchantia_polymorpha, score:95.00, bitscore:29.00, evalue: 2.34e-03
0   GAAAATCCTCGTGTCACCAGTTCAAATC  27
34  GAAAATCCTTGTGTCAGTGGTTCGAATC  61 

----------------------------------------

>F|gaa|Ourococcus_multisporus score: 22.0 ident: 76.1904761905
GAAAATCCTTGTGTCGTTC-GTTCAAATC-GAACTCTTGGCA
GAAAATCCTCGTGTC-ACCAGTTCAAATCTG-GTTCCTGGCA

# Best HSP:
id:F|gaa|Ourococcus_multisporus, score:95.00, bitscore:29.00, evalue: 2.34e-03
0   GAAAATCCTCGTGTCACCAGTTCAAATC  27
32  GAAAATCCTTGTGTCGTTCGTTCAAATC  59 

----------------------------------------

>F|gaa|Carica_papaya score: 18.0 ident: 82.1428571429
GAAAATCCTTGTGTCAGTGGTTCGAATC
GAAAATCCTCGTGTCACCAGTTCAAATC

# Best HSP:
id:F|gaa|Carica_papaya, score:95.00, bitscore:29.00, evalue: 2.34e-03
0   GAAAATCCTCGTGTCACCAGTTCAAATC  27
34  GAAAATCCTTGTGTCAGTGGTTCGAATC  61 

----------------------------------------

>F|gaa|Mychonastes_homosphaera score: 19.0 ident: 72.0930232558
GAAGCTCCTTGTGTCGTTC-GTTCAAATC-GGACT-CTAGGCA
GAAAATCCTCGTGTC-ACCAGTTCAAATCTGG-TTCCT-GGCA

# Best HSP:
id:F|gaa|Mychonastes_homosphaera, score:92.00, bitscore:28.00, evalue: 4.68e-03
0   GAAAATCCTCGTGTCACCAGTTCAAATCTGGTTCCTGGCA  39
32  GAAGCTCCTTGTGTCGTTCGTTCAAATCGGACTCTAGGCA  71 

----------------------------------------

>Y|gta|Arabidopsis_thaliana score: 16.0 ident: 80.7692307692
AAATCCTTGTGTCAGTGGTTCGAATC
AAATCCTCGTGTCACCAGTTCAAATC

# Best HSP:
id:Y|gta|Arabidopsis_thaliana, score:86.00, bitscore:26.00, evalue: 1.87e-02
0   GAAAATCCTCGTGTCACCAGTTCAAATC  27
35  GTAAATCCTTGTGTCAGTGGTTCGAATC  62 

----------------------------------------

>F|gaa|Chromochloris_zofingiensis score: 17.0 ident: 79.3103448276
GAAAATCCTTGTGTCGTTC-GTTCAATTC
GAAAATCCTCGTGTC-ACCAGTTCAAATC

# Best HSP:
id:F|gaa|Chromochloris_zofingiensis, score:86.00, bitscore:26.00, evalue: 1.87e-02
0   GAAAATCCTCGTGTCACCAGTTCAAATC  27
32  GAAAATCCTTGTGTCGTTCGTTCAATTC  59 

----------------------------------------

>I|gat|Mesostigma_viride score: 17.0 ident: 75.7575757576
GATAAGCGTATTGTCAGTAGTTCAAATCTGCTT
GAAAATCCTCGTGTCACCAGTTCAAATCTGGTT

# Best HSP:
id:I|gat|Mesostigma_viride, score:85.00, bitscore:26.00, evalue: 1.87e-02
0   GAAAATCCTCGTGTCACCAGTTCAAATCTGGTTCC  34
34  GATAAGCGTATTGTCAGTAGTTCAAATCTGCTTGG  68 


----------------------------------------
Total :  9




Update exemple [Jeudi 16 Novembre]

Je viens de mettre à jour l'output pour l'exemple 2. Notez en effet que l'algo à implémenter est une heuristique en partie à cause de l'algorithme glouton pour l'extension des HSPs. Ne vous attendez donc pas à obtenir exactement les mêmes résultats que moi.

Pour l'exemple 2, vos séquences doivent se retrouver dans celle affichées plus haut.


Démo 8 [Vendredi 17 Novembre]

L'énoncé de la démo 8 est disponible ici==> demo8.Elle porte sur la phylogénie.

TP4 [Lundi 20 Novembre]

L'énoncé du TP4 et les autres fichiers du TP sont disponibles ici ==> TP4. Vous pouvez commencer par faire la partie de la représentation d'arbres à partir de newick. J'expliquerai plus en détail le reste du TP plus tard.


Démo 9 [Vendredi 24 Novembre]

L'énoncé de la démo 9 est disponible ici==> demo9. Elle continue la phylogenie avec l'algorithme Neighbor Joining et les algos de Parcimonie. Notez que nous finirons la demo8 avant de commencer cette dernière. Dans le cas éventuel ou la démo ne sera pas fini, j'ai ajouté des pistes de solutions dans l'énoncé. Certains points sur le TP4 (distance RF, newick, NJ) seront aussi abordés.


Notes TP2 [Vendredi 24 Novembre]

Vos notes pour les TP2 sont disponibles sur remise et studium. Espérez les notes pour le TP3 au plus tard le Mercredi prochain


Arbre et Newick [Lundi 27 Novembre]

Voici une liste de package pour la gestion d'arbre:
  1. ETE [python] ==> http://etetoolkit.org/ | https://github.com/etetoolkit/ete (que je conseille)
  2. Dendropy [python] ==> https://pythonhosted.org/DendroPy/
  3. Bio.phylo [python] ==> https://github.com/biopython/biopython (Biopython fait beaucoup de choses et comprend un module Bio.phylo pour la phylogénie)
  4. libnewicktree [java] ==> https://github.com/cjb/libnewicktree
  5. Forester [java] ==> https://sites.google.com/site/cmzmasek/home/software/forester
  6. Biojava [java] ==> https://github.com/biojava/biojava (contient en faite un wrapper de Forester)
  7. Vous pouvez picker du code ici pour parser le newick et utiliser votre propre structure d'arbre ===> http://epicscotland.github.io/Broadwick/jacoco/broadwick.phylo/NewickTreeParser.java.html
  8. Spimap [C++] ==> http://compbio.mit.edu/spimap/pub/spimap/src/ (vous trouverez les extraits de codes pour parser du newick et représenter des arbres)
Bref si vous cherchez correctement, vous trouverez une liste importante de librairies, quelque soit votre language. Assurezz vous d'ajouter les dépendances dans votre programme si possible (pour python, ajouter juste un requirements.txt).

Démo 10 [Jeudi 7 Décembre]

Voici l'énoncé de la démo 10 sur les inversions (correction partielle) ==> demo10. N'oubliez pas que vous avez un TP à rendre ce vendredi!

Bonne chance pour l'examen et la suite de votre bac.


Disponibilité - Question Examen [Lundi 11 Décembre]

Je serai exceptionnellement disponible ce Mardi (12) à l'heure normal du cours, et le Jeudi (14) entre 11h-17h pour répondre à vos questions. Notez que je ne serai pas présent le Vendredi et probablement pas le Lundi prochain (18).