Exportar registro bibliográfico

Alinhamento de seqüências com rearranjos (2007)

  • Autores:
  • Autor USP: VELLOZO, AUGUSTO FERNANDES - IME
  • Unidade: IME
  • Sigla do Departamento: MAC
  • Assuntos: ALGORITMOS E ESTRUTURAS DE DADOS; BIOINFORMÁTICA
  • Agências de fomento:
  • Idioma: Português
  • Resumo: 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ções 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, trabalhos independentes propuseram algoritmos com tempo O(n POT.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 POT. 3 log n) e outro que, sob algumas condições no sistema de pontuação, tem tempo de execução O(n POT. 3), ambos em memória O(n POT. 2). Em 1997, Benson propôs um modelo de alinhamento que reconhecesse também as duplicações em tandem. Ele propôs dois algoritmos exatos para alinhar duas seqüências com duplicaçòes em tandem: um em tempo O(n POT. 5) e memória O(n POT. 2), e outro em tempo O(n POT. 4) e memória O(n POT. 3). Propomos um algoritmo para alinhar duas seqüências com duplicações em tandem em tempo O(n POT. 3) e meória O(n POT. 2). Propomos também um algoritmo para alinhar duasseqüências com transposons (um tipo mais geral que a duplicação em tandem), em tempo O(n POT. 3) e memória O(n POT. 2)
  • Imprenta:
  • Data da defesa: 18.04.2007
  • Acesso à fonte
    Como citar
    A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

    • ABNT

      VELLOZO, Augusto Fernandes; LAGO, Alair Pereira do. Alinhamento de seqüências com rearranjos. 2007.Universidade de São Paulo, São Paulo, 2007. Disponível em: < http://www.teses.usp.br/teses/disponiveis/45/45134/tde-04052007-185842/ >.
    • APA

      Vellozo, A. F., & Lago, A. P. do. (2007). Alinhamento de seqüências com rearranjos. Universidade de São Paulo, São Paulo. Recuperado de http://www.teses.usp.br/teses/disponiveis/45/45134/tde-04052007-185842/
    • NLM

      Vellozo AF, Lago AP do. Alinhamento de seqüências com rearranjos [Internet]. 2007 ;Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-04052007-185842/
    • Vancouver

      Vellozo AF, Lago AP do. Alinhamento de seqüências com rearranjos [Internet]. 2007 ;Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-04052007-185842/


Biblioteca Digital de Produção Intelectual da Universidade de São Paulo     2012 - 2021