Algorithm based on the Ant Colony Optimization for the DNA Motif Fusion
Abstract
Motifs (patterns, signatures, domains) are useful to determine nucleotides/amino-acids that are likely involved in structures, functions, regulations and evolutions, or to infer homology between genes/proteins. The main objective of this paper is the fusion of motifs. Our task is to analyze a set of possible motifs and to detect if similarity exists between them, to construct a general motif. The motifs fusion method is based on the algorithm of combinatorial optimization called Artificial Ants System. This method uses the nucleotides of the first motif to construct the graph where the ants will walk. Then, the graph is crossed by the ants according to the path of the second motif, using a transition function that promoves to flow the path between similar nucleotides. The ants when walking leave pheromone in the nodes, in a way that at the end several have a lot of or little pheromone. Finally the graph is crossed again to construct the resultant motif composed by the nodes with much pheromone.