[pt] Este trabalho consiste na criação de uma ferramenta provedora de dados para o BLAST, denominada BioProvider. Esta é usada para prover dados realizando um gerenciamento de buffer eficiente para o BLAST, controlando também o escalonamento dos processos do mesmo. A comunicação entre o BioProvider e os processos do BLAST, assim como o controle de concorrência e bloqueios, é feita por meio de um driver, que substitui as chamadas a funções de leitura e escrita de arquivos do banco de dados. Deste modo, o código do BLAST não precisa ser modificado para ser realizar a comunicação com o BioProvider e este pode ser usado para diferentes versões do BLAST. O desenvolvimento do BioProvider é a primeira etapa para a criação de uma solução aplicável também a outras ferramentas de Bioinformática. Por ser transparente aos programas, a ferramenta desenvolvida é facilmente extensível, podendo ser futuramente modificada para prover dados para outros aplicativos, usar outras estratégias de gerência de buffer ou prover dados armazenados em formatos diferentes dos lidos por processos clientes, convertendo-os em tempo de execução. O BioProvider foi testado com a versão recente do NCBI BLAST, obtendo consideráveis melhoras de desempenho, e seu funcionamento foi verificado também com a versão do WU-BLAST com código aberto. Foram realizadas análises de variações no algoritmo de gerenciamento de buffer e dos fatores que influenciam o desempenho dos processos BLAST. / [en] This work consists on the creation of a tool named BioProvider to provide data to BLAST. The tool provides the data using buffer management techniques that are efficient for BLAST and controls process scheduling. The communication between BioProvider and the BLAST processes, as well as the concurrency and blocking control, is done through a device driver that substitutes the read and write function calls to the database files. By this means, the application code can remain unchanged and BioProvider can be used with different versions of BLAST. The development of BioProvider was the first stage to the creation of a solution that can be applied as well to other Bioinformatics tools. Due to its transparency in the view of other applications, BioProvider can be easily extended in the future to provide data to other applications, to use other buffer management techniques or to provide data stored in different formats of those read by the client processes, converting the data in runtime. BioProvider has been tested with the most recent version of NCBI BLAST and considerable improvement has been verified. The tool has been shown to work as well with the open source version of WU-BLAST. Some variations on the buffer management algorithm were studied, as well as the different factors that influence the performance of BLAST processes.

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