Conforme visto na Seção 3.3.2, o algoritmo de Sankoff possui uma alta complexidade computacional e por isso várias heurísticas são utilizadas para reduzir o tempo e memória. O desafio desses métodos consiste em reduzir o espaço de busca e manter a qualidade do alinhamento. Nesta seção iremos descrever 3 variantes heurísticas baseadas no algoritmo de Sankoff que obtém o alinhamento estrutural para pares de sequências: Foldalign, PM- comp e LocARNA. A partir delas, foram criados métodos heurísticos progressivos (Seção 2.3.3.1) que permitem o alinhamento para mais de duas sequências: FoldalignM, PMmulti e mLocARNA. Esses métodos também são descritos nesta seção.
3.3.5.1 Foldalign
Foldalign [26] é uma variante heurística do algoritmo de Sankoff (Seção 3.3.2) para duas sequências. Uma versão simplificada da recursão do Foldalign está ilustrada na Equação 3.11 e uma versão completa pode ser encontrada em [39].
O Foldalign 1.0 [26] é considerado por muitos como a primeira variante heurística do algoritmo de Sankoff. Para reduzir o consumo de tempo e memória requeridos, e são utilizadas as seguintes restrições: (a) o alinhamento final é limitado a λ nucleotídeos; e (b) o tamanho máximo da diferença entre duas subsequências sendo alinhadas é limitado à δ nucleotídeos. Essas duas restrições reduzem a complexidade de memória do algoritmo para O(n2λ2δ2), onde n é o comprimento das sequências e a complexidade de espaço é
reduzida para O(λ3δ).
O Foldalign 2.0 [41], introduziu um modelo mais complexo de substituição, de melhor relevância biológica. A equação de recorrência do Foldalign está ilustrada na equação
3.11. Di,j,k,l= max Di+1,j−1,k+1,l−1+ Ebp(ni, nj, nk, nl, σbp) (a)
Di+1,j−1,k,l+ EbpiI(ni, nj, −, −, σbpiI) (b)
Di,j,k+1,l−1+ EbpiK(−, −, nk, nl, σbpiK) (c)
Di+1,j,k+1,l+ Eal(ni, nk, σal) (d)
Di,j−1,k,l−1+ Ear(nj, nl, σar) (e)
Di+1,j,k,l+ EglI(ni, −, σglI) (f)
Di,j−1,k,l+ EgrI(nj, −, σglrI) (g)
Di,j,k+1,l+ EglK(−, nk, σglK) (h) Di,j,k,l−1+ EgrK(−, nl, σgrK) (i) max i<m<j k<n<l{Di,m,k,n+ Dm+1,j,n+1,l+ σmbl} (j) (3.11)
Na equação 3.11, o caso (a) adiciona um par de bases em ambas as estruturas. Os casos (b) e (c) adicionam um par de bases em uma sequência e um gap na outra. Os casos (d) e (e) adicionam um nucleotídeo não pareado ao final do alinhamento. Os casos (f ), (g), (h), e (i) adicionam um nucleotídeo não pareado em uma sequência e um gap na outra sequência. O caso (j) é a regra de multibranch onde duas subestruturas são combinadas para formar uma estrutura maior. Nesta equação de recorrência, os termos E são funções de escore baseadas na enegia σ da estrutura secundária em questão.
O Foldalign 2.1 [38] adicionou uma nova heurística, a constante de pruning. Neste método, um sub-alinhamento é eliminado quando um escore atinge um valor muito ruim pré-determinado. Isto significa que o escore do alinhamento é tão ruim, que provavelmente não faz parte de um alinhamento biologicamente relevante. Com essas limitações, ele não garante obter a solução ótima, e em alguns casos nenhuma solução é obtida.
Para implementar a heurística de pruning, o Foldalign 2.1 utiliza programação dinâ- mica forward. Desta forma, ao se processar uma célula que possui um escore inferior a uma constante, o algoritmo não aplica os membros da equação de recorrência a ela. Esse método é conhecido na literatura e é utilizado também nos programas MSA 1.0 e MSA 2.0 (Seção 2.3.1.2), porém em vez de se utilizar uma constante passada como argumento pelo usuário, eles utilizam o limite de Carrillo-Lipman (Seção 2.3.1.1), que ainda garante a otimalidade.
Para verificar a melhoria do pruning, um teste foi realizado comparando execuções do Foldalign sem a heurística e com a heurística. Nele foram usadas sequências reais de várias famílias de RNA (5S rRNA, Purine, THI U1, tRNA). Na comparação foi verificado que o Foldalgin com pruning localiza os mesmos resultados que a versão sem pruning,
porém executa 5 vezes mais rápido.
Para avaliar a capacidade de detectar alinhamentos, o Foldalign foi comparado com outras estratégias estado da arte: Dynalign [33], LocARNA [134], Consan [18] e Steamloc [50]. Neste experimento, foram utilizadas sequências reais, contendo tRNA e 5S rRNAs. As sequências foram separadas em conjuntos, de acordo com a similaridade entre elas. Para esse experimento, o Foldalign obteve a melhor performance para sequências com similaridade entre 10% e 60% e o Dynalign obteve melhor resultados para similaridade entre 65% e 100%.
3.3.5.2 PMcomp
Hofacker et al. propuseram uma variante do algoritmo de Sankoff chamada PMcomp [49]. Nela, assume-se que um modelo de estrutura para cada uma das sequências já é conhecido através do algoritmo de McCaskill (Seção 3.2.2).
Considere duas sequências S1 e S2, com suas respectivas matrizes de probabilidades
PS1 e PS2. Com isso, o PMcomp calcula ΨS
ij é o escore relativo à posição (i, j) na matriz
de probabilidade da sequência S. O PMcomp permite duas formas de cálculo deste escore. Na primeira forma utiliza-se diretamente o escore da matriz de probabilidades, multiplicado por um número inteiro, que pode ser informado pelo usuário. A segunda forma utiliza o log score, dado pela equação 3.12:
Ψij = log(Pij/pmin) (3.12)
Nesta equação, Pij é o valor da posição (i, j) da matriz de probabilidade P , como
calculado pelo algoritmo de McCaskill (Seção 3.2.2) e pmin representa o valor da mínimo
para se considerar uma probabilidade ser significante.
Portanto, para resolver o problema do alinhamento estrutural das sequências S1 e S2,
considerando que o alinhamento possui Ngape uma estrutura secundária E1 e E2, busca-se
obter o maior escore possível com a fórmula 3.13. X (ij;kl)∈E (ΨS1 ij+Ψ S2 kl+τ (S1(i), S1(j), S2(k), S2(l)))+γNgap+ X i∈S1,k∈S26∈E σ(S1(i), S2(k)) → max (3.13) Na fórmula 3.13 o valor γ é a penalidade linear de gaps, a função σ(S1(i), S2(k))
descreve a substituição de nucleotídeos não pareados e a função τ(S1(i), S1(j), S2(k), S2(l))
descreve o custo de substituição compensatória.
A obtenção do valor máximo é feita através de programação dinâmica. Considere Di,j,k,l é o melhor escore para as subsequências S1[i..j] e S2[k..l]. Além disso, DMi,j,k,l ser
PMcomp apresenta duas equações de recorrência conforme 3.14 e3.15 Di,j,k,l = max Di+1,j,k,l+ γ Di,j,k+1,l+ γ Di+1,j,k+1,l + σ(S1(i), S2(k)) max m≤j n≤l{D M i,m,k,n+ Dm+1,j,n+1,l} (3.14) DMi,j,k,l= Di+1,j+1,k+1,l+1+ ΨSij1 + Ψ S2 kl + τ (S1(i), S1(j), S2(k), S2(l)) (3.15)
Na equação3.14 os dois primeiros termos descrevem a adição de um gap em uma das sequências, o terceiro termo descreve a adição de nucleotídeos não pareados, o quarto termo descreve a junção de estruturas em uma maior para ambas as sequências e final- mente o último termo descreve a adição de nucleotídeo pareados.
O PMcomp calcula as equações 3.14 e 3.15 em tempo O(n6) e memória O(n4). Se
considerarmos que PS
ij = 1 para todo i, j se i e j formam um par de base, e PijS = 0 caso
contrário, o algoritmo é equivalente ao algoritmo de Sankoff [49].
3.3.5.3 LocARNA
Will et al. [134] propuseram o LocARNA (local alignment of RNA), um algoritmo para predição da estrutura secundária local em pares. No mesmo trabalho também foi apresentado o mLocARNA, um método para estender o LocARNA para múltiplas sequên- cias. O LocARNA é implementado em C++, e seu desempenho permite o agrupamento de um grande grupo de ncRNAs.
Considere duas sequências S1 e S2, cada uma matrizes de probabilidades PS1 e PS2,
onde ΨS
ij é o escore relativo a posição (i, j) na matriz de probabilidade da sequência
S. Assim como o PMcomp, o LocARNA tem a opção de utilizar o escore da matriz de probabilidades ou log score, porém no LocARNA ele é definido conforme a equação 3.16.
Ψij = logPij p0 / log 1 p0 Se Pij ≥ p ∗ −∞ Caso contrário. (3.16)
Nesta equação, Pij é o valor da probabilidade na posição (i, j) como calculado pelo
algoritmo de McCaskill (Seção3.2.2), p∗ é um valor de corte (cutoff ), de forma que valores
menores que ele sejam ignorados no cálculo do escore e p0é a probabilidade do pareamento
ocorrer aleatoriamente. O termo log 1
p0 representa uma normatização para os pesos serem ao máximo 1.
Para resolver este problema com programação dinâmica, considere Di,j,k,lcomo o escore
máximo para o alinhamento das subsequências S1[i..j] e S2[k..l]. A equação de recorrência
está apresentada nas equações 3.17 e 3.18.
Di,j,k,l= max Di,j−1,k,l+ γ Di,j,k,l−1+ γ Di,j−1,k,l−1+ σ(S1(j), S2(l)) max j′l′{Di,j′−1,k,l′−1+ DMj′,j,l′,l} (3.17) Di,j,k,lM = Di,j−1,k,l−1+ ΨSij1 + Ψ S2 kl (3.18)
As células na matriz DM são armazenadas apenas para nucleotídeos pareados. Porém,
uma das heurísticas do LocARNA não armazena valores nas matrizes de programação dinâmica que não possuam um escore significante, conforme mostrado na equação3.16, os valores menor que p∗ são descartados. Uma variante desse conjunto de equações também
é proposta, onde uma entrada 0 é adicionada na equação de recorrência para todos os casos que i = k = 0. São adicionados também escores negativos para gaps e mismatches. Normalmente, o backtrace é iniciado na última célula e termina na primeira célula. Nesta variante, ele é alterado para terminar em escores que possuam o valor 0. Assim, é possível remover prefixos das sequências alinhadas, calculando o alinhamento local.
3.3.5.4 FoldalignM
O FoldalignM [131] é um programa de alinhamento de estrutura secundária global múltiplo, baseado no Foldalign [38]. Ele constrói um alinhamento múltiplo progressivo computando todas as N (N −1)
2 comparações dos pares de sequências envolvidos, gerando
uma matriz de probabilidade para cada comparação em pares. Então, alinha o par com o maior escore, calcula uma matriz de consenso e então alinha a próxima sequência a esta matriz de consenso e assim sucessivamente até que todas as sequências sejam alinhadas. O FoldalignM pode calcular a matriz de probabilidades usando o algoritmo de McCaskill (Seção 3.2.2) ou então usar a tabela de probabilidade do Foldalign para produzir uma árvore guia.
A escolha do agrupamento das sequências e escolha de qual sequência deve ser adicio- nada à matriz de probabilidade consenso é feita pelo método de clustering. Inicialmente, ordenam-se as sequências de acordo com seu escore. Então, são adicionadas as sequências com maior escore ao alinhamento do primeiro cluster e a lista de escores dos pares de sequência é percorrida de forma descendente. Caso o escore possua um valor de corte inferior a uma constante, então:
• Se nenhuma das sequências existir em um cluster, crie um novo cluster e adicione-o ambas as sequências a ele;
• Se uma das sequências existir em um cluster, adicione a outra sequência a este cluster ;
• Se ambas as sequências já estiverem em um mesmo cluster, não faça nada;
• Se as sequências existirem em clusters diferentes, utilize o escore do alinhamento entre elas para ser o escore de diferença entre os dois clusters, ou faça a união dos clusters se o valor for inferior ao de corte.
O valor de corte p∗ pode ser alterado pelo usuário. Este valor é essencial para a
sensibilidade dos clusters, afinal um valor de corte alto irá causar muitas uniões (merges) das matrizes, criando poucos clusters de baixa similaridade. Por outro lado, valores baixos irão criar muitos clusters. Desta forma, este método de alinhamento é progressivo pois, inicialmente, é gerada a matriz de probabilidade entre as duas sequências mais próximas, sendo adicionadas as próximas sequências, de acordo com a similaridade, até que todas as sequências tenham sido adicionadas.
O programa FoldalignM [131] foi comparado a alguns outros programas heurísticos de alinhamento múltiplo. Nos testes foram utilizados conjuntos de 9 a 75 sequências RFAM classificados com baixa ou alta similaridade entre elas. A comparação mostra que o desempenho do programa é equivalente a outras abordagens, porém o FoldalignM se mostrou muito eficiente para sequências de baixa similaridade.
3.3.5.5 PMmulti
O PMmulti [49] foi proposto como uma ferramenta para o alinhamento múltiplo base- ada no PMcomp (Seção3.3.5.2). Dado um alinhamento estrutural do PMComp, é possível definir uma matriz de probabilidades consenso entre as duas sequências, conforme a equa- ção 3.19. PS1S2 p,q = q PS1 ip,jqP S2 kp,lq para matches 0 para gaps (3.19) Nesta equação, o termo ip é a posição da sequência S1 correspondente à posição p no
alinhamento. Desta forma, é possível estender o método para a criação de alinhamento para mais de duas sequências.
Para o alinhamento de N sequências de RNA, calcula-se todos N(N −1)/2 alinhamen- tos em pares das sequências. Então o escore de similaridade dos alinhamentos é utilizado
para criar um árvore guia e usando a equação 3.19 o alinhamento múltiplo progressivo (Seção 2.3.3.1) das sequências é criado.
Em seus resultados, o PMmulti foi comparado com outras 3 ferramentas: ClustalW, PMstring e MARNA para o alinhamento de 7 sequências reais, cuja estrutura secundária é conhecida manualmente. Eles mostraram que, nesse experimento, o ClustalW produz um alinhamento de baixa qualidade, dado que o alinhamento é exclusivamente baseado na estrutura primária. O MARNA e o PMstring produzem um alinhamento aceitável, porém o PMmulti foi capaz de encontrar uma mutação adicional, sendo o método que mais se aproximou do alinhamento manual.
3.3.5.6 mLocARNA
O mLocARNA é o método de alinhamento múltiplo progressivo baseado nos alinha- mentos em pares do LocARNA (Seção 3.3.5.3). Da mesma forma que o PMmulti faz com o PMcomp, ele cria o alinhamento em pares de todas as sequências e usa o escore de similaridade para criar um árvore guiada.
Porém, foi notado que o PMmulti utiliza um escore 0 na matriz de consenso para gaps. Consequentemente, quando existe um gap em uma das sequências, o escore na matriz de consenso é muito baixo, por isso o PMmulti tem uma tendência de remover muitos pares de bases para um grande número de sequências.
Para resolver isso, o mLocARNA define a matriz de probabilidades consenso diferen- temente. Dada duas sequências, S1 e S2, considere que S é alguma dessas sequências:
PS1S2 p,q = q ¯ PS1 p,qP¯p,qS2 ¯ Pp,qS =
max(p0, PiSp,jq) para matches
p0 caso contrário
(3.20) onde ip e iq são as posições correspondente a p e q no alinhamento da sequência S e
p0 representa a probabilidade de pares de bases ocorrerem aleatoriamente. O restante do
algoritmo não foi alterado, onde o escore dos alinhamento par-a-par são utilizados para criar uma árvore guiada e obter o alinhamento múltiplo ao final.
O mLocARNA foi testado em um conjunto de 3.901 sequências de 503 famílias. Seus resultados mostraram que a ferramenta é capaz de agrupar classes conhecidas de RNA, tal como o tRNAs, mas também agrupou alguns candidatos a novas classes de ncRNA. Em alguns casos, foi possível adicionar algumas sequências à famílias de RNA já conhecidas, e além disso, o mLocARNA detectou um homólogo do mir-126 e outro do mir-7 que não foram detectados em nenhum estudo computacional anterior.