Post on 24-Jan-2016
description
UNIVERSITATEAPOLITEHNICA TIMIŞOARA
UNIVERSITATEAPOLITEHNICA TIMIŞOARA
MASTER SIIS MASTER SIIS
Sisteme Informatice în Îngrijirea Sisteme Informatice în Îngrijirea Sănătății Sănătății
1
www.medinfo.umft.ro/www.medinfo.umft.ro/dimdim/bioinformatica.htm/bioinformatica.htm
2
BIOINFORMATICABIOINFORMATICA
Prof Dr George I MihalaProf Dr George I Mihalaşş
UMF Victor BabeşUMF Victor Babeş
3
CURSUL 9CURSUL 9
4
ALINIEREA MULTIPLĂALINIEREA MULTIPLĂ
MSAMSA
““MULTIPLE SEQUENCE MULTIPLE SEQUENCE ALIGNEMENT”ALIGNEMENT”
5
Scop şi Motivaţie Scop şi Motivaţie pentru MSApentru MSA
PROBLEMA:
Fiind date:- un set de mai mult de 2 secvenţe- o metodă de scor pentru o aliniere,
să se determine corespondenţele între secvenţe astfel încât scorul de aliniere să fie maxim.
6
•Motivaţie:
– Stabilirea datelor de intrare pentru analiza filogenetică
– Determinarea istoriei evolutive a unui set de secvenţe (în ce punct au apărut anumite mutaţii?)
– Descoperirea unui “motiv” comun într-un set de secvenţe (ex secvenţe de ADN care leagă aceeaşi proteină)
– Caracterizarea unui set de secvenţe (ex o familie de proteine)
– Construcţia profilelor pentru căutarea bazelor de date de secvenţe (PSI-BLAST)
7
Ex: Aliniere Multiplă a Domeniului SH3Ex: Aliniere Multiplă a Domeniului SH3
• Domeniu scurt (60 AA)
• Prezent în enzime (kinaze, fosfolipaze etc)
• Cca 300 în genomul uman
8
ReprezentReprezentăriări• Pe coloane
• Cu simboluri
9
Scoruri pentru MSAScoruri pentru MSA
• Ipoteză: coloanele individuale ale unei alinieri sunt independente
• Formulă:
• Metode:– Suma perechilor (SP)
– Entropia minima
10
Suma perechilorSuma perechilor
• Calculează suma scorurilor din alinierea perechilor
11
ExempluExemplu
• 5 secvențe ADN și matricea de substituție
• Calculul sumei S(3)
Notăm: S12 = s(m31, m3
2)
S(3) = S12 + S13 + S14 + S15 + + S23 + S24 + S25 + + S34 + S35 + + S45 =
= s(g,a) + s(g,a) + s(g,-) + s(g,c) +
+ s(a,a) + s(a,-) + s(a,c) + + s(a,-) + s(a,c) + + s(-,c) =
= (-1 -1 -3 -2) + (+4 -3 -2) + (-3 -2) + (-3) = -7 -1 -5 -3 = -16
12
Entropia Minimă (i)Entropia Minimă (i)
• Ideea de bază: încercarea de minimizare a entropiei fiecărei coloane
• [sunt “bune” coloanele ce pot fi comunicate cu puţini biţi]
• Teoria informaţiei: codul optim foloseşte
- log2 p
biţi pentru a codifica un mesaj cu probabilitatea p.
13
Entropia Minimă (ii)Entropia Minimă (ii)
• Mesajul este considerat pe coloană• Entropia unei coloane este:
14
Programare dinamicăProgramare dinamică
• Generalizare a alinierii a două secvenţe– Se consideră o matrice de dimensiune “k” pt k secvenţe
– Fiecare element reprezintă scorul pentru k secvenţe (în loc de două)
• Pentru k secvenţe de lungime n, complexitatea spaţiului este O(nk)
15
Metode Euristice de AliniereMetode Euristice de Aliniere
• Alinierea Progresivă: construcţia unei succesiuni de alinieri perechi:– Abordare “stea”
– Abordare “arbore” (CLUSTALW)
• Rafinare iterativă – dat fiind o aliniere multiplă:– Se elimină o secvenţă care se realiniază la profilul altor
secvenţe
– Se repetă până la convergenţă
16
MMatricea coeficienatricea coeficienților în ților în alinierea progresivăalinierea progresivă
• Pași în Alinierea Progresivă – se aliniază secv. X1 cu X2 (notat Y) profilul Xp2
– se aliniază profilul Xp2 cu X3 (notat Y) profilul Xp3
– se aliniază profilul Xp3 cu X4 (notat Y) profilul Xp4 …
– OBS: matricea de substituție conține și“conservarea gap-urilor”
– Ex: fie secvențele c g g a – t g
– t g a - - t t
– a c g t -
17
Modelul “stea”Modelul “stea”• Se dau k secvenţe a fi aliniate: X1, …, Xk
• Se alege o secvenţă Xc ca şi “centru”
• Pentru fiecare Xi ≠ Xc se determină între Xi şi Xc o aliniere optimală
• Se reunesc alinierile perechi• Rezultatul – alinierea multiplă rezultă din agregare• Alegerea centrului:
– Se încearcă fiecare secvenţă ca centru, se ia cea mai bună aliniere multiplă
– Se calculează toate alinierile perechi şi se alege şirul Xc care maximizează
18
Ex: modelul “stea” (i)Ex: modelul “stea” (i)
19
Ex: modelul “stea” (ii)Ex: modelul “stea” (ii)
20
Modelul “arbore”Modelul “arbore”
• Ideea de bază: se organizează alinierea folosind un “arbore ghid” (guide tree)– Frunzele reprezintă secvenţele
– Nodurile interne reprezintă alinieri
• Alinierile se determină pornind de la bază în sus– Alinierea multiplă rezultă la rădăcina arborelui
• O variantă uzuală: CLUSTALW (Thompson, 1994)
21
Ex: modelul arboreEx: modelul arbore
22
Alinierea Progresivă în CLUSTALWAlinierea Progresivă în CLUSTALW
• În funcţie de nodul intern din arbore, putem avea de aliniat:– O secvenţă cu o secvenţă
– O secvenţă cu un profil (aliniere parţială)
– Un profil cu un profil
• În toate cazurile putem folosi DP – Programarea Dinamică– Pentru cazul profilelor se recomanda scorul SP
23
24
PAUZAPAUZA
25