A determinação de regiões homólogas de sequências moleculares muitas vezes é usado para mais de inferência de sua função e evolução, e, portanto, precisas de alinhamento múltiplo de seqüência (MSA) de ácido nucleico e de sequências de proteínas é crucial., Consequentemente, houve um enorme esforço no desenvolvimento e implementação de diferentes algoritmos MSA, usando abordagens distintas para melhorar a precisão de alinhamento resultante.

a avaliação de precisão dos programas MSA é muitas vezes feita através do emprego manual (ou semi-automaticamente) de bases de dados de sequência curadas , tais como BAliBASE, PREFAB e SABmark . Até agora, BAliBASE tem sido o banco de dados de alinhamento mais usado na avaliação do desempenho de diferentes programas de MSA. Foi construído usando sequências de proteínas ou modelos com estruturas tridimensionais conhecidas., A última versão 3.0 teve um aumento no número de sequências e alinhamentos disponíveis. Tais melhorias aparentemente abordaram as principais preocupações de Karplus e Hu no que diz respeito ao uso de BAliBASE para referenciar algoritmos de MSA.bases de dados de alinhamento

fornecem uma fonte de alinhamentos precisos para medir a precisão e velocidade de diferentes programas, mas também apresentam várias desvantagens. Embora os alinhamentos das bases de dados sejam curados manualmente, ainda há a possibilidade de desalinhamentos que resultariam em problemas de avaliação da precisão., Os conjuntos de alinhamentos ainda permanecem pequenos e podem não representar a gama completa de cenários de evolução proteica. Além disso, uma grande desvantagem da utilização de bases de dados de alinhamento é que os algoritmos podem potencialmente ser desenvolvidos e ajustados aos alinhamentos presentes apenas nestes conjuntos de dados.

recentemente tem havido vários pacotes de simulação de sequência de DNA que incorporam indels, tais como MySSP e DAWG . MySSP tem sido amplamente utilizado em diferentes estudos de inferência filogenética e estimativa de distância evolutiva, juntamente com precisão de alinhamento de DNA ., For proteins, Lassmann and Sonnhammer in a previous comparison of MSA algorithms used artificialmente created sequence sets generated by the simulation program Rose . Rose simula sequências de proteínas que permitem a ocorrência de indels. Os conjuntos de dados gerados pela Rose apresentam suas próprias limitações para o estudo da precisão do alinhamento. Em Rose, O tamanho e o número do indel não representam adequadamente dados empíricos para proteínas que divergiram em diferentes tempos evolutivos. Também o programa assume taxas evolucionárias iguais de todos os locais da proteína.,

neste estudo introduzimos uma abordagem melhorada para avaliar a precisão do alinhamento usando sequências simuladas de proteínas geradas por Simprot . Simprot é um programa de simulação avançado que emprega uma versão parametrizada da distribuição de inserção e exclusão Qian e Goldstein (indel). Embora a distribuição original fosse empiricamente derivada de um subconjunto de alinhamentos de sequências de proteínas altamente divergentes, a versão parametrizada permite uma simulação muito flexível de indels em sequências para todos os níveis de divergência de sequências., Simprot também permite substituições variáveis e taxas de indel em diferentes locais, implementando taxas de distribuição gamma. Também estão disponíveis três modelos de substituição de aminoácidos (PMB, PAM e JTT). Nós temos usado Simprot para gerar alinhamentos conhecidos com uma grande variedade de parâmetros evolutivos, bem como o mais recente banco de dados BAliBASE de alinhamentos curados, para investigar a precisão e velocidade dos programas populares e publicamente disponíveis de software de alinhamento de múltiplas sequências proteicas.,

programas de alinhamento

Existem muitos pacotes de computador disponíveis que geram MSAs de sequências de proteínas. Selecionamos nove dos programas atualmente mais usados (em ordem de data de publicação): Clustal W, Dialign2.2, T-Coffee, POA, Muscle, Mafft, ProbCons, Dialign-T e Kalign.

