Title
AcoSeeD : an ant colony optimization for finding optimal spaced seeds in biological sequence search AcoSeeD : an ant colony optimization for finding optimal spaced seeds in biological sequence search
Author
Faculty/Department
Faculty of Sciences. Mathematics and Computer Science
Publication type
article
Publication
Subject
Chemistry
Source (journal)
Lecture notes in computer science
Volume/pages
7461(2012) , p. 204-211
ISSN
0302-9743
Carrier
E
Target language
English (eng)
Full text (Publishers DOI)
Affiliation
University of Antwerp
Abstract
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.
E-info
http://www.springerlink.com/content/n1476j612302410k/
Handle