Alinhamento de Sequencia DNA

  • Published on
    15-Jun-2015

  • View
    229

  • Download
    0

Embed Size (px)

DESCRIPTION

Alinhamento de sequencia de DNA usando programao dinmica.

Transcript

<ul><li> 1. Comparar sequncias Recuperao de Informao: dada uma chave, buscar em um dicionrio por palavras que se assemelham chave. Biologia Molecular: dadas duas sequncias de DNA, identificar se so semelhantes. Para que serve? </li></ul> <p> 2. Por que alinhamos sequncias ? Comparar genes de DNA Estudar a estrutura de protenas Estudar evoluo molecular Deteco de doenas, vrus, etc. 3. Um alinhamento de duas sequncias de caracteres e obtido inserindo-se espaos (gaps) nas sequncias e ento colocando-se uma sobre a outra de modo que cada caractere ou espao esteja emparelhado a um nico caractere (ou a um espao) da outra cadeia. Exemplo: Sequncias: = AAACTGCACAATCTTAATGCCCTTTTAT = GCGGATCAACTTATTCCATCTCTT Alinhamento: = AAACTGCA-CAATCTTAATGCC--CTTTTAT =--GC-GGATCAA-CTT-ATTCCATCTCTT-- 4. Ex: match +1 (good) mismatch -1 (bad) gap -2 (worse) G A - C G G A T T A G G A T C G G A A T A G score = 9 1+ 1(-1) + 1(-2) = 6 O score que a soma dos valores associados a cada posio, de acordo com o grau de similaridade entre os elementos correspondentes. Clculo do Score 5. Problema: Alinhamento de duas cadeias de caracteres. Entrada: Duas cadeias de caracteres Sada: O alinhamento ideal das cadeias, possivelmente incluindo as lacunas gaps. 6. 1. Subestrutura tima Sendo assim, h trs alternativas possveis para resolver o problema: i) (m, n) M ii) a m-sima posio de X M iii) a n-sima posiao de Y M Caso ocorra o caso (i), teremos OPT(m, n) = XmYn + OPT(m -1, n -1). Caso ocorra o caso (ii), teremos que pagar o custo de um intervalo desde a m- sima posio de X que no foi encontrada e alinhar X1, X2, ..., Xm-1 bem como Y1, Y2, ..., Yn. Deste modo teremos: OPT(m, n) = + OPT(m -1, n). Caso ocorra o caso (iii), ser semelhante ao caso (ii), porm: OPT(m, n) = + OPT(m, n -1). 7. 2. Expresso Recursiva i * se j=0 j * se i=0 OPT(i,j) MAX [XiYj + OPT(i -1, j -1), + OPT(i -1, j), + OPT(i, j -1)] gap (custo pelo espao) XiYj custo de emparelhar Xi e Yj 8. 3. Algoritmo utilizando a fora bruta (RECURSIVO) 1. Alinhamento_recursivo(X,m,Y,n) 2. If m = 0 3. then return n* 4. If n = 0 5. then return m* 6. A = XiYj + Alinhamento_recursivo(X,m-1,Y,n-1) 7. B = + Alinhamento_recursivo(X,m-1,Y,n) 8. C = + Alinhamento_recursivo(X,m,Y,n-1) 9. return max (A,B,C) 9. A complexidade para o algoritmo alinhamento_recursivo(X,i,Y,j) baseado na expresso recursiva : T(m,n) = T(m-1,n-1) + T(m,n-1) + T(m-1,n) + (1) T(m,n) 3T(m-1,n-1) + (1) T(m,n) = (3min(m,n) ) Ordem exponencial! 3.1 Anlise do algoritmo alinhamento_ recursivo 10. 3.2 Algoritmo Utilizando Programao Dinmica 1. Alinhamento_PD(X,Y,) 2. Initialize A[i,0] = i* for i = 0, ..., m 3. Initialize A[0,j] = j* for j = 1, ..., n 4. For i = 1, ..., m 5. For j = 1, ..., n 6. A[i,j] = max (XiYj + A[i -1, j -1], + A[i -1, j], + A[i, j -1]) 7. Endfor 8. Endfor 9. Return A[m,n] 11. A complexidade para o algoritmo Alinhamento_PD (m*n), pois o tempo de preencher a matriz A. Este custo est expresso nas linhas 3 5 do algoritmo Alinhamento_PD(X,Y,). As demais linhas tm tempo constante, ou seja, (1). O espao ocupado (m*n), pois o tamanho da matriz (m+1)*(n+1). Tempo de execuo (m*n) 3.3 Anlise do algoritmo Alinhamento_PD(X,Y,) 12. 4. Algoritmo para mostrar a soluo tima 13. Matches: (+1) Mismatches: (-1) Gaps: (-1) Para alinhar as sequencias (traceback) comea-se na ltima entrada da matriz, onde est o score, e percorre-se a matriz pelos precedentes diretos de cada clula, at a posio inicial da matriz. As regras de alinhamento so dadas pela orientao relativa das setas: Diagonal: xi alinha com yi; Vertical: yi alinha com espao; Horizontal: xi alinha com espao. 14. entrada rec pd 5 0,01 0,011 10 0,086 0,011 15 406,265 0,01 16 2290,402 0,011 17 12069,45 0,012 18 0,011 19 0,01 20 0,011 15. Diferentesaplicaes,diferentesformasde soluo. Algoritmorecursivotemtempoexponencial. ProgramaoDinmicaofereceumasoluo emtempopolinomial. 16. T.H.Cormen,C.E.Leiserson,andR.L.Rivest,Introductiontoalgorithms,1st ed.,TheMITPress,1990. V. Bafna, E. L. Lawler, and P. A. Pevzner, Approximation algorithms for multiplesequencealignment,TheoreticalComputerScience182(1997),233 244. Freitas,AnaT.,AlinhamentodeSequncias,Guiado2oLaboratriode BiologiaComputacional,Outubrode2007. P.BonizzoniandG.D.Vedova,Thecomplexityofmultiplesequence alignmentwithSP-scorethatisametric,TheoreticalComputerScience259 (2001),6379. </p>