Heuristic-Based Primer Set Minimization for PCR

Adaptation of Iterated Local Search for a Set Cover Variant

Bachelor thesis (2024)

Authors

T.A. Kok Electrical Engineering, Mathematics and Computer Science

Contributors

J.A. Baaijens Pattern Recognition and Bioinformatics - EEMCS (supervisor 1)
J. van Bemmelen Pattern Recognition and Bioinformatics - EEMCS (supervisor 1)
C.A. Raman Pattern Recognition and Bioinformatics - EEMCS (supervisor 2)
Faculty
Electrical Engineering, Mathematics and Computer Science
Copyright: © 2024 Thys Kok
More Info
expand_more

Published Date

02-02-2024

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

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.