Similarity search in biological sequence database is one of the most popular and important bioinformatics tasks. Spaced seeds have been increasingly used to improve the quality and sensitivity of searching, for example, in seeded alignment methods. Finding optimal spaced seeds is a NP-hard problem. In this study we introduce an application of an Ant Colony Optimization (ACO) algorithm to address this problem in a metaheuristics framework. This method, called AcoSeeD, builds optimal spaced seeds in an elegant construction graph that uses the ACO standard framework with a modified pheromone update. Experimental results demonstrate that AcoSeeD brings a significant improvement of sensitivity while demanding the same computational time as other state-of-the-art methods. We also introduces an alternative way of using local search that exerts a fast approximation of the objective function in ACO.