Clustal w versão 1.8

Este é provavelmente o programa de alinhamento mais usado e mais antigo entre os pacotes testados. O software realiza um alinhamento progressivo, primeiro empregando uma comparação de sequência emparelhada calculando uma matriz de distância que armazena divergência de sequência., Depois que esta matriz é obtida, um guia de árvore é construído usando a junção do vizinho, seguido pelo terceiro e último passo onde as sequências são alinhadas de acordo com a ordem do ramo na árvore guia. O programa emprega duas penalizações de gap em seu procedimento de alinhamento: abertura de gap e extensão de gap, e no caso de polipeptídeos, uma matriz de peso total de aminoácidos. Estas penalizações são principalmente dependentes de fatores como a matriz de peso, comprimento de sequência e similaridade., Em casos simples, Clustal W pode alinhar com precisão domínios e sequências correspondentes de estrutura secundária ou terciária conhecida, enquanto em casos mais complexos pode ser usado como um bom ponto de partida para posterior refinamento.

Dialign2. 2 Versão 2.2.1

este programa usa um método diagonal para alinhar sequências localmente e globalmente. Dialign2. 2 não compara resíduos únicos, mas inteiros ininterruptos (sem lacunas, mismatches permitidos) extensões de resíduos que formariam diagonais em uma comparação de matriz de pontos de duas sequências., Consequentemente, não penaliza a inserção e a extensão das lacunas e pode deixar segmentos não relacionados inalterados. O primeiro passo no procedimento cria todos os possíveis alinhamentos emparelhados, armazenando uma coleção de diagonais que cumprem certos critérios de consistência, sem conflitantes missões duplas ou cruzadas de resíduos . Todas as diagonais gravadas são ponderadas a fim de definir entradas com a soma máxima de pesos, e, em seguida, ordenadas a fim de determinar o grau de sobreposição, enfatizando a existência de diagonais presentes em várias sequências., Um algoritmo ganancioso faz um processamento final, verificando pontuações diagonais de cima para baixo, criando um alinhamento múltiplo final. As aberturas são inseridas no final da criação do MSA até que todos os resíduos presentes estejam conectados.

T-Coffee (função objetiva de coerência baseada em árvores para avaliação do alinhamento) a versão 3.27

t-Coffee emprega uma estratégia progressiva em alinhamentos de sequências. O programa primeiro cria uma biblioteca de duas fontes diferentes: alinhamentos globais de Clustal W e alinhamentos locais de Lalign ., Para cada par de sequências, os alinhamentos globais e os alinhamentos locais emparelhados são criados a partir dos dez segmentos top-scoring não-intersectantes. O programa processa a informação global e local, atribuindo pesos a todos os alinhamentos emparelhados em relação à identidade de sequência . Isto é seguido pela combinação de grupos que são fundidos em uma única biblioteca. Há uma fase de extensão para esta biblioteca combinada, fazendo com que o peso final de qualquer par de resíduos reflita parte da informação contida em toda a biblioteca., Um passo final requer um cálculo de uma matriz de distância e uma árvore de união vizinha, uma vez que o alinhamento é gerado com uma estratégia progressiva, alinhando as duas sequências mais próximas na árvore de acordo com o peso armazenado na biblioteca estendida. O par inicial é então fixo e quaisquer lacunas existentes não podem ser deslocados mais tarde. O alinhamento progressivo continua até que cada sequência esteja alinhada.

POA (alinhamento parcial da ordem) versão 2.0

