O problema do alinhamento de segmentos

Abstract

Dentre a variedade de problemas de otimização existentes, aqueles que envolvem sequências destacam-se por sua aplicabilidade em vários campos de pesquisa. Nesta dissertação apresentamos um estudo detalhado de um novo problema de otimização combinatória envolvendo sequências, denominado Problema do Alinhamento de Segmentos (PASG). Esse estudo envolve a de nição formal desse problema e a descrição de um algoritmo e ciente, baseado na técnica de programação dinâ- mica, que o resolve. Ademais, formalizamos uma versão múltipla do PASG, denominada Problema do Alinhamento de Segmentos Múltiplo (PASGM). Para essa versão do problema, nós provamos que ela é NP-Completa e que é muito improvável existir um algoritmo de aproximação com uma boa razão para ela. Com base nesse resultado, propomos três heurísticas para tratar o PASGM e as avaliamos experimentalmente através de testes arti ciais. Por m, as implementações das soluções propostas neste trabalho foram aplicadas na tarefa de identi cação de genes. A aplicabilidade dos nossos programas nessa tarefa foi atestada através dos bons resultados obtidos por eles em um conjunto de instâncias de testes reais.

ABSTRACT - Among the variety of existing combinatorial optimization problems, those involving sequences stand out for their applicability in several research elds. In this work we present a detailed study of a new combinatorial optimization problem involving sequences, called Segment Alignment Problem (SAP). This study includes the formal de nition of this problem and the description of an e cient dynamic programming algorithm to solve it. Furthermore, we present the formal de nition of a multiple version of the SAP, called Multiple Segment Alignment Problem (MSAP). For this version of the problem, we prove its NP-Completeness and that it is very unlikely to exist an approximation algorithm for it with a good factor. With these results in mind, we propose three heuristics for MSAP and we evaluate them experimentally through arti cial tests. Finally, we apply the implementations of the solutions proposed in this work in the gene prediction task. The applicability of our programs in this task was attested by the good results achieved by all of them in a set of real test instances. Keywords: Combinatorial Optimization, Segment Alignment Problem, Dynamic Programming,