A bioinformatics engineer is working on a string of DNA, and wants to mutate one DNA sequence x into another DNA sequence y$.$ The tool at their disposal to achieve this is a state of the art Imprinter$3000$ machine, which operates as follows. The Imprinter$3000$ can be programmed with a template string t$,$ and after this, the Imprinter$3000$ can overwrite any part of x with t$.$

For example suppose x $=$ AAAAAA. Then if we have programmed the Imprinter$3000$ with t $=$ CAT, we could choose to imprint t at position $1$ of x$,$ to obtain CATAAA. If we have programmed another template GAG, we could then imprint that at position $4$ of the string to get CATGAG. We could then choose to use the first template CAT again at position $2$ to get CCATAG. We cannot imprint

these templates at positions $5$ or $6$ since that would cause the Imprinter$3000$ to attempt to write

t out of bounds $($every character of t needs to align with an existing character of x$).$

Once a template t has been programmed for the Imprinter$3000,$ running it to imprint t on different

parts of x is very quick. But the procedure of programming the template is very time$-$consuming.

Thus we would like to transform our original DNA string x into our target DNA string y using

as few programmings as possible. Due to technical limitations$1$

the length of a template t must

be exactly equal to some value $.$ The Imprinter$3000$ is not specific to Earthly DNA, and can

handle DNA strings using all characters A$-$Z $($in other words the input strings x and y do not

have to be restricted to the usual symbols ACGT most commonly used for DNA sequences$).$

Prove that it is NP$-$complete to decide whether or not it is possible to transform x to y using at

most k diferent length$-$ templates. In other words, an instance of this problem consists of the

initial string x$,$ the target string y$,$ the required template length $,$ and the maximum number k

of different templates allowed. The answer is YES if it is possible to use the Imprinter$3000$ to

transform x to y with at most k different templates, each template having length exactly $.$

Continuing the example below, we see that if x $=$ AAAAAA, y $=$ CCATAG, $=3$ and k $=2,$ the

answer is YES, since it is possible to transform x into y using only k $=2$ different templates of

length $=3($note that this uses one of the templates more than once, but that does not matter$).$

use a reduction involving any of the following known NP$-$hard problems like:

$3-$Coloring, $3-$Dimensional Matching, $3-$Sat, $($CNF$-)$Sat$,$ Graph Coloring, Hamiltonian Cycle,

Hamiltonian Path, Independent Set, Knapsack, Load Balancing, Set Cover, Subset

Sum, Travelling Salesman, Vertex Cover.