Please enable JavaScript.
Coggle requires JavaScript to display documents.
Alinhamento de sequência de caracteres - Coggle Diagram
Alinhamento de sequência de caracteres
Distância de edição
Definição
Essa distância é o número mínimo de edições necessárias para transformar uma sequência na outra.
Uma distância = 0 significa que as sequencias são iguais.
Uma distância ≥ 1 significa que as sequências são diferentes.
As edições que podem transformar uma sequência na outra são: substituição, inserção ou deleção.
A distância entre uma sequência vazia e uma sequência cheia de tamanho n é = n
Introdução
A diferença entre duas sequências de caracteres pode ser expressa por meio da
distância de edição de Levenshtein.
Algorítimo
Matrizes são usadas para armazenar os cálculos de distância de edição.
As células da matriz são preenchidas ao comparar os caracteres da primeira sequência com os caracteres da segunda sequência e gerar um valor que é armazenado.
Regras definem como a matriz é preenchida, quadro delas são a essencia do algorítimo.
o número de colunas é definido pelo tamanho da primeira sequência + 1 (uma célula é destinada ao vazio)
O número de linhas é definido pelo tamanho da segunda sequência + 1 (uma célula é destinada ao vazio)
As linhas são preenchidas de 0-tamanho de uma sequência, as colunas, semelhantemente, de 0-tamanho de outra sequência.
Os valores das colunas existentes são usados para calcular os valores das colunas vazias, após serem submetidas as regras.
Cada célula representa um caracter x da linha e um caractere y da coluna, sendo os caracteres precedentes (ou prefixos) chamados de alfa e beta:
Célula = alfaXbetaY, sendo alfa e beta caracteres precedentes
O valor da célula atual será o valor mínimo dentre uma das seguintes condições:
O valor da célula ALFAX-BETA (horizontal esquerda)
+1
Significa que o valor necessário para alfa virar beta é conhecido, porém mais uma operação será necessária devido a inserção
O valor da célula ALFA-BETAY (superior)
+!
Significa que o valor necessário para beta virar alfa é conhecido, porém mais uma operação será necessária devido a deleção.
O valor da célula ALFA-BETA (diagonal superior esquerda)
+0, se x e y forem iguais
+1 se x e y forem diferentes
"Significa que o valor necessário para um prefixo virar o outro já é conhecido, falta saber do caractere adicional ou sufixo"
Se os sufixos são iguais não será necessário mais nenhuma modificação da sequencia, ou seja, adiciona-se zero a distância de edição. Caso sejam distintos será necessário mais uma modificação na sequência, ou seja, adiciona-se 1 à distância de edição
Preenchida a matriz, a célula do canto inferior direito conterá a distância de edição (ações necessárias para converter uma sequência de caracteres em outra.
Alinhamento global
Introdução
Alinhar sequências permite compará-las.
O alinhamento global pode ser usado para comparar genes/alelos, sequências similares.
Algorítimo
O tamanho da matriz é definido. X+1 para linhas e Y+1 para colunas.
Com exceção de [0][0], as células da lateral esquerda e da borda superior recebem a penalidade máxima (pois estão alinhando com a célula que representa o caractere vazio
regras de preenchimento
O valor para substituição ou match é dado pela matriz
O valor de inserção é dado pela matriz
O valor de deleção é dado pela matriz
Traceback
Para determinar a sequencia de (menor) valor com (menos) penalidades, pega-se o valor da célula inferior direita e analisa as celulas vizinhas até chegar na origem. (zero mais distante).
Considerando X (lateral):
Considerando Y (vertical):
Cima: X + espaço
Esquerda: Y + espaço
Diagonal: X alinha com Y
Definição
É o alinhamento de toda a extensão de uma sequência de caracteres.
Consiste em inserir espaços entre as sequências até que todos os caracteres de uma sequência esteja pareado com o de outra sequência
Diferentemente do algorítimo de distância de edição que dá a mesma pontuação para cada mismatch, o alinhamento global atribui valores a célula por meio de uma tabela de penalidades.
Matches não recebem pontuação (=0), já as penalidades são dadas conforme a frequencia esperada de ocorrencia de eventosl, no caso os eventos mais infrequentes recebem as maiores pontuações, sendo a ordem: Indels>transverções>transições
Alinhamento local
Introdução
Dada duas sequencias, retorna a substring mais similar entre as duas.
É boa para detectar pontos similares de uma sequência
Definição
Encontra o par de substring mais similar entre X e Y
Algorítimo
Distingui-se do alinhamento global pelo sistema de penalidades:
Matches recebem valores positivos.
Todos outros mismatches recebem valores negativos que crescem na ordem de indels, transverções e transições.
O valor retornado é o maior entre as três possibilidades de preenchimento das células
Traceback
Encontra-se o maior valor da matriz e realiza-se o traceback