Penalidade para lacunas

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Penalidade para lacunas[1] ou Penalidade para gaps[2] (gap penalty) são usadas durante o alinhamento de seqüências. O esquema de penalidade para lacunas contribui para a pontuação geral de alinhamentos e, portanto, o tamanho da penalidade para espaços em relação às entradas na matriz de similaridade afeta o alinhamento que é finalmente selecionado. Selecionando uma penalidade maior para lacunas ou espaços fará com que caracteres menos favoráveis sejam alinhados, buscando o algoritmo a evitar a criação de muitas lacunas.

Penalidade para Lacunas Constante[editar | editar código-fonte]

A Penalidade constante para lacunas é o tipo mais simples de penalidade para lacunas. O único parâmetro, w, é adicionado à pontuação do alinhamento quando a lacuna é aberta pela primeira vez. Isto significa que qualquer lacuna recebe a mesma penalidade, independentemente do seu tamanho.

Penalidade para Lacunas Linear[editar | editar código-fonte]

Penalidades para lacunas linear tem apenas um parâmetro, w, que é uma penalidade por unidade de comprimento[3] . Essa é quase sempre negativa, de modo que o alinhamento com menos lacunas é favorecido sobre o alinhamento com mais lacunas. Sob uma penalidade para lacunas linear, a penalidade total para uma lacuna grande é a mesma que para muitas lacunas pequenas.

Denotando a função linear por w(k), para k \geq 1, e a penalidade associada com uma lacuna de k espaços temos

w(k) = gk,

onde g é o valor absoluto do escore associado a um espaço.

Penalidade para Lacunas Afim[editar | editar código-fonte]

O modelo de penalidade para lacunas afim[Nota 1] penaliza inserções e deleções usando uma função linear em que um termo é o comprimento independente, e a outra é o comprimento dependente[4] . Algumas seqüências são mais propensas a ter uma grande lacuna, em vez de muitas lacunas pequenas. Por exemplo, uma seqüência biológica é muito mais propensa a ter uma grande lacuna de comprimento 10, devido a um único evento de inserção ou deleção, do que ter 10 pequenas lacunas de comprimento 1. Penalidades para Lacunas Afim usam uma penalidade de lacunas de abertura (opening), o, e uma penalidade de lacunas de extensão e. Uma lacuna de comprimento l é então dada uma penalidade o + (l-1)e. De modo que as lacunas são desencorajadas, o é quase sempre negativo. Porque algumas lacunas grandes são melhores do que muitas lacunas pequenas, e, apesar de negativo, quase sempre é menos negativo do que o, de modo a incentivar a extensão da lacuna, ao invés da introdução de uma lacuna.

Denotando a função afim por w(k), para k \geq 1, e a penalidade associada com uma lacuna de k espaços temos

w(k) = h + gk,

onde g é o valor absoluto do escore associado a um espaço, h + g é o custo do primeiro espaço e g é o custo dos espaços adicionais. Considera-se w(0) = 0. Desta forma podemos denotar a função como:


  w(k) =  
   \begin{cases}
    0 & \text{se } k = 0 \\
    h + gk & \text{se } k \ge 1 \\
   \end{cases}

Penalidade para Lacunas Não-Linear[editar | editar código-fonte]

Embora o modelo de penalidade para lacunas afim seja o mais comumente usado nos dias de hoje, alguns estudos indicam que penalidades para lacunas não-lineares podem trazer vantagens sobre o modelo afim[5] [6] [7] . Waterman em seu artigo infere que uma deleção de, por exemplo, 14 bases, não deveria ser pensada como quatorze deleções simples independentes, mas como provavelmente um único evento de deleção que portanto pesaria bem menos que a soma dos pesos das quatorze deleções somadas individualmente. para modelar melhor esta realidade, Waterman propõe funções com concavidade para baixo como por exemplo[8] :

w(k) = h + g \,log(k)

Penalidade para Lacunas Arbitrária[editar | editar código-fonte]

Needleman e Wunsch em seu artigo sobre o algoritmo Needleman-Wunsch apontam que o procedimento recursivo pode acomodar fórmulas de penalização de lacunas arbitrárias:

Um fator de penalidade, um número subtraído de cada lacuna feita, pode ser avaliado como uma barreira para permissão de lacunas. O fator de penalidade poderia ser uma função do comprimento e/ou direção da lacuna. Nenhuma lacuna seria permitida na operação, salvo se o benefício de permitir essa lacuna ultrapassasse a barreira[9] . [página 444]

