BACKGROUND
to extract biologically meaningful information from a large amount of gene expression data and genomic information is one of the most challenging tasks in the post human genome project era  <cit> .
since transcriptional processes are regulated combinatorially by multiple regulatory elements, computational modeling is inevitable and an efficient algorithm capable of solving combinatorial optimization problems is desirable  <cit> .
swarm intelligence is a computational technique that mimics the collective behavior of social insects such as ants and bees  <cit> .
although there is no centralized module that dictates the behavior of individuals, local interactions cause a global optimization pattern to emerge  <cit> .
algorithms based on swarm intelligence have been applied successfully to a large number of hard discrete optimization problems including traveling salesman, quadratic assignment and routing in telecommunications networks  <cit> .
the ant algorithm is a branch of swarm intelligence techniques inspired by the foraging behavior of ant colonies.
here, the solution in a combinatorial problem is initialized with a population of randomly positioned ants.
each ant represents a particular solution and deposits a varying amount of artificial pheromone based on the fitness of the solution.
the concentrations of pheromone provide distributed information in a whole solution space, and they are constantly updated through deposition and evaporation.
with a positive feedback mechanism through reinforcement of the previously favored solutions, algorithm-based ants are guided towards the solution of higher fitness like the social behavior of natural ants .
the ant algorithm is designed to predict a set of transcription-factor binding motifs using array-derived gene expression data.
based on the idea that gene expression levels are regulated by the combinatorial actions of multiple transcription-factor binding motifs, we formulated a linear relationship between the observed gene expression patterns and the appearance number of potential transcription-factor binding sites in the regulatory region of each gene.
thus, the ant algorithm seeks the motifs whose occurrences in the regulatory region collectively correlate with the global expression levels.
we examined whether the unique version of ant algorithms presented here would predict a potential contribution of all conceivable transcription-factor binding motifs.
most of the existing methods evaluate either a single oligo sequence at a time  <cit> , or a fixed set of multiple binding motifs with little information on a role of individual motifs  <cit> .
we previously utilized the genetic algorithm  <cit>  as well as a particle swarm optimization procedure  <cit> , and searched for a suboptimal combination of binding motifs.
such approaches, however, were not ideal because of the astronomical number of possibilities in the solution space  and the limited scope in the presence of redundant regulatory mechanisms.
here, we describe a novel application of ant algorithms to evaluate the role of each of individual binding motifs from a population of random dna sequences.
unlike the genetic algorithm or particle swarm optimization, the ant algorithm aims to evaluate individual binding sites rather than searching for the best motif combination using a unique artificial pheromone spectrum.
in the current study prediction of transcription-factor binding motifs was formulated as a foraging problem of artificial ants using human chondrogenesis in vitro as a model system.
each ant represented a set of random dna sequences and deposited a varying amount of artificial pheromones depending on the deviation from the array-derived data, which is defined in eq.
<dig> later in the section of methods.
pheromones were constantly renewed by deposition as well as partial evaporation, and ants were attracted to dna sequences with high concentration of pheromones.
this reinforcement process was aimed to select the most desirable group of transcription-factor binding motifs from random dna sequences.
the microarray-derived mrna expression data, being used throughout the study, were published by sekiya et al.
<cit>  .
the prediction of transcription-factor binding motifs was conducted previously with the genetic algorithm, and the results were experimentally validated using the genes specific to chondrogenesis such as type ii collagen  <cit> .
here, we extended our analysis by developing a unique version of ant algorithms and evaluated the potential role of all dna sequences in the solution space.
all conceivable random sequences from  <dig> bp to  <dig> bp in length were analyzed, although the results with 5-bp dna sequences were mainly described to validate the novel ant algorithm using the previous results with the genetic algorithm.
the transfac database was used to derive biologically known consensus sequences   <cit> .
RESULTS
the overall strategy with the ant algorithm is to evaluate individual motif candidates considering combinatorial effects with other motifs.
briefly, each ant is defined to represent a potential combination of multiple transcription-factor binding motifs where the number of ants was determined based on the statistical studies with akaike information criterion  <cit> ).
using a mathematical model for expression profiles , each ant is associated with a model error .
a pheromone concentration is assigned high if the model error of the ant is small and vice versa .
in the next iteration of ant migration, the probability of particular motifs being selected by any ant is affected by the previous pheromone concentration .
the pheromone concentration deposited to each motif candidate is additive and evaporative .
in the current study,  <dig> ants  were utilized with  <dig> computational iterations for deposition and evaporation of pheromones.
the final pheromone concentrations assigned to individual dna sequences were plotted in a form of pheromone spectrum .
two key parameters here were a "pheromone preference factor " and a "pheromone evaporation factor ": the pheromone preference factor regulated affinity of ants towards artificial pheromone, and the pheromone evaporation factor was used to reduce influence from the earlier computational outcomes.
using these two factors, "reproducibility " and "selectivity " of the motif selections were analyzed.
reproducibility was defined as cross-correlation among the pheromone spectra, and selectivity was defined as " <dig> – information entropy" .
pheromone spectrum
using  <dig> random dna sequences of  <dig> bp in length as potential transcription-factor binding motifs, the fitness of individual motif candidates was analyzed from their final pheromone concentrations .
in the pheromone spectrum that illustrated  <dig> pheromone concentrations assigned to the sequences such as aaaaa, aaaac, etc., they varied considerably depending on the choice of the pheromone preference factor  and the pheromone evaporation factor .
with ε =  <dig> and δ =  <dig> , most dna sequences received a relatively uniform pheromone concentration  except for ctgac.
note that the highest concentration was normalized to  <dig>  with ε =  <dig> and δ =  <dig>  , on the other hand,  <dig> dna fragments including ctgac received the concentration higher than  <dig> s.d.
above the average.
these two examples indicated dependence of the pheromone spectrum on selection of ε and δ .
reproducibility and selectivity
in order to characterize the effects of ε and δ in the ant algorithm, reproducibility  and selectivity  were determined for varying pairs of ε and δ for  <dig> ≤ ε ≤  <dig> and  <dig> ≤ δ ≤  <dig> .
as expected from random selection, the selectivity value became ~ <dig> with ε ~  <dig> .
the selectivity value was high for a pair of large ε and small δ, while the reproducibility value approached  <dig>  or above for  <dig>  <ε <  <dig> and δ <  <dig> .
based on statistical considerations, we aimed at high reproducibility and significantly low selectivity that would provide ~ <dig> local peaks in the pheromone spectrum.
selecting of  <dig> local peaks corresponds to building a model with  <dig> potential binding motifs.
hereafter, a pair of ε =  <dig> and δ =  <dig>  was employed to achieve r =  <dig>  and s =  <dig>  for modeling human chondrogenesis in vitro.
motif length analysis
since the length of known transcription-factor binding motifs vary from  <dig> bp up to more than  <dig> bp, we examined sequence similarities among the predicted motifs ranging from  <dig> to  <dig> bp .
there are  <dig>   <dig>   <dig>  and  <dig> dna sequences in total for 4-, 5-, 6-, and 7-bp binding motifs, respectively.
interestingly, the motifs consisting of particular dna sequences such as gccc, cagg, and ctga repeatedly appeared with a high concentration of pheromone.
biological relevance
among the four models , the most influential  <dig> transcription-factor binding motifs were selected from a pool of  <dig>  potential motifs .
first, 4-bp dna sequences such as ctga, cagg, and gccc were selected in all four models.
to test statistical significance of selecting any 4-bp core sequence throughout the four models, monte carlo simulations were conducted.
the simulation result supported statistical significance  of picking three 4-bp core sequences from  <dig> to  <dig> bp motifs , although a null hypothesis assumed here was significantly weak because of a multiple motif selection.
second, the binding motifs such as ap- <dig>  sox <dig> and nfκb known to be involved in chondrogenesis were selected in the 5-bp model .
third, nine out of  <dig> binding motifs, predicted previously by the genetic algorithm, were included in this short list.
the state transition representing the time-dependent role of the predicted transcription-factor binding motifs are illustrated on days  <dig>   <dig>   <dig>  and  <dig> .
the figure reveals that dna sequences such as cgtac and aactc were predicted to up-regulate the selected genes in the model, while the sequences such as accca and aacat were modeled to down-regulate the same genes.
in particular, the predicted role of agggg is consistent to the molecular experiments using a transient dna transfection  <cit> .
discussion
this study described a novel application of the ant algorithm in predicting a role of each of the random dna sequences as a transcription-factor binding motif in human chondrogenesis.
the prediction procedure was formulated as the combinatorial problem to select a set of multiple motifs followed by a histogram analysis to build a spectrum of potential contributions among all conceivable motifs.
using human chondrogenesis in vitro as a model system, we demonstrate that the ant algorithm is capable of identifying dna sequences found in the biologically known motifs such as ap- <dig>  creb, sox <dig>  nfκb, erg- <dig>  ap- <dig>  stat, smad, e <dig>  and oct- <dig> as well as unknown candidates.
we discuss the described ant algorithm focusing on its characteristic formulation, selectivity and reproducibility, computational efficiency, and biological relevance.
the first feature of the described algorithm is definition of artificial ants as a set of m transcription-factor binding motifs .
in this algorithm, each ant was assigned to its own set of m binding motifs and it deposited an equal amount of pheromone to the assigned set.
a pheromone spectrum was then built from the sum of deposited pheromones by na ants .
the value of m >  <dig> allowed us not only to evaluate a combinatorial effect of multiple binding motifs but also to reduce the number of computational iterations.
the second feature among biology-inspired algorithms is a well-characterized choice of selectivity and reproducibility by the two key parameters: pheromone preference factor, ε, and pheromone evaporation factor, δ. the value of ε determines the preference to pheromones, and the value of δ regulates fading of the previous concentration of pheromone.
selectivity was defined as " <dig> – informational entropy" to evaluate distance from randomness, while reproducibility was defined as correlation among the spectra.
a higher selectivity in general implies that the limited number of motif candidates receive a significantly higher pheromone concentration than most of the other candidates.
the extreme case for ε ~  <dig> or ε >  <dig> yielded low reproducibility, since the final pheromone spectrum was predominantly influenced by the ants in the first or the last generation.
a value of δ controlled evaporation of previous information, and a large value of δ placed more emphasis on recent decisions.
the values of ε and δ can be selected arbitrarily depending on the purpose of a particular study.
in this study we determined these parameters to reproducibly obtain ~ <dig> peaks in the spectrum.
the number of peaks was pre-determined using akaike information criterion  <cit> .
a clear advantage of the ant algorithm is a computational efficiency to reach a stable solution compared to the other evolutionary algorithms such as the genetic algorithm.
the major difference between the ant algorithm and the genetic algorithm is their solution space.
the ant algorithm searches for a group of the best motifs in a space of individual binding motifs, while the genetic algorithm seeks the best combination.
the former space is apparently more restricted than the latter combinatorial space.
therefore, the ant algorithm has a clear advantage to terminate the search.
furthermore, the advantage of the ant algorithm includes identification of redundant transcription-factor binding motifs in eukaryotic gene regulation.
neither the genetic algorithm nor particle swarm optimization is well suited to include redundant motifs in a final solution.
the ant algorithm is also different from other model-based approaches such as reduce  <cit>  and the principal component analysis  <cit> .
in reduce, for instance, motifs are selected recursively in an add-on manner to reduce the model error by the largest degree at each selection.
this selection strategy makes later selections strongly affected by the earlier ones.
the ant algorithm, on the other hand, can avoid such a potential conflict in selection.
in order to compare these two algorithms, numerical simulations were conducted using a benchmark dataset for  <dig> artificial genes .
simulation results suggested that both reduce and ant algorithm offers similar power in predicting correct number of embedded motifs.
although the advantage of reduce is its superior reproducibility with a shorter computational time, the ant algorithm is apparently more suited to predict a motif longer than  <dig> bp including a motif consisting of a dimeric binding site.
biologists are usually advised to use several complementary computational tools to identify regulatory elements from microarray data  <cit> .
the ant algorithm seems to complement analytical approaches such as reduce and the principal component-based method in identifying longer motifs and dimeric binding sites.
the ant algorithm can still evaluate combinatorial effects among multiple factors like other model-based approaches reported previously  <cit> .
defining a background model is a general approach in searching for over-representation of dna words within a sequence set.
the ant algorithm, however, aims at searching for the dna sequences whose occurrences in the regulatory region correlate with the observed expression levels in the context of combinations of multiple motifs.
therefore, the described ant algorithm is in principle not overly sensitive to over-represented dna words.
the expression levels are described as a linear combination of the role of individual motifs with different functions.
therefore, it is possible that some motifs, predicted to be a stimulator by the ant algorithm, may appear in the regulatory region of the gene whose expression level is down-regulated.
a motif length analysis and sequence comparisons supported, at least in part, statistical and biological significance of the selected transcription-factor binding motifs.
the  <dig> predicted motifs matched with the sequences of  <dig> known binding motifs known to be involved in human chondrogenesis.
these binding motifs include ap- <dig>  creb, sox <dig>  nfκb, erg- <dig>  ap- <dig>  stat, smad, e <dig>  and oct- <dig>  interestingly, two of the 5-bp motifs  together with a 6-bp motif  and a 7-bp motif  constituted a contiguous 10-bp binding motif of egr- <dig> , confirming a strong involvement of egr- <dig> in chondrogenesis.
furthermore, two 5-bp motifs  coincided with 9-bp consensus sequence of nfκb  binding sites .
it is possible to evaluate a pool of candidates with varying length simultaneously by including them together in the simulation.
note that the prediction by the ant algorithm should be used to address a set of hypotheses, and biological experiment is inevitable.
in summary, the described procedure is the first application of ant algorithms for prediction of transcription-factor binding motifs.
other definitions of artificial ants and pheromones are possible.
for instance, a group of heterogeneous ants could behave like transcription factors or rna polymerases and deposit different kinds of pheromones directly onto genomic dna sequences.
we believe that this application will be advanced by further studies for improving computational efficiency and biological relevance.
CONCLUSIONS
we developed one form of ant algorithms for prediction of transcription-factor binding motifs.
the consensus sequences of  <dig> biologically known binding motifs have significant similarities with the predicted motifs.
unlike healing capability of bones, joint tissues such as articular cartilage hardly regenerate and therefore in vitro chondrogenesis is an extremely challenging subject in tissue engineering.
the transcriptional mechanism of human chondrogenesis remains largely unknown.
with its efficient search procedure and its controllable reproducibility and selectivity, the described version of ant algorithms allows us to provide a known and novel set of molecular targets for biological verification.

 to extract biologically meaningful information from a large amount of gene expression data and genomic information is one of the most challenging tasks in the post human genome project era. since transcriptional processes are regulated combinatorially by multiple regulatory elements, computational modeling is inevitable and an efficient algorithm capable of solving combinatorial optimization problems is desirable. swarm intelligence is a computational technique that mimics the collective behavior of social insects such as ants and bees. although there is no centralized module that dictates the behavior of individuals, local interactions cause a global optimization pattern to emerge. algorithms based on swarm intelligence have been applied successfully to a large number of hard discrete optimization problems including traveling salesman, quadratic assignment and routing in telecommunications networks. the ant algorithm is a branch of swarm intelligence techniques inspired by the foraging behavior of ant colonies. here, the solution in a combinatorial problem is initialized with a population of randomly positioned ants. each ant represents a particular solution and deposits a varying amount of artificial pheromone based on the fitness of the solution. the concentrations of pheromone provide distributed information in a whole solution space, and they are constantly updated through deposition and evaporation. with a positive feedback mechanism through reinforcement of the previously favored solutions, algorithm-based ants are guided towards the solution of higher fitness like the social behavior of natural ants. the ant algorithm is designed to predict a set of transcription-factor binding motifs using array-derived gene expression data. based on the idea that gene expression levels are regulated by the combinatorial actions of multiple transcription-factor binding motifs, we formulated a linear relationship between the observed gene expression patterns and the appearance number of potential transcription-factor binding sites in the regulatory region of each gene. thus, the ant algorithm seeks the motifs whose occurrences in the regulatory region collectively correlate with the global expression levels. we examined whether the unique version of ant algorithms presented here would predict a potential contribution of all conceivable transcription-factor binding motifs. most of the existing methods evaluate either a single oligo sequence at a time, or a fixed set of multiple binding motifs with little information on a role of individual motifs. we previously utilized the genetic algorithm as well as a particle swarm optimization procedure, and searched for a suboptimal combination of binding motifs. such approaches, however, were not ideal because of the astronomical number of possibilities in the solution space and the limited scope in the presence of redundant regulatory mechanisms. here, we describe a novel application of ant algorithms to evaluate the role of each of individual binding motifs from a population of random dna sequences. unlike the genetic algorithm or particle swarm optimization, the ant algorithm aims to evaluate individual binding sites rather than searching for the best motif combination using a unique artificial pheromone spectrum. in the current study prediction of transcription-factor binding motifs was formulated as a foraging problem of artificial ants using human chondrogenesis in vitro as a model system. each ant represented a set of random dna sequences and deposited a varying amount of artificial pheromones depending on the deviation from the array-derived data, which is defined in eq. later in the section of methods. pheromones were constantly renewed by deposition as well as partial evaporation, and ants were attracted to dna sequences with high concentration of pheromones. this reinforcement process was aimed to select the most desirable group of transcription-factor binding motifs from random dna sequences. the microarray-derived mrna expression data, being used throughout the study, were published by sekiya et al.. the prediction of transcription-factor binding motifs was conducted previously with the genetic algorithm, and the results were experimentally validated using the genes specific to chondrogenesis such as type ii collagen. here, we extended our analysis by developing a unique version of ant algorithms and evaluated the potential role of all dna sequences in the solution space. all conceivable random sequences from bp to bp in length were analyzed, although the results with 5-bp dna sequences were mainly described to validate the novel ant algorithm using the previous results with the genetic algorithm. the transfac database was used to derive biologically known consensus sequences.  the overall strategy with the ant algorithm is to evaluate individual motif candidates considering combinatorial effects with other motifs. briefly, each ant is defined to represent a potential combination of multiple transcription-factor binding motifs where the number of ants was determined based on the statistical studies with akaike information criterion ). using a mathematical model for expression profiles, each ant is associated with a model error. a pheromone concentration is assigned high if the model error of the ant is small and vice versa. in the next iteration of ant migration, the probability of particular motifs being selected by any ant is affected by the previous pheromone concentration. the pheromone concentration deposited to each motif candidate is additive and evaporative. in the current study, ants were utilized with computational iterations for deposition and evaporation of pheromones. the final pheromone concentrations assigned to individual dna sequences were plotted in a form of pheromone spectrum. two key parameters here were a "pheromone preference factor " and a "pheromone evaporation factor ": the pheromone preference factor regulated affinity of ants towards artificial pheromone, and the pheromone evaporation factor was used to reduce influence from the earlier computational outcomes. using these two factors, "reproducibility " and "selectivity " of the motif selections were analyzed. reproducibility was defined as cross-correlation among the pheromone spectra, and selectivity was defined as " – information entropy". pheromone spectrum using random dna sequences of bp in length as potential transcription-factor binding motifs, the fitness of individual motif candidates was analyzed from their final pheromone concentrations. in the pheromone spectrum that illustrated pheromone concentrations assigned to the sequences such as aaaaa, aaaac, etc., they varied considerably depending on the choice of the pheromone preference factor and the pheromone evaporation factor. with ε = and δ =, most dna sequences received a relatively uniform pheromone concentration except for ctgac. note that the highest concentration was normalized to with ε = and δ =, on the other hand, dna fragments including ctgac received the concentration higher than s.d. above the average. these two examples indicated dependence of the pheromone spectrum on selection of ε and δ. reproducibility and selectivity in order to characterize the effects of ε and δ in the ant algorithm, reproducibility and selectivity were determined for varying pairs of ε and δ for ≤ ε ≤ and ≤ δ ≤. as expected from random selection, the selectivity value became ~ with ε ~. the selectivity value was high for a pair of large ε and small δ, while the reproducibility value approached or above for <ε < and δ <. based on statistical considerations, we aimed at high reproducibility and significantly low selectivity that would provide ~ local peaks in the pheromone spectrum. selecting of local peaks corresponds to building a model with potential binding motifs. hereafter, a pair of ε = and δ = was employed to achieve r = and s = for modeling human chondrogenesis in vitro. motif length analysis since the length of known transcription-factor binding motifs vary from bp up to more than bp, we examined sequence similarities among the predicted motifs ranging from to bp. there are and dna sequences in total for 4-, 5-, 6-, and 7-bp binding motifs, respectively. interestingly, the motifs consisting of particular dna sequences such as gccc, cagg, and ctga repeatedly appeared with a high concentration of pheromone. biological relevance among the four models, the most influential transcription-factor binding motifs were selected from a pool of potential motifs. first, 4-bp dna sequences such as ctga, cagg, and gccc were selected in all four models. to test statistical significance of selecting any 4-bp core sequence throughout the four models, monte carlo simulations were conducted. the simulation result supported statistical significance of picking three 4-bp core sequences from to bp motifs, although a null hypothesis assumed here was significantly weak because of a multiple motif selection. second, the binding motifs such as ap- sox and nfκb known to be involved in chondrogenesis were selected in the 5-bp model. third, nine out of binding motifs, predicted previously by the genetic algorithm, were included in this short list. the state transition representing the time-dependent role of the predicted transcription-factor binding motifs are illustrated on days and. the figure reveals that dna sequences such as cgtac and aactc were predicted to up-regulate the selected genes in the model, while the sequences such as accca and aacat were modeled to down-regulate the same genes. in particular, the predicted role of agggg is consistent to the molecular experiments using a transient dna transfection. discussion this study described a novel application of the ant algorithm in predicting a role of each of the random dna sequences as a transcription-factor binding motif in human chondrogenesis. the prediction procedure was formulated as the combinatorial problem to select a set of multiple motifs followed by a histogram analysis to build a spectrum of potential contributions among all conceivable motifs. using human chondrogenesis in vitro as a model system, we demonstrate that the ant algorithm is capable of identifying dna sequences found in the biologically known motifs such as ap- creb, sox nfκb, erg- ap- stat, smad, e and oct- as well as unknown candidates. we discuss the described ant algorithm focusing on its characteristic formulation, selectivity and reproducibility, computational efficiency, and biological relevance. the first feature of the described algorithm is definition of artificial ants as a set of m transcription-factor binding motifs. in this algorithm, each ant was assigned to its own set of m binding motifs and it deposited an equal amount of pheromone to the assigned set. a pheromone spectrum was then built from the sum of deposited pheromones by na ants. the value of m > allowed us not only to evaluate a combinatorial effect of multiple binding motifs but also to reduce the number of computational iterations. the second feature among biology-inspired algorithms is a well-characterized choice of selectivity and reproducibility by the two key parameters: pheromone preference factor, ε, and pheromone evaporation factor, δ. the value of ε determines the preference to pheromones, and the value of δ regulates fading of the previous concentration of pheromone. selectivity was defined as " – informational entropy" to evaluate distance from randomness, while reproducibility was defined as correlation among the spectra. a higher selectivity in general implies that the limited number of motif candidates receive a significantly higher pheromone concentration than most of the other candidates. the extreme case for ε ~ or ε > yielded low reproducibility, since the final pheromone spectrum was predominantly influenced by the ants in the first or the last generation. a value of δ controlled evaporation of previous information, and a large value of δ placed more emphasis on recent decisions. the values of ε and δ can be selected arbitrarily depending on the purpose of a particular study. in this study we determined these parameters to reproducibly obtain ~ peaks in the spectrum. the number of peaks was pre-determined using akaike information criterion. a clear advantage of the ant algorithm is a computational efficiency to reach a stable solution compared to the other evolutionary algorithms such as the genetic algorithm. the major difference between the ant algorithm and the genetic algorithm is their solution space. the ant algorithm searches for a group of the best motifs in a space of individual binding motifs, while the genetic algorithm seeks the best combination. the former space is apparently more restricted than the latter combinatorial space. therefore, the ant algorithm has a clear advantage to terminate the search. furthermore, the advantage of the ant algorithm includes identification of redundant transcription-factor binding motifs in eukaryotic gene regulation. neither the genetic algorithm nor particle swarm optimization is well suited to include redundant motifs in a final solution. the ant algorithm is also different from other model-based approaches such as reduce and the principal component analysis. in reduce, for instance, motifs are selected recursively in an add-on manner to reduce the model error by the largest degree at each selection. this selection strategy makes later selections strongly affected by the earlier ones. the ant algorithm, on the other hand, can avoid such a potential conflict in selection. in order to compare these two algorithms, numerical simulations were conducted using a benchmark dataset for artificial genes. simulation results suggested that both reduce and ant algorithm offers similar power in predicting correct number of embedded motifs. although the advantage of reduce is its superior reproducibility with a shorter computational time, the ant algorithm is apparently more suited to predict a motif longer than bp including a motif consisting of a dimeric binding site. biologists are usually advised to use several complementary computational tools to identify regulatory elements from microarray data. the ant algorithm seems to complement analytical approaches such as reduce and the principal component-based method in identifying longer motifs and dimeric binding sites. the ant algorithm can still evaluate combinatorial effects among multiple factors like other model-based approaches reported previously. defining a background model is a general approach in searching for over-representation of dna words within a sequence set. the ant algorithm, however, aims at searching for the dna sequences whose occurrences in the regulatory region correlate with the observed expression levels in the context of combinations of multiple motifs. therefore, the described ant algorithm is in principle not overly sensitive to over-represented dna words. the expression levels are described as a linear combination of the role of individual motifs with different functions. therefore, it is possible that some motifs, predicted to be a stimulator by the ant algorithm, may appear in the regulatory region of the gene whose expression level is down-regulated. a motif length analysis and sequence comparisons supported, at least in part, statistical and biological significance of the selected transcription-factor binding motifs. the predicted motifs matched with the sequences of known binding motifs known to be involved in human chondrogenesis. these binding motifs include ap- creb, sox nfκb, erg- ap- stat, smad, e and oct- interestingly, two of the 5-bp motifs together with a 6-bp motif and a 7-bp motif constituted a contiguous 10-bp binding motif of egr-, confirming a strong involvement of egr- in chondrogenesis. furthermore, two 5-bp motifs coincided with 9-bp consensus sequence of nfκb binding sites. it is possible to evaluate a pool of candidates with varying length simultaneously by including them together in the simulation. note that the prediction by the ant algorithm should be used to address a set of hypotheses, and biological experiment is inevitable. in summary, the described procedure is the first application of ant algorithms for prediction of transcription-factor binding motifs. other definitions of artificial ants and pheromones are possible. for instance, a group of heterogeneous ants could behave like transcription factors or rna polymerases and deposit different kinds of pheromones directly onto genomic dna sequences. we believe that this application will be advanced by further studies for improving computational efficiency and biological relevance.  we developed one form of ant algorithms for prediction of transcription-factor binding motifs. the consensus sequences of biologically known binding motifs have significant similarities with the predicted motifs. unlike healing capability of bones, joint tissues such as articular cartilage hardly regenerate and therefore in vitro chondrogenesis is an extremely challenging subject in tissue engineering. the transcriptional mechanism of human chondrogenesis remains largely unknown. with its efficient search procedure and its controllable reproducibility and selectivity, the described version of ant algorithms allows us to provide a known and novel set of molecular targets for biological verification. 
