Stéphane Grandcolas
Laurent
Tichit
L'objectif de ce projet est de programmer une application permettant, à partir d'un ensemble de séquences (nucléiques ou protéiques) présumées homologues, de visualiser l'arbre phylogénétique représentant l'évolution de ces séquences.
On possède un fichier contenant des séquences. Ce fichier est au format FASTA.
La première étape est de calculer une distance entre chaque paire de séquences et de produire ainsi une matrice de distances
Cette matrice de distances va nous permettre de construire un arbre phylogénétique. L'idée est de regrouper dans le même sous-arbre les séquences proches
Une fois notre arbre produit, nous allons le visualiser (en format texte)
Chacune de ces étapes devrait permettre de produire un fichier intermédiaire. De cette façon il vous sera possible de réaliser trois programmes indépendants, plus faciles à tester. Il vous sera donc nécessaire de maîtriser les entrées/sorties de haut niveau en C (FILE, fopen, fclose, fprintf, fscanf, stderr, fgets de <stdio.h>). Vous devrez en outre manipuler des chaînes de caractères. Les fonctions relatives aux chaînes (strcat, strcpy, strcmp, strlen de <string.h>) vous seront peut-être également utiles.
Dans ce répertoire, vous trouverez un ensemble de fichiers de données permettant de tester vos programmes.
Quantifier le degré de similarité entre deux objets est une opération relativement commune. Toute la difficulté réside dans le choix du critère de comparaison. Il existe plusieurs façons de mesurer la distance entre deux séquences. La plus connue est l'alignement de séquences. Intuitivement, l'objectif est d'essayer de « faire correspondre » le mieux possible les séquences l'une sur l'autre, en insérant éventuellement des gaps dans l'une et l'autre.
Exemple : distance entre ARCACHON et MARATHON.
Meilleur alignement possible :
-ARCACHON MAR-ATHON
Distance = 3 (insertion du M, suppression du C, mauvaise correspondance entre C et T).
Le but est de calculer une distance entre chaque paire de séquences et de produire un fichier contenant cette matrice au format Phylip.
7 C1 0.0000 0.0549 0.0703 0.2196 0.1673 0.0549 0.0701 C2 0.0549 0.0000 0.0286 0.2206 0.1742 0.0435 0.0507 C3 0.0703 0.0286 0.0000 0.2072 0.1834 0.0511 0.0508 C4 0.2196 0.2206 0.2072 0.0000 0.2498 0.1986 0.1975 C5 0.1673 0.1742 0.1834 0.2498 0.0000 0.1621 0.1656 C6 0.0549 0.0435 0.0511 0.1986 0.1621 0.0000 0.0587 C7 0.0701 0.0507 0.0508 0.1975 0.1656 0.0587 0.0000
Pour le calcul de la distance, vous pouvez choisir l'algorithme de votre choix. Commencez par quelque chose de simple (composition en acides de vos séquences). Vous pourrez toujours améliorer ça par la suite avec l'alignement de séquences utilisant des scores de substitution tirés des matrices PAM ou Blosum.
A partir d'un fichier de matrice au format Phylip, nous allons utiliser un algorithme de partitionnement hiérarchique ascendant (par exemple UPGMA) permettant de regrouper itérativement des partitions.
Au départ, chaque partition contient un seul taxon. A chaque étape, les deux partitions les plus proches sont agrégées en une partition plus grande. La distance entre deux partitions A et B données peut-être définie par la moyenne de toutes les distances entre paires d'objets x de A et y de B (c'est le principe d'UPGMA). Vous pouvez aussi utiliser des critères plus grossiers.
Dans un premier temps il est demandé de ne pas tenir compte de la longueur des branches. Il sera toujours possible d'améliorer notre algorithme par la suite.
Un arbre peut se définir récursivement de la façon suivante :
Un arbre est :
Un nœud
Une liste (éventuellement vide) d'arbres.
On peut donc coder un arbre par un mot bien parenthésé : (B, (D, E)C)A est l'arbre ayant A pour racine. A possède 2 fils : B et C. C possède deux fils : D et E.
Le format de fichier à obtenir est le format Newick. Il s'agit aussi d'un format parenthésé, dans lequel apparaît aussi la longueur des branches. En voici un exemple :
(VR-V6:0.11682,VR-V8:0.06318,((VR-V1:0.06853,(VR-V2:0.01681, VR-V4:0.03669):0.03887):0.00814,((VR-V3:0.01653,(VR-V5:0.02734, VR-V5P:0.04446):0.00437):0.03987,VR-V7:0.06190):0.01172):0.00775);
Sur vos systèmes, vous pouvez lancer la commande: phylip drawgram, puis lui spécifier le nom d'un fichier au format Newick afin de visualiser un arbre phylogénétique (et tester que votre format de fichier est correct).
A partir d'un fichier au format Newick, le but de cette partie est de « dessiner » un sous-arbre de ce style :
+--1:Human
+-22
+-21 +--2:Chimp
| |
+-20 +-----3:Gorilla
| |
+----------19 +--------4:Orang
| |
+-18 +-----------5:Gibbon
| |
| | +--------6:Barbary Ma
| +-------------23
| | +-----7:Crab-e. Ma
-------17 +-24
| | +--8:Rhesus Mac
| +-25
| +--9:Jpn Macaq
|
+-------------------------10:Squir. Mon