Alinhamentos e comparação de sequências / Alignment and comparison of sequences

AUTOR(ES)

Francisco Eloi Soares de Araujo

FONTE

IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia

DATA DE PUBLICAÇÃO

24/05/2012

RESUMO

A comparação de sequências finitas é uma ferramenta que é utilizada para a solução de problemas em várias áreas. Comparamos sequências inferindo quais são as operações de edição de substituição, inserção e remoção de símbolos que transformam uma sequência em uma outra. As matrizes de pontuação são estruturas largamente utilizadas e que definem um custo para cada tipo de operação de edição. Uma matriz de pontuação G é indexada pelos símbolos do alfabeto. A entrada de G na linha A, coluna B mede o custo da operação de edição para substituir o símbolo A pelo símbolo B. As matrizes de pontuação induzem funções que atribuem uma pontuação para um conjunto de operações de edição. Algumas dessas funções para a comparação de duas e de várias sequências são estudadas nesta tese. Quando cada símbolo de cada sequência é editado exatamente uma vez para transformar uma sequência em outra, o conjunto de operações de edição pode ser representado por uma estrutura conhecida por alinhamento. Descrevemos uma estrutura para representar o conjunto de operações de edição que não pode ser representado por um alinhamento convencional e descrevemos um algoritmo para encontrar a pontuação de uma sequência ótima de operações de edição usando um algoritmo conhecido para encontrar a pontuação de um alinhamento convencional ótimo. Considerando três diferentes funções induzidas de pontuação, caracterizamos, para cada uma delas, a classe das matrizes para as quais as funções induzidas de pontuação são métricas nas sequências. Dadas duas matrizes de pontuação G e G\ , dizemos que elas são equivalentes para uma dada função que é induzida por uma matriz de pontuação e que avalia a qualidade de um alinhamento se, para quaisquer dois alinhamentos A e B, vale o seguinte: o alinhamento A é ``melhor\ \ do que o alinhamento B considerando a matriz G se e somente se A é ``melhor\ \ do que o alinhamento B considerando a matriz G\ . Neste trabalho, determinamos condições necessárias e suficientes para que duas matrizes de pontuação sejam equivalentes. Finalmente, definimos três novos critérios para pontuar alinhamentos de várias sequências. Todos os critérios consideram o comprimento do alinhamento além das operações de edição por ele representadas. Para cada um dos critérios definidos,propomos um algoritmo e o problema de decisão correspondente mostramos ser NP-completo.

ASSUNTO(S)

alinhamento de sequências alinhamento de várias sequências. alinhamento estendido custo normalizado de alinhamentos distância de edição edit distance equivalent matrices extended alignment matrizes equivalentes metric métrica multiple sequence alignments. normalized alignment cost sequence alignment

Documentos Relacionados

• Alinhamento múltiplo progressivo de sequências de proteínas
• Protein structure comparison via contact map alignment
• Compilation and alignment of DNA polymerase sequences.
• A COMPLEXIDADE INTERACIONAL NA CENTRAL DE RESERVAS DE UMA COMPANHIA AÉREA: ENQUADRES, ALINHAMENTOS E SEQÜÊNCIAS CONVERSACIONAIS EM UM CONTEXTO INSTITUCIONAL
• FPGA architectures for biological sequence comparison in linear space