Sounds like you are doing bioinformatics stuff. Usually the long computation time in these sort of problems is due to searching large numbers of strings.

In this case, the problem is trivially parallelizable. Partition the strings into N sets and create N processes on N processors, each searching one set. If you don't run into I/O bottlenecks at that point, you may even consider more than one process per CPU.