BRAZILIAN JOURNAL OF BIOINFORMATICS ARTIGO ORIGINAL Vol. 2 No. 3 (2014), pages xx-xx

LABIO Press 2012 1

Bioinformática Comparativa

Comparação de matrizes de substituição para alinhamento de

pequenos fragmentos de proteínas

Michele dos Santos da Silva 1,* 1Faculdade Informática (FACIN), PUCRS, Av. Ipiranga, 6681, Prédio 32, Sala 602, 90619-900, Porto Alegre, RS, Brasil.

Received on November 12, 2014; revised on November 14, 2014; accepted on November 17, 2014

Editor-Chefe: Osmar Norberto de Souza

Editores Associados: Luís Fernando Saraiva Macedo Timmers, José Fernando Ruggiero Bachega & Thiago Lipinski-Paes

ABSTRACT

Motivation: Substitution matrices are used in biological sequence

alignment to model amino-acids substitution frequencies during

evolution. The choice of the most suitable matrix strongly depends

on the sequence length. This study investigates how different substi-

tution matrices impact on alignment of short fragments, often used in

template-based protein structure prediction.

Results: Since the statistics of local alignment with gaps is not fully

known, not all substitution matrices work well for short fragments.

The PAM (Percent Accepted Mutation) matrices show a better result

when aligning short sequences. Moreover, using different costs for

gaps has an important impact on the alignment.

Supplementary information: NCBI-BLAST has an option to opti-

mize the alignment for short sequences. It uses substitution matrices

and gap penalties that fit most use cases. Having a better under-

standing of these parameters, however, comes in handy when fine

tuning for a given domain.

RESUMO

Motivação: Matrizes de substituição são usadas no alinhamento de

sequências biológicas para modelar as frequências de substituição

de aminoácidos durante a evolução. A escolha da matriz mais

adequada está atrelada ao tamanho da sequência. Este estudo

investiga o impacto de diferentes matrizes de substituição no

alinhamento de fragmentos curtos.

Resultados: Como a estatística de alinhamentos locais com

espaços não é bem conhecida, nem todas as matrizes de

substituição são adequadas a fragmentos pequenos. As matrizes

PAM (Percent Accepted Mutation) apresentam melhor resultado

para alinhamento de sequências curtas. Além disso, o custo de

espaçamentos tem impacto importante na qualidade do

alinhamento.

Informação suplementar: O NCBI-BLAST tem uma opção para

otimizar o alinhamento de sequências curtas. Ele seleciona matrizes

de substituição e custo de espaçamentos que funcionam bem no

caso geral. No entanto, o entendimento desses parâmetros

*To whom correspondence should be addressed.

individualmente permite ajustes finos, que podem ser mais

adequados a um dado domínio.

1 INTRODUÇÃO

O alinhamento de sequências biológicas permite identificar regiões

similares que podem ser consequência de relações funcionais,

estruturais ou evolucionárias (Mount, 2004). Um elemento

importante na avaliação da qualidade de um alinhamento é a matriz

de substituição, que atribui um score para o alinhamento entre

pares de resíduos.

As matrizes de substituição mais utilizadas são as PAM

(Percent Accepted Mutation) e as BLOSUM (BLOck SUbstitution

Matrix). Essas matrizes contêm valores proporcionais à

probabilidade de um aminoácido i sofrer mutação para um

aminoácido j, considerando todos os pares de aminoácidos. Elas

são construídas através de uma amostra ampla e diversa de

alinhamentos de sequências de proteínas. Se a amostra for

suficientemente grande, as matrizes resultantes refletem as reais

probabilidades de mutação que ocorrem em um período evolutivo

(NCBI, 2014a).

As diversas matrizes de similaridade existentes são adaptadas à

detecção de similaridades entre sequências que divergiram em

diferentes graus. Apesar disso, uma mesma matriz pode ser

eficiente em um amplo espectro de mudanças evolutivas (Altschul,

1993). Experimentos mostraram que a matriz BLOSSUM-62 está

entre as melhores para a detecção de similaridades mais fracas

entre proteínas (Henikoff, 1992). No entanto, não existe uma teoria

estatística para alinhamentos com espaçamentos. Os custos dos

espaçamentos são determinados de forma empírica. Alinhamentos

