Um algoritmo evolutivo baseado em heurísticas construtivas para problemas de agrupamento aplicado à PCR multiplex

• Ano de defesa: 2019
• Autor(a) principal: Silva, Aluísio Cardoso
• Orientador(a): Borges, Carlos Cristiano Hasenclever
• Banca de defesa: Arbex, Wagner Antônio , Oliveira, Fabrízzio Condé de
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Federal de Juiz de Fora (UFJF)
• Programa de Pós-Graduação: Programa de Pós-graduação em Ciência da Computação
• Departamento: ICE – Instituto de Ciências Exatas
• País: Brasil
• Palavras-chave em Português: PCR multiplex; Algoritmo genético; Heurísticas construtivas; Problema do empacotamento; Problemas de agrupamento; Multiplex PCR; Genetic algorithm; Building heuristics; Bin packing problem; Grouping problems
• Área do conhecimento CNPq: CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO
• Link de acesso: https://repositorio.ufjf.br/jspui/handle/ufjf/12479

A reação em cadeia da polimerase (Polymerase Chain Reaction, PCR) é um dos métodos de biologia molecular mais utilizados em laboratórios clínicos e de pesquisa. Com a PCR é possível gerar bilhões de cópias de um determinado fragmento de DNA em um curto período de tempo. O potencial dessa reação e de suas variantes é explorado em um vasto conjunto de aplicações inseridas em diferentes campos científicos, motivando a pesquisa direcionada à otimização dos ensaios de PCR. A PCR multiplex consiste em uma variação da PCR convencional que permite a amplificação de múltiplos fragmentos específicos de DNA em um mesmo tubo, propiciando economia de tempo, custos e principalmente amostras do material genético. O projeto da reação é especialmente desafiador na medida em que exige a difícil tarefa de agrupar as amplificações de acordo com a compatibilidade dos componentes envolvidos. Geralmente, métodos in silico para essa reação são baseados no problema combinatório decorrente do agrupamento dos pares de primers utilizados, que consistem em sequências curtas de DNA sintetizadas para delimitar especificamente cada fragmento alvo. Neste trabalho, foi desenvolvido um modelo computacional para o problema de agrupamento da PCR multiplex, visando uma abordagem que compreenda, simultaneamente, aspectos determinantes para a aplicabilidade do modelo e a otimização eficiente da reação, a saber: o tratamento de problemas que exijam múltiplos tubos de PCR multiplex para a cobertura dos alvos; a minimização do número de tubos necessários; a utilização de uma estratégia de busca estocástica em oposição a algoritmos determinísticos; o desacoplamento do método de busca em relação ao conjunto de medidas de compatibilidade adotadas; e a capacidade de tratar o cenário mais complexo em que duas ou mais opções pares de primers são fornecidas por amplificação. O modelo é composto pela adaptação de um algoritmo evolutivo à busca de permutações dos elementos e uma heurística construtiva responsável pela decodificação das soluções mapeadas. Além disso, um processo de restrição do espaço de busca é implementado visando aprimorar o desempenho da busca. A construção da proposta foi inspirada em métodos desenvolvidos para a solução do conhecido problema do empacotamento, o que permitiu uma avaliação inicial baseada em benchmarks amplamente explorados na literatura. Nesse caso, a análise comparativa apresentada evidencia a competitividade do modelo desenvolvido diante dos algoritmos referenciados. Posteriormente, o modelo foi adaptado para a otimização da PCR multiplex. Os resultados de experimentos exploratórios realizados indicam a escalabilidade do modelo e ressaltam a relevante contribuição decorrente da amplitude da abordagem. Finalmente, é apresentada uma análise experimental comparativa com o programa MultiPLX, que baseia-se em uma formulação semelhante do problema. Os resultados superiores obtidos pelo algoritmo proposto reforçam a aplicabilidade do modelo desenvolvido.