Publication
Title
AcoSeeD : an ant colony optimization for finding optimal spaced seeds in biological sequence search
Author
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.
Language
English
Source (journal)
Lecture notes in computer science
Publication
2012
Volume/pages
7461(2012), p. 204-211
Full text (Publishers DOI)
UAntwerpen
Faculty/Department
Research group
Publication type
Subject
Affiliation
Publications with a UAntwerp address
External links
E-info
Record
Identification
Creation 17.09.2012
Last edited 22.11.2016
To cite this reference