Dissertação (mestrado)—Universidade de Brasília, Instituto de Ciências Exatas, Departamento de Ciência da Computação, 2009. / Submitted by Allan Wanick Motta (allan_wanick@hotmail.com) on 2010-07-16T19:38:07Z
No. of bitstreams: 1
2009_LidiaAraujoMiranda.pdf: 5472186 bytes, checksum: 3bc128515fab954a95e110f39e6c356c (MD5) / Approved for entry into archive by Lucila Saraiva(lucilasaraiva1@gmail.com) on 2010-07-19T14:24:14Z (GMT) No. of bitstreams: 1
2009_LidiaAraujoMiranda.pdf: 5472186 bytes, checksum: 3bc128515fab954a95e110f39e6c356c (MD5) / Made available in DSpace on 2010-07-19T14:24:14Z (GMT). No. of bitstreams: 1
2009_LidiaAraujoMiranda.pdf: 5472186 bytes, checksum: 3bc128515fab954a95e110f39e6c356c (MD5)
Previous issue date: 2009 / O Alinhamento Múltiplo de Sequências genéticas (AMS) é executado milhares de vezes ao dia por cientistas, a fim de identificar regiões de semelhança entre três ou mais sequências. Os alinhamentos múltiplos assim obtidos são usados na resolução de problemas complexos, como a determinação do histórico evolutivo das espécies. Por se tratar de um problema NP-completo, geralmente são utilizadas soluções heurísticas para a sua resolução. Dentre soluções adotadas, destaca-se o Algoritmo Genético (AG), que é um método iterativo não-determinístico, baseado nos princípios da Evolução das Espécies de Darwin. Apesar de apresentar soluções boas para o AMS, os algoritmos genéticos demandam um alto poder de processamento, que se traduz em um alto tempo de execução. Por essa razão, algumas estratégias paralelas foram propostas na literatura para acelerar a obtenção de alinhamentos múltiplos com AGs, geralmente utilizando a estratégia da ilha como base de paralelização. A presente dissertação de mestrado propõe e avalia uma estratégia paralela que utiliza Algoritmo Genético para o Alinhamento Múltiplo de Sequências, inspirada no modelo Multi-ilha. De maneira diferente das abordagens para AMS existentes na literatura, a estratégia proposta utiliza 3 Super Ilhas, onde cada Super Ilha implementa um modelo tradicional de ilhas. Os resultados obtidos com bases reais de proteínas mostram que a estratégia proposta é capaz de encontrar alinhamentos múltiplos de melhor qualidade em menor tempo, quando comparada com a estratégia de ilha tradicional. _______________________________________________________________________________ ABSTRACT / The Multiple Sequence Alignment (MSA) between genetic sequences is exhaustively
done by scientists trying to identify matching regions within three or
more sequences. The resulting multiple alignments are used in complex problems
like the one of establishing genetic relationships between biological sequences.
The MSA has been shown to be an NP-complete problem, therefore heuristic
solutions are usually used to solve it. One of the solutions that has shown good
results for MSA is the Genetic Algorithm (GA), a non deterministic iterative
method, based on Charles Darwin's theory of evolution. Though presenting good
results, the GA demands high amount of computing power, taking usually a lot
of time to be executed. To speed up the sequential algorithms execution, parallel
algorithms were proposed in the literature, most of them using the island
strategy of parallelization. This masters dissertation proposes and evaluates a
parallel strategy that uses Genetic Algorithms to the Multiple Sequence Alignment
based on the Multi-island parallelization strategy. Di erently from other
MSA strategies, the proposed strategy creates three Super Islands and each one
executes a GA parallelized by the island strategy. The results were obtained with
real protein banks and revealed that the proposed strategy is capable of nding
better multiple alignments in a smaller amount of time, when compared to the
conventional island strategy.
| Identifer | oai:union.ndltd.org:IBICT/oai:repositorio.unb.br:10482/5284 |
| Date | January 2009 |
| Creators | Miranda, Lídia Araujo |
| Contributors | Melo, Alba Cristina Magalhães Alves de, Correa, Jan Mendonça |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Source | reponame:Repositório Institucional da UnB, instname:Universidade de Brasília, instacron:UNB |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.002 seconds