How to overcome the problem?
Designing faster and faster algorithms will remain a constant challenge in bioinformatics.
If the worst-case running time of an algorithm is too long, its average running time may still make it suitable for your purposes.
If your problem is an optimization problem, one can work with approximation algorithms that are not guaranteed to find the best solution, but a pretty good one.
One can use heuristic algorithms that have no performance guarantee whatsoever, but in most cases appear to find pretty good solutions.