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.
The program:
- Provable:
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.)
After downloading the program, you can run it as follows:
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:
- randGen:
Executable compiled under Linux.
After downloading this program, you can run it as follows:
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.