curtos precisam ser relativamente fortes, com alta taxa de resíduos

similares, para que o ruído não impossibilite a análise (Altschul,

1991). Sequências curtas podem produzir somente alinhamentos

curtos e, portanto, a busca dessas sequências em bancos de dados

deve usar uma matriz apropriada.

O alinhamento de sequências curtas tem diversas aplicações, em

especial a predição da estrutura de proteínas: dada uma sequência

de aminoácidos, qual é sua conformação espacial? Diversas

técnicas para predição de estruturas utilizam fragmentos como, por

exemplo, o CReF (Dorn; Norberto de Souza, 2008). O CReF

divide uma sequência de aminoácidos em fragmentos de cinco

Osmar Norberto de Souza et al.

2

resíduos e executa o alinhamento nesses fragmentos, com o

objetivo de obter ângulos de torção para o aminoácido central de

cada fragmento.

Este trabalho avalia o impacto da utilização de diferentes

matrizes de substituição no alinhamento local de sequências curtas

de aminoácidos, contendo de cinco a nove resíduos. Além disso,

são consideradas diferentes penalidades para espaçamentos, com o

objetivo de encontrar o conjunto ótimo de parâmetros para o

alinhamento de pequenos fragmentos.

2 FUNDAMENTAÇÃO TEÓRICA

2.1 Dogma central da biologia molecular

O dogma central da biologia molecular descreve o caminho através

do qual a informação contida no DNA é convertida em proteínas

com funções específicas. A Figura 1 mostra um diagrama desse

processo.

Figura 1. A partir de uma sequência de DNA o RNA mensageiro é

transcrito (1). Esse RNA dá origem a uma proteína através do processo de

tradução (2). Simplificadamente, o processo segue o caminho do DNA para

o RNA para a proteína. Fonte: (Korf et al., 2013).

As sequências biológicas têm importantes funções, necessárias

ao funcionamento de um organismo. O DNA pode sofrer mutações

aleatórias, capazes de mudar a função de uma sequência. Com o

tempo, tanto restrições funcionais quanto processos aleatórios

impactam o curso de evolução da sequência. As sequências

biológicas que apresentam alto grau de similaridade normalmente

têm ancestral comum e seguiram diferentes caminhos evolutivos.

O alinhamento auxilia no entendimento dessas relações.

2.2 BLAST

BLAST (Basic Local Alignment Search Tool) é um algoritmo para

comparação de sequências biológicas, tais como sequências de

aminoácidos e nucleotídeos. Uma busca BLAST permite a

comparação com um banco de dados de sequências e a

identificação de sequências similares ao termo de busca, acima de

um dado limiar (Altschul et al., 1990).

O algoritmo BLAST encontra similaridades estatisticamente

relevantes entre sequências. Existem dois tipos de alinhamento:

global e local. No alinhamento global, ambas as sequências são

alinhadas ao longo de todo o seu comprimento. No alinhamento

local, busca-se o melhor alinhamento entre subsequências. Para

comparar duas sequências de ponta a ponta, o alinhamento global é

a melhor escolha. Para obter sequências similares a uma dada

sequência em um banco de dados, o alinhamento local é o mais

utilizado.

Alinhamento Global - Needleman-Wunsch

Needleman-Wunsch é um dos principais algoritmos de

alinhamento global (Needleman; Wunsch, 1970). Para

exemplificar o alinhamento das sequências COELANCANTH e

PELICAN, podemos usar um esquema simples de score que atribui

+1 para identidade e -1 para letras diferentes ou espaçamentos

(Korf et al., 2003). Os dois melhores alinhamentos, de acordo com

esse sistema são:

COELACANTH COELACANTH

P-ELICAN-- -PELICAN--

Note que cada letra é alinhada a outra letra ou a um

espaçamento, diferente do que ocorre com alinhamentos locais.

O alinhamento é feito através de uma matriz bidimensional em

que a célula corresponde ao pareamento de uma letra de cada

sequência (Fig. 2).

Figura 2. Exemplo de matriz de alinhamento global. Uma célula

corresponde ao pareamento de uma letra de cada sequência. (Korf et al.,

2013).

Na matriz da Figura 2, o alinhamento começa no topo esquerdo

e segue um caminho quase diagonal para o canto inferior direito.

Quando duas letras estão alinhadas, o caminho é diagonal. Quando

