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.