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

[pt] HEURÍSTICAS PARA O PROBLEMA DE SEQÜÊNCIAMENTO DE DNA POR HIBRIDAÇÃO

[pt] ERALDO LUIS REZENDE FERNANDES

[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

[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.

[en] Sequencing by hybridization is an attractive alternative for DNA sequencing. This novel method can be less time and cost consuming than the techniques applied nowadays. A very important step of this method is to solve a combinatorial problem formulated as a special case of the prize-collecting traveling salesman problem. In this work, we propose a new multistart construtive heuristic to solve this problem. A learning strategy based on adaptive memory and a vocabulary building procedure are used to improve the performance of the multistart heuristic. The adaptive memory is used to intensify the construction of new solutions with the elements that appear frequently in the best solutions previously found by the multistart heuristic. The objective of the vocabulary building procedure is to construct new solutions combining parts of good solutions. Computational experiments have shown that these two methods significantly improves the performance of the multistart heuristic and are particularly suitable for scheduling problems whose best solutions are in most cases built by blocks of elements that appear together very often. The proposed heuristic obtains systematically better solutions and is less time consuming than the best algorithms found in the literature.

CELSO DA CRUZ CARNEIRO RIBEIRO

NOEMI DE LA ROCQUE RODRIGUEZ

CELSO DA CRUZ CARNEIRO RIBEIRO

LUIZ SATORU OCHI

LUIZ FERNANDO BESSA SEIBEL

ANTONIO BASILIO DE MIRANDA

2005-05-04

2005-03-28

[pt] TEXTO

application/pdf

application/pdf

application/pdf

application/pdf

application/pdf

application/pdf

application/pdf

PORTUGUÊS

https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=6412@1

https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=6412@2

https://doi.org/10.17771/PUCRio.acad.6412