Comparação de matrizes de substituição para alinhamento de pequenos fragmentos de proteínas

3

uma letra está alinhada a um espaçamento, a trajetória é horizontal

ou vertical.

Diferente do exemplo, a matriz de alinhamento utilizada pelo

algoritmo Needleman-Wunsch armazena scores. Esses scores são

provenientes de matrizes de substituição, que serão detalhadas na

próxima seção.

Alinhamento Local - Algoritmo Smith-Waterman

O algoritmo de alinhamento local Smith-Waterman (Smith;

Waterman, 1981) é uma modificação de Needleman-Wunsch, com

três principais diferenças:

(1) As bordas da matriz são inicializadas com 0 em vez de

penalidades crescentes para espaçamentos.

(2) O score máximo nunca é menor do que 0, nenhum ponteiro

é armazenado a menos que o score seja maior do que zero.

(3) O procedimento trace-back começa do score mais alto da

matriz e termina com o score 0.

Essas pequenas modificações têm grande impacto no algoritmo.

Usando as mesmas sequências e esquema de score usado no

alinhamento global, a matriz resultante apresenta muitos zeros.

Isso ocorre porque há diversos lugares em que não é possível obter

um score positivo.

2.3 Matrizes de substituição

Uma matriz de substituição é uma matriz bidimensional contendo

scores para todos os pares de aminoácidos. Matrizes de

substituição representam taxas relativas de substituições

evolucionárias. Observando-se uma matriz como a BLOSUM62,

ficam evidentes as similaridades químicas entre os diferentes

aminoácidos.

Dois tipos de matrizes de score são amplamente utilizados:

PAM (Percent Accepted Mutation) e BLOSUM (BLOcks

SUbstitution Matrix). As matrizes PAM foram criadas por

Margaret Dayhoff (1970), têm um forte componente teórico,

baseando-se em hipóteses evolucionárias. As matrizes BLOSUM

são mais empíricas, porém derivadas de um conjunto de dados

mais amplo. A maioria dos pesquisadores prefere as BLOSUM

porque experimentos in silico indicam que buscas usando matrizes

BLOSUM têm maior sensibilidade (Korf et al., 2013).

Existem diversas matrizes PAM, cada uma com um sufixo

numérico. A matriz PAM1 foi criada com um conjunto de

proteínas que tinham 85% ou mais de identidade. As outras

matrizes PAM foram construídas pela multiplicação da matriz

PAM por ela mesma: 100 vezes para a PAM100, 160 vezes para a

PAM160, e assim por diante. Havia poucas sequências quando as

PAM foram criadas e, portanto, esse era um jeito razoável de

extrapolar para maiores distâncias.

Os bancos de dados de proteínas continham muito mais

sequências nos anos 90 e, portanto, métodos mais empíricos se

tornaram possíveis. As matrizes BLOSUM foram criadas pela

extração de segmentos sem espaçamentos, ou blocos, de um

conjunto de famílias de proteínas multiplamente alinhado. Esses

blocos foram agrupados com base em seu percentual de

identidades. Os blocos usados para derivar a matrix BLOSUM62,

por exemplo, têm pelo menos 62% de identidade com os demais

blocos membro.

Algumas hipóteses para as matrizes BLOSUM normalmente

apresentarem maior sensibilidade são: (1) a extrapolação

empregada nas matrizes PAM acentua pequenos erros nas

probabilidades de mutação para períodos evolucionários curtos e

(2) as forças que governam a evolução de sequências a longo prazo

são diferentes das que atuam a curto prazo.

Os valores utilizados nas matrizes de substituição disponíveis no

NCBI-BLAST podem ser consultados em (NCBI, 2014c).

2.4 Estatística dos Scores de Similaridade

Para avaliar se um dado alinhamento é uma evidência para homologia, deve-se verificar qual a chance desse alinhamento ser casual (NCBI, 2014b). Um alinhamento casual pode ser proveniente de (1) sequências reais mas não homólogas; (2) sequências reais que foram permutadas de forma a conservar suas propriedades composicionais (Fitch, 1983); ou (3) sequências geradas aleatoriamente baseadas em um modelo de DNA ou proteína. Métodos analíticos utilizam a última definição, enquanto os empíricos podem utilizar todas elas.

