[en] HEURISTICS FOR THE PROBLEM OF DNA SEQUENCING BY HYBRIDIZATION

• Ano de defesa: 2005
• Autor(a) principal: ERALDO LUIS REZENDE FERNANDES
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: MAXWELL
• Palavras-chave em Português: [pt] OTIMIZACAO COMBINATORIA; [pt] MEMORIA ADAPTATIVA; [pt] CONSTRUCAO DE VOCABULARIO; [pt] SEQUENCIAMENTO DE DNA; [pt] SEQUENCIAMENTO POR HIBRIDACAO; [pt] BIOLOGIA COMPUTACIONAL; [pt] ALGORITMO; [pt] HEURISTICA; [en] COMBINATORIAL OPTIMIZATION; [en] ADAPTIVE MEMORY; [en] VOCABULARY BUILDING; [en] DNA SEQUECING; [en] SEQUENCING BY HYBRIDIZATION; [en] COMPUTATIONAL BIOLOGY; [en] ALGORITHM; [en] HEURISTICS
• Link de acesso: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=6412&idi=1; https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=6412&idi=2; http://doi.org/10.17771/PUCRio.acad.6412

[pt] O seqüenciamento por hibridação é uma alternativa interessante para a tarefa de seqüenciamento de DNA. Este método ainda está sendo aperfeiçoado e pode superar as técnicas utilizadas em termos de tempo e custo. Uma etapa crucial do método consiste em resolver um problema combinatório que pode ser formulado como um caso especial do problema do caixeiro viajante com coleta de prêmios. Neste trabalho, propõe-se uma nova heurística construtiva multi-partida para resolver este problema. Uma estratégia de aprendizado baseada em uma memória adaptativa e um procedimento de construção de vocabulário são utilizados para melhorar o desempenho da heurística multi-partida. A memória adaptativa é utilizada para intensificar as construções de novas soluções com os elementos que aparecem com uma freqüência maior nas melhores soluções encontradas anteriormente pela heurística multi-partida. O procedimento de construção de vocabulário consiste em construir novas soluções através da combinação de partes comuns a boas soluções. Testes computacionais mostraram que estas duas estratégias aumentam significativamente o desempenho da heurística multi-partida e são particularmente indicadas para problemas de escalonamento nos quais as melhores soluções são na maioria dos casos formadas por blocos de elementos que aparecem juntos com muita freqüência. A heurística proposta supera os resultados dos melhores algoritmos encontrados na literatura, tanto em termos da qualidade das soluções encontradas, como do tempo de computação.