Heuristic-Based Primer Set Minimization for PCR

Heuristic-Based Primer Set Minimization for PCR: Adaptation of Iterated Local Search for a Set Cover Variant

Kok, Thys (TU Delft Electrical Engineering, Mathematics and Computer Science)

Baaijens, J.A. (mentor)
van Bemmelen, J. (mentor)
Raman, C.A. (graduation committee)

Delft University of Technology

Computer Science and Engineering

CSE3000 Research Project

2024-02-02

AmpliDiff is an algorithm for studying environmental samples. As the study of those DNA samples is complicated, the runtime of AmpliDiff holds back its usability. One time-consuming part is exactly solving a variant of the Set Cover problem. This paper researches whether this exact solution can be replaced by heuristics to reduce the runtime. The Iterated Local Search framework is applied as heuristic and translated onto our problem. After that, it is tested and compared to the original version of the algorithm based on the found solution size. From the results we can deduce that the heuristic version finds the same solutions as the original. It does so in a faster relative time frame as well. However, due to time constraints, the dataset that was used for testing is rather small and therefore not representative of more complex problems, which are usually solved by AmpliDiff. Thus, for future work we recommend to test the heuristics version on a larger, more representative dataset to check its viability. This paper has laid the groundwork by implementing the heuristic and showing that it effectively works for small datasets, giving reason to also try it out on more complicated problems.

Heuristic
Set Cover
PCR

http://resolver.tudelft.nl/uuid:a8101bc8-00d9-41cd-938b-ea91581bde29

Student theses

bachelor thesis

© 2024 Thys Kok