Estatística de alinhamentos globais

Muito pouco se sabe sobre a distribuição de scores de alinhamento global (Deken, 1983). Experimentos de Monte Carlo podem fornecer alguma aproximação da distribuição para sistemas de score e sequências específicas. No entanto, não podem ser generalizados facilmente.

Uma das formas de se avaliar a significância estatística de um dado alinhamento global é gerar muitos pares de sequências aleatórias, de tamanho e composição adequada, e calcular o score do alinhamento ótimo para cada par.

Apesar de ser possível expressar o score em termos de desvios padrões de uma média, não se pode assumir que a distribuição é normal e converter esse Z-valor em um P-valor; a cauda das distribuições de alinhamento global é desconhecida. O máximo que se pode dizer é que se 100 alinhamentos aleatórios têm score inferior ao alinhamento de interesse, o P-valor em questão é provavelmente menos de 0,01 (NCBI, 2014b). Estatística de alinhamentos locais

Diferentemente da estatística de alinhamentos globais, a estatística de alinhamentos locais sem espaçamento é bem conhecida (Altschul et al., 1990).

Um alinhamento local sem espaçamentos é formado por um par de segmentos de igual comprimento, extraído de cada uma das sequências que estão sendo comparadas. Uma modificação do algoritmo Smith-Waterman encontra pares de segmentos cujo score não pode ser melhorado por extensão ou corte. Esses segmentos são chamados de HSPs (high-scoring segment pairs), pares de segmentos com alto score.

Para analisar a probabilidade de um score alto ser obtido ao acaso, um modelo de sequências aleatórias é necessário. Para proteínas, o modelo mais simples seleciona aminoácidos em uma sequência de forma independente, considerando as probabilidades dos vários resíduos. Além disso, o score esperado para o alinhamento de um par aleatório de aminoácidos deve ser negativo. Caso contrário, alinhamentos longos teriam score alto, independente de os segmentos alinhados serem relacionados.

Osmar Norberto de Souza et al.

4

Assim como a soma de um grande número de variáveis independentes igualmente distribuídas tende a uma distribuição normal, o máximo tende a uma distribuição de valor extremo ou de Gumbel (1958). Alinhamentos locais ótimos seguem a distribuição de Gumbel (Karlin; Altschul, 1990). Considerando-se sequências com tamanhos m e n suficientemente grandes, a estatística dos scores é caracterizada por dois parâmetos, K e lambda. O E-value para um score S é dado por:

𝐸 = 𝐾𝑚𝑛 𝑒−𝜆𝑆 (1)

Pela Equação 1, pode-se notar que dobrando o tamanho de qualquer uma das sequências dobra o número de HSPs que têm um dado score. Além disso, para um HSP obter um score 2x ele precisa obter o score x duas vezes em sequência e, portanto, o E decresce exponencialmente com o score. Os parâmetros K e lambda representam as escalas naturais para o tamanho do espaço de busca e do sistema de score, respectivamente.

Valores de score sozinhos têm pouco significado. O score pode

ser normalizado utilizando-se os parâmetros K e lambda (Eq. 2).

𝑆′ =𝜆𝑆−ln 𝐾

ln 2 (2)

O score normalizado é conhecido como bit score. Como o bit

score considera a distribuição do sistema de score, é possível calcular o E-value correspondente a um score utilizando somente o tamanho do espaço de busca (Eq. 3).

𝐸 = 𝑚𝑛2−𝑠′ (3)

A partir do E-value é possível calcular o valor-p. No entanto, o

uso do E-value para alinhamento é mais comum, pois seus valores são de mais fácil interpretação. Por exemplo, E-value de 5 e 10 ou valor-p de 0,993 e 0,99995.

Embora os desenvolvimentos mostrados nesta seção tenham sido feitos considerando-se alinhamentos locais sem espaçamentos, diversos experimentos computacionais e alguns resultados analíticos sugerem que a mesma teoria pode ser aplicada a alinhamentos com espaçamento (NCBI, 2014b).

A estatística descrita acima tende a ser conservadora para sequências curtas. A teoria que dá suporte a essa estatística é a assintótica, que assume que um alinhamento local ótimo pode começar com quaisquer pares de resíduos alinhados. No entanto, um alinhamento de alto score precisa ter um certo comprimento e, portanto, não pode começar próximo ao fim de nenhuma das sequências sendo comparadas. Esse efeito pode ser corrigido, calculando-se um comprimento efetivo para essas sequências (Altschul; Gish, 1996). O programa BLAST calcula esse ajuste.

