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

Detalhes bibliográficos
Ano de defesa: 2014
Autor(a) principal: Mazaro, Regina Beretta
Orientador(a): Adi, Said Sadique
Banca de defesa: Não Informado pela instituição
Tipo de documento: Dissertação
Tipo de acesso: Acesso aberto
Idioma: por
Instituição de defesa: Não Informado pela instituição
Programa de Pós-Graduação: Não Informado pela instituição
Departamento: Não Informado pela instituição
País: Não Informado pela instituição
Palavras-chave em Português:
Link de acesso: https://repositorio.ufms.br/handle/123456789/2241
Resumo: 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.