an ant algorithm is a biology-inspired computational technique, through which a combinatorial problem is solved by mimicking the behavior of social insects such as ants. identification of transcription-factor binding motifs can be formulated as a combinatorial problem, where an efficient algorithm is indispensable to predict the role of multiple binding motifs. the results revealed that the ant algorithm was able to identify biologically known binding motifs in chondrogenesis such as ap- nfκb, and sox some of the predicted motifs were identical to those previously derived with the genetic algorithm. unlike the genetic algorithm, however, the ant algorithm was able to evaluate a contribution of individual binding motifs as a spectrum of distributed information and predict core consensus motifs from a wider dna pool. we developed a unique version of ant algorithms to select a set of binding motifs by considering a potential contribution of each of all random dna sequences of 4- to 7-bp in length. human chondrogenesis was used as a model system. the ant algorithm offers an efficient, reproducible procedure to predict a role of individual transcription-factor binding motifs using a unique definition of artificial ants.
 identification of transcription-factor binding motifs can be formulated as a combinatorial problem, where an efficient algorithm is indispensable to predict the role of multiple binding motifs. an ant algorithm is a biology-inspired computational technique, through which a combinatorial problem is solved by mimicking the behavior of social insects such as ants. we developed a unique version of ant algorithms to select a set of binding motifs by considering a potential contribution of each of all random dna sequences of 4- to 7-bp in length.  human chondrogenesis was used as a model system. the results revealed that the ant algorithm was able to identify biologically known binding motifs in chondrogenesis such as ap- nfκb, and sox some of the predicted motifs were identical to those previously derived with the genetic algorithm. unlike the genetic algorithm, however, the ant algorithm was able to evaluate a contribution of individual binding motifs as a spectrum of distributed information and predict core consensus motifs from a wider dna pool.  the ant algorithm offers an efficient, reproducible procedure to predict a role of individual transcription-factor binding motifs using a unique definition of artificial ants. 