Use este identificador para citar ou linkar para este item: https://repositorio.ufms.br/handle/123456789/2241
Tipo: Dissertação
Título: Uma 3−aproximação e uma formulação de PLI para o Problema do Alinhamento Spliced Múltiplo
Autor(es): Mazaro, Regina Beretta
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.
Palavras-chave: Otimização Combinatória
Programação Linear
Biologia Computacional
Combinatorial Optimization
Linear Programming
Computational Biology
Tipo de Acesso: Acesso Aberto
URI: https://repositorio.ufms.br/handle/123456789/2241
Data do documento: 2014
Aparece nas coleções:Programa de Pós-graduação em Ciência da Computação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
Regina Beretta Mazaro..pdf750,08 kBAdobe PDFThumbnail
Visualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.