Um algoritmo evolutivo baseado em heurísticas construtivas para problemas de agrupamento aplicado à PCR multiplex
Loading...
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Universidade Federal de Juiz de Fora (UFJF)
DOI
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.
Description
Citation
Endorsement
Review
Supplemented By
Referenced By
Creative Commons license
Except where otherwise noted, this item's license is described as Acesso Aberto

