• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Tese de Doutorado
DOI
10.11606/T.45.2012.tde-12092012-230830
Documento
Autor
Nome completo
Francisco Eloi Soares de Araujo
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2012
Orientador
Banca examinadora
Soares, Jose Augusto Ramos (Presidente)
Dias, Zanoni
Ferreira, Carlos Eduardo
Martinez, Fabio Henrique Viduani
Rozante, Luiz Carlos da Silva
Título em português
Alinhamentos e comparação de sequências
Palavras-chave em português
alinhamento de sequências
alinhamento de várias sequências.
alinhamento estendido
custo normalizado de alinhamentos
distância de edição
matrizes equivalentes
métrica
Resumo em português
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.
Título em inglês
Alignment and comparison of sequences
Palavras-chave em inglês
edit distance
equivalent matrices
extended alignment
metric
multiple sequence alignments.
normalized alignment cost
sequence alignment
Resumo em inglês
Comparison of finite sequences is a tool used to solve problems in several areas. In order to compare sequences, we infer which are the edit operations of substitution, insertion and deletion of symbols that transform one sequence into another. Scoring matrices are a widely used structure to define a cost for each type of edit operation. A scoring matrix G is indexed by symbols of an alphabet. The entry in G in row A and column B measures the cost of the edit operation for replacing symbol A by symbol B. Scoring matrices induce functions that assign a score for a set of edit operations. Some of these functions for comparing two and multiple sequences are studied in this thesis. If each symbol is edited exactly once for transforming a sequence into another, the set of edit operations can be represented by a structure called alignment. We describe a structure to represent the set of edit operations that cannot be represented by a conventional alignment and we design an algorithm to find the cost of an optimal sequence of edit operations by using a known algorithm to find the cost of an optimal alignment. Considering three different kinds of induced scoring functions, we characterize, for each one of them, the class of matrices for which the induced scoring functions are metrics on sequences. Given two scoring matrices G and G', we say they are equivalent for a given function that is induced by a scoring matrix and that evaluates the quality of an alignment if, for any two alignments A and B of two sequences, we have the following: alignment A is ``better'' than B considering scoring matrix G if and only if A is ``better'' than B considering scoring matrix G'. In this work, we determine necessary and sufficient conditions for scoring matrices to be equivalent. Finally, we define three new criteria for scoring alignments of several sequence. Every criterion considers the length of the alignment and the edit operations represented by it. An algorithm for each criterion is studied and the corresponding decision problem is shown to be NP-complete.
 
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
Data de Publicação
2012-09-13
 
AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
Centro de Informática de São Carlos
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2019. Todos os direitos reservados.