Score de buscas em bancos de dados O cálculo do E-value (Eq. 1) se aplica à comparação de duas proteínas de tamanho m e n. Existem alternativas para avaliar a significância de um alinhamento de uma proteína de tamanho m a um banco de dados.

Uma abordagem é considerar que todas as proteínas no banco de dados são igualmente prováveis a priori. Isso significa que um E-value baixo para um alinhamento envolvendo uma sequência curta deve ter o mesmo peso que o para um alinhamento envolvendo uma sequência longa. Para calcular o E-value de uma busca em um banco de dados, multiplica-se o E-value pelo número de sequências no banco. Essa abordagem é adotada pelo programa de comparação de proteínas FASTA (Pearson, 1995).

Outra técnica considera que é mais provável que uma busca esteja relacionada a uma sequência longa, porque sequências longas são frequentemente compostas por múltiplos domínios. Se considerarmos que a chance de relacionamento a priori é proporcional ao tamanho da sequência, o E-value do alinhamento envolvendo uma sequência de tamanho n deve ser multiplicado por N/n. N é o tamanho do banco de dados em número de resíduos. Essa é a forma como o programa BLAST calcula o E-value (Altschul et al., 1990).

2.5 Custo de espaçamentos

Não existe uma teoria para o custo dos espaçamentos na produção de scores. As penalidades para espaçamento foram selecionadas ao longo dos anos por tentativa e erro (Pearson, 1995). A maioria dos programas de alinhamento selecionam, por padrão, penalidades para espaçamentos apropriadas à matriz de susbstituição. Se o usuário usa uma matriz de substituição diferente, não há garantia que os mesmos custos ainda serão apropriados. Na prática, uma penalidade grande para o início de um espaçamento e uma bem menor para extendê-lo é bastante efetiva (NCBI, 2014b).

3 MATERIAIS E MÉTODOS

Para investigar-se o impacto da matriz de similaridade e do custo de espaçamentos no alinhamento local, foi desenvolvido um algoritmo que implementa os seguintes passos:

(1) Recebe uma sequência como entrada e produz fragmentos

usando janelas deslizantes de 5, 7 e 9 aminoácidos.

(2) Para cada fragmento obtido aplica BLAST usando as

combinações de matrizes de substituição PAM e BLOSUM

e custos de penalidade apresentados na Tabela 1.

(3) Separa os resultados de alinhamento usando limiar de E-

value 10e-5.

(4) Superimpõe a estrutura da sequência original à das obtidas

usando BLAST e calcula o RMSD.

O passo 4 do algoritmo é uma forma automatizada de avaliar o relacionamento a partir da similaridade estrutural entre as sequências. Além disso, foi realizada inspeção manual das estruturas tridimensionais a fim de identificar nuances não facilmente capturadas por cálculos usando as estruturas superimpostas.

Tabela 1. Custo dos espaçamentos avaliados.

Existência Extensão

5-7 2

8-10 1

13 3

14 1 e 2

15 3

A hipótese é que algum dos limiares de E-value consiga

identificar sequências relacionadas. Em bioinformática, a definição desse limiar é muito importante, pois é comum termos interesse somente em sequências homólogas ou somente em sequências não homólogas. Conforme detalhado nas seções anteriores, essa tarefa é especialmente difícil para sequências curtas.

As matrizes utilizadas neste experimento e suas respectivas entropias são apresentadas na Tabela 2.

Comparação de matrizes de substituição para alinhamento de pequenos fragmentos de proteínas

5

Tabela 2. Matrizes de substituição e suas entropias (Chao; Zang,

2009).

Matriz de substituição Entropia

PAM30 2,57

PAM70 1,60

PAM250 0,354

BLOSUM45 0,3795

BLOSUM50 0,4808

BLOSUM62 0,6979

BLOSUM80 0,9868

BLOSUM90 1,1806

. Foram executados experimentos com proteínas cujo código PDB

é 1ZDD e 1L2Y (Fig. 3). Foram aplicadas todas as combinações de tamanhos de fragmentos, matrizes de substituição e custos de espaçamentos. Os resultados são descritos na próxima seção.

