Algoritmos genéticos e o problema de montagem de reads

Abstract

O problema de montagem de reads e um problema da Bioinform atica considerado de grande complexidade devido a sua caracter stica combinat oria e ao fato de ser um problema dependente das tecnologias de sequenciamento. Reads s~ao fragmentos de DNA e o processo de montagem consiste, idealmente, na obten c~ao de uma unica sequ^encia de DNA a partir deste conjunto de fragmentos. S~ao encontradas na literatura diferentes abordagens para a realiza c~ao da montagem. Dentre elas destacam-se aquelas baseadas em grafos de sobreposi c~ao e de Bruijn e as estrat egias gulosas. Heur sticas est~ao sendo exploradas, tais como Simulated annealing (arrefecimento simulado), Scartter search (busca tabu) e Algoritmo Gen etico (GA). Este trabalho apresenta um modelo e uma implementa c~ao para o problema de montagem de reads atrav es de um algoritmo gen etico. Os resultados mostram que este modelo e capaz de realizar a montagem e demonstram como o modelo se comporta mediantes os par^ametros estabelecido para sua execu c~ao.

ABSTRACT - The DNA Fragment Assembly Problem is a Bioinformatics problem considered as a problem of large complexity due to its combinatorial characteristic and to the fact it being a problem that depends on the sequencing technologies. Reads are DNA fragments and the assembly process consists, ideally, in obtaining a DNA sequence from this set of fragments. There are di erent approaches in the literature to make the assembly. Among them are those based on overlay graphs, Bruijn graphs and greedy strategies. Heuristics are being explored, such as Simulated Annealing, Scatter Search and genetic algorithms. This work presents a model and an implementation for the DNA Fragment Assembly Problem using a genetic algorithm. The results show that this model is capable of performing the assembly and demonstrates how the model behaves using parameters established for its running.