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/x3
où x5 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.)