Em formação

2.5: O Algoritmo Needleman-Wunsch - Biologia


Agora usaremos a programação dinâmica para resolver o problema mais difícil de alinhamento geral de sequência. O algoritmo que desenvolveremos nas seções a seguir para resolver o alinhamento de sequência é conhecido como algoritmo Needleman-Wunsch.

Programação dinâmica vs. memoização

Antes de mergulharmos no algoritmo, uma nota final sobre memoização é necessária. Muito parecido com o problema de Fibonacci, o problema de alinhamento de sequência pode ser resolvido em uma abordagem de cima para baixo ou de baixo para cima.

Em um abordagem recursiva de cima para baixo podemos usar a memoização para criar um dicionário potencialmente grande indexado por cada um dos subproblemas que estamos resolvendo (sequências alinhadas). Isso requer espaço (O left (n ^ {2} m ^ {2} right) ) se indexarmos cada subproblema pelos pontos inicial e final das subsequências para as quais um alinhamento ótimo precisa ser calculado. A vantagem é que resolvemos cada subproblema no máximo uma vez: se não estiver no dicionário, o problema é calculado e inserido no dicionário para referência futura.

Em um abordagem iterativa ascendente podemos usar programação dinâmica. Definimos a ordem dos subproblemas de computação de tal forma que uma solução para um problema seja calculada uma vez que os subproblemas relevantes tenham sido resolvidos. Em particular, subproblemas mais simples virão antes dos mais complexos. Isso elimina a necessidade de manter o controle de quais subproblemas foram resolvidos (o dicionário na memoização se transforma em uma matriz) e garante que não haja trabalho duplicado (cada subalinhamento é calculado apenas uma vez).

Assim, neste caso particular, a única diferença prática entre memoização e programação dinâmica é o custo das chamadas recursivas incorridas no caso de memoização (uso de espaço é o mesmo).

Declaração do Problema

Suponha que temos um alinhamento ótimo para duas sequências (S_ {1 ldots n} ) e (T_ {1 ldots m} ) nas quais Si corresponde a Tj. O ponto principal é que este alinhamento ideal é composto de um alinhamento ideal entre ( left (S_ {1}, ldots, S_ {i-1} right) ) e ( left (T_ {1}, ldots, T_ {i-1} right) ) e um alinhamento ótimo entre ( left (S_ {i + 1}, ldots, S_ {n} right) ) e ( left (T_ {j + 1}, ldots, T_ {m} right) ). Isso segue de um argumento de recortar e colar: se um desses alinhamentos parciais for subótimo, então recortamos e colamos um alinhamento melhor no lugar do subótimo. Isso atinge uma pontuação mais alta do alinhamento geral e, portanto, contradiz a otimização do alinhamento global inicial. Em outras palavras, cada subcaminho em um caminho ótimo também deve ser ótimo. Observe que as pontuações são aditivas, então a pontuação do alinhamento geral é igual à adição das pontuações dos alinhamentos das subsequências. Isso implicitamente assume que os subproblemas de calcular os alinhamentos de pontuação ideais das subsequências são independentes. Precisamos motivar biologicamente que tal suposição leva a resultados significativos.

Espaço de índice de subproblemas

Agora precisamos indexar o espaço de subproblemas. Seja (F_ {i, j} ) a pontuação do alinhamento ótimo de ( left (S_ {1}, ldots, S_ {i} right) ) e ( left (T_ {1 }, ldots, T_ {i} right) ). O espaço dos subproblemas é ( left {F_ {i, j}, i in [0, | S |], j in [0, | T |] right } ). Isso nos permite manter uma matriz F ((m + 1) × (n + 1) ) com as soluções (ou seja, pontuações ideais) para todos os subproblemas.

Otimização local

Podemos calcular a solução ótima para um subproblema fazendo uma escolha ótima local com base nos resultados dos subproblemas menores. Assim, precisamos estabelecer uma função recursiva que mostre como a solução para um determinado problema depende de seus subproblemas. E usamos essa definição recursiva para preencher a tabela F de forma ascendente.

Podemos considerar as 4 possibilidades (inserir, excluir, substituir, combinar) e avaliar cada uma delas com base nos resultados que calculamos para subproblemas menores. Para inicializar a tabela, definimos (F_ {0, j} = −j · d ) e (F_ {i, 0} = −i · d ) uma vez que essas são as pontuações de alinhamento ( left ( T_ {1}, ldots, T_ {i} right) ) com j intervalos e ( left (S_ {1}, ldots, S_ {i} right) ) com (i ) intervalos (também conhecido como sobreposição zero entre as duas sequências). Em seguida, percorremos a matriz coluna por coluna calculando a pontuação ideal para cada subproblema de alinhamento, considerando as quatro possibilidades:

• A sequência S tem uma lacuna na posição de alinhamento atual.

• A sequência T tem uma lacuna na posição de alinhamento atual.

• Há uma mutação (substituição de nucleotídeos) na posição atual.

• Há uma correspondência na posição atual.

Em seguida, usamos a possibilidade que produz a pontuação máxima. Expressamos isso matematicamente pela fórmula recursiva para (F_ {i, j} ):

[F (0,0) = 0 não numérico ]

[Inicialização: F (i, 0) = F (i - 1, 0) - d não numérico ]

[F (0, j) = F (0, j - 1) - d não numérico ]