POA é outro pacote MSA que usa um algoritmo de alinhamento progressivo sem usar perfis generalizados., Este programa introduz o uso de uma ordem parcial-alinhamento de sequências múltiplas (PO-MSA) formato para representar sequências, e mais precisamente reflete o conteúdo biológico. Este formato armazena o alinhamento como um grafo compactado para contagens mínimas de nó e aresta, ainda contendo toda a informação disponível em um MSA tradicional. Sequências são armazenadas como uma série linear de nós cada um conectado por duas arestas. POA usa um algoritmo de programação dinâmica tradicional, onde sequências lineares são substituídas por grafos de ordem parcial (PO)., Estas estruturas PO são transformadas em matrizes 2D usuais e cada combinação de células são contadas para trás como em um procedimento tradicional de alinhamento de sequências Smith-Waterman . Estas matrizes são então estendidas em qualquer direção (diagonal, horizontal, vertical) permitindo a produção do alinhamento emparelhado em pontos de junção. O MSA é obtido a partir do alinhamento de duas sequências no início com a adição de outras sequências sucessivamente ao par inicial.

Muscle (Multiple sequence comparison by log-expectation) version 3.,6

músculo utiliza uma abordagem de alinhamento do perfil emparelhado. O programa primeiro constrói um alinhamento progressivo que é então melhorado e refinado em duas fases subsequentes. O alinhamento progressivo é criado após as semelhanças de sequência, uma estimativa de distância e uma árvore UPGMA são calculadas. Muscle usa duas medidas de distância: uma distância K mer para pares de sequência Não Alinhados e uma distância Kimura para pares alinhados . O estágio de melhoria progressiva do alinhamento cria uma nova árvore com a já calculada matriz de distância Kimura e, em seguida, constrói um melhor alinhamento com base nesta árvore melhorada., A última fase de refinamento emprega uma variante do particionamento Restrito dependente da árvore . Este método elimina uma das arestas das árvores, bi-particionando o alinhamento e extraindo os perfis de ambas as partições que são então realinhados com um alinhamento perfil-perfil. Cada aresta da árvore é visitada iterativamente e o alinhamento com uma pontuação agregada actualizada de cada par de sequências é mantido. As bordas são visitadas por ordem decrescente de distância da raiz, com um realinhamento de sequências individuais, movendo-se para grupos de sequências mais estreitamente relacionados .,

Mafft (alinhamento Múltiplo de seqüência baseada na transformada Rápida de Fourier) versão 5.732

Mafft é um programa que pode ser usado com diferentes alinhamento se aproxima, um progressivo alinhamento sozinho (com a transformada Rápida de Fourier), ou progressivo seguido por iterativo de refinamento. A execução básica do Mafft pode ter até três etapas, mas o procedimento padrão executa as duas etapas iniciais. Primeiro, um alinhamento progressivo é criado com base em uma distância aproximada entre cada par de sequências baseado em 6-tuplas compartilhadas., Uma árvore guia também é gerada pela UPGMA com ligação modificada e sequências são então alinhadas seguindo a ordem do ramo da árvore (este passo sozinho é chamado de estratégia FFT-NS-1). O segundo passo recalcula uma matriz de distância, com base em informações coletadas no passo anterior, e o alinhamento progressivo é re-feito usando uma árvore obtida a partir da nova matriz como um ponto de partida (até esta etapa, a estratégia é conhecida como FFT-NS-2 e é o padrão utilizado pelo software)., A última fase é o refinamento iterativo que otimiza a Pontuação da soma ponderada de pares (WSP) do Gotoh, com um alinhamento Grupo-A-grupo e a técnica de partição de restrição árvore-dependente . Se todos os três passos são empregados, o procedimento é chamado FFT-NS-i, O que significa que ele usa um método FFT para identificar rapidamente regiões homólogas presentes nas sequências que é seguido por uma fase iterativa de refinamento., FFT converte cada aminoácido presente em uma sequência para um vetor representando volume e polaridade, que são fatores importantes em eventos de substituição, permitindo que o software predisse tais ocorrências com precisão.

