Use este identificador para citar ou linkar para este item: https://repositorio.ufms.br/handle/123456789/2590
Tipo: Dissertação
Título: O problema do particionamento de similaridade máxima
Autor(es): Zaccaron, Alex Zanella
Abstract: Neste trabalho, nós propomos um novo problema de otimização combinatória envolvendo sequências de caracteres chamado Problema do Particionamento de Similaridade Máxima. Apresentamos também uma prova de que esse problema é NP-difícil no sentido forte, o que signi fica que não existe um algoritmo polinomial e nem pseudo-polinomial que o resolve, a menos que P = NP. Além disso, desenvolvemos e testamos duas heurísticas baseadas na estratégia gulosa que encontram soluções para o Problema do Particionamento de Similaridade Máxima em tempo polinomial. Este trabalho também traz uma aplicação do problema em questão através da modelagem de um problema importante da Biologia Computacional chamado problema da reconstrução e quanti ficação de transcriptoma, modelagem essa pioneira na abordagem desse problema omo um problema de otimização combinatória envolvendo sequências.
ABSTRACT - In this work, we propose a new ombinatorial optimization problem Involving strings alled Maximum Similarity Partitioning Problem. We also present a proof that this problem is NP-hard in the strong sense, whi h means that there is no polynomial nor pseudo-polynomial time algorithm that an solve it, unless P = NP. Besides, we developed and tested two greedy heuristis that nd solutions for the Maximum Similarity Partitioning Problem in polynomial time. This work brings as well an appli ation for the orresponding problem in the modeling of an important problem in Computational Biology known as trans riptome reonstrution and quanti ation problem. We onsider suh modeling the rst to deal with the transriptome reonstru tion and quanti ation problem as a combinatorial optimization problem involving strings.
Palavras-chave: Computação
Computer Science
Complexidade Computacional
Computational Complexity
Otimização Combinatória
Combinatorial Optimization
Tipo de Acesso: Acesso Aberto
URI: https://repositorio.ufms.br/handle/123456789/2590
Data do documento: 2015
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 
ALEX ZANELLA ZACCARON.pdf846,92 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.