[ text {Iteração}: quad F (i, j) = max left { begin {array} {l}
F (i-1, j) -d text {inserir lacuna em S}
F (i, j-1) -d text {inserir lacuna em T}
F (i-1, j-1) + s left (x_ {i}, y_ {j} right) text {correspondência ou mutação}
end {array} right. nonumber ]

Rescisão: canto inferior direito

Depois de percorrer a matriz, a pontuação ótima para o alinhamento global é dada por (F_ {m, n} ). A ordem de travessia precisa ser tal que tenhamos soluções para determinados subproblemas quando precisarmos deles. Ou seja, para calcular (F_ {i, j} ), precisamos saber os valores à esquerda, para cima e diagonalmente acima (F_ {i, j} ) na tabela. Assim, podemos percorrer a tabela na ordem principal da linha ou coluna ou mesmo diagonalmente da célula superior esquerda para a célula inferior direita. Agora, para obter o alinhamento real, só temos que lembrar as escolhas que fizemos em cada etapa.

Solução Ótima

Os caminhos pela matriz (F ) correspondem aos alinhamentos de sequência ideais. Ao avaliar cada célula (F_ {i, j} ), fazemos uma escolha selecionando o máximo das três possibilidades. Assim, o valor de cada célula (não inicializada) na matriz é determinado pela célula à sua esquerda, acima dela ou diagonalmente à esquerda acima dela. Uma partida e uma substituição são ambas representadas como viajando na direção diagonal; no entanto, um custo diferente pode ser aplicado para cada um, dependendo se os dois pares de bases que estamos alinhando correspondem ou não. Para construir o alinhamento ideal real, precisamos rastrear nossas escolhas na matriz. É útil manter um ponteiro para cada célula enquanto preenche a tabela que mostra qual escolha foi feita para obter a pontuação dessa célula. Então, podemos simplesmente seguir nossos ponteiros para trás para reconstruir o alinhamento ideal.

Análise da Solução

A análise de tempo de execução desse algoritmo é muito simples. Cada atualização leva (O (1) ) tempo, e como há mn elementos na matriz F, o tempo total de execução é (O (mn) ). Da mesma forma, o espaço total de armazenamento é O (mn). Para o caso mais geral em que a regra de atualização é mais complicada, o tempo de execução pode ser mais caro. Por exemplo, se a regra de atualização requer o teste de todos os tamanhos de lacunas (por exemplo, o custo de uma lacuna não é linear), então o tempo de execução seria (O (mn (m + n)) ).

Needleman-Wunsch na prática

Suponha que queremos alinhar duas sequências S e T, onde

S = AGT

T = AAGC

A primeira etapa é colocar as duas sequências ao longo das margens de uma matriz e inicializar as células da matriz. Para inicializar, atribuímos um 0 à primeira entrada na matriz e, em seguida, preenchemos a primeira linha e coluna com base na adição incremental de penalidades de lacuna, como na Figura 2.9 abaixo. Embora o algoritmo possa preencher a primeira linha e coluna por meio da iteração, é importante definir e definir claramente os limites do problema.

A próxima etapa é a iteração por meio da matriz. O algoritmo prossegue ao longo de linhas ou colunas, considerando uma célula de cada vez. Para cada célula, três pontuações são calculadas, dependendo das pontuações de três células da matriz adjacentes (especificamente a entrada acima, aquela diagonalmente para cima e à esquerda e a outra para a esquerda). A pontuação máxima desses três rastreamentos possíveis é atribuída à entrada e o ponteiro correspondente também é armazenado. O encerramento ocorre quando o algoritmo atinge o canto inferior direito. Na Figura 2.10, a matriz de alinhamento para as sequências S e T foi preenchida com pontuações e indicadores.

A etapa final do algoritmo é o rastreamento do caminho ideal. Em nosso exemplo, começamos no canto inferior direito e seguimos os ponteiros disponíveis para o canto superior esquerdo. Ao registrar as decisões de alinhamento feitas em cada célula durante o rastreamento, podemos reconstruir o alinhamento de sequência ideal do fim ao início e, em seguida, invertê-lo. Observe que, neste caso específico, existem vários caminhos ideais (Figura 2.11). Uma implementação em pseudocódigo do algoritmo Needleman-Wunsch está incluída no Apêndice 2.11.4

Otimizações

O algoritmo dinâmico que apresentamos é muito mais rápido do que a estratégia de força bruta de enumerar alinhamentos e tem um bom desempenho para sequências de até 10 quilobases de comprimento. No entanto, na escala de alinhamentos do genoma inteiro, o algoritmo fornecido não é viável. Para alinhar sequências muito maiores, podemos fazer modificações no algoritmo e melhorar ainda mais seu desempenho.

Programação Dinâmica Limitada

Uma otimização possível é ignorar Alinhamentos Mildly Boring (MBAs) ou alinhamentos que têm muitas lacunas. Explicitamente, podemos nos limitar a ficar a alguma distância W da diagonal na matriz

F de subproblemas. Ou seja, assumimos que o caminho de otimização em F de (F_ {0,0} ) a (F_ {m, n} ) está dentro da distância W ao longo da diagonal. Isso significa que a recursão (2.2) só precisa ser aplicada às entradas em F dentro da distância W ao redor da diagonal, e isso produz um custo de tempo / espaço de (O ((m + n) W) ) (consulte a Figura 2,12).

Observe, no entanto, que essa estratégia é heurística e não garante mais um alinhamento ideal. Em vez disso, atinge um limite inferior na pontuação ideal. Isso pode ser usado em uma etapa subsequente, onde descartamos as recursões na matriz F que, dado o limite inferior, não pode levar a um alinhamento ideal.

Alinhamento Linear do Espaço

A recursão (2.2) pode ser resolvida usando apenas espaço linear: atualizamos as colunas em F da esquerda para a direita, durante as quais monitoramos apenas a última coluna atualizada que custa (O (m) ) espaço. No entanto, além da pontuação (F_ {m, n} ) do alinhamento ótimo, também queremos calcular um alinhamento correspondente. Se usarmos trace back, então precisamos armazenar ponteiros para cada uma das entradas em F, e isso custa (O (mn) ) espaço.

Também é possível encontrar um alinhamento ideal usando apenas espaço linear! O objetivo é usar dividir e conquistar para calcular a estrutura do alinhamento ideal para uma entrada de matriz em cada etapa. A Figura 2.13 ilustra o processo. A ideia principal é que um alinhamento de programação dinâmico pode prosseguir com a mesma facilidade na direção reversa, começando no canto inferior direito e terminando no canto superior esquerdo. Portanto, se a matriz for dividida ao meio, um passe para frente e um passe reverso podem ser executados ao mesmo tempo e convergir na coluna do meio. No ponto de cruzamento, podemos somar as duas pontuações de alinhamento; a célula na coluna do meio com a pontuação máxima deve cair no caminho ideal geral.

Podemos descrever esse processo de forma mais formal e quantitativa. Primeiro calcule o índice de linha (u ∈ {1, ..., m} ) que está no caminho ótimo ao cruzar a coluna ( frac {n} {2} th ). Para (1 ≤ i ≤ m ) e (n ≤ j ≤ n ), deixe (C_ {i, j} ) denotar o índice de linha que está no caminho ideal para (F_ {i, j} ) ao cruzar a coluna ( frac {n} {2} th ). Então, enquanto atualizamos as colunas de F da esquerda para a direita, também podemos atualizar as colunas de C da esquerda para a direita. Assim, em (O (mn) ) tempo e (O (m) ) espaço, podemos calcular a pontuação (F_ {m, n} ) e também (C_ {m, n} ), que é igual ao índice da linha (u ∈ {1,., m} ) que está no caminho ideal enquanto cruza a coluna ( frac {n} {2} th ). Agora a ideia de dividir e conquistar entra em ação. Repetimos o procedimento acima para a submatriz superior esquerda (u times frac {n} {2} ) de F e também repetimos o procedimento acima para a inferior direita (( mu) times frac {n} {2} ) submatriz de F. Isso pode ser feito usando (O (m + n) ) espaço linear alocado. O tempo de execução para a submatriz superior esquerda é (O left ( frac {un} {2} right) ) e o tempo de execução para a submatriz inferior direita é (O left ( frac {(mu) n} {2} right) ), que somados dá um tempo de execução de (O left ( frac {mn} {2} right) = O (mn) ).

Continuamos repetindo o procedimento acima para submatrizes cada vez menores de F enquanto reunimos mais e mais entradas de um alinhamento com pontuação ideal. O tempo total de execução é (O (mn) + O left ( frac {mn} {2} right) + O left ( frac {mn} {4} right) + ldots = O (2mn ) = O (mn) ). Portanto, sem sacrificar o tempo total de execução (até um fator constante), dividir e conquistar leva a uma solução espacial linear (veja também a Seção ?? na Aula 3).


Detalhes do algoritmo Needleman-Wunsch

Tento entender os detalhes do algoritmo Needleman – Wunsch e uso um exemplo do livro [Nello Cristianini, Matthew W. Hahn. Introdução à Genômica Computacional. Uma abordagem de estudos de caso, www.computational-genomics.net].

Na minha opinião, o algoritmo não é descrito de maneira muito clara, então surge a pergunta.

Além disso, o cálculo da pontuação para o vizinho diagonal também é claro,

porque este é um alinhamento sem lacuna:

Momento obscuro é o alinhamento para o vizinho esquerdo (ou acima). Diga, o vizinho da esquerda


3.1 Algoritmos de Alinhamento e Programação Dinâmica

Uma das primeiras tentativas de alinhar duas sequências foi realizada por Vladimir Levenstein em 1965, chamada de “editar distância”, e agora é freqüentemente chamada de distância de Levenshtein. A distância de edição é definida como o número de edições de um único caractere necessárias ”para alterar uma palavra para outra. Inicialmente, ele descreveu textos e palavras escritas, mas esse método foi posteriormente aplicado a sequências biológicas. Um dos algoritmos mais comumente usados ​​para calcular a distância de edição é o algoritmo de Wagner-Fischer, um algoritmo de Programação Dinâmica.

A Programação Dinâmica expressa de forma otimizada o problema completo como a solução ideal para as partes menores (subproblemas). O problema geral pode então ser expresso como uma composição dos subproblemas. Além do algoritmo de Wagner-Fischer, vários outros algoritmos de programação dinâmica foram desenvolvidos para alinhar sequências biológicas, incluindo os algoritmos Needleman-Wunsch [22] e Smith-Waterman [23].


Algoritmos de alinhamento de sequência

Algoritmos de programação dinâmica são algoritmos recursivos modificados para armazenar resultados intermediários, o que melhora a eficiência para certos problemas. O algoritmo Smith-Waterman (Needleman-Wunsch) usa um algoritmo de programação dinâmica para encontrar o alinhamento local (global) ideal de duas sequências - e. O algoritmo de alinhamento é baseado em encontrar os elementos de uma matriz onde o elemento é a pontuação ideal para alinhar a sequência (,.) Com (,.). Dois aminoácidos semelhantes (por exemplo, arginina e lisina) recebem uma pontuação alta, dois aminoácidos diferentes (por exemplo, arginina e glicina) recebem uma pontuação baixa. Quanto maior a pontuação de um caminho na matriz, melhor será o alinhamento. A matriz é encontrada encontrando-se progressivamente os elementos da matriz, começando e procedendo nas direções de aumento e. Cada elemento é definido de acordo com:

onde é a pontuação de similaridade da comparação de aminoácidos com aminoácidos (obtida aqui da tabela de similaridade BLOSUM40) e é a penalidade para uma única lacuna. A matriz é inicializada com. Ao obter o alinhamento local Smith-Waterman, é modificado:

A penalidade de intervalo pode ser modificada, por exemplo, pode ser substituída por, onde é a penalidade para um único intervalo e é o número de intervalos consecutivos.

Uma vez que a pontuação de alinhamento ideal é encontrada, o `` rastreio '' ao longo do caminho ideal é encontrado, o que corresponde ao alinhamento de sequência ideal para a pontuação. No próximo conjunto de exercícios, você implementará manualmente o alinhamento Needleman-Wunsch para um par de sequências curtas e, em seguida, realizará alinhamentos de sequência global com um programa de computador desenvolvido por Anurag Sethi, que é baseado no algoritmo Needleman-Wunsch com uma penalidade de gap afim ,, onde está a penalidade de intervalo de extensão. O arquivo de saída estará no formato GCG, um dos dois formatos padrão em bioinformática para armazenar informações de sequência (o outro formato padrão é FASTA).

Realize manualmente um alinhamento Needleman-Wunsch

No primeiro exercício, você testará o algoritmo Smith-Waterman em uma sequência curta de partes de hemoglobina (código PDB 1AOW) e mioglobina 1 (código PDB 1AZI).

    Aqui, você irá alinhar a sequência HGSAQVKGHG com a sequência KTEAEMKASEDLKKHGT.

H G S UMA Q V K G H G
0 -8 -16 -24 -32 -40 -48 -56 -64 -72 -80
K -8
T -16
E -24
UMA -32
E -40
M -48
K -56
UMA -64
S -72
E -80
D -88
eu -96
K -104
K -112
H -120
G -128
T -136

    A primeira etapa é preencher as pontuações de similaridade S procurando as correspondências na tabela BLOSUM40, mostrada aqui rotulada com códigos de aminoácidos de 1 letra:

    Preenchemos as pontuações de similaridade BLOSUM40 para você na Tabela 4.

, usando a convenção de que os valores aparecem na parte superior de um quadrado em letras grandes e os valores aparecem na parte inferior de um quadrado em letras pequenas. Nossa penalidade de gap é 8.

Nota: consideramos ser o `` predecessor '' de, uma vez que ajudou a decidir o valor. Posteriormente, os predecessores se qualificarão para estar no caminho de rastreamento.

Tabela 4: Planilha de pontuação de alinhamento. Em todas as caixas de alinhamento, a pontuação de similaridade da pesquisa da matriz BLOSUM40 é fornecida (texto pequeno, parte inferior do quadrado). Quatro pontuações de alinhamento são fornecidas como exemplos (texto grande, topo do quadrado), tente calcular pelo menos mais quatro, seguindo a direção fornecida no texto para o cálculo.
H G S UMA Q V K G H G
0 -8 -16 -24 -32 -40 -48 -56 -64 -72 -80
K -8
T -16
E -24
UMA -32
E -40
M -48
K -56
UMA -64
S -72
E -80
D -88
eu -96
K -104
K -112
H -120
G -128
T -136
Tabela 5: Planilha Traceback. A matriz de pontuação de alinhamento concluída (texto grande, parte superior de cada quadrado) com as pontuações de pesquisa BLOSUM40 S (texto pequeno, parte inferior de cada quadrado). Para encontrar o alinhamento, trace de volta começando da parte inferior direita (T vs G, pontuação -21) e prossiga na diagonal (para a esquerda e para cima), para a esquerda ou para cima. Só prossiga, entretanto, se o quadrado naquela direção pudesse ter sido um predecessor, de acordo com as condições descritas no texto.
H G S UMA Q V K G H G
0 -8 -16 -24 -32 -40 -48 -56 -64 -72 -80
K -8
T -16
E -24
UMA -32
E -40
M -48
K -56
UMA -64
S -72
E -80
D -88
eu -96
K -104
K -112
H -120
G -128
T -136

    Agora, para verificar seus resultados em um programa de computador. Preparamos um programa de alinhamento em pares Needleman-Wunsch, par, que você aplicará às mesmas sequências que acabou de alinhar manualmente.

/tbss.work/Bioinformatics/pairData
em seguida, inicie o executável de alinhamento de pares digitando:
par targlist
. Todos os alinhamentos serão realizados utilizando a matriz BLOSUM40, com uma penalidade de intervalo de 8. Os caminhos para os arquivos de entrada e a matriz BLOSUM40 utilizados são definidos no arquivo targlist, a matriz BLOSUM40 são as primeiras 25 linhas do arquivo blosum40. (Outras matrizes de substituição podem ser encontradas no site do NCBI / Blast.)

Nota: Em algumas instalações, o executável do par é
no

/tbss.work/Bioinformatics/pairData e aqui você deve
digite ./pair targlist para executá-lo.
Se você não puder acessar o executável do par, você pode ver a saída desta etapa em

Encontrando pares homólogos de sintetases de tRNA ClassII

As proteínas homólogas são proteínas derivadas de um gene ancestral comum. Neste exercício com o algoritmo Needleman-Wunsch, você estudará a identidade de sequência de várias tRNA sintetases de classe II, que são de Eucarya, Eubacteria ou Archaea ou diferem no tipo de reação de aminoacilação que catalisam. A Tabela 6 resume o tipo de reação, o organismo e o código de acesso do PDB e o nome da cadeia dos domínios de tRNA sintetase de Classe II empregados.

Especificidade Organismo Código PDB: corrente Domínio catalítico ASTRAL
Aspartil Eubacteria 1EQR: B d1eqrb3
Aspartil Archaea 1B8A: A d1b8aa2
Aspartil Eukarya 1ASZ: A d1asza2
Glycl Archaea 1ATI: A d1atia2
Histidil Eubacteria 1ADJ: C d1adjc2
Lysl Eubacteria 1BBW: A d1bbwa2
Aspartil Eubacteria 1EFW: A d1efwa3

    Preparamos um programa de computador múltiplo que alinhará vários pares de proteínas.


Indel é um termo usado para as operações de inserção e deleção em sequências biológicas.

Alsmirat MA, Jararweh Y, Al-Ayyoub M, Shehab MA, Gupta BB (2017) Acelerando algoritmos de segmentação de imagens médicas com uso intensivo de computação usando implementações de CPU-GPU híbridas. Multimed Tools Appl 76 (3): 3537–3555

Balhaf K, Alsmirat MA, Al-Ayyoub M, Jararweh Y, Shehab MA (2017) Acelerando levenshtein e damerau para editar algoritmos de distância usando gpu com memória unificada. In: 2017 8ª conferência internacional sobre sistemas de informação e comunicação (ICICS). IEEE, pp 7-11

Balhaf K, Shehab MA, Wala’a T, Al-Ayyoub M, Al-Saleh M, Jararweh Y (2016) Usando gpus para acelerar o cálculo de distância de edição de levenshtein. In: 2016 7ª conferência internacional sobre sistemas de informação e comunicação (ICICS). IEEE, pp 80-84

Butenhof DR (1997) Programação com threads POSIX. Addison-Wesley Professional, Boston

Chan S, Wong A, Chiu D (1992) Uma pesquisa de métodos de comparação de múltiplas sequências. Bull Math Biol: 563–598

Cook S (2012) Programação CUDA: um guia do desenvolvedor para computação paralela com GPUs. Newnes, p 16-25

De Oliveira Sandes E, Miranda G, Martorell X, Ayguade E, Teodoro G, Magalhães Alves de Melo AC (2016) Cudalign 4.0: rastreamento especulativo incremental para alinhamento exato de todo o cromossomo em clusters de GPU. IEEE Trans Parallel Distrib Syst 27 (10): 2838-2850

Durbin R, Eddy S, Krogh A, Mitchison G (1998) Biological sequence analysis. Cambridge University Press, Cambridge

El-Metwally S, Ouda O, Helmy M (2014) Tecnologias de sequenciamento de última geração e desafios na montagem de sequência. Springer Sci Bus 7: 16–25

Fakirah M, Shehab MA, Jararweh Y, Al-Ayyoub M (2015) Acelerando o algoritmo de alinhamento global do alfaiate-wunsch com gpus. In: 2015 IEEE / ACS 12ª conferência internacional de sistemas e aplicações informáticas (AICCSA). IEEE, pp 1-5

Farrar M (2007) Striped smith-waterman acelera pesquisas de banco de dados seis vezes em relação a outras implementações simd. Bioinformática 23 (2): 156-161

Gebali F (2011) Algoritmos e computação paralela, vol 84. Wiley, Nova York

Gotoh O (1982) Um algoritmo melhorado para combinar sequências biológicas. J Mol Biol 162 (3): 705–708

Jones C, Pevzner P (2004) Uma introdução aos algoritmos de bioinformática. Imprensa do MIT, Cambridge

Katoh K, Toh H (2008) Desenvolvimentos recentes no programa de alinhamento de seqüência múltipla mafft. Brief Bioinform 92: 86-98

Liu Y, Schmidt B (2015) Gswabe: alinhamento de sequência acelerado por GPU mais rápido com recuperação de alinhamento ideal para sequências de DNA curtas. Concurr Comput: Pract Exper 27 (4): 958–972

Lomont C (2011) Introdução às extensões de vetor avançadas da Intel. Livro Branco, Intel

Needleman SB, Wunsch CD (1970) Um método geral aplicável à pesquisa de semelhanças na sequência de aminoácidos de duas proteínas. J Mol Biol 48 (3): 443-453

Rognes T (2011) Pesquisas de banco de dados Faster Smith-Waterman com paralelização SIMD entre sequências. BMC Bioinform 12: 221. https://doi.org/10.1186/1471-2105-12-221

Rognes T, Seeberg E (2000) Six-fold-up of smith-waterman banco de dados de buscas usando processamento paralelo em microprocessadores comuns. Bioinformática 16 (8): 699–706

Sanders J, Kandrot E (2010) CUDA por exemplo: uma introdução à programação de GPU de uso geral. Addison-Wesley Professional, Boston

Serrano JP, De Oliveira Sandes E, Magalhães Alves de Melo A, Ujaldon M (2017) Aceleração Smith-waterman em multi-gpus: uma análise de desempenho por watt. In: Bioinformática e engenharia biomédica - 5ª conferência internacional de trabalho, IWBBIO 2017, Granada, Espanha, 26–28 de abril de 2017, Proceedings, Parte II, pp 512–523

Setubal J, Meidanis J (1997) Introdução à biologia molecular computacional. PWS Pub, Boston

Shehab MA, Al-Ayyoub M, Jararweh Y (2015) Melhorando o desempenho dos algoritmos fcm e t2fcm usando gpus para segmentação de imagens médicas. In: 2015 6ª conferência internacional sobre sistemas de informação e comunicação (ICICS), pp 130–135

Siriwardena P, Ranasinghe N (2010) Acelerando o alinhamento de sequência global usando gpu de múltiplos núcleos compatível com cuda. In: 5ª conferência internacional em informação e automação para a sustentabilidade (ICIAFS), pp 201–206

Vermij P (2011) Alinhamento de sequência genética em uma plataforma de supercomputação. Tese de doutorado, TU Delft, Delft University of Technology

Wozniak A (1997) Usando instruções orientadas a vídeo para acelerar a comparação de sequências. Comput Appl Biosci: CABIOS 13 (2): 145-150

Zhou W, Zhanxiu C, Lian B, Wang J, Jianping M (2017) Pesquisa de banco de dados de proteínas de algoritmo de alinhamento híbrido baseado em aceleração paralela gpu. J Supercomput. https://doi.org/10.1007/s11227-017-2030-x

Zhu X, Li K, Salah A, Shi L, Li K (2015) Implementação paralela de MAFFT em hardware gráfico habilitado para cuda. IEEE / ACM Trans Comput Biol Bioinform 12 (1): 205–218. https://doi.org/10.1109/TCBB.2014.2351801


Conclusão

Uma heurística de alinhamento de sequências de RNA em pares eficiente, que considera intrinsecamente os pares de bases subótimos, discrimina com precisão entre famílias de RNA estruturadas distintas. Quando combinado com um algoritmo de agrupamento baseado em densidade tolerante a ruído, esta abordagem identifica motivos de estrutura de RNA conhecidos e novos a partir de um conjunto de sequências de entrada sem conhecimento a priori. Os motivos de estrutura de RNA resultantes são subsequentemente usados ​​para identificar homólogos no genoma humano, melhorando a anotação de lncRNAs e aumentando o repertório de elementos genéticos funcionais.


Alinhamento e importância da sequência:

Alinhamento de Sequênciaou comparação de sequências está no cerne da bioinformática, que descreve a forma de arranjo de sequências de DNA / RNA ou proteínas, a fim de identificar as regiões de similaridade entre elas. É usado para inferir a relação estrutural, funcional e evolutiva entre as sequências. O alinhamento encontra o nível de similaridade entre a sequência de consulta e diferentes sequências de banco de dados. O algoritmo funciona por abordagem de programação dinâmica que divide o problema em subproblemas independentes menores. Ele encontra o alinhamento de forma mais quantitativa, atribuindo pontuações.

Quando uma nova sequência é encontrada, a estrutura e a função podem ser facilmente previstas fazendo o alinhamento da sequência. Uma vez que se acredita que, uma sequência que compartilha um ancestral comum exibiria uma estrutura ou função semelhante. Quanto maior a similaridade da sequência, maior é a chance de que compartilhem uma estrutura ou função semelhante.

Métodos de alinhamento de sequência:

Existem principalmente dois métodos de alinhamento de sequência:

Alinhamento Global: Seqüências intimamente relacionadas com o mesmo comprimento são muito apropriadas para o alinhamento global. Aqui, o alinhamento é realizado do início ao fim da sequência para encontrar o melhor alinhamento possível.

O algoritmo Needleman-Wunsch (uma fórmula ou conjunto de etapas para resolver um problema) foi desenvolvido por Saul B. Needleman e Christian D. Wunsch em 1970, que é um algoritmo de programação dinâmica para alinhamento de sequência. A programação dinâmica resolve o problema original dividindo o problema em subproblemas independentes menores. Essas técnicas são usadas em muitos aspectos diferentes da ciência da computação. O algoritmo explica o alinhamento de sequência global para alinhar sequências de nucleotídeos ou proteínas.

Alinhamento local: As sequências suspeitas de terem semelhanças ou mesmo sequências diferentes podem ser comparadas com o método de alinhamento local. Encontra regiões locais com alto nível de similaridade.

Esses dois métodos de alinhamento são definidos por algoritmos diferentes, que usam matrizes de pontuação para alinhar as duas séries diferentes de caracteres ou padrões (sequências). Os dois métodos de alinhamento diferentes são definidos principalmente pela abordagem de programação dinâmica para alinhar duas sequências diferentes.

Programaçao dinamica:

A programação dinâmica é usada para o alinhamento ideal de duas sequências. Ele encontra o alinhamento de uma forma mais quantitativa, fornecendo algumas pontuações para correspondências e incompatibilidades (matrizes de pontuação), em vez de apenas aplicar pontos. Ao pesquisar as pontuações mais altas na matriz, o alinhamento pode ser obtido com precisão. A Programação Dinâmica resolve o problema original dividindo o problema em subproblemas independentes menores. Essas técnicas são usadas em muitos aspectos diferentes da ciência da computação. Os algoritmos Needleman-Wunsch e Smith-Waterman para alinhamento de sequência são definidos por abordagem de programação dinâmica.

Matrizes de pontuação:

Em procedimentos de alinhamento ideal, principalmente os algoritmos Needleman-Wunsch e Smith-Waterman usam o sistema de pontuação. Para o alinhamento da sequência de nucleotídeos, as matrizes de pontuação usadas são relativamente mais simples, uma vez que a frequência de mutação para todas as bases são iguais. Um valor positivo ou superior é atribuído a uma correspondência e um valor negativo ou inferior é atribuído a uma incompatibilidade. Essas pontuações baseadas em suposições podem ser usadas para pontuar as matrizes. Existem outras matrizes de pontuação que são predefinidas principalmente, usadas no caso de substituições de aminoácidos.

Matrizes predefinidas usadas principalmente são PAM e BLOSUM.

Matrizes PAM: Margaret Dayhoff foi a primeira a desenvolver a matriz PAM, PAM significa Point Accepted Mutations. As matrizes PAM são calculadas observando as diferenças em proteínas intimamente relacionadas. Uma unidade PAM (PAM1) especifica uma mutação de ponto aceita por 100 resíduos de aminoácidos, ou seja, 1% de mudança e 99% permanece como tal.

BLOSUM: O BLOcks SUbstitution Matrix, desenvolvido por Henikoff e Henikoff em 1992, usou regiões conservadas. Essas matrizes são valores de identidade de porcentagem reais. Para dizer simplesmente, eles dependem da semelhança. Blosum 62 significa que há 62% de similaridade.

Pontuação de lacuna ou penalidade de lacuna: Algoritmos de programação dinâmica usam penalidades de intervalo para maximizar o significado biológico. A penalidade da lacuna é subtraída para cada lacuna que foi introduzida. Existem diferentes penalidades de gap, como gap aberto e extensão de gap. A pontuação de lacuna define uma penalidade dada ao alinhamento quando temos inserção ou exclusão. Durante a evolução, pode haver um caso em que possamos ver lacunas contínuas ao longo da sequência, de modo que a penalidade de lacuna linear não seria apropriada para o alinhamento. Assim, a abertura e a extensão da lacuna foram introduzidas quando há lacunas contínuas (cinco ou mais). A penalidade de abertura é sempre aplicada no início da lacuna, e então as outras lacunas seguintes são atribuídas com uma penalidade de extensão de lacuna que será menor em comparação com a penalidade de abertura. Os valores típicos são –12 para a abertura do gap e –4 para a extensão do gap.


Introdução

Hoje, o conceito de rede da Internet das Coisas (IoT) tornou-se parte integrante da infraestrutura de informação moderna da sociedade. A IoT é uma rede única que conecta os objetos inteligentes do mundo real e os objetos virtuais ao nosso redor. O número e a variabilidade de tais objetos (dispositivos inteligentes) continuam a crescer, afetando vários aspectos da vida humana, de veículos a eletrônicos móveis e saúde [26]. In other words, the IoT is not just a set of different devices and sensors connected by wired and wireless communications and the global cyber space of the Internet, but it is a closer integration of the real and virtual worlds, in which communication takes place between people and devices.

The sustainability of IoT is the availability of the system to perform its functions in the context of external influence [6]. Considering that the subsystems and components of the IoT have many horizontal connections, thus forming a heterogeneous cyber infrastructure with a large number of entities, most of which lack built-in protection mechanisms the problem of network security in such networks is especially actual. Main attack vectors are aimed for overtaking the control by the IoT device and capturing the confidential data, as well as the purposeful node deactivation [1]. Not only objects of the virtual world�ta, files, personal information𠅊re under threat, but also physical objects of the real world. According to a report by Kaspersky Laboratory, in the first half of 2019, more than 100 million attacks were detected on the smart IoT devices, which are seven times more than in the <"type":"entrez-nucleotide","attrs":<"text":"H12018","term_id":"876838","term_text":"H12018">> H12018 [10]. Network infrastructure and wireless data transmission channels are the most vulnerable objects of the modern infocommunication environment [27]. Attackers using wireless links can remotely invade a target subnet or device (group of devices), intercept traffic, launch denial of service attacks (including distributed attacks), and take control of the IoT devices to create megabotnets.

In 2020, the world is facing with the COVID-2019 coronavirus pandemic, and life has almost completely moved to the network, people around the world work, study, shop and have fun online. This could not affect the goals of the cybercriminals, medical organizations, educational services, delivery, etc., faced massive DDoS attacks. A large network of hospitals in France fell victim to one of these attacks, when attackers tried to disable the infrastructure of medical institutions. As a result of the attack, hospital staff working remotely was unable to use work programs and corporate e-mail for some time. In Germany, on the first day of distance learning, a distance learning platform was attacked. The service through which teachers exchange teaching materials, homework, and tests with students was not available. In the Netherlands, the food delivery service Thuisbezorgd was unable to process orders as a result of a DDoS attack and had to refund customers. In the first quarter of 2020, there was a significant increase in the number and quality of DDoS attacks. In particular, the popularity of smart attacks that exploit vulnerabilities in the network infrastructure is noted. SYN flood is the leader among the types of attacks (92.6%) the share of attacks via ICMP continued to grow and exceeded the share of UDP and TCP floods (Kaspersky [11].

To counter cyber attacks at the IoT, as in traditional networks, various intrusion detection systems (IDS) are applied (e.g., [17]. There are two main approaches on which most the IoT IDSs are based: anomaly detection and misuse detection. The advantages of the former are a global view on the network, the ability to detect new attacks, and the use of fewer rules (compared to signature methods) their disadvantages include a high level of errors of the first and second kind and low adaptation for changing conditions (new profiles, dynamic anomalies). The advantages of an IDS based on search for abuse are reliability, speed, low false positives for known intrusions. Its disadvantages are the strict dependence on the relevance of the signature base and the impossibility of detecting new attacks.

The work of an IDS usually consists of three stages: (1) monitoring, (2) sequence extraction and misuse detection by pattern matching, (3) signaling of attack to provide the attack response. Matching with attack patterns is currently the main method for IDS when detecting malicious activity [13] however, it has two significant drawbacks. Firstly, the IoT-specific attacks, such as forced power consumption, forced topology change, etc., have a split sequence of operations, time intervals in the chain of actions, and some attacks may also have a non-linear sequence of actions. Secondly, there is a class of polymorphic attacks that have mutations (namely local differences, omissions, delays) in the sequences of actions during the implementation of the attack. These polymorphic attacks adapt to a wide range of conditions, operating systems, and circumstances and try to avoid scanning by defenses to infect endpoints [8]. They are called the polymorphic attacks because they have different signatures that make them difficult to identify using a single signature. For example, in order to disguise ongoing network attacks, attackers can use polymorphic shellcode to create unique attack patterns. This method usually involves encoding the payload, with the decoder placed at the front of the payload before sending it. All known the pattern matching methods do not detect such variations of a single sample.

Our research proposes new, the nature inspired, technologies, namely a genetic sequence alignment computing and a sequence similarity calculation, instead of massive equity checking of multiple packets and signatures traditionally used for the IDS composing. The aim of our research is to assess the prospects of using the biological coded sequence alignment algorithms for solving the task of detection the specific network intrusions. The novelty of our results is the fact that it has been proposed to encode network packets (or the chain of activity acts) into the sequences of the nucleotide codes for their subsequent alignment and matching with patterns. The matching operation is based on the similarity checking, not equity checking, as it was usually applied for the intrusion detection. Therefore, our contribution to the cyber security is the proposed bio-inspired approach that, in contrast to traditional methods, makes it possible to detect new variations of the attacks in the IoT networks, to reduce the signature database, and to increase the detection effectiveness on the low-resource devices.

The following material is organized in the next manner: Sect.ਂ reviews successful cases of applying modern nature-inspired methods in solving cyber security issues Sect.ਃ discusses methods for aligning sequences: global, local, and additive approaches Sect.਄ presents the proposed coding and alignment technique Sect.ਅ presents our results of the experiments on detecting the DDoS attacks using a BoT-IoT dataset on the portative IoT Raspberry Pi4 platform Sect.ਆ presents a discussion of the results of applying the bio-inspired methods Sect.ਇ concludes our contribution.


Fundo

Biological sequence alignment is a cornerstone of bioinformatics and is widely used in such fields as phylogenetic reconstruction, gene finding, genome assembly. The accuracy of the sequence alignments and similarity measures are directly related to the accuracy of subsequent analysis. CDS alignment methods have many important applications for gene tree and protein tree reconstruction. In fact, they are useful to cluster homologous CDS into groups of orthologous splicing isoforms [1, 2] and combine partial trees on orthology groups into a complete protein tree for a gene family [3, 4]. Aligning and measuring the similarity between homologous CDS requires to account for frameshift (FS) translations that cannot be detected at the amino acid (AA) level, but lead to a high similarity at the nucleotide level between functionnaly different sub-sequences.

FS translation consists in alternative AA translations of a coding region of DNA using different translation frames [5]. It is an important phenomenon resulting from different scenarios such as, insertion or deletion of a nucleotide sequence whose length is not a multiple of 3 in a CDS through alternative splicing [6, 7] or evolutionary genomic indels [8, 9], programmed ribosomal frameshifting [10], or sequencing errors [11]. Recent studies have reported the role of FS translations in the appearance of novel CDS and functions in gene evolution [6, 12]. FS translation has also been found to be linked to several diseases such as the Crohn’s disease [13]. The computational detection of FS translations requires the alignment of CDS while accounting for their codon structure. A classical approach for aligning two CDS used in most alignment tools [14, 15] consists in a three-step method, where the CDS are first translated into AA sequences using their actual coding frame, then AA sequences are aligned, and finally the AA alignment is back-translated to a CDS alignment. This approach does not account for alternative AA translations between two CDS and it leads to incorrect alignment of the coding regions subject to FS translation. The opposite problem of aligning protein sequences while recovering their hypothetical nucleotide CDS sequences and accounting for FS translation was also studied in several papers [16, 17].

Here, we consider the problem of aligning two CDS while accounting for FS translation, by simultaneously accounting for their nucleotide and AA sequences. The problem has recently regained attention due to the increasing evidence for alternative protein production through FS translation by eukaryotic gene families [18, 19].

The problem was first addressed by Hein et al. [20, 21] who proposed a DNA/protein model such that the score of an alignment between two CDS of length n e m is a combination of its score at the nucleotide level and its score at the AA level. They described a O(n 2 m 2 ) algorithm in [20], later improved to a O(nm) algorithm in [21] for computing an optimal score alignment, under the constraint that the search space of the problem is restricted. Arvestad [22] later proposed a CDS alignment scoring model with a O(nm) alignment algorithm accounting for codon structures and FS translations based on the concept of generalized substitutions introduced in [23]. In this model, the score of a CDS alignment depends on its decomposition into a concatenation of codon fragment alignments, such that a codon fragment of a CDS is defined as a substring of length C, (0le w le 5) . This decomposition into codon fragment alignments allows to define a score of the CDS alignment at the AA level. More recently, Ranwez et al. [18] proposed a simplification of the model of Arvestad limiting the maximum length of a codon fragment to 3. Under this model, a O(nm) CDS alignment algorithm was described and extended in the context of multiple sequence alignment [18]. In the models of Arvestad [22] and Ranwez et al. [18], several scores may be computed for the same alignment based on different decompositions into codon fragment alignments. The corresponding algorithms for aligning two CDS then consist in computing an optimal score decomposition of an alignment between the two CDS. This optimal score exclusively accounts for FS translation initiations, i.e a FS translation in an alignment is penalized by adding a constant FS cost, which only penalizes the initiation of the FS, not accounting for the length of this FS translation. However, taking account of FS translation lengths is important in order to increase the precision of CDS alignment scores, as these lengths induce more or less disruptions between the protein sequences.

In this paper, we propose the first alignment algorithm that accounts for both the initiation and the length of FS translations in order to compute the similarity scores of CDS alignments. The remaining of the paper is organized as follows. In the “Motivation”, we illustrate the importance of accounting for FS translation length when aligning CDS. In the “Preliminaries”, we give some preliminary definitions and we introduce a new CDS alignment scoring model with a self-contained definition of the score of an alignment penalizing both the initiation and the extension of FS translations. In the “Methods”, a dynamic programming algorithm for computing an optimal score alignment between two CDS is described. Finally, in the “Results”, we present and discuss the results of a comparison of our method with other CDS alignment methods for a pairwise comparison of CDS from homologous genes of ten mammalian gene families.

Motivation: importance of accounting for FS translation length

The two main goals of aligning biological sequences are to evaluate the similarity and to identify similar regions between the sequences, used thereafter to realize molecular analyses such as evolutionary, functional and structural predictions. In practice, CDS alignment can be used to exhaustively identify the conserved features of a set of proteins. Thus, the definition of CDS similarity must account for sequence conservation and disruptions at both the nucleotide and the protein levels.

Figure 1 illustrates the importance of accounting for AA translations and FS translation length in order to compute an adequate similarity score for a CDS alignment. It describes an example of three CDS Seq1 , Seq2 and Seq3 . Seq1 has a length of 45. The CDS Seq2 has length 60 and is obtained from Seq1 by deleting the nucleotide ‘G’ at position 30 and adding 16 nucleotides at the end. The CDS Seq3 has length 60 and is obtained from Seq1 by deleting the nucleotide ‘G’ at position 15 and adding 16 nucleotides at the end.

Principal an example of three CDS Seq1 , Seq2 and Seq3 . Meio an optimal alignment between Seq1 and Seq2 with a FS translation region of length 15. Fundo an optimal alignment between Seq1 and Seq3 with a FS translation region of length 30

When looking at the AA translations of Seq1 , Seq2 and Seq3 , we observe that the similarity between Seq2 and Seq1 is higher than the similarity between Seq3 and Seq1 at the protein level, because Seq1 and Seq2 share a longer AA prefix “M T E S K Q P W H” (amino acids in black characters in the alignments). However, the pairwise CDS alignment algorithms that do not account for the length of FS translations would return the same score for the two following optimal alignments of Seq1 with Seq2 and Seq1 with Seq3 , penalizing only the initiation of one FS translation in both cases (positions marked with a “!” symbol in the alignments), and not penalizing the sequence disruptions at the protein level.

From an evolutionary point of view, a good scoring model for evaluating the similarity between two CDS in the presence of FS translations should then penalize not only the initiation of FS but also the length of FS translations extension (amino acids in gray characters in the alignments). The alignment of Seq1 with Seq2 would then have a higher similarity score than the alignment of Seq1 with Seq3 .

Preliminaries: score of CDS alignment

In this section, we formally describe a new definition of the score of a CDS alignment that penalizes both the initiation and the extension of FS translations.

Definição 1

[Coding DNA sequence (CDS)] A coding DNA sequence (CDS) is a DNA sequence on the alphabet of nucleotides (Sigma _N=) whose length n is a multiple of 3. A coding sequence is composed of a concatenation of (frac<3>) codons that are the words of length 3 in the sequence ending at positions 3eu, (1 le i le frac<3>) . The AA translation of a CDS is a protein sequence of length (frac<3>) on the alphabet (Sigma _A) of AA such that each codon of the CDS is translated into an AA symbol in the protein sequence.

Note that, in practice an entire CDS begins with a start codon “ATG” and ends with a stop codon “TAA” , “TAG” or “TGA” .

Definição 2

(Alignment between DNA sequences) An alignment between two DNA sequences A e B is a pair ((A',B')) where (A') and (B') are two sequences of same length eu derived by inserting gap symbols ('-') in A e B, such that (forall i,

1 le i le L) , in the alignment is called a column of the alignment.

Given an alignment ((A',B')) of length eu between two CDS A e B, let S be the sequence (A') or (B') . We denote by (S[k

1 le k le l le L) , the substring of S going from position k to position eu. (left| ight|) denotes the number of letters in () that are different from the gap symbol ('-') . For example, if (A'= exttt) and (B'= exttt) , (|A'[4

8]| = | exttt| = 3) . A codon of A ou B é grouped in the alignment ((A',B')) if its three nucleotides appear in three consecutive columns of the alignment. For example, the first codon ACC of A is grouped, while the first codon ACT of B is not grouped.

An alignment ((A',B')) of length 48 between two CDS, A (13 codons) and B (14 codons). o number arrays indicate the positions of the consecutive alignment columns. Codons of A e B estão colored according to the set to which they belong: IM codons in blue color, FSext codons in red color, InDel codons in green color and FSinit codons in black color. MFS nucleotides contained in FSinit codons are underlined

In the following, we give our definition of the score of an alignment ((A',B')) between two CDS A e B. It is based on a partition of the codons of A (resp. B) into four sets depending on the alignment of codons (see Fig. 2 for an illustration):

The set of In-frame Matching codons (IM) contains the codons that are grouped in the alignment and aligned with a codon of the other CDS.

The set of Frameshift extension codons (FSext) contains the codons that are grouped in the alignment and aligned with a concatenation of three nucleotides that overlaps two codons of the other CDS.

The set of Deleted/Inserted codons (InDel) contains the codons that are grouped in the alignment and aligned with a concatenation of 3 gap symbols.

All other codons constitutes Frameshift initiation codons (FSinit) . The set of Matching nucleotides in FSinit codons (MFS) contains all the nucleotides belonging to FSinit codons and aligned with a nucleotide of the other CDS.

The following notations and conventions are used in Definition 3 to denote the different sets of codons and nucleotides in A e B. The set of IM codons in A (resp. B) is denoted by ( exttt_) (resp. ( exttt_) ). The set of FSext codons in A (resp. B) is denoted by ( exttt_) (resp. ( exttt_) ). The set of InDel codons in A (resp. B) is denoted by ( exttt_) (resp. ( exttt_) ). The set of MFS nucleotides in A (resp. B) is denoted by ( exttt_) (resp. ( exttt_) ). In these sets, the codons of A e B are simply identified by the position (column) of their last nucleotide in the alignment. In this case, we always have ( exttt_ = exttt_) as in the example below. The MFS nucleotides are also identified by their positions in the alignment.

In the alignment scoring model described in Definition 3, the substitutions of IM and FSext codons are scored using an AA scoring function (s_) such that aligned codons with silent nucleotide mutations get the same score as identity. A fixed FS extension cost denoted by fs_extend_cost is added for each FSext codon. The insertions/deletions of InDel codons are scored by adding a fixed gap cost denoted by gap_cost for each InDel codon. The alignment of MFS nucleotides are scored independently from each other, using a nucleotide scoring function (s_). The insertions or deletions of nucleotides in FSinit codons are responsible for the initiation of FS translations. They are then scored by adding a fixed FS opening cost denoted by fs_open_cost for each FSinit codon. Note that, by convention, the values of all penalty costs for gap and FS ( gap_cost , fs_open_cost , fs_extend_cost ) are negative. Note also that the scoring scheme assumes that the AA and the nucleotide scoring functions, (s_) and (s_) , are symmetric.

Definition 3

(Score of an alignment) Let ((A',B')) be an alignment of length eu between two CDS A e B. The score of the alignment ((A',B')) is defined by:


Title: Pocket arithmetic and Needleman-Wunsch on Cray Research computers

In the interest of providing more efficient computer-based analysis of DNA and protein sequences, Cray Research has developed a high performance implementation of the sequence alignment method of Needleman and Wunsch using the programming technique of pocket arithmetic. The basis for this implementation is the program SEQHDP, which finds locally homologous subsequences of a protein sequence pair and determines the statistical significance of the homology. Pocket arithmetic takes advantage of the 64-bit width of an operand on the Cray Y-MP by packing more than one integer value per word, then performing logical or integer operations on the packed word to yield multiple results per operation. This technique, in combination with the vector processing capabilities of the Cray Y-MP CPU, produces substantially improved performance over the conventionally coded version of the same algorithm. The authors will introduce the programming technique of pocket arithmetic, then describe its implementation in the Needleman-Wunsch sequence comparison function in SEQHDP. Performance results based on actual protein sequence comparisons are presented.


Assista o vídeo: Algorithm Needleman-Wunsch (Janeiro 2022).