Mafft também inclui três algoritmos de refinamento adicionais: L-INS-i, G-INS-i e E-INS-I. Estas estratégias aumentam o número de passos necessários para criar um alinhamento MSA para cinco. Nestes casos, o primeiro passo também requer a construção de uma matriz de distância, não usando 6 tuplas., Diferentemente das abordagens FFT-NS-* não há reconstrução da árvore UPGMA calculada e o programa se move para o segundo passo, dividindo os segmentos livres de gap e armazenando matrizes de pontuação para cada segmento livre de gap de uma sequência para outra. Mafft então calcula um valor de “importância” a partir da pontuação do segmento e armazena a frequência com que os resíduos aparecem em outros segmentos., Todos os valores de ” importância “são então reunidos em uma matriz de” importância ” na etapa três, que é rapidamente seguido por um alinhamento Grupo-A-grupo obtido a partir das matrizes de pontuação e um esquema de ponderação baseado em um algoritmo Needleman-Wunsch. Uma etapa final refina os alinhamentos obtidos, otimizando uma pontuação WSP e os valores de” importância ” calculados anteriormente.

ProbCons (probabilistic Consistency-based multiple sequence alignment) version 1.1

ProbCons is the only program that uses a probabilistic consistency method of alignment., É uma modificação do tradicional sistema de pontuação de soma de pares, e, além disso, incorpora um algoritmo de alinhamento progressivo baseado no modelo Markov. O procedimento de alinhamento é dividido em quatro etapas, começando com um cálculo de matrizes de probabilidade posterior para cada par de sequências. Isto é seguido por um cálculo dinâmico de programação da precisão esperada de cada alinhamento emparelhado. A transformação de consistência probabilística é então empregada a fim de reavaliar as pontuações de precisão do jogo., Calcula-se uma árvore-guia com agrupamento hierárquico com a semelhança definida por uma média ponderada de valores entre sequências de cada conjunto. A árvore guia é usada para alinhar as sequências usando uma abordagem progressiva. Uma fase de pós-processamento também é feita, onde bi-partições aleatórias do alinhamento gerado são realinhadas, a fim de verificar as regiões de melhor alinhamento. Os ProbCons diferem de outros programas de alinhamento, uma vez que não incorporam conceitos biológicos como pontuação de gap específica da posição, construção evolutiva de árvores e outras características comumente usadas por outros pacotes.,

Dialign-T versão 0.2.1

este programa é uma re-implementação do procedimento desenvolvido em Dialign2.2, mas com uma melhor solução para lidar com fragmentos inconsistentes, incluindo encadeamento de fragmentos. Ele também implementa uma nova abordagem para estimar probabilidades da ocorrência aleatória de cada fragmento presente na sequência a ser alinhada. Dialign-T não usa tabelas pré-calculadas para obter pontuações de peso: calcula tabelas de probabilidade de várias matrizes de substituição. Além disso, o algoritmo de alinhamento múltiplo ganancioso de Dialign2.,2 foi alterado a fim de evitar semelhanças locais espúrias.

Kalign version 1.04

Kalign is another program that uses a progressive alignment approach to obtain the best MSA possible. A principal diferença deste algoritmo para outros métodos é que ele emprega o algoritmo de aproximação de cordas Wu-Manber ao calcular a distância entre as sequências. O algoritmo de Wu-Manber mede a distância entre duas cadeias de caracteres usando uma distância de edição Levenshtein, o que permite uma busca eficiente por discrepâncias (compartilhadas ou não) e padrões presentes nas sequências., De acordo com os desenvolvedores do Kalign, esta metodologia permite uma estimativa de distância que é tão rápida quanto um algoritmo k-tuple, mas é mais precisa . O primeiro passo no processo de alinhamento é calcular as distâncias em pares usando a abordagem Wu-Manber. A estimativa da distância emparelhada é seguida por uma construção de uma árvore guia usando UPGMA, que é empregado em um método de programação dinâmica global para alinhar as sequências/perfis., Além disso, o programa executa uma verificação de consistência a fim de definir o maior conjunto de sequência de jogos que podem ser inseridos em um alinhamento, utilizando uma versão modificada do Needleman-Wunsch para encontrar mais consistentes caminho através da matriz de programação dinâmica. Além disso, Kalign atualiza as posições de matchings de padrões, que ajusta a posição absoluta de matchs encontrados dentro das seqüências para suas posições relativas dentro dos perfis gerados .