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

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.