TP1 - Assemblage de séquences 🧬

Figure 1 : Graphe de chevauchement entre les reads (seuil = 80).

Présentation

Ce projet a été réalisé dans le cadre du cours IFT3295 et porte sur l’assemblage de séquences ADN à partir de fragments (reads) produits par un séquenceur.
L’objectif est de reconstruire la séquence complète du gène étudié, d’en identifier les introns et d’analyser la structure secondaire d’un ARN.

---

Objectifs du TP

1. Développer un algorithme de programmation dynamique pour calculer le chevauchement maximal entre deux séquences ADN.
2. Utiliser cet algorithme pour assembler un ensemble de fragments (reads) et obtenir la séquence génomique complète.
3. Identifier la position et la structure du gène X dans cette séquence, en traduisant les cadres de lecture et en recherchant les introns.
4. Étudier le repliement d’un ARN en tiges-boucles à l’aide d’un algorithme optimisant les appariements de bases.

---

Étapes principales

1. Chevauchement de séquences (25 pts)

• Implémentation d’un alignement local modifié où seules les extrémités des séquences sont considérées (chevauchement).
• Utilisation de la programmation dynamique pour calculer le score maximal de chevauchement entre deux reads :
  • match = +4
  • mismatch = -4
  • indel = -8
• Le programme retourne :
  • le score maximal
  • la longueur du chevauchement
  • les alignements correspondants
• Entrée : fichier FASTQ contenant les deux séquences.

---

2. Assemblage de fragments (40 pts)

• Calcul de la matrice 20x20 des scores de chevauchement entre tous les reads du fichier reads.fq.
• Construction du graphe orienté de chevauchement G = (V, E) :
  • Un nœud par read.
  • Une arête (Ri, Rj) si un suffixe de Ri chevauche un préfixe de Rj.
• Application de :
  • Un filtrage par score (seuil ≥ 80).
  • Une réduction transitive pour simplifier le graphe.
• Détermination de :
  • L’ordre d’assemblage des reads.
  • La séquence génomique finale et sa longueur.

---

3. Recherche d’introns et identification du gène X (20 pts)

• Traduction de la séquence génomique dans les trois cadres de lecture pour repérer la position du codon start de la protéine X.
• Développement d’un algorithme de programmation dynamique pour aligner la séquence génomique et la séquence protéique :
  • Minimisation du nombre d’introns.
  • Autorisation des mismatches dans les exons (mais pas d’indels).
• Utilisation de BLASTp et/ou UniProt pour :
  • Identifier le nom de la protéine X.
  • Déterminer sa fonction biologique.

---

4. Repliement d’ARNs (15 pts)

• Implémentation d’un algorithme pour prédire le repliement optimal d’une séquence d’ARN.
• Les appariements valides sont :
  • A-U
  • G-C
• Bonus : Développement d’un algorithme en O(n³) maximisant le nombre d’empilements (paires (i,j) telles que (i+1, j-1) sont aussi appariées).

---

Langage et exigences

• Langage recommandé : Python
• Librairies autorisées :
  • NetworkX (pour la construction et la visualisation du graphe)
  • Aucune librairie externe d’alignement n’est permise
• Fichier à fournir :
  • main.py (ou équivalent)
  • requirements.txt (avec pip freeze > requirements.txt)
  • Rapport PDF pour les questions théoriques

---

Auteur

• Josué Mongan

GitHub : Josh012006

• David Stanescu

GitHub : DavidStanescu13

---