Software for the Closest Substring Problem and the Planted (L,d)-Motif Problem
This site provides a program for solving
the closest substring problem and
the planted (L,d)-motif problem.
After downloading the program, you can run it as follows:
Executable compiled under 32-bit Linux OS.
(Note: The program has been corrected to
explicitly output all the "uninteresting" solutions which can be
obtained by other solutions via further modifications.)
Provable fileName L d
where fileName is a file containing sequences in Fasta format, L is the length of
the center substring (or the planted motif) to be found, and d is an upper bound on
the minimum distance between the center substring (or the planted motif) and
a substring of each sequence in the file.
A program for generating random instances of the planted (L,d)-motif problem:
After downloading this program, you can run it as follows:
Executable compiled under Linux.
randGen n K s L d fileName
where n is the number of sequences to be generated, K is the length of each sequence to be generated,
s is the size of the alphabet of the sequences to be generated,
L is the length of the motif to be planted, and d is the number of positions of the motif
to be modified when it is planted in each sequence, fileName is a file to
hold the generated sequences in Fasta format.
An example for which PMSPrune does not work.