Abstract
This paper proposes a combinational optimization algorithm Extremal Optimization (EO) for protein structure alignment based on the Contact map overlap (CMO) model. EO is a meta-heuristic algorithm, as genetic algorithm and simulated annealing, but with a local fitness introduced to guide the improvement of the optimization. By exploiting similarity matrix between two contact maps, the results demonstrate that our algorithm is significantly faster and gets better results for most of the test sets.