|Subject:||Stocastic Search Algorithm|
A GRASP Algorithm for Motif Finding (the course project for
CPSC 532D: Stochastic Search Algorithms
Motif finding in biosequences is a very important and well-studied problem. However, the best algorithms to date either give a poor performance on some problem instances, or are computationally impractical. As it turns out that this problem is computationally hard, in this work, we propose a GRASP algorithm to solve the motif finding problem. We have also built an ILS algorithm and a problem instance generator. We have tested the two algorithms on generated data sets and found that they both work pretty well, with a better performance for the GRASP algorithm. The GRASP algorithm also works well for the CRP real data set, and both algorithms perform poorly for simulated sets from the Challenge Problem. The results we have got in this work are promising, and maybe with more improvement of the GRASP algorithm, we can get results comparable with the state of the art algorithms for this problem.