Devoir 5

Date limite de remise: lundi le 14 avril 2003, 18:00. Si votre devoir est remis avant 18:00, le 11 avril (vendredi), vous obtenez 5 points de boni, et le devoir sera corrigé avant lundi.

1. Parcimonie pondérée (15 points)

Donnez un algorithme qui minimise la valeur de parcimonie pondérée sur un arbre. Soit S une matrice de pondération de substitutions sur un alphabet A de taille m. (Le probléme de base considéré dans le cours utilise S(i,j)=0 si i=j et =1 sinon.) Soit T une phylogénie avec n feuilles où chaque noeud u est étiqueté par un caractère cu de A. La valeur de parcimonie sur cet arbre est égale au somme des valeurs S(cu, cv) sur les branches uv. L'algorithme doit trouver les meilleurs caractères cu ainsi que la valeur de parcimonie minimale sur l'arbre. Démontrer que l'algorithme est correct. Analysez son temps et espace de calcul en fonction de n et m.

2. Analyse de données d'expression de gènes (20 points)

Dans cet exercice vous travaillez avec des données d'une expérince classique. Il s'agit d'une étude sur le cancer du sein, décrite dans l'article de Perou et al. Distinctive gene expression patterns in human mammary epithelial cells and breast cancers, Proceedings of the National Acadamy of Sciences of the USA, vol. 96, pages 9212-9217, 1999. Vous pouvez télécharger l'article à partir du site du journal. Tout d'abord, lisez l'article. Les données sont accessibles au site du Stanford Breast Cancer Microarray Project.

a.   Les données pour chaque échantillon sont stockées dans un fichier texte. Dans cet exercice vous travaillez avec les fichiers pour les échantillons de BC4 (copie locale), BC14 (copie locale), BC21 (copie locale), -EGF (copie locale), et +Matrigel (copie locale). Chaque fichier et de taille 1.3M. Le tableau de chaque fichier contient les données pour une expérience: chaque rangée correspond à une sonde (spot). Familiarisez-vous avec le format du tableau, en lisant la déscription des colonnes. On veut travailler avec la valeur x5/x3x5 est la valeur du signal Cy5 après la sous-traction du bruit (background), et x3 et la même pour Cy3. Quelle colonne donne cette valeur? Soit v(s,p) la valeur observée pour sonde s sur puce p (p=BC4,BC14,BC21,-EGF,+Matrigel). Compilez un tableau qui donne le logarithme (base 2) de v(s,p) pour des sondes (s) avec nombres d'accession R11480, H46600, N92646, AA004872, T63045, H71488, AA100116 (attention: il est possible qu'il y a plusieurs sondes avec le même accession). Exemple (la colonne id sert seulement à distinguer entre des sondes avec accessions identiques) :

id  accno    BC4 BC14 BC21 -EGF +Matrigel
1   AA004872 2.4 5.7  6.0  0.15 12.1
2   T63045   1.1 2.6  10.2 18.2 1.15
... 

b.   Trouvez les entrées de Genbank pour ces nombres d'accession: ce sont des ESTs (Expressed Sequence Tags), donnez les génes qui y correspondent (PUTATIVE ID). Trouvez les clusters auxquels ils appartiennent selon l'article (Figure 2, clusters A,B,C et D).

c.   Finalement, calculez un clustering hiérarchique agglomeratif sur les colonnes du tableau par la méthode de Eisen ( Eisen et al. Cluster analysis and display of genome-wide expression patterns, PNAS vol. 95, pages 14863-14868, 1998). Dans cette approche, la similarité de deux vecteurs (clusters ou feuilles) est calculée par la correlation de Pearson. Donnez un tableau de similarités entre les colonnes (tableau de taille 5*5). Montrez chaque étape dans le calcul du clustering. Est-ce que votre arbre correspond à celui de l'article?

Vous pouvez faire tous les calculs à l'aide d'un logiciel comme Excel. Pour extraire les rangées pour des sondes avec accession AA99999, vous pouvez taper awk -F '[\t]+' '$4 == "AA99999" {print ;}' < fichier.txt sous Unix.

3. Chevauchement exact (15 points)

Soit S et T deux séquences de longueurs n et m. Donnez un algortihme qui calcule le plus grand chevauchement exact entre les deux en temps O(n+m). On a un chevauchement exact de longueur t si S[1 ... t]=T[m-t+1 ... m] ou si T[1 ... t]=S[n-t+1 ... n]. L'algorithme doit trouver la valeur maximale de t, ainsi que spécifier si le chevauchement et entre le préfixe de S et le suffixe de T ou vice versa. (Les techniques de recherche exacte peuvent vous aider à trouver un algo.)