O problema dos uns consecutivos utilizando arquiteturas reconfiguráveis

Abstract

As arquiteturas reconfiguráveis possibilitam que a função do hardware seja implementada pelo usuário. Por causa de suas características, estas arquiteturas têm sido usadas em muitas áreas, inclusive a Bioinformática. Muitos problemas em Bioinformática podem ser representados por modelos matemáticos que, por sua vez, podem ser resolvidos por métodos computacionais. O problema dos uns consecutivos é um exemplo destes problemas, e trata da obtenção de uma permutação de colunas em uma matriz binária, de modo que todos os uns em cada linha sejam consecutivos. Esta matriz representa informações sobre fragmentos de DNA e sondas, os quais permitem a identificação da ordem relativa entre os fragmentos e, assim, auxiliam a determinação da ordem das bases nitrogenadas que formam o DNA original. Nesta dissertação são descritos alguns conceitos sobre arquiteturas reconfiguráveis e os principais dispositivos de lógica programável. Também são revisados o problema dos uns consecutivos e um algoritmo para resolvê-lo. São apresentadas diversas implementações, em hardware reconfigurável, de partes do algoritmo para resolução do problema dos uns consecutivos de modo a obter um melhor desempenho em sua execução. Também são apresentados e discutidos os resultados obtidos através de experimentos realizados com estas implementações. Finalmente, são descritas as conclusões deste trabalho e mostrados os trabalhos futuros que podem expandir as soluções apresentadas.

Reconfigurable architectures enable the hardware function to be implemented by the user. Due to its characteristics, these architectures have been used in many areas, including Bioinformatics. Many problems in Bioinformatics can be represented by mathematical models that, in turn, can be solved by computational methods. The consecutive ones problems is an example of such problems. Its goal is to find a permutation of columns in a binary matrix, in such a way that all the ones in each row are consecutive. This matrix represents information abou DNA fragments and, thus, assist the determination of the order of the nitrogened bases that form the original DNA. This work describes the concepts of reconfigurable architectures and the main programmable logic devices. The consecutive ones problem and an algorithm to solve it are also revised. It is also presented several implementations, in a reconfigurable hardware, of sections of the algorithm for solving the ones consecutive problem, in order to achieve a better performance in its execution. The results obtained through experiments performed with these implementations are presented and analyzed. Finally, the conclusions of this work are describe and the future work that can expand the presented solutions are shown.