• 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
 
 
Tesis Doctoral
DOI
10.11606/T.45.2007.tde-04052007-185842
Documento
Autor
Nombre completo
Augusto Fernandes Vellozo
Dirección Electrónica
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Paulo, 2007
Director
Tribunal
Lago, Alair Pereira do (Presidente)
Almeida Junior, Nalvo Franco de
Ferreira, Carlos Eduardo
Laber, Eduardo Sany
Telles, Guilherme Pimentel
Título en portugués
Alinhamento de seqüências com rearranjos
Palabras clave en portugués
Alinhamento de seqüências
bioinformática
biologia computacional
duplicação
inversão
programação dinâmica
Resumen en portugués
Uma das tarefas mais básicas em bioinformática é a comparação de seqüências feita por algoritmos de alinhamento, que modelam as alterações evolutivas nas seqüências biológicas através de mutações como inserção, remoção e substituição de símbolos. Este trabalho trata de generalizações nos algoritmos de alinhamento que levam em consideração outras mutações conhecidas como rearranjos, mais especificamente, inversões, duplicações em tandem e duplicações por transposição. Alinhamento com inversões não tem um algoritmo polinomial conhecido e uma simplificação para o problema que considera somente inversões não sobrepostas foi proposta em 1992 por Schöniger e Waterman. Em 2003, dois trabalhos independentes propuseram algoritmos com tempo O(n^4) para alinhar duas seqüências com inversões não sobrepostas. Desenvolvemos dois algoritmos que resolvem este mesmo problema: um com tempo de execução O(n^3 logn) e outro que, sob algumas condições no sistema de pontuação, tem tempo de execução O(n^3), ambos em memória O(n^2). Em 1997, Benson propôs um modelo de alinhamento que reconhecesse as duplicações em tandem além das inserções, remoções e substituições. Ele propôs dois algoritmos exatos para alinhar duas seqüências com duplicações em tandem: um em tempo O(n^5) e memória O(n^2), e outro em tempo O(n^4) e memória O(n^3). Propomos um algoritmo para alinhar duas seqüências com duplicações em tandem em tempo O(n^3) e memória O(n^2). Propomos também um algoritmo para alinhar duas seqüências com transposons (um tipo mais geral que a duplicação em tandem), em tempo O(n^3) e memória O(n^2).
Título en inglés
Sequences alignment with rearrangements
Palabras clave en inglés
bioinformatics
Computational Biology
duplications
dynamic programming
inversions
Sequence alignment
Resumen en inglés
Sequence comparison done by alignment algorithms is one of the most fundamental tasks in bioinformatics. The evolutive mutations considered in these alignments are insertions, deletions and substitutions of nucleotides. This work treats of generalizations introduced in alignment algorithms in such a way that other mutations known as rearrangements are also considered, more specifically, we consider inversions, duplications in tandem and duplications by transpositions. Alignment with inversions does not have a known polynomial algorithm and a simplification to the problem that considers only non-overlapping inversions were proposed by Schöniger and Waterman in 1992. In 2003, two independent works proposed algorithms with O(n^4) time to align two sequences with non-overlapping inversions. We developed two algorithms to solve this problem: one in O(n^3 log n) time and other, considering some conditions in the scoring system, in O(n^3) time, both in O(n^2) memory. In 1997, Benson proposed a model of alignment that recognized tandem duplication, insertion, deletion and substitution. He proposed two exact algorithms to align two sequences with tandem duplication: one in O(n^5) time and O(n^2) memory, and other in O(n^4) time and O(n^3) memory. We propose one algorithm to align two sequences with tandem duplication in O(n^3) time and O(n^2) memory. We also propose one algorithm to align two sequences with transposons (a type of duplication more general than tandem duplication), in O(n^3) time and O(n^2) memory.
 
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
tesefinal.pdf (1.14 Mbytes)
Fecha de Publicación
2007-09-27
 
ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.
Todos los derechos de la tesis/disertación pertenecen a los autores
Centro de Informática de São Carlos
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2021. Todos los derechos reservados.