BACKGROUND
ant colony optimisation  is a population-based stochastic search method for solving a wide range of combinatorial optimisation problems.
aco is based on the concept of stigmergy – indirect communication between members of a population through interaction with the environment.
an example of stigmergy is the communication of ants during the foraging process: ants indirectly communicate with each other by depositing pheromone trails on the ground and thereby influencing the decision processes of other ants.
this simple form of communication between individual ants gives rise to complex behaviours and capabilities of the colony as a whole.
from the computational point of view, aco is an iterative construction search method in which a population of simple agents  repeatedly constructs candidate solutions to a given problem; this construction process is probabilistically guided by heuristic information on the given problem instance as well as by a shared memory containing experience gathered by the ants in previous iterations .
following the seminal work by dorigo et al.
<cit> , aco algorithms have been successfully applied to a broad range of hard combinatorial problems, including the traveling salesman problem, the graph colouring problem, the quadratic assignment problem and vehicle routing problems .
the research presented in this paper builds on an aco algorithm first proposed in  <cit>   for ab-initio protein folding under a widely studied abstract model – the hydrophobic polar  model.
in particular, we extend our previous aco algorithm to the 3d hp model and improve its performance by modifying the subsidiary local search procedure.
the protein folding problem is one of the most challenging problems in computational biology, molecular biology, biochemistry and physics.
even under simplified lattice models, the protein folding problem is non-deterministic polynomial-time hard   <cit> .
the ab-initio protein folding problem can be broken down into three sub-problems: 1) design of a model ; 2) definition of an energy function that can effectively discriminate between native and non-native states; and 3) design of a search algorithm that can efficiently find minimal-energy conformations.
a number of search  methods have been proposed in the literature to solve the protein folding problem, including monte carlo algorithms, evolutionary algorithms, tabu search and hybrid approaches.
aco, which has been very successfully applied to other combinatorial problems, appears to be a very attractive computational method for solving the protein folding problem, since it combines aspects of chain-growth and permutation-based search with ideas closely related to reinforcement learning.
these concepts and ideas apply rather naturally to protein folding: by folding from multiple initial folding points, guided by the energy function and experience from previous iterations of the algorithm, an ensemble of promising, low-energy complete conformations is obtained.
these conformations are further improved by a subsidiary local search procedure and then evaluated to update the accumulated pheromone values that are used to bias the generation of conformations in future iterations of the algorithm.
in this paper, we ask and address the following questions: is aco a competitive method for solving the ab-initio protein folding problem under the 2d and 3d hp models?
how does its performance scale with sequence length?
what is the role of the parameters of the aco algorithm for the efficiency of the optimisation process?
which classes of structures  are solved more efficiently by aco than by any other known algorithms?
finally, it should be noted that our aco algorithm for this problem is based on very simple design choices, in particular with respect to the solution components reinforced in the pheromone matrix and of the subsidiary local search procedure.
we discuss which of the many design choices underlying our algorithm should be reconsidered in order to achieve further performance improvements.
the hydrophobic polar model
due to the complexity of the protein folding problem, simplified models such as dill's hydrophobic-polar  model have become one of the major tools for studying protein structure  <cit> .
the hp model is based on the observation that the hydrophobic force is the main force determining the unique native conformation  of small globular proteins  <cit> .
in the hp model, the primary amino acid sequence of a protein  is abstracted to a sequence of hydrophobic  and polar  residues that is represented as a string over the letters h and p. the conformations of such an hp sequence are restricted to self-avoiding walks on a lattice.
for the 2d hp model, a 2-dimensional square lattice is typically used, and the 3d hp model is generally based on a 3-dimensional cubic lattice.
an example of a protein conformation under the 2d hp model is shown in figure  <dig>  the energy of a conformation is defined as the number of topological contacts between hydrophobic amino acids that are not neighbours in the given sequence.
more specifically, a conformation c with exactly n such h-h contacts has energy e = n·; for example, the 2d hp conformation shown in figure  <dig> has energy - <dig>
the hp protein folding problem can be formally defined as follows: given an hp sequence s = s <dig> s <dig> ..sn, find an energy-minimising conformation of s, i.e., find c* ∈ c such that e = min{e | c ∈ c}, where c is the set of all valid conformations for s. it has been proved recently that this problem and several variations of it are np-hard  <cit> .
existing 2d and 3d hp protein folding algorithms
a number of well-known heuristic optimisation methods have been applied to the 2d and 3d hp protein folding problem, including evolutionary algorithms   <cit>  and monte carlo  algorithms  <cit> .
the latter have been found to be particularly robust and effective for finding high-quality solutions to the hp protein folding problem  <cit> .
besides general optimisation methods, there are other heuristic methods that rely on specific heuristics that are based on intuitions or assumptions about the folding process, such as co-operativity of folding or the existence of a hydrophobic core.
co-operativity is believed to arise from local conformational choices that result in a globally optimal state without exhaustive search  <cit> .
among these methods are the hydrophobic zipper method   <cit> , the contact interactions method   <cit> , the core-directed chain growth method   <cit> , and the constraint-based hydrophobic core construction method   <cit> .
the hydrophobic zipper  strategy developed by dill et al.
is based on the hypothesis that once a hydrophobic contact is formed it cannot be broken, and other contacts are formed in accordance with already folded parts of the chain   <cit> .
the contact interactions  algorithm by toma and toma  <cit>  combines the idea of hz with a monte carlo search procedure that assigns different conformational freedom to the different residues in the chain, and thus allows previously formed contacts to be modified according to their computed mobilities.
the core-directed chain growth method  by beutler and dill  <cit>  biases construction towards finding a good hydrophobic core by using a specifically designed heuristic function and by approximating the hydrophobic core with a square  or a cube .
the constraint-based hydrophobic core construction method  by yue and dill  <cit>  is complete, i.e., always guaranteed to find a global optimum; it attempts to find the hydrophobic core with the minimal possible surface area by systematically introducing geometric constraints and by pruning branches of a conformational search tree.
a similar, but more efficient complete constraint satisfaction search method has been proposed by backofen et al.
<cit>  for the more complex face-centred cubic lattice.
an early application of evolutionary algorithms to protein structure prediction was presented by unger and moult  <cit> .
their non-standard ea incorporates characteristics of monte carlo methods.
currently among the best known algorithms for the hp protein folding problem are various monte carlo algorithms, including the 'pruned-enriched rosenbluth method'  of grassberger et al.
<cit> .
perm is a biased chain growth algorithm that evaluates partial conformations and employs pruning and enrichment strategies to explore promising partial solutions.
other methods for solving protein folding problems include the dynamic monte carlo algorithm by ramakrishnan et al.
<cit> , which introduced long-range moves involving disconnection of the chain, and the evolutionary monte carlo  algorithm by liang and wong  <cit> , which works with a population of individuals that each perform monte carlo optimisation; a variant of emc also reinforces certain secondary structures .
finally, chikenji et al.
introduced the multi-self-overlap ensemble  monte carlo method  <cit> , which considers overlapping chain configurations.
other monte carlo methods that have been particularly useful in off-lattice protein folding include generalised ensemble methods, such as umbrella sampling  <cit>   and multi-canonical  sampling  <cit> .
replica exchange monte carlo  has also been applied to the off-lattice hp model  <cit> .
currently, when applied to the square and cubic lattice hp model, none of these algorithms appears to completely dominate the others in terms of solution quality and run-time.
our aco algorithm for the 2d and 3d hp protein folding problem
in previous work, we have applied aco to the 2d hp protein folding problem  <cit> ; in the following, we briefly summarise the main features of our aco algorithm and the improvements introduced in this work.
details on our aco framework and the new aco-hppfp- <dig> algorithm developed in the context of this work are given in the 'methods' section.
as usual, the ants in our aco algorithm iteratively undergo three phases: the construction phase – during which each ant constructs a candidate solution by sequentially growing a conformation of the given hp sequence, starting from a folding point that is chosen uniformly at random among all sequence positions; the local search phase – when ants further optimise protein conformations folded during the construction phase; and the pheromone update phase – when ants update the pheromone matrix  based on the energies of the conformations obtained after the construction and the local search phases.
a general outline of aco is shown in figure  <dig>
the solution components used during the construction process, the local search phase and the pheromone update are local structure motifs  straight , left , right  in 2d, and straight , left , right , up , down  in 3d, which for each amino acid indicate its position on the 2d or 3d lattice relative to its direct predecessors in the given sequence .
in 3d, the relative folding directions are defined as in  <cit> : a local coordinate system is associated with every sequence position, such that s corresponds to the direction of the x axis, l to the direction of the y axis, and u to the direction of the z axis.
each local motif corresponds to a relative rotation of this coordinate system .
since conformations are rotationally invariant, the position of the first two amino acids can be fixed without loss of generality.
hence, we represent candidate conformations for a protein sequence of length n by a sequence of local structure motifs of length n -  <dig>  for example, the conformation of sequence s1- <dig> shown in figure  <dig> corresponds to the motif sequence lsllrrlrllslrrllsl.
during the construction phase, ants fold a protein from an initial folding point by probabilistically adding one amino acid at a time based on the two sources of information: pheromone matrix values τ  and heuristic function values η ; details of this process are given in the 'methods' section.
the relative importance of τ and η is determined by parameters α and β, respectively, whose settings are detailed in the 'discussion' section.
similar to other aco algorithms known from the literature, our algorithm for the hp protein folding problem incorporates a local search phase that takes the initially built protein conformation and attempts to optimise its energy further, using probabilistic long-range moves that are described in detail in the 'methods' section.
finally, the pheromone update procedure is based on two mechanisms: uniform pheromone evaporation is modelled by decreasing all pheromone levels by a constant factor ρ , and pheromone reinforcement is achieved by increasing the pheromone levels associated with the local folding motifs used in a fraction of the best conformations  obtained during the preceding construction and local search phase.
furthermore, to prevent search stagnation when all of the pheromone is accumulated on very few structural motifs, we introduce an additional renormalisation mechanism for the pheromone levels .
different from our previous aco algorithms for the hp protein folding problem, our new algorithm, aco-hppfp- <dig>  supports the 3d hp cubic lattice model in addition to the 2d hp square lattice model.
furthermore, it uses a different iterative improvement strategy, a modified long-range move operator and a less restrictive termination criterion in its local search phase.
aco-hppfp- <dig> was used in all aco experiments described in the following.
RESULTS
to compare aco-hppfp- <dig> with algorithms for the 2d and 3d hp protein folding problem described in the literature, we tested it on a number of standard benchmark instances as well as on two newly created data sets, one of which was obtained by randomly generating amino acid sequences with hydrophobicity value characteristic of globular proteins, while the other consists of biological sequences that were translated into hp strings using a standard hydrophobicity scale.
results for standard benchmark instances
the  <dig> standard benchmark instances for 2d- and 3d-hp protein folding shown in table  <dig> have been widely used in the literature  <cit> .
experiments on these standard benchmark instances were conducted by performing a number of independent runs for each problem instance .
unless explicitly indicated otherwise, we used the following parameter settings for all experiments: α: =  <dig>  β: =  <dig>  ρ: =  <dig>  and θ: =  <dig> .
furthermore, all pheromone values were initialised to 1/ <dig> in 2d and to 1/ <dig> in 3d, and a population of  <dig> ants was used, 50% of which were allowed to perform local search.
the local search procedure was terminated when no improvement in energy had been obtained after between  <dig>  <dig>  and  <dig>  <dig>  scans through the protein sequence.
we used an elitist pheromone updating scheme in which only the best 1% of all ants was allowed to perform pheromone updates.
the probability  of keeping the previous direction when feasible during the long-range mutation move was set to  <dig>  .
these settings were determined in a series of experiments in which we studied the influence of different parameter settings and will be further discussed later.
all experiments were performed on pcs with  <dig>  ghz pentium iv cpus,  <dig> kb cache and  <dig> mb ram, running redhat linux , and run-time was measured in terms of cpu time.
most studies of ea and mc methods in the literature, including  <cit> , report the number of valid conformations scanned during the search.
this makes a performance comparison difficult, since run-time spent for backtracking and the checking of partial or infeasible conformations, which may vary substantially between different algorithms, is not accounted for.
we therefore compared aco to the best-performing algorithm from the literature for which performance data in terms of cpu time is available – perm  <cit>  .
we note that the most efficient perm variant for the hp protein folding problem uses an additional penalty of  <dig>  for h-p contacts  <cit> .
since this corresponds to an energy function different from that of the standard hp model underlying our aco algorithm as well as other algorithms developed in literature, we used the best performing variant of perm  <cit>  based on the standard energy function in our experiments.
it may be noted that the chain growth process in perm can start from the n- or c-terminus of the given hp sequence, and in many cases, this results in substantial differences in the performance of the algorithm.
to capture this effect, we always ran perm in both directions, and in addition to the respective average run-times, t <dig> and t <dig>  we report the expected time for solving a given problem instance when performing both runs concurrently, texp = 2·- <dig>  for all runs of perm, the following parameter settings were used: inverse temperature γ: =  <dig> and q: =  <dig> .
the results obtained on standard 2d benchmark instances  indicate that aco-hppfp- <dig> is competitive with the ea and mc methods described in the literature; it works very well on sequences of sizes up to  <dig> amino acids and produces high quality suboptimal configurations for the longest sequences considered here .
on average, aco requires less cpu time than perm for finding best known conformations for sequence s1-8; but perm performs better for sequences s1- <dig> and s1- <dig> as well as for the longer sequences of  <dig> to  <dig> residues .
sequence s1- <dig> has a very symmetrical optimal state , which – as argued in  <cit>  – would be difficult to find for any chain growing algorithm.
all algorithms from the literature which we are aware of have problems folding this sequence; aco-hppfp- <dig>  on the other hand, is able to handle this instance quite well, since a number of ants folding from different starting points in conjunction with a local search procedure that involves large-scale mutations originating from different sequence positions can produce good partial folds for various parts of the chain.
in comparison with other algorithms for the 2d hp protein folding problem considered here , aco-hppfp- <dig> generally shows very good performance on standard benchmark instances.
in case of the 3d hp protein folding problem , the majority of algorithms for which we were able to find performance results in the literature use heuristics that are highly specialised for this problem.
unlike hz, cg and ci, aco-hppfp- <dig> finds optimal  solution qualities for all sequences.
however, perm  and chcc consistently outperform aco-hppfp- <dig> on these standard 3d hp benchmark instances, and cg reaches best known solution qualities substantially faster in many cases.
we note that for sequence s2- <dig> and s2- <dig>  perm's performance is greatly dependent on the folding direction.
result for new biological and random data sets
to thoroughly test the performance of aco-hppfp- <dig>  we created two new data sets of random and biological sequences of length ≈  <dig> and ≈  <dig> amino acids .
random sequences were generated based on the observation that most globular proteins have a fairly uniform amino acid profile, and the percent of hydrophobic residues of majority of globular proteins falls in the range of 40–50%  <cit> .
thus, the probability of generating character h at each position of a sequence was chosen to be  <dig> , and in the remaining cases , we generated a p.
for the biological test-sets, ten sequences were taken from the pdbselect data set with homology < 25% from the protein data bank  in order to obtain a non-redundant representative set of proteins.
these protein sequences were translated into hp strings using the hydrophobicity scale classification of rasmol  <cit> , according to which the following amino acids were considered hydrophobic: ala, leu, val, ile, pro, phe, met, trp, gly and tyr.
non-standard amino acid symbols, such as x and z, were skipped in this translation.
figures  <dig> and  <dig> illustrate the performance of aco-hppfp- <dig> vs perm in terms of mean cpu time over  <dig> runs per instance and algorithm; for practical reasons, each run was restricted to  <dig> cpu hour on our reference machine, and the lowest energies obtained in these runs  are not necessarily optimal.
as can be seen from these results, in 2d, aco-hppfp- <dig> performs roughly comparably to perm : aco-hppfp- <dig> reaches the same energies as perm, but on some instances, particularly of length  <dig>  requires more run-time.
in 3d, aco-hppfp- <dig> generally requires a comparable amount of run-time on sequences of length  <dig> and outperforms perm on one random sequences of length  <dig>  but performs noticeably worse on sequences of length  <dig> and in some cases does not reach the same energy.
we also generated longer sequences of length 75; for these, aco-hppfp- <dig> failed to reach the minimal energy values obtained by perm in a number of cases.
the run-times for both algorithms are reported in detail in additional file 1; we note that on some sequences, the performance of perm depends significantly on the direction of folding.
interestingly, there is no significant difference in performance between the biological and random test-sets for either perm or aco-hppfp- <dig>
in summary, the performance of aco-hppfp- <dig> is comparable with that of perm  on biological and random sequences of length 30– <dig>  but worse on longer sequences.
this scaling effect is significantly more pronounced in 3d than in 2d.
we note that neither aco-hppfp- <dig> nor perm were optimised for short sequences , but by using parameter settings different from the ones specified earlier, the performance of both algorithms can be significantly improved in this case.
characteristic performance differences between aco and perm
to further investigate the conditions under which aco performs well compared to perm, we visually examined native conformations found by both algorithms, paying special attention to conformations for which one of the two algorithms does not perform well .
based on our observations, we hypothesised that perm usually performs well on sequences that have a structural nucleus in the native conformation at one of the ends of the sequence ; on the other hand, it has trouble folding sequences whose native conformations have structural nuclei in the middle of the sequence.
in comparison, aco is not significantly affected by the location of the structural nucleus  in the sequence, since it uses construction from different folding points as well as the long-range mutation moves in local search, which can initiate refolding from arbitrary sequence positions.
here, we use the term 'structural nucleus' to refer to a predominantly locally folded part of the chain that can be relatively easily folded sequentially based on local sequence information  <cit> .
for most sequences considered in this study, we observed a single structural nucleus, which is not surprising, given their relatively short length; however, it is generally believed that longer sequences have multiple folding nuclei  <cit> .
the left side of figure  <dig> shows an example of a relatively short biological sequence  with a unique native hydrophobic core in the 2d hp model.
this sequence has no structural nuclei at its ends; instead, the two ends interact with each other.
aco-hppfp- <dig> outperforms perm by a factor of  <dig> on this sequence in terms of cpu time: using a cut-off time of  <dig> cpu hour per run, perm found the optimum with energy - <dig> in an average run-time of  <dig>  cpu seconds , while using the same cut-off time and machine, aco-hppfp- <dig> found the optimum in an average run-time of  <dig> cpu seconds.
we also designed two additional sequences, d- <dig> and d- <dig>  of length  <dig> and  <dig>  respectively, that have a unique native state in which both ends of the sequence interact with each other .
sequence d- <dig> also has a structural nucleus near its c-terminus.
when testing the performance of perm and aco-hppfp- <dig> on these sequences, we found that on d- <dig>  aco-hppfp- <dig> requires a mean run-time of  <dig> cpu seconds, compared to t <dig> =  <dig>  <dig>  t <dig> =  <dig>  texp =  <dig> cpu seconds for perm .
when this sequence was reversed, perm started folding the sequence from the structural nucleus, and its mean run-time dropped to  <dig> cpu second.
a result similar to that for sequence b50- <dig> was obtained for sequence d- <dig>  which has no structural nuclei at the ends, but a native state in which the ends interact with each other.
here, aco-hppfp- <dig> was found to require a mean run-time of  <dig> cpu seconds , compared to t <dig> =  <dig>  <dig>  t <dig> =  <dig>  <dig>  texp =  <dig>  <dig> cpu seconds for perm; as expected, in this case, reversing the folding order of the sequence did not cause a decrease in perm's run-time.
we also analysed native conformations of sequences on which perm outperforms aco and observed that the end from which perm starts folding is relatively compact and forms a structural nucleus in the resulting conformation.
an example of a conformation with the structural nucleus at the beginning of the sequence  is shown in the right panel of figure  <dig>  for this biological sequence , perm finds an optimal conformation with an energy of - <dig> in t <dig> =  <dig>  t <dig> =  <dig>  texp =  <dig> cpu seconds, while the average run-time for aco-hppfp- <dig> is  <dig> cpu seconds.
our aco algorithm generally performs worse than perm on sequences that have structural nuclei at the ends, because it tends to spend substantial amounts of time compacting local regions in the interior of the sequence, while perm folds more systematically from one end.
these observations also hold in 3d, as seen from two random sequences folded in 3d .
to further investigate our hypothesis, we studied differences between the distributions of native conformations found by aco-hppfp- <dig> and perm, respectively.
for this purpose, we introduced the notion of relative h-h contact order, which captures arrangement of h residues in the core of the folded protein, and thus determines the topology of the conformation .
relative h-h contact order is defined as follows:
where l is the number of h-h contacts, n is the number of h residues in the sequence, and i and j are interacting h residues that are not neighbours in the chain.
intuitively, coh-h specifies the average sequence separation between h-h residues in contact per h in the sequence.
to further examine the topological differences between ensembles of native conformations found by the two algorithms, we also looked at the hydrophobic solvent accessible area , the number of h-h contacts, and the h-h contact order as a function of the length of the sequence prefix .
in this analysis, we calculated the properties of interest mentioned above for the native conformations found in  <dig> independent runs by aco-hppfp- <dig> and perm, and plotted the mean values of the respective quantities as functions of the sequence prefix length .
as seen in figure  <dig>  aco-hppfp- <dig> is less greedy than perm, both in 2d  and in 3d , and it tends to leave more lattice sites around h residues accessible for future contacts with other h residues that appear later in the chain.
this is also reflected in the mean number of h-h contacts formed when folding prefixes of increasing length; aco-hppfp- <dig> tends to form fewer h-h contacts than perm for short and medium size prefixes .
by examining the dependence of absolute h-h contact order  on prefix length, we furthermore observed that different from perm, aco-hppfp- <dig> realises the bulk of its local h-h interactions in the middle of the given sequence .
this further confirms that aco is capable of finding native conformations with structural folding nuclei that are not located at or near the end of a given protein sequence.
the results illustrated in figures  <dig>   <dig> and  <dig> are typical for all 2d and 3d hp instances we studied.
discussion
although conceptually rather simple, our aco algorithm is based on a number of distinct components and mechanisms.
a natural question to ask is whether and to which extent each of these contributes to the performance reported in the previous section.
a closely related questions concerns the impact of parameter settings on the performance of aco-hppfp-3; further details concerning parameters can be found in the 'methods' section.
to address these questions, we conducted several series of experiments.
in this context, we primarily used three standard test sequences: sequence s1- <dig> of length  <dig> and sequence s1- <dig> of length  <dig>  in 2d, as well as sequence s2- <dig> of length  <dig> in 3d ; these sequences were chosen because the cpu time required to find the best known solutions was sufficiently small to perform a large number of runs .
following the methodology of hoos and stützle  <cit> , we measured run-time distributions  of our aco algorithm, which represent the  probability distribution over the run-time required to reach  a given solution quality; the solution qualities used here are the known optima or best known energies for the respective sequences.
pheromone values and heuristic information
two important components of any aco algorithm are the heuristic function, which indicates the desirability of using particular solution components during the construction phase, and the pheromone values, which represent information learned over multiple iterations of the algorithm.
three parameters control the influence of the pheromone information versus heuristic information on the construction of candidate solutions: the relative weight of the pheromone information, α; the relative weight of the heuristic information, β; and the pheromone persistence, ρ .
in the first experiment, we investigated the impact of pheromone  and heuristic information , and their relative importance for the performance of our aco algorithm.
as can be seen from the results shown in figure  <dig>  both the pheromone values and the heuristic information are important in 2d and 3d; when ignoring either of them , the algorithm performs worse, particularly for longer 2d sequences .
the optimal settings for α and β for most problem instances seem to be around α =  <dig> and β =  <dig>  as shown in figure  <dig>  it should be noted that in 3d, pheromone information appears to be less important than in 2d, which suggests that the specific solution components used in our algorithms are somewhat less meaningful in 3d.
the goal of the next experiment was to further explore the role of experience accumulated over previous iterations in the form of pheromone values.
to this end, we varied the pheromone persistence, ρ, while keeping other parameters constant.
the results shown in figure  <dig> show that in 2d, it is important to utilise past experience , but also to weaken its impact over time .
at the same time, closer examination revealed that for ρ >  <dig>  attrition, i.e., the construction of inextensible partial conformations, is a major problem, which is a result of the accumulation of pheromone from multiple conformations.
this is why the backtracking mechanism described in the 'methods' section is extremely important for the performance of our algorithm in 2d.
in 3d, for the previously stated reasons and because of the fact that the attrition problem is much less severe, the impact of the persistence parameter is generally smaller than in 2d.
ant colony size and length of local search phase
during the initial empirical evaluation of our algorithm, we observed that ant colony size  and the duration of local search  are correlated and significantly affect its performance.
to further investigate this phenomenon, we conducted additional experiments in which we fixed the ant colony size and varied the maximal number of non-improving steps during local search, and vice versa.
in this series of experiments, different colony sizes were considered, from a single ant up to a population of  <dig>  <dig> ants, and the number of non-improving steps in local search was varied from  <dig> to  <dig>  <dig>  the results, shown in figure  <dig>  indicate that there is an optimal colony size of about  <dig> ants for both, 2d and 3d; aco-hppfp- <dig> is quite robust with respect to colony size, but performance decreases for very small or very large colony sizes.
intuitively, this is the case because the use of a population of ants provides diversification to the search process, which enables it to explore different regions of the underlying search space; very small populations provide insufficient diversification, and the search stagnates easily, while for very large populations, the additional time required for running the search phases for each ant on the same sequential machine is not amortised any longer by increased efficiency of the overall search process.
our results also indicate that the performance of aco-hppfp- <dig> is more sensitive to the number of non-improving steps than to ant colony size.
the optimal value for the maximum number of non-improving steps tolerated  before the local search phase terminates was found to be around  <dig>  <dig> for short 2d sequences  and around  <dig>  <dig> for long 2d sequences ; the latter value also appeared to be optimal for all 3d sequences considered here.
this observation follows the intuition that more degrees of freedom, as present for longer sequences and in higher dimensions, require more time for local optimisation, since for any conformation, improving neighbours tend to be rarer and hence harder to find.
selectivity and persistence of local search
as described in the 'methods' section, our aco algorithm uses selective local search, i.e., local search is only performed on a certain fraction of the lowest energy conformations.
we observed that aco-hppfp- <dig> is fairly robust with respect to the fraction of conformations to which local search is applied; good performance was obtained for local search selectivity values between 5% and 50%, but performance was found to deteriorate when local search is performed by all ants.
intuitively, similar to colony size, local search selectivity has an impact on search diversification.
if too few ants perform local search, insufficient diversification is achieved, which typically leads to premature stagnation of the search process.
on the other hand, if local search is performed by too many ants, the resulting substantial overhead in run-time can no longer be amortised by increased search efficiency.
similarly to selective local search, pheromone update was performed only by a certain fraction of so-called 'elitist ants' whose solution quality after the local search phase is highest within the population.
as in the case of local search selectivity, aco-hppfp- <dig> shows robustly high performance for elitist fractions between 1% and 50% , but performance deteriorates markedly when all ants in the colony are allowed to update the pheromone matrix.
in a final experiment, we studied the impact of the persistence of local search, i.e., of the probability  of retaining  previous relative directions during long-range mutation moves.
as can be seen in figure  <dig>  good performance is generally obtained for  values between  <dig>  and  <dig> .
both extreme cases,  =  <dig>  which corresponds to an extremely h-contact greedy mutation operator, and  =  <dig>  in which refolding always follows previous directions when feasible, result in a substantial decrease in performance.
when  =  <dig>  the decrease of performance in 3d is smaller than in 2d, because there is no severe attrition as in 2d, where greedy placement of h residues leads to early formation of very compact partial conformations, which often cannot be extended into valid complete conformations.
the performance decrease for high  values is due to insufficient ability of the chain to fold into a new conformation that accommodates well the local change in structure which triggered the refolding.
CONCLUSIONS
in this work, we have shown that ant colony optimisation  can be applied in a rather straight-forward way to the 2d and 3d hp protein folding problems.
even though our aco-hppfp- <dig> algorithm is based on very simple structure components  and a simple subsidiary local search procedure , it performs fairly well compared to other algorithms and specialised heuristics on the benchmark instances considered here, particularly in 2d.
the only non-specialised algorithm that typically performs better than our aco algorithm, both in 2d and 3d, is perm.
we observed that, particularly in 3d, the run-time required by aco-hppfp- <dig> for finding minimum  energy conformations scales worse with sequence length than perm.
however, our results show that our aco algorithm finds a different ensemble of native conformations compared to perm, and has less difficulty folding sequences whose native states contain structural nuclei located in the middle rather than at the ends of a given sequence, as well as sequences with structures in which the ends interact.
we found that two major components of aco-hppfp- <dig> – the pheromone values, which capture experience accumulated over multiple iterations of the search process and from multiple conformations, as well as the heuristic information that provides myopic guidance to the folding process – play a significant role for longer 2d sequences and, to a lesser extent, for 3d sequences, which suggests that in 3d, it may be preferable to associate pheromone values with more complex solution components.
we also found that the subsidiary local search procedure is crucial for the performance of the algorithm; in particular, to ensure that high-quality conformations are obtained, it is very important to allow the local search procedure to run sufficiently long.
in an earlier version of our algorithm  <cit> , we used substantially more stringent termination criteria, which forced us to additionally use non-greedy local search  in addition to the greedy local search procedure used here.
the results presented in this study indicate that by using a new and simpler local search procedure, aco-hppfp- <dig> achieves better performance; this is probably due to the fact that the new local search procedure is based on a type of long-range move that leads to a larger effective search neighbourhood.
we have shown that all components of our aco algorithms contribute to its performance.
in particular, its performance is affected by the following components and parameters : pheromone values, termination criterion for local search, persistence of long-range moves, ant colony size, pheromone persistence, heuristic function, selectivity of local search, and selectivity of pheromone update .
because of its ability to find more balanced ensembles of minimum  energy conformations, our new aco algorithm can greatly facilitate investigations of the topology and location of structural nuclei, which we plan to undertake in future work.
finally, while hp protein folding problems are of considerable interest because of their conceptual simplicity, ultimately, most applications of protein folding algorithms require the use of more realistic models of protein structure.
since it does not rely on heuristics and properties that are specific to the hp model and yet performs very well on this restrictive, but not entirely unrealistic abstract model, we believe that relatively straight-forward extensions of our aco algorithm to more complex and realistic models of protein structure hold significant promise.

 ant colony optimisation is a population-based stochastic search method for solving a wide range of combinatorial optimisation problems. aco is based on the concept of stigmergy – indirect communication between members of a population through interaction with the environment. an example of stigmergy is the communication of ants during the foraging process: ants indirectly communicate with each other by depositing pheromone trails on the ground and thereby influencing the decision processes of other ants. this simple form of communication between individual ants gives rise to complex behaviours and capabilities of the colony as a whole. from the computational point of view, aco is an iterative construction search method in which a population of simple agents repeatedly constructs candidate solutions to a given problem; this construction process is probabilistically guided by heuristic information on the given problem instance as well as by a shared memory containing experience gathered by the ants in previous iterations. following the seminal work by dorigo et al., aco algorithms have been successfully applied to a broad range of hard combinatorial problems, including the traveling salesman problem, the graph colouring problem, the quadratic assignment problem and vehicle routing problems. the research presented in this paper builds on an aco algorithm first proposed in for ab-initio protein folding under a widely studied abstract model – the hydrophobic polar model. in particular, we extend our previous aco algorithm to the 3d hp model and improve its performance by modifying the subsidiary local search procedure. the protein folding problem is one of the most challenging problems in computational biology, molecular biology, biochemistry and physics. even under simplified lattice models, the protein folding problem is non-deterministic polynomial-time hard. the ab-initio protein folding problem can be broken down into three sub-problems: 1) design of a model; 2) definition of an energy function that can effectively discriminate between native and non-native states; and 3) design of a search algorithm that can efficiently find minimal-energy conformations. a number of search methods have been proposed in the literature to solve the protein folding problem, including monte carlo algorithms, evolutionary algorithms, tabu search and hybrid approaches. aco, which has been very successfully applied to other combinatorial problems, appears to be a very attractive computational method for solving the protein folding problem, since it combines aspects of chain-growth and permutation-based search with ideas closely related to reinforcement learning. these concepts and ideas apply rather naturally to protein folding: by folding from multiple initial folding points, guided by the energy function and experience from previous iterations of the algorithm, an ensemble of promising, low-energy complete conformations is obtained. these conformations are further improved by a subsidiary local search procedure and then evaluated to update the accumulated pheromone values that are used to bias the generation of conformations in future iterations of the algorithm. in this paper, we ask and address the following questions: is aco a competitive method for solving the ab-initio protein folding problem under the 2d and 3d hp models? how does its performance scale with sequence length? what is the role of the parameters of the aco algorithm for the efficiency of the optimisation process? which classes of structures are solved more efficiently by aco than by any other known algorithms? finally, it should be noted that our aco algorithm for this problem is based on very simple design choices, in particular with respect to the solution components reinforced in the pheromone matrix and of the subsidiary local search procedure. we discuss which of the many design choices underlying our algorithm should be reconsidered in order to achieve further performance improvements. the hydrophobic polar model due to the complexity of the protein folding problem, simplified models such as dill's hydrophobic-polar model have become one of the major tools for studying protein structure. the hp model is based on the observation that the hydrophobic force is the main force determining the unique native conformation of small globular proteins. in the hp model, the primary amino acid sequence of a protein is abstracted to a sequence of hydrophobic and polar residues that is represented as a string over the letters h and p. the conformations of such an hp sequence are restricted to self-avoiding walks on a lattice. for the 2d hp model, a 2-dimensional square lattice is typically used, and the 3d hp model is generally based on a 3-dimensional cubic lattice. an example of a protein conformation under the 2d hp model is shown in figure the energy of a conformation is defined as the number of topological contacts between hydrophobic amino acids that are not neighbours in the given sequence. more specifically, a conformation c with exactly n such h-h contacts has energy e = n·; for example, the 2d hp conformation shown in figure has energy - the hp protein folding problem can be formally defined as follows: given an hp sequence s = s s..sn, find an energy-minimising conformation of s, i.e., find c* ∈ c such that e = min{e | c ∈ c}, where c is the set of all valid conformations for s. it has been proved recently that this problem and several variations of it are np-hard. existing 2d and 3d hp protein folding algorithms a number of well-known heuristic optimisation methods have been applied to the 2d and 3d hp protein folding problem, including evolutionary algorithms and monte carlo algorithms. the latter have been found to be particularly robust and effective for finding high-quality solutions to the hp protein folding problem. besides general optimisation methods, there are other heuristic methods that rely on specific heuristics that are based on intuitions or assumptions about the folding process, such as co-operativity of folding or the existence of a hydrophobic core. co-operativity is believed to arise from local conformational choices that result in a globally optimal state without exhaustive search. among these methods are the hydrophobic zipper method, the contact interactions method, the core-directed chain growth method, and the constraint-based hydrophobic core construction method. the hydrophobic zipper strategy developed by dill et al. is based on the hypothesis that once a hydrophobic contact is formed it cannot be broken, and other contacts are formed in accordance with already folded parts of the chain. the contact interactions algorithm by toma and toma combines the idea of hz with a monte carlo search procedure that assigns different conformational freedom to the different residues in the chain, and thus allows previously formed contacts to be modified according to their computed mobilities. the core-directed chain growth method by beutler and dill biases construction towards finding a good hydrophobic core by using a specifically designed heuristic function and by approximating the hydrophobic core with a square or a cube. the constraint-based hydrophobic core construction method by yue and dill is complete, i.e., always guaranteed to find a global optimum; it attempts to find the hydrophobic core with the minimal possible surface area by systematically introducing geometric constraints and by pruning branches of a conformational search tree. a similar, but more efficient complete constraint satisfaction search method has been proposed by backofen et al. for the more complex face-centred cubic lattice. an early application of evolutionary algorithms to protein structure prediction was presented by unger and moult. their non-standard ea incorporates characteristics of monte carlo methods. currently among the best known algorithms for the hp protein folding problem are various monte carlo algorithms, including the'pruned-enriched rosenbluth method' of grassberger et al.. perm is a biased chain growth algorithm that evaluates partial conformations and employs pruning and enrichment strategies to explore promising partial solutions. other methods for solving protein folding problems include the dynamic monte carlo algorithm by ramakrishnan et al., which introduced long-range moves involving disconnection of the chain, and the evolutionary monte carlo algorithm by liang and wong, which works with a population of individuals that each perform monte carlo optimisation; a variant of emc also reinforces certain secondary structures. finally, chikenji et al. introduced the multi-self-overlap ensemble monte carlo method, which considers overlapping chain configurations. other monte carlo methods that have been particularly useful in off-lattice protein folding include generalised ensemble methods, such as umbrella sampling and multi-canonical sampling. replica exchange monte carlo has also been applied to the off-lattice hp model. currently, when applied to the square and cubic lattice hp model, none of these algorithms appears to completely dominate the others in terms of solution quality and run-time. our aco algorithm for the 2d and 3d hp protein folding problem in previous work, we have applied aco to the 2d hp protein folding problem; in the following, we briefly summarise the main features of our aco algorithm and the improvements introduced in this work. details on our aco framework and the new aco-hppfp- algorithm developed in the context of this work are given in the'methods' section. as usual, the ants in our aco algorithm iteratively undergo three phases: the construction phase – during which each ant constructs a candidate solution by sequentially growing a conformation of the given hp sequence, starting from a folding point that is chosen uniformly at random among all sequence positions; the local search phase – when ants further optimise protein conformations folded during the construction phase; and the pheromone update phase – when ants update the pheromone matrix based on the energies of the conformations obtained after the construction and the local search phases. a general outline of aco is shown in figure the solution components used during the construction process, the local search phase and the pheromone update are local structure motifs straight, left, right in 2d, and straight, left, right, up, down in 3d, which for each amino acid indicate its position on the 2d or 3d lattice relative to its direct predecessors in the given sequence. in 3d, the relative folding directions are defined as in: a local coordinate system is associated with every sequence position, such that s corresponds to the direction of the x axis, l to the direction of the y axis, and u to the direction of the z axis. each local motif corresponds to a relative rotation of this coordinate system. since conformations are rotationally invariant, the position of the first two amino acids can be fixed without loss of generality. hence, we represent candidate conformations for a protein sequence of length n by a sequence of local structure motifs of length n - for example, the conformation of sequence s1- shown in figure corresponds to the motif sequence lsllrrlrllslrrllsl. during the construction phase, ants fold a protein from an initial folding point by probabilistically adding one amino acid at a time based on the two sources of information: pheromone matrix values τ and heuristic function values η; details of this process are given in the'methods' section. the relative importance of τ and η is determined by parameters α and β, respectively, whose settings are detailed in the'discussion' section. similar to other aco algorithms known from the literature, our algorithm for the hp protein folding problem incorporates a local search phase that takes the initially built protein conformation and attempts to optimise its energy further, using probabilistic long-range moves that are described in detail in the'methods' section. finally, the pheromone update procedure is based on two mechanisms: uniform pheromone evaporation is modelled by decreasing all pheromone levels by a constant factor ρ, and pheromone reinforcement is achieved by increasing the pheromone levels associated with the local folding motifs used in a fraction of the best conformations obtained during the preceding construction and local search phase. furthermore, to prevent search stagnation when all of the pheromone is accumulated on very few structural motifs, we introduce an additional renormalisation mechanism for the pheromone levels. different from our previous aco algorithms for the hp protein folding problem, our new algorithm, aco-hppfp- supports the 3d hp cubic lattice model in addition to the 2d hp square lattice model. furthermore, it uses a different iterative improvement strategy, a modified long-range move operator and a less restrictive termination criterion in its local search phase. aco-hppfp- was used in all aco experiments described in the following.  to compare aco-hppfp- with algorithms for the 2d and 3d hp protein folding problem described in the literature, we tested it on a number of standard benchmark instances as well as on two newly created data sets, one of which was obtained by randomly generating amino acid sequences with hydrophobicity value characteristic of globular proteins, while the other consists of biological sequences that were translated into hp strings using a standard hydrophobicity scale. results for standard benchmark instances the standard benchmark instances for 2d- and 3d-hp protein folding shown in table have been widely used in the literature. experiments on these standard benchmark instances were conducted by performing a number of independent runs for each problem instance. unless explicitly indicated otherwise, we used the following parameter settings for all experiments: α: = β: = ρ: = and θ: =. furthermore, all pheromone values were initialised to 1/ in 2d and to 1/ in 3d, and a population of ants was used, 50% of which were allowed to perform local search. the local search procedure was terminated when no improvement in energy had been obtained after between and scans through the protein sequence. we used an elitist pheromone updating scheme in which only the best 1% of all ants was allowed to perform pheromone updates. the probability of keeping the previous direction when feasible during the long-range mutation move was set to. these settings were determined in a series of experiments in which we studied the influence of different parameter settings and will be further discussed later. all experiments were performed on pcs with ghz pentium iv cpus, kb cache and mb ram, running redhat linux, and run-time was measured in terms of cpu time. most studies of ea and mc methods in the literature, including, report the number of valid conformations scanned during the search. this makes a performance comparison difficult, since run-time spent for backtracking and the checking of partial or infeasible conformations, which may vary substantially between different algorithms, is not accounted for. we therefore compared aco to the best-performing algorithm from the literature for which performance data in terms of cpu time is available – perm. we note that the most efficient perm variant for the hp protein folding problem uses an additional penalty of for h-p contacts. since this corresponds to an energy function different from that of the standard hp model underlying our aco algorithm as well as other algorithms developed in literature, we used the best performing variant of perm based on the standard energy function in our experiments. it may be noted that the chain growth process in perm can start from the n- or c-terminus of the given hp sequence, and in many cases, this results in substantial differences in the performance of the algorithm. to capture this effect, we always ran perm in both directions, and in addition to the respective average run-times, t and t we report the expected time for solving a given problem instance when performing both runs concurrently, texp = 2·- for all runs of perm, the following parameter settings were used: inverse temperature γ: = and q: =. the results obtained on standard 2d benchmark instances indicate that aco-hppfp- is competitive with the ea and mc methods described in the literature; it works very well on sequences of sizes up to amino acids and produces high quality suboptimal configurations for the longest sequences considered here. on average, aco requires less cpu time than perm for finding best known conformations for sequence s1-8; but perm performs better for sequences s1- and s1- as well as for the longer sequences of to residues. sequence s1- has a very symmetrical optimal state, which – as argued in – would be difficult to find for any chain growing algorithm. all algorithms from the literature which we are aware of have problems folding this sequence; aco-hppfp- on the other hand, is able to handle this instance quite well, since a number of ants folding from different starting points in conjunction with a local search procedure that involves large-scale mutations originating from different sequence positions can produce good partial folds for various parts of the chain. in comparison with other algorithms for the 2d hp protein folding problem considered here, aco-hppfp- generally shows very good performance on standard benchmark instances. in case of the 3d hp protein folding problem, the majority of algorithms for which we were able to find performance results in the literature use heuristics that are highly specialised for this problem. unlike hz, cg and ci, aco-hppfp- finds optimal solution qualities for all sequences. however, perm and chcc consistently outperform aco-hppfp- on these standard 3d hp benchmark instances, and cg reaches best known solution qualities substantially faster in many cases. we note that for sequence s2- and s2- perm's performance is greatly dependent on the folding direction. result for new biological and random data sets to thoroughly test the performance of aco-hppfp- we created two new data sets of random and biological sequences of length ≈ and ≈ amino acids. random sequences were generated based on the observation that most globular proteins have a fairly uniform amino acid profile, and the percent of hydrophobic residues of majority of globular proteins falls in the range of 40–50%. thus, the probability of generating character h at each position of a sequence was chosen to be, and in the remaining cases, we generated a p. for the biological test-sets, ten sequences were taken from the pdbselect data set with homology < 25% from the protein data bank in order to obtain a non-redundant representative set of proteins. these protein sequences were translated into hp strings using the hydrophobicity scale classification of rasmol, according to which the following amino acids were considered hydrophobic: ala, leu, val, ile, pro, phe, met, trp, gly and tyr. non-standard amino acid symbols, such as x and z, were skipped in this translation. figures and illustrate the performance of aco-hppfp- vs perm in terms of mean cpu time over runs per instance and algorithm; for practical reasons, each run was restricted to cpu hour on our reference machine, and the lowest energies obtained in these runs are not necessarily optimal. as can be seen from these results, in 2d, aco-hppfp- performs roughly comparably to perm: aco-hppfp- reaches the same energies as perm, but on some instances, particularly of length requires more run-time. in 3d, aco-hppfp- generally requires a comparable amount of run-time on sequences of length and outperforms perm on one random sequences of length but performs noticeably worse on sequences of length and in some cases does not reach the same energy. we also generated longer sequences of length 75; for these, aco-hppfp- failed to reach the minimal energy values obtained by perm in a number of cases. the run-times for both algorithms are reported in detail in additional file 1; we note that on some sequences, the performance of perm depends significantly on the direction of folding. interestingly, there is no significant difference in performance between the biological and random test-sets for either perm or aco-hppfp- in summary, the performance of aco-hppfp- is comparable with that of perm on biological and random sequences of length 30– but worse on longer sequences. this scaling effect is significantly more pronounced in 3d than in 2d. we note that neither aco-hppfp- nor perm were optimised for short sequences, but by using parameter settings different from the ones specified earlier, the performance of both algorithms can be significantly improved in this case. characteristic performance differences between aco and perm to further investigate the conditions under which aco performs well compared to perm, we visually examined native conformations found by both algorithms, paying special attention to conformations for which one of the two algorithms does not perform well. based on our observations, we hypothesised that perm usually performs well on sequences that have a structural nucleus in the native conformation at one of the ends of the sequence; on the other hand, it has trouble folding sequences whose native conformations have structural nuclei in the middle of the sequence. in comparison, aco is not significantly affected by the location of the structural nucleus in the sequence, since it uses construction from different folding points as well as the long-range mutation moves in local search, which can initiate refolding from arbitrary sequence positions. here, we use the term'structural nucleus' to refer to a predominantly locally folded part of the chain that can be relatively easily folded sequentially based on local sequence information. for most sequences considered in this study, we observed a single structural nucleus, which is not surprising, given their relatively short length; however, it is generally believed that longer sequences have multiple folding nuclei. the left side of figure shows an example of a relatively short biological sequence with a unique native hydrophobic core in the 2d hp model. this sequence has no structural nuclei at its ends; instead, the two ends interact with each other. aco-hppfp- outperforms perm by a factor of on this sequence in terms of cpu time: using a cut-off time of cpu hour per run, perm found the optimum with energy - in an average run-time of cpu seconds, while using the same cut-off time and machine, aco-hppfp- found the optimum in an average run-time of cpu seconds. we also designed two additional sequences, d- and d- of length and respectively, that have a unique native state in which both ends of the sequence interact with each other. sequence d- also has a structural nucleus near its c-terminus. when testing the performance of perm and aco-hppfp- on these sequences, we found that on d- aco-hppfp- requires a mean run-time of cpu seconds, compared to t = t = texp = cpu seconds for perm. when this sequence was reversed, perm started folding the sequence from the structural nucleus, and its mean run-time dropped to cpu second. a result similar to that for sequence b50- was obtained for sequence d- which has no structural nuclei at the ends, but a native state in which the ends interact with each other. here, aco-hppfp- was found to require a mean run-time of cpu seconds, compared to t = t = texp = cpu seconds for perm; as expected, in this case, reversing the folding order of the sequence did not cause a decrease in perm's run-time. we also analysed native conformations of sequences on which perm outperforms aco and observed that the end from which perm starts folding is relatively compact and forms a structural nucleus in the resulting conformation. an example of a conformation with the structural nucleus at the beginning of the sequence is shown in the right panel of figure for this biological sequence, perm finds an optimal conformation with an energy of - in t = t = texp = cpu seconds, while the average run-time for aco-hppfp- is cpu seconds. our aco algorithm generally performs worse than perm on sequences that have structural nuclei at the ends, because it tends to spend substantial amounts of time compacting local regions in the interior of the sequence, while perm folds more systematically from one end. these observations also hold in 3d, as seen from two random sequences folded in 3d. to further investigate our hypothesis, we studied differences between the distributions of native conformations found by aco-hppfp- and perm, respectively. for this purpose, we introduced the notion of relative h-h contact order, which captures arrangement of h residues in the core of the folded protein, and thus determines the topology of the conformation. relative h-h contact order is defined as follows: where l is the number of h-h contacts, n is the number of h residues in the sequence, and i and j are interacting h residues that are not neighbours in the chain. intuitively, coh-h specifies the average sequence separation between h-h residues in contact per h in the sequence. to further examine the topological differences between ensembles of native conformations found by the two algorithms, we also looked at the hydrophobic solvent accessible area, the number of h-h contacts, and the h-h contact order as a function of the length of the sequence prefix. in this analysis, we calculated the properties of interest mentioned above for the native conformations found in independent runs by aco-hppfp- and perm, and plotted the mean values of the respective quantities as functions of the sequence prefix length. as seen in figure aco-hppfp- is less greedy than perm, both in 2d and in 3d, and it tends to leave more lattice sites around h residues accessible for future contacts with other h residues that appear later in the chain. this is also reflected in the mean number of h-h contacts formed when folding prefixes of increasing length; aco-hppfp- tends to form fewer h-h contacts than perm for short and medium size prefixes. by examining the dependence of absolute h-h contact order on prefix length, we furthermore observed that different from perm, aco-hppfp- realises the bulk of its local h-h interactions in the middle of the given sequence. this further confirms that aco is capable of finding native conformations with structural folding nuclei that are not located at or near the end of a given protein sequence. the results illustrated in figures and are typical for all 2d and 3d hp instances we studied. discussion although conceptually rather simple, our aco algorithm is based on a number of distinct components and mechanisms. a natural question to ask is whether and to which extent each of these contributes to the performance reported in the previous section. a closely related questions concerns the impact of parameter settings on the performance of aco-hppfp-3; further details concerning parameters can be found in the'methods' section. to address these questions, we conducted several series of experiments. in this context, we primarily used three standard test sequences: sequence s1- of length and sequence s1- of length in 2d, as well as sequence s2- of length in 3d; these sequences were chosen because the cpu time required to find the best known solutions was sufficiently small to perform a large number of runs. following the methodology of hoos and stützle, we measured run-time distributions of our aco algorithm, which represent the probability distribution over the run-time required to reach a given solution quality; the solution qualities used here are the known optima or best known energies for the respective sequences. pheromone values and heuristic information two important components of any aco algorithm are the heuristic function, which indicates the desirability of using particular solution components during the construction phase, and the pheromone values, which represent information learned over multiple iterations of the algorithm. three parameters control the influence of the pheromone information versus heuristic information on the construction of candidate solutions: the relative weight of the pheromone information, α; the relative weight of the heuristic information, β; and the pheromone persistence, ρ. in the first experiment, we investigated the impact of pheromone and heuristic information, and their relative importance for the performance of our aco algorithm. as can be seen from the results shown in figure both the pheromone values and the heuristic information are important in 2d and 3d; when ignoring either of them, the algorithm performs worse, particularly for longer 2d sequences. the optimal settings for α and β for most problem instances seem to be around α = and β = as shown in figure it should be noted that in 3d, pheromone information appears to be less important than in 2d, which suggests that the specific solution components used in our algorithms are somewhat less meaningful in 3d. the goal of the next experiment was to further explore the role of experience accumulated over previous iterations in the form of pheromone values. to this end, we varied the pheromone persistence, ρ, while keeping other parameters constant. the results shown in figure show that in 2d, it is important to utilise past experience, but also to weaken its impact over time. at the same time, closer examination revealed that for ρ > attrition, i.e., the construction of inextensible partial conformations, is a major problem, which is a result of the accumulation of pheromone from multiple conformations. this is why the backtracking mechanism described in the'methods' section is extremely important for the performance of our algorithm in 2d. in 3d, for the previously stated reasons and because of the fact that the attrition problem is much less severe, the impact of the persistence parameter is generally smaller than in 2d. ant colony size and length of local search phase during the initial empirical evaluation of our algorithm, we observed that ant colony size and the duration of local search are correlated and significantly affect its performance. to further investigate this phenomenon, we conducted additional experiments in which we fixed the ant colony size and varied the maximal number of non-improving steps during local search, and vice versa. in this series of experiments, different colony sizes were considered, from a single ant up to a population of ants, and the number of non-improving steps in local search was varied from to the results, shown in figure indicate that there is an optimal colony size of about ants for both, 2d and 3d; aco-hppfp- is quite robust with respect to colony size, but performance decreases for very small or very large colony sizes. intuitively, this is the case because the use of a population of ants provides diversification to the search process, which enables it to explore different regions of the underlying search space; very small populations provide insufficient diversification, and the search stagnates easily, while for very large populations, the additional time required for running the search phases for each ant on the same sequential machine is not amortised any longer by increased efficiency of the overall search process. our results also indicate that the performance of aco-hppfp- is more sensitive to the number of non-improving steps than to ant colony size. the optimal value for the maximum number of non-improving steps tolerated before the local search phase terminates was found to be around for short 2d sequences and around for long 2d sequences; the latter value also appeared to be optimal for all 3d sequences considered here. this observation follows the intuition that more degrees of freedom, as present for longer sequences and in higher dimensions, require more time for local optimisation, since for any conformation, improving neighbours tend to be rarer and hence harder to find. selectivity and persistence of local search as described in the'methods' section, our aco algorithm uses selective local search, i.e., local search is only performed on a certain fraction of the lowest energy conformations. we observed that aco-hppfp- is fairly robust with respect to the fraction of conformations to which local search is applied; good performance was obtained for local search selectivity values between 5% and 50%, but performance was found to deteriorate when local search is performed by all ants. intuitively, similar to colony size, local search selectivity has an impact on search diversification. if too few ants perform local search, insufficient diversification is achieved, which typically leads to premature stagnation of the search process. on the other hand, if local search is performed by too many ants, the resulting substantial overhead in run-time can no longer be amortised by increased search efficiency. similarly to selective local search, pheromone update was performed only by a certain fraction of so-called'elitist ants' whose solution quality after the local search phase is highest within the population. as in the case of local search selectivity, aco-hppfp- shows robustly high performance for elitist fractions between 1% and 50%, but performance deteriorates markedly when all ants in the colony are allowed to update the pheromone matrix. in a final experiment, we studied the impact of the persistence of local search, i.e., of the probability of retaining previous relative directions during long-range mutation moves. as can be seen in figure good performance is generally obtained for values between and. both extreme cases, = which corresponds to an extremely h-contact greedy mutation operator, and = in which refolding always follows previous directions when feasible, result in a substantial decrease in performance. when = the decrease of performance in 3d is smaller than in 2d, because there is no severe attrition as in 2d, where greedy placement of h residues leads to early formation of very compact partial conformations, which often cannot be extended into valid complete conformations. the performance decrease for high values is due to insufficient ability of the chain to fold into a new conformation that accommodates well the local change in structure which triggered the refolding.  in this work, we have shown that ant colony optimisation can be applied in a rather straight-forward way to the 2d and 3d hp protein folding problems. even though our aco-hppfp- algorithm is based on very simple structure components and a simple subsidiary local search procedure, it performs fairly well compared to other algorithms and specialised heuristics on the benchmark instances considered here, particularly in 2d. the only non-specialised algorithm that typically performs better than our aco algorithm, both in 2d and 3d, is perm. we observed that, particularly in 3d, the run-time required by aco-hppfp- for finding minimum energy conformations scales worse with sequence length than perm. however, our results show that our aco algorithm finds a different ensemble of native conformations compared to perm, and has less difficulty folding sequences whose native states contain structural nuclei located in the middle rather than at the ends of a given sequence, as well as sequences with structures in which the ends interact. we found that two major components of aco-hppfp- – the pheromone values, which capture experience accumulated over multiple iterations of the search process and from multiple conformations, as well as the heuristic information that provides myopic guidance to the folding process – play a significant role for longer 2d sequences and, to a lesser extent, for 3d sequences, which suggests that in 3d, it may be preferable to associate pheromone values with more complex solution components. we also found that the subsidiary local search procedure is crucial for the performance of the algorithm; in particular, to ensure that high-quality conformations are obtained, it is very important to allow the local search procedure to run sufficiently long. in an earlier version of our algorithm, we used substantially more stringent termination criteria, which forced us to additionally use non-greedy local search in addition to the greedy local search procedure used here. the results presented in this study indicate that by using a new and simpler local search procedure, aco-hppfp- achieves better performance; this is probably due to the fact that the new local search procedure is based on a type of long-range move that leads to a larger effective search neighbourhood. we have shown that all components of our aco algorithms contribute to its performance. in particular, its performance is affected by the following components and parameters: pheromone values, termination criterion for local search, persistence of long-range moves, ant colony size, pheromone persistence, heuristic function, selectivity of local search, and selectivity of pheromone update. because of its ability to find more balanced ensembles of minimum energy conformations, our new aco algorithm can greatly facilitate investigations of the topology and location of structural nuclei, which we plan to undertake in future work. finally, while hp protein folding problems are of considerable interest because of their conceptual simplicity, ultimately, most applications of protein folding algorithms require the use of more realistic models of protein structure. since it does not rely on heuristics and properties that are specific to the hp model and yet performs very well on this restrictive, but not entirely unrealistic abstract model, we believe that relatively straight-forward extensions of our aco algorithm to more complex and realistic models of protein structure hold significant promise. 
