Alinhamento de seqüências com rearranjos (2007)
- Authors:
- Autor USP: VELLOZO, AUGUSTO FERNANDES - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Subjects: ALGORITMOS E ESTRUTURAS DE DADOS; BIOINFORMÁTICA
- Agências de fomento:
- Language: Português
- Abstract: 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
-
ABNT
VELLOZO, Augusto Fernandes. Alinhamento de seqüências com rearranjos. 2007. Tese (Doutorado) – Universidade de São Paulo, São Paulo, 2007. Disponível em: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-04052007-185842/. Acesso em: 19 abr. 2024. -
APA
Vellozo, A. F. (2007). Alinhamento de seqüências com rearranjos (Tese (Doutorado). 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. Alinhamento de seqüências com rearranjos [Internet]. 2007 ;[citado 2024 abr. 19 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-04052007-185842/ -
Vancouver
Vellozo AF. Alinhamento de seqüências com rearranjos [Internet]. 2007 ;[citado 2024 abr. 19 ] Available from: http://www.teses.usp.br/teses/disponiveis/45/45134/tde-04052007-185842/
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
