https://repositorio.ufjf.br/jspui/handle/ufjf/12479
Arquivo | Descrição | Tamanho | Formato | |
---|---|---|---|---|
aluisiocardososilva.pdf | 744.29 kB | Adobe PDF | ![]() Visualizar/Abrir |
Tipo: | Dissertação |
Título: | Um algoritmo evolutivo baseado em heurísticas construtivas para problemas de agrupamento aplicado à PCR multiplex |
Autor(es): | Silva, Aluísio Cardoso |
Primeiro Orientador: | Borges, Carlos Cristiano Hasenclever |
Co-orientador: | Ribeiro, João Batista |
Membro da banca: | Arbex, Wagner Antônio |
Membro da banca: | Oliveira, Fabrízzio Condé de |
Resumo: | 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. |
Abstract: | Polymerase chain reaction (PCR) is one of the most widely used molecular biology methods in clinical and research laboratories. Through it, it is possible to generate billions of copies of a given DNA fragment in a short period of time. The potential of this reaction and its variants is explored in a wide range of applications in different scientific fields, which motivates research aimed at optimizing PCR assays. Multiplex PCR is a variation of conventional PCR that allows the amplification of multiple specific DNA fragments in the same assay, saving time, costs, and especially samples of genetic material. Designing this reaction is especially challenging because it requires the difficult task of efficiently grouping the amplifications according to the compatibility of their components. This task is usually abstracted to a combinatorial problem about grouping the primer pairs used, which consist of short sequences of DNA synthesized to delimit specifically each target fragment. In this work, a computational model was developed to solve the multiplex PCR grouping problem aiming at an approach capable of dealing with interests frequently approached in isolation by other works. They are: the use of a robust computational strategy as opposed to deterministic algorithms; the applicability of the model in contexts requiring grouping of amplifications in multiple multiplex PCR tubes; minimizing the number of tubes required; the dissociation of the search method from the set of compatibility measures adopted; and the ability to handle the more complex scenario in which two or more options of primer pairs are provided by amplification, expanding the universe of possibilities and potentially the quality of the results. The construction of the model was inspired by methods previously applied to the known bin packing problem. Thus, an evolutionary algorithm is adapted to the search for specific element permutations aiming at the subsequent decoding of the solutions through a building heuristic. Besides, is presented a search space restriction process that allowed to improve the optimization performance. The approach was initially adapted to the bin packing problem, which allowed an evaluation based on benchmarks widely explored in the literature. In this case, the comparative analysis presented points to the competitiveness of the developed model in relation to the referenced algorithms. Subsequently, the proposal was adapted to the multiplex PCR problem. The results of exploratory experiments conducted indicate the scalability of the model and highlight the relevant contribution arising from the breadth of the approach. Finally, it is presented a comparative experimental analysis with the MultiPLX program, which is available for multiplex PCR design and is based on a similar problem formulation. The results obtained by the developed algorithm were superior in the three considered cases, reinforcing the applicability of the proposed model. |
Palavras-chave: | 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 |
CNPq: | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO |
Idioma: | por |
País: | Brasil |
Editor: | Universidade Federal de Juiz de Fora (UFJF) |
Sigla da Instituição: | UFJF |
Departamento: | ICE – Instituto de Ciências Exatas |
Programa: | Programa de Pós-graduação em Ciência da Computação |
Tipo de Acesso: | Acesso Aberto Attribution-NonCommercial-NoDerivs 3.0 Brazil |
Licenças Creative Commons: | http://creativecommons.org/licenses/by-nc-nd/3.0/br/ |
URI: | https://repositorio.ufjf.br/jspui/handle/ufjf/12479 |
Data do documento: | 30-Ago-2019 |
Aparece nas coleções: | Mestrado em Ciência da Computação (Dissertações) |
Este item está licenciado sob uma Licença Creative Commons