various optimisation methods have been applied to formulations of the ab-initio folding problem that are based on reduced models of protein structure, including monte carlo methods, evolutionary algorithms, tabu search and hybrid approaches. the application of aco to this bioinformatics problem compares favourably with specialised, state-of-the-art methods for the 2d and 3d hp protein folding problem; our empirical results indicate that our rather simple aco algorithm scales worse with sequence length but usually finds a more diverse ensemble of native states. in our work, we have introduced an ant colony optimisation algorithm to address the non-deterministic polynomial-time hard combinatorial problem of predicting a protein's conformation from its amino acid sequence under a widely studied, conceptually simple model – the 2-dimensional and 3-dimensional hydrophobic-polar model. we present an improvement of our previous aco algorithm for the 2d hp model and its extension to the 3d hp model. we show that this new algorithm, dubbed aco-hppfp- performs better than previous state-of-the-art algorithms on sequences whose native conformations do not contain structural nuclei at the ends, but rather in the middle of the sequence, and that it generally finds a more diverse set of native conformations. therefore the development of aco algorithms for more complex and realistic models of protein structure holds significant promise.
 the protein folding problem is a fundamental problems in computational molecular biology and biochemical physics. various optimisation methods have been applied to formulations of the ab-initio folding problem that are based on reduced models of protein structure, including monte carlo methods, evolutionary algorithms, tabu search and hybrid approaches. in our work, we have introduced an ant colony optimisation algorithm to address the non-deterministic polynomial-time hard combinatorial problem of predicting a protein's conformation from its amino acid sequence under a widely studied, conceptually simple model – the 2-dimensional and 3-dimensional hydrophobic-polar model.  we present an improvement of our previous aco algorithm for the 2d hp model and its extension to the 3d hp model. we show that this new algorithm, dubbed aco-hppfp- performs better than previous state-of-the-art algorithms on sequences whose native conformations do not contain structural nuclei at the ends, but rather in the middle of the sequence, and that it generally finds a more diverse set of native conformations.  the application of aco to this bioinformatics problem compares favourably with specialised, state-of-the-art methods for the 2d and 3d hp protein folding problem; our empirical results indicate that our rather simple aco algorithm scales worse with sequence length but usually finds a more diverse ensemble of native states. therefore the development of aco algorithms for more complex and realistic models of protein structure holds significant promise. 