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 7CURSUL 7

4

ANALIZA SECVENŢIALĂANALIZA SECVENŢIALĂ• Analiza unei secvenţe• Compararea a două secvenţe

– Metode simple: Dot Plots și Distanțe

– Programare dinamică• Aliniere globală

• Aliniere locală

– Modele complexe

• Matrici de substituție– Pentru Proteine

– Pentru Acizi nucleici

• Alinierea multiplă

5

COMPARAREA COMPARAREA A A DOUDOUĂ SECVENȚE (II)Ă SECVENȚE (II)

Programare Dinamică Programare Dinamică

6

Compararea a două secvenţe“Pairwise alignement”

• Măsurarea similarităţii, distanţe, substituţii, gap-uri

• Programare dinamică – Aliniere globală: algoritmul Needleman Wunsch

• Construcţia matricii

• “traceback”

– Aliniere locală: algoritmul Smith Waterman

– Potriviri repetate, suprapuse, hibride, complexe

• Matrici de substituţie– PAM

– BLOSUM

• Semnificaţia scorului de aliniere

• Lanţuri Markov

• Lanţuri Markov Ascunse (Hidden Markov Models HMM)7

Programare dinamicăProgramare dinamică• Compararea directă: 4m+n comparaţii• Aliniere:

– Globală - Needleman-Wunsch (1970)

– Locală• Smith-Waterman (1981)• Potriviri repetate• Potriviri suprapuse• Modele hibride

• Paşi:– Iniţializare– Completare– Aliniere (traceback)

8

ALINIEREA GLOBALĂAlgoritmul Needleman-Wunsch

• Aliniere globală• Matricea de programare dinamică

– Cele două secvenţe pe axe– Calculul unui element diagonal

F(i,j), i = indice prima secv (oriz) [i = coloană, j = linie]

9

Schema de scorPotrivire = +5Nepotrivire = -3Indel (gap) = -4

10

11

12

13

ALINIEREA LOCALĂAlgoritmul Smith WatermanAlgoritmul Smith Waterman

• Aplicaţii– Detecţie domenii comune în proteine

– Secţiuni extinse de ADN

– Foarte sensibil la detecţia similarităţii între secvenţe divergente(cu origine comună; doar o parte se păstrează)

• Aspecte teoretice– Marginile sunt 0

– Conţine numai valori 0 sau pozitive

– Alinierea se poate opri oriunde în matrice

– La “traceback” pornim nu din colţul dreapta-jos ci de la cea mai mare valoare 14

Algoritmul Smith WatermanAlgoritmul Smith Waterman - formalizare - formalizare

15

Completarea matriciiCompletarea matricii

- initializare cu 0- initializare cu 0- prima linie- prima linie- prima coloan- prima coloanăă

16

17

18

Ex.2Ex.2

19

PAUZAPAUZA

20