Figura 3. Estrutura tridimensional das proteínas de código PDB 1ZDD

(esquerda), de 35 resíduos, e 1L2Y, de 20 resíduos, utilizadas no

experimento.

4 RESULTADOS

Para os três tamanhos de fragmentos testados, 5, 7 e 9 resíduos, a matriz PAM30 foi a que apresentou resultados mais específicos. A performance das diversas matrizes de substituição foi diretamente proporcional à entropia relativa dessas matrizes. Maiores entropias permitiram mais facilmente distinguir alinhamentos curtos de alinhamentos gerados ao acaso.

Apesar de a matriz PAM30 apresentar maior especificidade para alinhamentos de sequências curtas, acredita-se que isso não ocorre pela diferença na forma como foram modeladas as matrizes PAM e BLOSUM. Por exemplo, as matrizes PAM250 e BLOSUM45 apresentam scores com especificidade bastante similar.

Para a penalização de espaçamentos, independente da matriz testada, os melhores resultados se deram com custo de existência entre 8 e 10 e custo de extensão de 1. Foram observadas pequenas diferenças utilizando-se custos de existência entre 8 a 10. Há uma tendência de diminuição da penalização à medida que a entropia aumenta.

REFERÊNCIAS

Altschul, S.F., Gish, W., Miller, W., Myers, E.W. & Lipman, D.J. (1990) Basic local

alignment search tool. J. Mol. Biol. 215:403-410.

Altschul, S.F. (1991) Amino acid substitution matrices from an information theoretic

perspective. J. Mol. Biol. 219:555-565.

Altschul, S.F. (1993) A protein alignment scoring system sensitive at all evolutionary

distances. J. Mol. Evol. 36:290-300.

Altschul, S.F. & Gish, W. (1996) Local alignment statistics. Meth. Enzymol. 266:460-

480.

Chao, K.M. and Zhang, L. (2008). Sequence Comparison: Theory and Methods.

Springer. 230 p.

Deken, J. (1983) Probabilistic behavior of longest-common-subsequence length." In

"Time Warps, String Edits and Macromolecules: The Theory and Practice of Se-

quence Comparison. D. Sankoff & J.B. Kruskal (eds.), pp. 55-91

Dorn, M.; Norberto de Souza, O. (2008) CReF: a central-residue-fragment-based

method for predicting approximate 3-D polypeptides structures. In Proceedings of

the 2008 ACM symposium on Applied computing.

Fitch, W.M. (1983) Random sequences. J. Mol. Biol. 163:171-176.

Gumbel, E. J. (1958) Statistics of extremes. Columbia University Press, New York,

NY.

Henikoff, J.G. (1992) Amino acid substitution matrices from protein blocks. Proc.

Natl. Acad. Sci. USA 89:10915-10919

Karlin, S. & Altschul, S.F. (1990) Methods for assessing the statistical significance of

molecular sequence features by using general scoring schemes. Proc. Natl. Acad.

Sci. USA 87:2264-2268.

Korf, I. and Yandell, M. and Bedell, J (2003). BLAST. O'Reilly Media, Incorporated.

339 p.

Mount DM. (2004) Bioinformatics: Sequence and Genome Analysis (2nd ed.). Cold

Spring Harbor Laboratory Press: Cold Spring Harbor, NY.

NCBI (2014a) BLAST® Help [Internet]. Bethesda (MD): National Center for Bio-

technology Information (US); 2008-. Available from:

http://www.ncbi.nlm.nih.gov/books/NBK1762/

NCBI (2014b) The Statistics of Sequence Similarity Scores Available from:

http://www.ncbi.nlm.nih.gov/BLAST/tutorial/Altschul-1.html

NCBI (2014c) Substitution Matrices [Internet]. National Center for Biotechnology

Information (US). Available from: ftp://ftp.ncbi.nih.gov/blast/matrices/

Needleman, Saul B.; and Wunsch, Christian 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): 443–53.

Pearson, W.R. (1995) Comparison of methods for searching protein sequence data-

bases. Prot. Sci. 4:1145-1160.

Smith, Temple F.; and Waterman, Michael S. (1981). Identification of Common

Molecular Subsequences. Journal of Molecular Biology 147: 195–197.