Gunsfeld fornece uma questão exemplificando um problema da penalização de lacunas arbitrária[4] . Supondo por exemplo que:


  w(k) =  
   \begin{cases}
    1 & \text{se } k \le 5 \\
    1000000 & \text{se } k > 5 \\
   \end{cases}

Então uma lacuna de comprimento 10 teria peso 1000000 se fosse considerada uma simples lacuna, mas teria peso 2 se fossem consideradas duas lacunas adjacentes. Quel seria o modelo de lacunas adequado?

Leituras adicionais[editar | editar código-fonte]

  • Taylor WR, Munro RE. (1997). "Multiple sequence threading: conditional gap placement". Fold Des 2 (4) p. S33-9.
  • Taylor WR. (1996). "A non-local gap-penalty for profile alignment". Bull Math Biol 58 (1) p. 1–18. DOI:10.1007/BF02458279. PMID 8819751.
  • Vingron M, Waterman MS. (1994). "Sequence alignment and penalty choice. Review of concepts, case studies and implications". J Mol Biol 235 (1) p. 1–12. DOI:10.1016/S0022-2836(05)80006-3. PMID 8289235.
  • Panjukov VV. (1993). "Finding steady alignments: similarity and distance". Comput Appl Biosci 9 (3) p. 285–90. PMID 8324629.
  • Alexandrov NN. (1992). "Local multiple alignment by consensus matrix". Comput Appl Biosci 8 (4) p. 339–45. PMID 1498689.
  • Hein J. (1989). "A new method that simultaneously aligns and reconstructs ancestral sequences for any number of homologous sequences, when the phylogeny is given". Mol Biol Evol 6 (6) p. 649–68. PMID 2488477.
  • Henneke CM. (1989). "A multiple sequence alignment algorithm for homologous proteins using secondary structure information and optionally keying alignments to functionally important sites". Comput Appl Biosci 5 (2) p. 141–50. PMID 2751764.
  • Reich JG, Drabsch H, Daumler A. (1984). "On the statistical assessment of similarities in DNA sequences". Nucleic Acids Res 12 (13) p. 5529–43. DOI:10.1093/nar/12.13.5529. PMID 6462914.

Notas[editar | editar código-fonte]

  1. Nome dado em razão da relação com a função afim. Dan Gusfield, p. 240 afirma que o modelo "afim" é algumas vezes chamados modelo "linear" e que ele próprio prefere assim. Mas o termo "afim" se tornou o termo dominante na literatura biológica e "linear" usualmente se refere a função afim com h = 0.

Referências

  1. Lesk, Arthur M.. Introdução à Bioinformática. Porto Alegre: Artmed, 2005. 381 p. p. 199. ISBN 978-85-363-1104-3
  2. Gibas, Cynthia; Jambeck, Per. Desenvolvendo Bioinformática: Ferramentas de Software para Aplicações em Biologia. Rio de Janeiro: Campus, 2001. 440 p. p. 183-184. ISBN 85-352-0923-9
  3. Setubal, João; Meidanis, João. Introduction to Computational Molecular Biology. Boston: PWS Publishing Company, 1997. 296 p. p. 60-64. ISBN 0-534-95262-3
  4. a b Gusfield, Dan. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology (em inglês). Cambridge: Cambridge University Press, 1997. 534 p. p. 241-253. ISBN 0-521-58519-8
  5. Pevzner, Pevel A.. Computational Molecular Biology: An Algorithm Approach (em inglês). Cambridge: MIT Press, 2000. 314 p. p. 100-101. ISBN 0-262-16197-4
  6. Higgins, Des; Taylor, Willie (editores). Bioinformatics: Sequence, Structure and Databanks (em inglês). Oxford: Oxford, 2000. 249 p. p. 56. ISBN 0-19-963790-3
  7. Apostolico, Alberto; Galil, Zvi (editores). Pattern Matching Algorithms (em inglês). Oxford: Oxford, 1997. 377 p. p. 223-224. ISBN 0-19-511367-5
  8. Waterman, Michael S.. (1984). "Efficient Sequence Alignment Algorithms". J Theor Biol. 108 (3) p. 334-335. DOI:10.1.1.15.7383. PMID 6748696.
  9. Needleman, S.B.; Wunsch, C.D.. (1970). "A general method applicable to the search for similarities in the amino acid sequence of two proteins". Journal of Molecular Biology 48 (3) p. 443. DOI:10.1016/0022-2836(70)90057-4. PMID 5420325.

Ver também[editar | editar código-fonte]