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

BIOINFORMATICA

Prof Dr George I MihalaProf Dr George I MihalaşşUMF Victor BabeşUMF Victor Babeş

3

CURSUL 8

4

COMPARAREA A DOUĂ COMPARAREA A DOUĂ SECVENŢE (III)SECVENŢE (III)

5

Potriviri repetate (Repeated matches) Potriviri repetate (Repeated matches) [i][i]

• Aplicaţii– Găseşte copii (nesuprapuse) ale unei secţiuni care se

repetă (există domenii numite “motive”)

6

Potriviri repetatePotriviri repetate [ii] [ii]

• Aspecte teoretice– Se ia un prag T (threshold)– Se reţin doar secvenţele pentru care se ajunge la scoruri > T– Prima linie F(i,0) = max [F(i-1,0),

F(i-1,j)-T, pt. j=1,…,m]– La F(i,j), în loc de 0 punem F(i,0)

• Comentarii– T mare – poate exclude potriviri– T mic – divizează secvenţele ca să găsească şi potriviri slabe

7

Potriviri suprapuse (Overlap matches)Potriviri suprapuse (Overlap matches) [i] [i]

• Aplicaţii– Când ne aşteptăm ca o secvenţă să o conţină pe cealaltă,

sau să se suprapună parţial– La compararea fragmentelor genomice de ADN– La compararea unor secvenţe cromozomale mari

8

Potriviri suprapusePotriviri suprapuse [ii] [ii]

• Aspecte teoretice– Nu se penalizează gap-urile de la margini– Marginile se iniţializează cu 0 şi se aplică algoritmul N-W– Se setează maximul Fmax la valoarea maximă de pe linia de jos sau coloana

din dreapta– “traceback” începe de la Fmax până la marginea de sus

sau stânga– Există versiune cu “repeat”:

F(i,0) = max [F(i-1,0), F(i-1,m)-T]

9

Potriviri hibride (Hybrid mPotriviri hibride (Hybrid matchatch conditions) conditions)

• Aplicaţii– Fiecare variantă are avantaje şi dezavantaje– Exemple ce necesită abordări specifice:

• O secvenţă repetitivă tinde să fie găsită în copii tandem neseparate • Căutăm secvenţe ce încep la startul ambelor secvenţe dar se pot

termina în orice punct• Avem probabilitate mare ca o secvenţă să fie regăsită integral în alta,

dar şi o probabilitate de a găsi numai un segment (căutări în familii)

– Este bine să ştim ce potriviri căutăm• Aspecte teoretice

– Cazurile standard sunt limitate, dar putem găsi ceva apropiat– Se pot face “postprocesări”

10

Programare dinamică – modele complexeProgramare dinamică – modele complexe

• Aplicaţii– Gap-urile sunt adesea “în lanţ”

• Aspecte teoretice – Tipuri de penalizare gap:

• Liniară γ(g) = - g d (g = nr.gap-uri, d = penalizare 1 gap)• Gap-uri afine: γ(g) = - d – (g-1) e (e = penalizare gap în lanţ; e << d)

– Modificarea relaţiilor de recurenţă– “Automate cu stări finite”, modele complexe

• Scoruri diferite la substituţie în diverse regiuni (transmembranar, intracelular, extracelular)

– Metode euristice - BLAST

11

MATRICIMATRICI DE DE

SUBSTITUȚIESUBSTITUȚIE

12

Matrici de substituţie Matrici de substituţie pentru proteine [i]pentru proteine [i]

A. Matrici PAM – Percent Accepted Mutations

• Ipoteză Ipoteză – fiecare schimbare a unui AA este independentă de alte schimbări anterioare

• Calculul matricilor PAM (Margaret Dayhoff, 1978)– Au fost evaluate 1572 schimbări în 71 grupe de secvenţe proteice cu

similaritate cel puţin 85%– PAM1 – se acceptă 1 mutaţie la 100 AA– PAM10 – 10 mutaţii, etc– PAM-N = PAM1 x PAM1 x … de N ori

• Folosire în funcţie de procent de similaritate– PAM250 pt 20%, PAM120 / 80 / 60 pt 40%, 50%, 60%

13

14

15

• Exprimare cu “log odds”• Fiecare celulă = log OR (scor aditiv)

OR = p(AA1mAA2) / fr(AA1)= frecv.rel.a schimbării

16

B. Matrici BLOSUM

- Blocks (Amino Acid) Substitution Matrices - Stephen şi Georgia Henikoff (1992)- Pe baza a 2000 patternuri de AA organizaţi în blocuri- (blocuri – semnăturile unor familii de proteine)- BLOSUM50,60,80 – secvenţe 50% (60%, 80%) similare, etc

s(a,b) = (1/λ) log [p(a,b) / fa fb]

17

• Blosum62

18

Matrici de substituţieMatrici de substituţiepentru Acizi Nucleicipentru Acizi Nucleici [ii][ii]

• Matrici pentru Acizi nucleici– bazate pe modele de evoluţie / substituţie

a nucleotidelor

A) Modelul Jukes-Cantor– rate uniforme la mutaţii

B) Modelul Kimura– rate diferite la mutaţii

19

• Modelul Kimura

- tranziţiitranziţii (conservă purină/pirimidină), - rata α

- transversiitransversii – rate mai mici β < α

20

Aspecte StatisticeAspecte Statistice

21

Testarea semnificaţiei alinieriiTestarea semnificaţiei alinierii

Distribuţia Poisson (Gumbel)

E = K m n e- λS

E = nr alinieri cu scor min. Sm, n = lungimile secvenţelorK, λ = parametrii statistici ai S

S = 10 log x

22

Semnificaţia alinierii - NormalizareSemnificaţia alinierii - Normalizare

- Nr bits (log2) de informaţie în scor- Nr nats (ln)• Conversia la biţi:

S’ = (λ S – ln K) / ln 2E = m n 2- S’

• Valori P – probabilitatea de a obţine S la întâmplare

P = 1 – e –E ~ e –E • Determinarea rapidă a semnificaţiei

– Uzual K = 0.1, λ este precalculat în PAM şi BLOSUM– Ex: matricea log odds în biţi:

λ = ln 2 şi prag = ln (mn)23

24

PAUZAPAUZA

25