Uma 3−aproximação e uma formulação de PLI para o Problema do Alinhamento Spliced Múltiplo

Abstract

Com os avanços recentes em áreas específicas da Ciência da Computação como a Biologia Computacional, vários problemas novos envolvendo sequencias vem surgindo, enquanto que problemas tradicionais tornam-se mais difíceis dada a expressiva quantidade de dados gerada nos últimos anos. O interesse aqui ´e no estudo de um problema específico que envolve sequências denominado Problema do Alinhamento Spliced Múltiplo, estendendo um trabalho anteriormente realizado por Kishi e Adi em cima desse mesmo problema. Enquanto que nesse estudo prévio mostrou-se que o Problema do Alinhamento Spliced Múltiplos e NP-completo e foram propostas heurísticas para o problema, o presente trabalho visa sugerir um algoritmo de aproximação e uma formulação de programação linear inteira para ele, possibilitando confrontar essas novas abordagens com as heurísticas já desenvolvidas para o Problema do Alinhamento Spliced Múltiplo. Para isso, foram executados testes com instâncias artificiais e reais, sendo essas ultimas instâncias de um problema tradicional da Bioinformática denominado Problema da Identificação de Genes.

ABSTRACT - Recent advances in specific areas of Computer Science as Computational Biology brought to light several new problems involving sequences, while traditional problems become more difficult given the significant amount of data generated in the last years. The interest here is to study a specific problem which involves sequences, called Multiple Spliced Alignment Problem, extending a previously study conducted by Kishi and Adi about that same problem. While in this previous study it was shown that the Multiple Spliced Alignment Problem is NP-complete and heuristics have been proposed for the problem, this paper aims to suggest an approximation algorithm and an integer linear programming formulation for it, allowing to confront these new approaches with the already developed heuristics for the Multiple Spliced Alignment Problem. For this purpose, experimental tests with real and artificial instances were executed, with the latter being instances of a traditional problem in Bioinformatics called Gene Prediction Problem.