universitatea politehnica timiŞoara
Post on 13-Jan-2016
44 Views
Preview:
DESCRIPTION
TRANSCRIPT
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
top related