Please use this identifier to cite or link to this item: https://repositorio.ufjf.br/jspui/handle/ufjf/12479
Files in This Item:
File Description SizeFormat 
aluisiocardososilva.pdf744.29 kBAdobe PDFThumbnail
View/Open
Full metadata record
DC FieldValueLanguage
dc.contributor.advisor1Borges, Carlos Cristiano Hasenclever-
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/2487554612123446pt_BR
dc.contributor.advisor-co1Ribeiro, João Batista-
dc.contributor.advisor-co1Latteshttp://lattes.cnpq.br/pt_BR
dc.contributor.referee1Arbex, Wagner Antônio-
dc.contributor.referee1Latteshttp://lattes.cnpq.br/7805432023782520pt_BR
dc.contributor.referee2Oliveira, Fabrízzio Condé de-
dc.contributor.referee2Latteshttp://lattes.cnpq.br/5149229612250815pt_BR
dc.creatorSilva, Aluísio Cardoso-
dc.creator.Latteshttp://lattes.cnpq.br/6209586545271439pt_BR
dc.date.accessioned2021-03-18T14:31:27Z-
dc.date.available2021-03-18-
dc.date.available2021-03-18T14:31:27Z-
dc.date.issued2019-08-30-
dc.identifier.urihttps://repositorio.ufjf.br/jspui/handle/ufjf/12479-
dc.description.abstractPolymerase 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.pt_BR
dc.description.resumoA 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.pt_BR
dc.description.sponsorshipCAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superiorpt_BR
dc.languageporpt_BR
dc.publisherUniversidade Federal de Juiz de Fora (UFJF)pt_BR
dc.publisher.countryBrasilpt_BR
dc.publisher.departmentICE – Instituto de Ciências Exataspt_BR
dc.publisher.programPrograma de Pós-graduação em Ciência da Computaçãopt_BR
dc.publisher.initialsUFJFpt_BR
dc.rightsAcesso Abertopt_BR
dc.rightsAttribution-NonCommercial-NoDerivs 3.0 Brazil*
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/br/*
dc.subjectPCR multiplexpt_BR
dc.subjectAlgoritmo genéticopt_BR
dc.subjectHeurísticas construtivaspt_BR
dc.subjectProblema do empacotamentopt_BR
dc.subjectProblemas de agrupamentopt_BR
dc.subjectMultiplex PCRpt_BR
dc.subjectGenetic algorithmpt_BR
dc.subjectBuilding heuristicspt_BR
dc.subjectBin packing problempt_BR
dc.subjectGrouping problemspt_BR
dc.subject.cnpqCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAOpt_BR
dc.titleUm algoritmo evolutivo baseado em heurísticas construtivas para problemas de agrupamento aplicado à PCR multiplexpt_BR
dc.typeDissertaçãopt_BR
Appears in Collections:Mestrado em Ciência da Computação (Dissertações)



This item is licensed under a Creative Commons License Creative Commons