BACKGROUND
considering the close connection between the function of proteins and their three-dimensional  structure, there are many reasons for studying protein folding; these include the desire to predict protein function based on sequence data , to better understand a number of diseases that are directly caused by protein misfolding, aggregation and fibrillogenesis , and to design proteins with desired structure and function.
since experimental methods  for protein structure determination are highly labour intensive and require purification and, in the case of x-ray crystallography, crystallization of proteins, computational methods for predicting protein structure from sequence are very attractive.
the ab initio protein folding problem is the problem of predicting the tertiary structure  of a protein from its amino acid sequence by minimizing a given energy function.
even for simple models that discretize conformations on a lattice , this optimization problem is n
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbamrthrhal1wy0l2yhvtyaehbnfgdovwbhrxajfwnaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabawaaegaeaaakeaaimaacqwfnevtaaa@383b@p-hard  <cit> .
its difficulty stems from the fact that the space of possible conformations is vast, and the search landscapes induced by the given energy function are very complex.
one of the most prominent and successful approaches for solving this and many other n
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbamrthrhal1wy0l2yhvtyaehbnfgdovwbhrxajfwnaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabawaaegaeaaakeaaimaacqwfnevtaaa@383b@p-hard optimization problems is known as stochastic local search   <cit> .
applied to protein folding problems, sls methods attempt to find native states by iteratively performing small conformational modifications guided by the given energy function; randomized decisions are used to avoid getting trapped in local minima of the given energy landscape.
monte carlo algorithms, which are widely used in protein structure prediction, are a prominent special case of sls methods.
the performance of stochastic local search algorithms is critically dependent on the properties of the search landscape encountered, such as the number and distribution of local minima, the overall landscape ruggedness , and the basin structure.
therefore, search strategies that can extract important features of the landscape and adapt the search accordingly are among the most effective tools for solving optimization problems with complex search landscapes.
as evident from an analysis of the literature describing search methods for ab initio protein folding presented in the related work section, such adaptive search strategies have not been widely studied for this problem.
in this work, we introduce a novel adaptive sls method that is based on a system of bins for storing a diverse set of conformations  in memory.
the general idea behind our approach is to store promising conformations encountered during the search for later use in situations when search stagnation is detected.
these conformations are pooled into a number of bins according to energy and diversity criteria.
the storage and retrieval mechanisms used in this context adaptively control the behaviour of a subsidiary local search procedure, such as canonical monte carlo search, and are shown to greatly improve its performance.
the remainder of this paper is structured as follows: first, we provide background information and discuss related work on protein folding problems and algorithms.
next, we introduce the bin framework and describe a monte carlo algorithm that utilizes this bin framework adaptively.
we then compare the performance of our algorithm with that of other prominent methods from the literature, followed by a discussion of how the behavior and performance of our algorithm is influenced by its parameters.
finally, we explain how the bin framework introduced in this work relates to other search methods known from the literature, summarize our findings, draw some general conclusions, and indicate directions for future work.
in the "methods" section, we describe the face-centered cubic  lattice model and β-sheet energy potential used in our computational analysis and provides details of the experimental protocols used in the empirical analysis of our algorithm.
related work
to address the ab initio protein folding problem, the following three issues need to be considered:  the model used for the representation of protein structure ;  the energy potential function ; and  the method used for searching through the space of possible conformations .
in this section, we discuss the choice of protein representation and energy function made in this work; we also provide a brief overview of the best-performing search methods for ab initio protein folding known from the literature.
to facilitate ab initio protein structure prediction by means of more efficient methods for searching in the space of protein conformations, various reduced models of protein structure have been introduced by biochemists and physicists.
these reduced models fall into two major classes: lattice and off-lattice models.
the primary reason for choosing off-lattice models over lattice models is to obtain better geometrical accuracy.
despite the biases introduced by the lattice models, namely a somewhat restricted ability to accurately represent secondary structure and backbone conformation, lattice models still retain essential properties of the system  <cit>  and offer a number of computational advantages; these advantages include fast energy computation, easiness of testing self-avoidance and the ability to use pre-computed tables of moves, all of which help to compute search steps efficiently.
an important representative of lattice models is the face-centered cubic  lattice, which underlies the crystalline structure of most metals.
even though in the context of ab initio protein structure prediction, the simpler square and cubic lattices are the most widely studied models in the literature, the fcc lattice captures real protein conformations with higher accuracy   <cit>  while still being representationally rather simple .
it has also been shown that local packing of amino acids in real proteins closely fits a distorted fcc lattice  <cit> , and that the fcc model allows a reasonable description of secondary structure elements; furthermore, it can represent geometrically accurate hydrogen bonding  <cit> .
as a result, the fcc lattice is considered the best overall choice among the simpler regular lattice models  <cit> .
a detailed description of the fcc lattice is provided in the "methods" section.
as an energy function to be used in conjunction with the fcc lattice model we chose the β-sheet potential  <cit> .
this choice was motivated by the fact that there are no universally used energy functions for ab initio protein structure prediction; at the same time, the β-sheet potential has been used relatively widely in the literature for the empirical evaluation of the best-performing protein structure prediction methods discussed later in this section.
this enables us to compare our new approach against a relatively wide range of other conformation search methods known from the literature.
furthermore, this β-sheet potential exhibits characteristics of more complicated energy functions used for off-lattice models  <cit>  .
finally, the problem of folding of β-sheet proteins is particularly important, since the accuracy of protein structure prediction methods for β-sheet proteins is the lowest among all structural classes of proteins  <cit> .
the β-sheet potential used in this work is described in detail in the "methods" section.
there are a number of search methods applicable to the protein folding problem that can be used in conjunction with reduced complexity models and simplified potentials to perform a broad search through low-resolution structures.
the most widely used methods include metropolis monte carlo  search  <cit> , genetic algorithms  <cit>  and generalized ensemble methods  <cit> , which include the currently best-performing algorithms for ab initio protein structure prediction.
this last class of algorithms is based on the observation that canonical monte carlo methods sample conformations according to boltzmann probabilities.
for typical distributions of states  over energy levels this means that very high and, more importantly, very low energy conformations are rarely sampled.
generalized ensemble monte carlo methods attempt to overcome this problem by striving to perform a random walk in energy space by computing the density of states, by sampling expanded range of temperatures or by computing other physical quantities affecting transitions between the states during search.
currently, the best-performing generalized ensemble method for ab initio protein structure prediction is replica exchange monte carlo search   <cit> , also known as the multiple markov chain method or parallel tempering  <cit> .
in remc, a number of non-interacting copies  of the given protein sequence are folded independently and at different temperature settings of the underlying canonical monte carlo search.
every few steps, pairs of replicas are exchanged  with a probability that depends on the energies of the respective conformations .
while other generalized ensemble methods, such as multicanonical  monte carlo  search  <cit> , maintain only one conformation at any given time, the number of replicas required in remc increases as the square root of the number of degrees of freedom   <cit> .
improvements of remc introduced in the literature include hybrid approaches between remc  and muca, or simulated tempering production runs  <cit> .
the parallel-hat tempering  monte carlo method utilizes an additional weight factor based on the histogram of energies sampled by each temperature replica  <cit>  to achieve an exponential increase in the acceptance probabilities for high- and low-energy conformations, which increases the efficiency of the search process by allowing it to effectively overcome higher energy barriers and to explore a wider range of conformations for each replica.
the following algorithms have been implemented and empirically evaluated for the fcc lattice model with the β-sheet energy function considered in this work: canonical metropolis monte carlo search  <cit> , muca  <cit> , remc  <cit>  and phat  <cit> .
of these, phat is the best-performing conformation search method for the ab initio prediction of protein structures on the fcc lattice using the β-sheet potential.
bin framework monte carlo search
the key idea behind our adaptive bin framework is to improve the effectiveness of a given search process, such as canonical monte carlo search, by making it adaptive and augmenting it with a mechanism for storing and retrieving promising conformations.
this is achieved by using a series of bins each of which holds a set of conformations within a certain energy range and an adaptive strategy for restarting a given search process with a conformation retrieved from these bins when the search stagnates.
by varying the search strategy according to a priori defined transition probabilities , this approach leads to an algorithm that sacrifices an exact relationship with the canonical ensemble for search efficiency.
this method effectively reduces the slow convergence, or quasi-ergodicity, in rugged energy landscapes; it is therefore very useful when the main interest is in finding global minima, rather than in obtaining other physical properties from canonical ensembles.
conformations are added to the bins in a way that is aimed at maintaining a diverse set of low-energy conformations.
to achieve this we define energy and diversity thresholds for each bin, which are dynamically modified during the search process .
with each bin i the following properties are associated:
• the capacity of the bin, capi, i.e., the maximal number of conformations that can be stored in the bin at any given time.
• the current number of conformations stored in the bin, numi.
these conformations themselves are stored in a list that is sorted according to energy, to facilitate efficient retrieval of low-energy conformations.
• the width of the bin's maximal energy range, Δei.
• the bin's energy threshold, ei+
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacqwgfbqrdaqhaawcbagaemyaakgabagaey4kascaaaaa@3029@.
this is the highest energy that a conformation can reach and still be placed into bin i if the respective diversity threshold  is satisfied.
• the diversity threshold, which determines how different a conformation has to be from other conformations already stored at the same energy level in order for the new conformation to be accepted into the bin.
the pairwise diversity of conformations is measured using a distance measure that depends on the protein model under consideration.
here, we use the normalized average hamming distance, hd, between the β-sheet energy sequence of a newly considered conformation c and all β-sheet energy sequences for the set c' of all conformations with the same energy that are already in the bin, see methods section for details.
furthermore, the overall bin framework has the following parameters:
• the total number of bins, numbins.
• the energy range of interest, Δe.
together with the current estimate of the ground state energy, e^
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacuwgfbqrgaqcaaaa@2dcf@, which is modified throughout the search to always represent the lowest energy encountered so far, Δe controls the energy interval into which conformations must fall in order to be accepted into any bin.
this range represents the estimate of the maximal barrier height that needs to be surmounted to reach lower energy conformations.
• the temperature tbin, which controls the retrieval of conformations from bins.
the general bin framework search mechanism is outlined in figure  <dig>  procedure initalizebins is used to set all bin parameters to their initial values.
bins are numbered  <dig> ... numbins, and for every bin i, Δei and ei+
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacqwgfbqrdaqhaawcbagaemyaakgabagaey4kascaaaaa@3029@ are always assigned such that ei+<ei−1+−Δei−1+1
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacqwgfbqrdaqhaawcbagaemyaakgabagaey4kascaaogaeyipawjaemyrau0aa0baasqaaiabdmgapjabgkhitiabigdaxaqaaiabgucaraaakiabgkhitiabfs5aejabdweafnaabaaaleaacqwgpbqacqghsislcqaixaqmaeqaaogaey4kasiaegymaedaaa@3f41@, i.e., the energy intervals [ei+,ei+−Δei)
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacqggbbwwcqwgfbqrdaqhaawcbagaemyaakgabagaey4kascaaogaeiilawiaemyrau0aa0baasqaaiabdmgapbqaaiabgucaraaakiabgkhitiabfs5aejabdweafnaabaaaleaacqwgpbqaaeqaaogaeiykakcaaa@3ba9@ for different bins never overlap.
furthermore, the energy bounds are always assigned such that ei+>e2+>⋯>enumbins+
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacqwgfbqrdaqhaawcbagaemyaakgabagaey4kascaaogaeyopa4jaemyrau0aa0baasqaaiabikdayaqaaiabgucaraaakiabg6da+iabl+uimjabg6da+iabdweafnaadaaaleaacqwgubgbcqwg1bqdcqwgtbqbcqwgcbgqcqwgpbqacqwgubgbcqwgzbwcaeaacqghrawkaaaaaa@43f0@, i.e., bin  <dig> always has the highest energy interval, while bin numbins stores the lowest energy conformations.
procedure subsearchstep performs one step of a subsidiary search procedure  on a given conformation c and returns the resulting conformation c'.
this step involves a single proposal of the move from the given move set and its subsequent acceptance or rejection.
the two procedures considerstoringinbin and retrievefrombin control the storage of conformations in the bin system and the retrieval of previously stored conformations.
note that conformations will only be stored in a bin if they satisfy the corresponding energy and diversity thresholds.
storing a conformation may lead to adjustments of the energy thresholds for the corresponding bin or addition of a new bin .
finally, a stagnation criterion is used to decide when to retrieve a conformation from the bin system in order to overcome search stagnation, and a termination condition is used to determine when the search process should terminate.
in the following, we will describe the specific instantiation of this framework on which the remainder of our study is focused: the binmc algorithm.
in binmc, for simplicity all bin capacities capi are set to the same value, and this value is kept constant during the search.
the same holds for the energy ranges Δei.
finally, for simplicity we also keep the number of bins, numbins, constant during the run of the algorithm.
this number is determined by the interval of energies of interest and the energy window width used:
numbins = ⌈Δe/Δei⌉.
at the beginning of the search process, the energy threshold for each bin i is set to ei+
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacqwgfbqrdaqhaawcbagaemyaakgabagaey4kascaaaaa@3029@ := -·Δei.
initially, the energy intervals of all bins form a partition of the interval [ <dig>  numbins·Δei), note that this interval is larger than or equal to the desired interval [ <dig>  Δe); it is larger if Δe does not divide evenly by Δei.
it should be noted that  <dig> is the highest energy possible under the model chosen in this work and all the energies are integer values; in the general case energy thresholds can be adjusted initially to store the highest energy conformations under the protein model considered.
the bin energy bounds are adjusted during the search, as will be explained later.
the diversity thresholds for the bins, hdi, are determined based on the following formula:
hdi = hdmin + ·/,
where hdmin and hdmax are parameters of the algorithm that determine the diversity threshold of the lowest and highest energy bins, respectively.
this choice is based on the experimental observation that fewer protein conformations exist for lower energies, and therefore, the set of of conformations to be found at low energy levels can be expected to be less diverse.
figure  <dig> depicts some of the properties of bins and conformations in a bin and the overall relationship of conformations stored in the framework to the energy landscape.
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacuwgfbqrgaqcaaaa@2dcf@ is the best solution quality found so far and serves as an estimate of the ground state energy, Δe is the energy range of interest, and conformations within this range are binned.
each bin i has energy threshold ei+
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacqwgfbqrdaqhaawcbagaemyaakgabagaey4kascaaaaa@3029@, diversity threshold hdi, and energy window Δei.
binmc uses a standard canonical monte carlo search procedure running at a constant inverse temperature βmc := 1/ , that controls the probability with which worsening search steps are accepted.
our canonical monte carlo procedure for the fcc lattice is based on the same search neighbourhood  as used by gront et al.
<cit>  and by zhang and skolnick  <cit> .
in each search step, either a double-bond move or a chain-end move is attempted.
a double-bond move involves the modification of two successive bond angles, whose position in the chain is chosen uniformly at random.
similarly, in a chain-end move, the location of the first or the last residue is changed.
for efficiency and speed, double-bond moves are pre-computed in a table, as done by gront et al.
<cit>  and by zhang & skolnick  <cit> .
the search proceeds in phases, each of which starts with two attempts at chain-end moves  followed by n/ <dig> successive attempts at double-bond moves  any number of which may be accepted.
procedure subsearchstep in figure  <dig> performs a single step of this simple subsidiary search process by attempting one move, starting from conformation c and resulting in conformation c' ; the attempted moves are chosen such that the previously described phasing of chain-end and double-bond moves is ensured.
after a new conformation has been accepted by the subsidiary mc procedure, it is considered for placement into a bin.
if the new conformation c' has lower energy then any other conformation encountered so far, i.e., if e <e^
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacuwgfbqrgaqcaaaa@2dcf@, it is always accepted into the bin framework and the current estimate of the ground state, e^
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacuwgfbqrgaqcaaaa@2dcf@, is updated.
if e falls outside the energy range currently represented by the bin framework, before accepting the new conformation, a new bin  is created and the first bin storing conformations with high energies  is deleted as follows: : we add a new bin numbins +  <dig> and delete all conformations from bin  <dig> along with bin  <dig> itself.
we also shift bin numbers by - <dig>  such that bin  <dig> becomes bin  <dig> and bin numbins +  <dig> becomes bin numbins.
the energy threshold enumbins+
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacqwgfbqrdaqhaawcbagaemoba4maemydaunaemyba0maemoqaikaemyaakmaemoba4maem4camhabagaey4kascaaaaa@3845@ for the newly added bin is set to enumbins−1+−Δenumbins−1+1
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacqwgfbqrdaqhaawcbagaemoba4maemydaunaemyba0maemoqaikaemyaakmaemoba4maem4camnaeyoei0iaegymaedabagaey4kascaaogaeyoei0iaeuildqkaemyrau0aasbaasqaaiabd6gaujabdwha1jabd2gatjabdkeacjabdmgapjabd6gaujabdohazjabgkhitiabigdaxaqabagccqghrawkcqaixaqmaaa@4aee@.
the diversity thresholds are not shifted with the bins, such that hdmax and hdmin remain associated with the first and the last bin, respectively.
if conformation e falls within the energy interval of a bin i that is not yet filled to capacity , and c' satisfies the diversity criterion for that bin – i.e., the hamming distance between the conformation c' and other conformations c" with the same energy e should be larger or equal to hdi  – c' is added to that bin, and numi is incremented by one.
finally, if e falls within the energy interval of a bin i that is already filled to capacity  and it satisfies the diversity criterion for that bin, c' is added to the content of bin i and the highest energy conformation is removed.
at the same time, e^
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacuwgfbqrgaqcaaaa@2dcf@ is set to the energy of the conformation that is currently the highest in the bin; as a consequence, conformations with energy above the updated e^
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacuwgfbqrgaqcaaaa@2dcf@ will not be accepted into bin i in the future, and therefore, the energy ranges of bins i -  <dig> and i are now may no longer be adjacent.
the stagnation detection mechanism used in binmc is quite simple: the search is considered to be stagnated when no improvement on the lowest energy has been achieved for noimprretrieve search steps, where noimprretrieve is a parameter of the algorithm.
to retrieve a conformation from the bin system, binmc uses a two-phase procedure that first selects a bin and then chooses one of the conformations stored in that bin.
in the first phase, the probability of selecting a bin i depends on the difference between its upper energy threshold e^
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacuwgfbqrgaqcaaaa@2dcf@ and the best energy reached so far, and is proportional to:
e−βbin
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacqwglbqzdaahaawcbeqaaiabgkhitggaciab=j7ainaabaaameaacqwgibgycqwgpbqacqwgubgbaeqaasgaeiikagiaemyrau0aa0baawqaaiabdmgapbqaaiabgucaraaaliabgkhitiqbdweafzaajagaeiykakcaaaaa@3c51@
where βbin = 1/, kb denotes the boltzmann constant, and tbin is binmc's temperature parameter.
in the second phase, the probability of choosing a conformation c from that bin is analogously proportional to:
e−βbin⋅−e^)
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacqwglbqzdaahaawcbeqaaiabgkhitggaciab=j7ainaabaaameaacqwgibgycqwgpbqacqwgubgbaeqaasgaeyyxictaeiikagiaemyraukaeiikagiaem4yammaeiykakiaeyoei0iafmyraukbakaacqggpaqkaaaaaa@3f26@
in general, conformations could be chosen with or without replacement; here we limited ourselves to choosing conformation with replacement, since the same conformation can yield a different fold each time it is picked.
as in the stochastic tunneling approach  <cit> , to lessen exponential decay of the probability function we used boltzmann-based modified weights proportional to e−β
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacqwglbqzdaahaawcbeqaaiabgkhitggaciab=j7aijabcicaoiabdweafjabgkhitiqbdweafzaajagaeiykakcaaaaa@3596@.
this weighting preserves the location of all minima, but maps the entire energy space from e^
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacuwgfbqrgaqcaaaa@2dcf@ to the maximum energy  <dig> onto the interval  <cit> .
the dynamic process following the boltzmann distribution can therefore pass through energy barriers of an arbitrary height.
overall, this retrieval procedure ensures that lower energy conformations are selected with higher probability, which is in accordance with the belief that the energy landscapes of real proteins are funneled.
the search is terminated when the target energy level has been reached or when a user-specified number of steps has been executed.
RESULTS
in this section, we present empirical performance results for binmc as compared to the best-performing algorithms known from the literature.
mc, remc and phat have been tested by their original authors on the homopolymers of length  <dig> and  <dig>  but only results for the homopolymer of length  <dig> have been published  <cit> .
for the protein of length  <dig>  gront et al.
believed the lowest energy they had reached, - <dig>  to correspond to a ground state conformation; however, zhang and skolnick later reported a conformation with energy - <dig> for this system  <cit> .
analogous with the results of gront et al.
for mc and remc  <cit>  and of zhang and skolnick for phat  <cit> , in table  <dig> we provide results averaged over  <dig> independent runs of each algorithm.
it should be noted that several details were not evident from the published descriptions of these algorithms.
from personal communication with d. gront, we learned that their mc procedure was run with temperatures from  <dig>  to  <dig>  .
since we could not determine the exact annealing schedule used in their study, we chose a constant temperature of  <dig>  for our mc procedure.
therefore, the results for the mcsa algorithm of gront et al.
may not be exactly comparable with that of our implementation of pure mc.
since the number of iterations performed within a given amount of time varies significantly based on implementation details, we used the average cpu times reported by gront et al.
<cit>  and by zhang and skolnick  <cit>  as the cut-off time for our algorithms.
comparison of the energy levels reached for the homopolymer of length n =  <dig> by monte carlo simulated annealing   <cit> , the replica exchange monte carlo  algorithm with a linear set of temperatures  <cit>  and the parallel-hat tempering algorithm   <cit>  with our implementation of monte carlo , remc and phat, as well as with our new bin framework monte carlo  algorithm.
the run-time reported for mcsa and remc  <cit>  has been conservatively adjusted to our  <dig>  ghz reference machine .
the same was done for the run-times for phat .
as seen from table  <dig>  our implementations of mc and remc show comparable performance to that of mcsa and remc by gront et al.
<cit> .
however, our implementation of phat did not reach the performance reported in the literature  <cit> .
therefore, we contacted y. zhang to check unpublished details of their algorithm, but unfortunately, those details along with the precise information on the best conformation reported in their paper  were no longer available due to data loss.
our novel binmc algorithm performs better than mc and remc, and than our implementation of phat.
we used the following set of parameters for the bin framework for the homopolymer of length 64: Δe =  <dig> , Δei =  <dig> , tmc =  <dig>  , tbin =  <dig>  , bincapacity =  <dig>  hdmax =  <dig> , hdmin =  <dig> , noimprretrieve =  <dig>  <dig>  <dig> steps.
these settings were determined in a series of experiments in which we studied the influence of different parameter settings; these will be further discussed in discussion section.
the lowest energy level for the homopolymer of length  <dig> reached by our binmc algorithm is -391; this is lower than the energy of any conformation previously reported in the literature.
conformations with energy - <dig> were found in  <dig> out of  <dig> runs, each with a  <dig> cpu hour cut-off on our reference machine, after  <dig> and  <dig> cpu hours, respectively.
one of the two resulting conformations is shown in figure  <dig>  the other is its exact mirror image.
conformations with energies of - <dig> and - <dig> , were found multiple times by binmc within a cpu time cut-off of  <dig> hours on our reference machines.
to extend our comparison of the re-implemented methods from the literature  with binmc, we tested these methods on instances of length  <dig>   <dig> and  <dig>  again, we performed  <dig> independent runs of each algorithm on every problem instance, measuring the mean as well as the standard deviation of the energy levels reached after a run-time of  <dig> cpu hour.
for binmc when applied to the homopolymers of length  <dig> and  <dig>  we used the following parameter settings: Δe =  <dig> , Δei =  <dig> , tmc =  <dig>  , tbin =  <dig>  , bincapacity =  <dig>  hdmax =  <dig> , hdmin =  <dig>  and noimprretrieve =  <dig>  <dig> steps, whereas on the homopolymer of length  <dig>  we set the parameters to: Δe =  <dig> , Δei =  <dig> , tmc =  <dig>  , tbin =  <dig>  , bincapacity =  <dig>  hdmax =  <dig> , hdmin =  <dig>  and noimprretrieve =  <dig>  <dig>  <dig> steps.
as can be seen from our results presented in table  <dig>  all methods find what appears to be the lowest energy  for the homopolymer of length  <dig> in less than  <dig> cpu second on our reference machine.
for the homopolymer of length  <dig>  we are starting to see differences among the algorithms: binmc slightly outperforms all other algorithms in terms of cpu time required for reaching an energy of - <dig>  which we believe to be the global minimum for this problem instance.
mc is the next best method in terms of performance, followed by phat and remc.
the performance results for remc and phat are worse than for mc because this homopolymer is too short for the additional time invested in exchanges between replicas to be amortized.
for the homopolymer of length  <dig>  binmc outperforms the other algorithms by obtaining lower average energy , followed by phat, remc and finally mc.
we show minimum energy conformations for the polymers of length  <dig>   <dig>  and  <dig> in figure  <dig>  these solutions appear to be unique in terms of short-range and long-range energy values, since all of the conformations found by any of the algorithms we ran show the same short- vs long-range energy interplay.
comparison of the average energy level obtained and the average time required for the homopolymers of lengths n =  <dig>   <dig>   <dig> for the re-implemented mc, remc, phat, and binmc.
the time cut-off used was  <dig> cpu hour on our  <dig>  ghz reference machine, and all statistics were calculated from  <dig> independent runs.
the temperature sets used for our implementations of mc, remc and are the same as in table  <dig>  the p-values reported in the last column were determined using the mann-whitney u test to test the null hypothesis that the mean run-time  and the mean energies reached by the respective algorithm vs binmc , respectively, are identical  <cit> ; p-values marked with an asterisk  correspond to cases in which the null hypothesis is rejected at a standard significance level of  <dig> , and therefore indicate statistically significant performance differences.
additionally, to see to which extent the results reported in tables  <dig> and  <dig> could be further improved, we carried out  <dig> long independent runs for the homopolymers of length  <dig> and  <dig>  using a cut-off time of  <dig> cpu hours on our reference machine.
the results of this experiment are shown in table 3; clearly, binmc outperforms our implementation of the state-of-the-art remc and phat algorithms as well as the canonical mc algorithm in terms of the solution quality reached in these long runs, with remc ranking second, followed by phat and mc.
comparison of the energy levels reached for the homopolymers of length  <dig> and  <dig> by our implementations of mc, remc , phat, and the new binmc algorithm in  <dig> independent runs of  <dig> cpu hours each on our  <dig>  ghz reference machine.
the p-values reported in the last column were determined using the mann-whitney u test to test the null hypothesis that the mean energies reached by the respective algorithm and binmc  are identical  <cit> ; p-values marked with an asterisk  correspond to cases in which the null hypothesis is rejected at a standard significance level of  <dig> , and therefore indicate statistically significant performance differences.
next, we conducted a more thorough performance comparison of the algorithms based on run-time distributions  measured on the homopolymers of length  <dig> and  <dig>  the goal of this analysis was to analyze the variability between independent runs on the same problem instance, which is known to reflect the parallelization efficiency of an algorithm and can also reveal detrimental stagnation behavior  <cit> .
in order to be able to perform  <dig> independent runs of each algorithm on both sequences within a reasonable overall computation time using our reference machine, we used sub-optimal energy levels of - <dig> and - <dig> for n =  <dig> and n =  <dig>  respectively.
the resulting empirical rtds are shown in figure  <dig> in the form of the respective cumulative distribution functions.
for the homopolymer of length  <dig>  binmc and mc outperform remc and phat in terms of the time required to reach the sub-optimal solution quality of - <dig>  for the homopolymer of length  <dig> binmc performs best in terms of the time required to reach the sub-optimal solution quality of - <dig>  followed by mc, remc and phat.
as can be seen from the graphs in figure  <dig>  the rtds of all four algorithms closely resemble exponential distributions.
this indicates that for reaching the energy levels considered here, none of the algorithms stagnates and all of them can be parallelized efficiently by concurrently executing independent runs  <cit> .
it may come as a surprise that mc performs better than remc and phat.
however, it is important to note that the rtds reported in figure  <dig> are for sub-optimal qualities only.
since mc at a low temperature is "greedier" and does not run multiple chains at different temperatures nor attempts exchanges between them, it gets to sub-optimal energies faster.
after reaching them, however, it stagnates; this is reflected in the observation that solution quality does not improve when running mc for a long time  for the homopolymers of length  <dig> and  <dig>  as shown in table  <dig>  we also investigated the scaling behaviour of remc and binmc with homopolymer length.
we measured the median run-time to reach the global minimum over  <dig> runs for sequences of length  <dig>   <dig>  and  <dig> amino acids .
the resulting sets of three data points for each algorithm were each fitted with a line in a semi-logarithmic plot .
based on this analysis, the median run-time required for finding  conformations appears to scale as  <dig> ·n- <dig>  for remc and as  <dig> ·n- <dig>  for binmc.
finally, we inspected the distribution of energies sampled by each method for the long homopolymer of length  <dig>  based on approximately  <dig> ×  <dig> conformations each.
as seen in figure  <dig>  remc and phat show typical energy distributions for each replica, as reported by zhang and skolnick  <cit> ; as expected, in the case of phat, the probabilities of encountering low and high energies are elevated.
interesting differences are observed when examining the distribution of energies visited by mc and binmc : while our new algorithm samples energies according to the boltzmann probability density function, the distributions are shifted towards lower energy values, reflecting the fact that binmc tends to reach lower-energy conformations more efficiently.
discussion
similar to the model-based search  method  <cit>  introduced for off-lattice fragment insertion as used in the rosetta  <cit>  algorithm, our bin framework stores promising candidate solutions for future reuse.
however, unlike mbs, we developed and tested an adaptive diversification mechanism that varies based on the energy level considered and takes into account how different a conformation is from other conformations with the same energy.
additionally, the energy level of interest, which determines the highest energy conformations stored in the bin framework are allowed to have, and individual hamming distance criteria used for each bin, are adapted according to the current estimate of the ground state energy.
mbs does not have a mechanism comparable to our diversity criteria between stored conformations.
in mbs, a number of elite conformations are stored, whose quality is measured using a score determined from their energies and the radius of the local minimum represented by them.
another important distinction between binmc and mbs is that in binmc, the model  is updated during the search and influences the choice of a new candidate solution every noimprretrieve steps, when search stagnation is detected.
on the other hand, in mbs for the discrete off-lattice model with structural fragment insertion as described by brunette and brock  <cit> , the choice of a new candidate solution is influenced at every step by the pool of conformations stored.
thus, mbs exploration of the search space is only dependent on the conformations stored  <cit> .
therefore, regions that are pruned based on the model are eliminated and not explored any further.
in contrast, the bin framework provides only a subsidiary mechanism for generating candidate solutions when search stagnation is detected, and does not completely eliminate unexplored regions of the search space.
this is achieved by running a non-model-based search  for a sufficiently long time to allow it to explore other regions of the search space.
the bin framework sorts conformations into bins representing different energy levels to make sure that the model contains as many energy levels of interest as possible while still reducing the search space.
this aspect of the search is conceptually related to histogram-based sampling and search methods such as multicannonical algorithm   <cit>  and energy landscape paving  method  <cit> .
it should be noted, however, that our bin framework is a non-parametric model of the search space that consists of a diverse set of promising candidate conformations stored in the bins.
muca, on the other hand, and to some degree elp, are based on a parametric model of sampling all energy levels with the same probability without emphasis on low energies.
in addition, our bin framework uses hamming distance criteria that are based on the energy level of each bin to ensure that the respective sets of conformations stored are diverse and capture the overall funnel-like structure of the landscape.
up to this point, we have focused on comparing binmc with existing algorithms.
we now turn our attention to the question how the performance of the binmc algorithm depends on its parameters and the algorithm components controlled by them, and to the determination of good settings for these parameters.
we conducted this investigation for the homopolymer of length  <dig>  since reaching its best known energy level of - <dig> is challenging, but not too computationally expensive to preclude performing multiple successful runs for a large number of parameter settings.
for each parameter configuration, we conducted  <dig> independent runs on our reference machine and recorded the time required in each of these to reach an energy of -161; from these runs, we then determined the average cpu time required to reach this target energy.
to study the influence of the different parameters on algorithm performance, we varied one  of them at a time, while keeping all other parameter values fixed.
unless indicated otherwise, the parameters kept fixed in these experiments were set to the following values: Δe =  <dig> , Δei =  <dig> , tmc =  <dig>  , tbin =  <dig>  , bincapacity =  <dig>  hdmax =  <dig> , hdmin =  <dig> , noimprretrieve =  <dig>  <dig> steps.
here, we summarize the results of this study; details are provided in the supplementary material, see additional file  <dig>  the impact of the parameters on the performance of binmc can be ranked as follows :
<dig>  the number of non-improving steps  that are performed before reaching into a bin and replacing the current conformation in the monte carlo run, noimprretrieve ;
<dig>  the ratio between the width of the energy of interest considered for binning, Δe, and the bin temperature, tbin ;
<dig>  the diversity criteria used during binning high- and low-energy conformations , values of hdmin =  <dig>  and hdmax =  <dig>  guarantee that we are selective enough when storing promising conformations at low and high energy levels correspondingly and result in the best performance;
<dig>  the width of the energy window considered by each bin ; and
<dig>  the capacity of bins, capi .
furthermore, we made the following observations regarding parameter settings of our algorithm for the longer homopolymer of length 64:
<dig>  a higher value of noimprretrieve should be used , which indicates that longer search times are required to effectively explore the neighbourhood of the current conformation before reaching into the bin framework and replacing it with another promising conformation;
<dig>  Δe should be increased, which is consistent with the common belief that the barrier heights for longer homopolymers are higher, and tbin should be adjusted such that the ratio Δe/tbin remains the same as for length 32;
<dig>  Δei should be increased to ei =  <dig>  which suggests that a coarser search space discretization may be beneficial for longer homopolymers; note that the combination of increases in Δe and Δei results in only a slight increase in the total number of bins, numbins;
<dig>  the same values for hdmin, hdmax and capi can be used as in the case of length  <dig>
finally, our empirical results presented in additional file  <dig> show that the binmc algorithm performs substantially better than the simple restart strategy and than the pure monte carlo on which it is based.
we also determined that all components of our algorithm are important for its efficiency, see additional file  <dig>  for example, the average time required for finding purportedly optimal conformations increases significantly  when increasing noimprretrieve until bin framework retrieval is performed very infrequently, when decreasing Δe or capi or when increasing the diversity thresholds hdmin and hdmax, resulting in very few conformations being stored, or when reducing the number of bins .
CONCLUSIONS
the bin framework introduced in this work is a general approach that can be used to augment existing conformation search methods in order to increase their ability to focus on promising regions of the search phase  and to effectively overcome stagnation in regions of sub-optimal conformations .
as shown by our computational experiments, even very simple instantiations of the general bin framework can result in highly effective search algorithms.
in particular, our novel bin framework monte carlo algorithm  surpasses replica exchange monte carlo search and its heuristic variant, parallel-hat tempering, in its ability to find  minimum energy conformations for β-sheet homopolymers on the fcc lattice.
furthermore, using our new algorithm we have improved the best known solution for the homopolymer of length  <dig> from - <dig> to - <dig>
in future work, we plan to consider more advanced adaptive bin framework strategies that control search diversification and intensification reactively during the search, based on observed features of the search landscape.
additionally, we are planning to generalize our bin framework to work on partial as well as complete conformations, producing an efficient generalized framework that combines two distinct search strategies.
finally, we would like to extend our bin framework to address other models of protein structure, such as the fcc model with a more complex energy function or other discrete and continuous off-lattice models.
given the results for β-sheet homopolymers on the fcc lattice achieved in this work, we believe that further investigation of our adaptive bin framework and its application to other protein structure prediction problems holds much promise.

 considering the close connection between the function of proteins and their three-dimensional structure, there are many reasons for studying protein folding; these include the desire to predict protein function based on sequence data, to better understand a number of diseases that are directly caused by protein misfolding, aggregation and fibrillogenesis, and to design proteins with desired structure and function. since experimental methods for protein structure determination are highly labour intensive and require purification and, in the case of x-ray crystallography, crystallization of proteins, computational methods for predicting protein structure from sequence are very attractive. the ab initio protein folding problem is the problem of predicting the tertiary structure of a protein from its amino acid sequence by minimizing a given energy function. even for simple models that discretize conformations on a lattice, this optimization problem is n mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbamrthrhal1wy0l2yhvtyaehbnfgdovwbhrxajfwnaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabawaaegaeaaakeaaimaacqwfnevtaaa@383b@p-hard. its difficulty stems from the fact that the space of possible conformations is vast, and the search landscapes induced by the given energy function are very complex. one of the most prominent and successful approaches for solving this and many other n mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbamrthrhal1wy0l2yhvtyaehbnfgdovwbhrxajfwnaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabawaaegaeaaakeaaimaacqwfnevtaaa@383b@p-hard optimization problems is known as stochastic local search. applied to protein folding problems, sls methods attempt to find native states by iteratively performing small conformational modifications guided by the given energy function; randomized decisions are used to avoid getting trapped in local minima of the given energy landscape. monte carlo algorithms, which are widely used in protein structure prediction, are a prominent special case of sls methods. the performance of stochastic local search algorithms is critically dependent on the properties of the search landscape encountered, such as the number and distribution of local minima, the overall landscape ruggedness, and the basin structure. therefore, search strategies that can extract important features of the landscape and adapt the search accordingly are among the most effective tools for solving optimization problems with complex search landscapes. as evident from an analysis of the literature describing search methods for ab initio protein folding presented in the related work section, such adaptive search strategies have not been widely studied for this problem. in this work, we introduce a novel adaptive sls method that is based on a system of bins for storing a diverse set of conformations in memory. the general idea behind our approach is to store promising conformations encountered during the search for later use in situations when search stagnation is detected. these conformations are pooled into a number of bins according to energy and diversity criteria. the storage and retrieval mechanisms used in this context adaptively control the behaviour of a subsidiary local search procedure, such as canonical monte carlo search, and are shown to greatly improve its performance. the remainder of this paper is structured as follows: first, we provide background information and discuss related work on protein folding problems and algorithms. next, we introduce the bin framework and describe a monte carlo algorithm that utilizes this bin framework adaptively. we then compare the performance of our algorithm with that of other prominent methods from the literature, followed by a discussion of how the behavior and performance of our algorithm is influenced by its parameters. finally, we explain how the bin framework introduced in this work relates to other search methods known from the literature, summarize our findings, draw some general conclusions, and indicate directions for future work. in the "methods" section, we describe the face-centered cubic lattice model and β-sheet energy potential used in our computational analysis and provides details of the experimental protocols used in the empirical analysis of our algorithm. related work to address the ab initio protein folding problem, the following three issues need to be considered: the model used for the representation of protein structure; the energy potential function; and the method used for searching through the space of possible conformations. in this section, we discuss the choice of protein representation and energy function made in this work; we also provide a brief overview of the best-performing search methods for ab initio protein folding known from the literature. to facilitate ab initio protein structure prediction by means of more efficient methods for searching in the space of protein conformations, various reduced models of protein structure have been introduced by biochemists and physicists. these reduced models fall into two major classes: lattice and off-lattice models. the primary reason for choosing off-lattice models over lattice models is to obtain better geometrical accuracy. despite the biases introduced by the lattice models, namely a somewhat restricted ability to accurately represent secondary structure and backbone conformation, lattice models still retain essential properties of the system and offer a number of computational advantages; these advantages include fast energy computation, easiness of testing self-avoidance and the ability to use pre-computed tables of moves, all of which help to compute search steps efficiently. an important representative of lattice models is the face-centered cubic lattice, which underlies the crystalline structure of most metals. even though in the context of ab initio protein structure prediction, the simpler square and cubic lattices are the most widely studied models in the literature, the fcc lattice captures real protein conformations with higher accuracy while still being representationally rather simple. it has also been shown that local packing of amino acids in real proteins closely fits a distorted fcc lattice, and that the fcc model allows a reasonable description of secondary structure elements; furthermore, it can represent geometrically accurate hydrogen bonding. as a result, the fcc lattice is considered the best overall choice among the simpler regular lattice models. a detailed description of the fcc lattice is provided in the "methods" section. as an energy function to be used in conjunction with the fcc lattice model we chose the β-sheet potential. this choice was motivated by the fact that there are no universally used energy functions for ab initio protein structure prediction; at the same time, the β-sheet potential has been used relatively widely in the literature for the empirical evaluation of the best-performing protein structure prediction methods discussed later in this section. this enables us to compare our new approach against a relatively wide range of other conformation search methods known from the literature. furthermore, this β-sheet potential exhibits characteristics of more complicated energy functions used for off-lattice models. finally, the problem of folding of β-sheet proteins is particularly important, since the accuracy of protein structure prediction methods for β-sheet proteins is the lowest among all structural classes of proteins. the β-sheet potential used in this work is described in detail in the "methods" section. there are a number of search methods applicable to the protein folding problem that can be used in conjunction with reduced complexity models and simplified potentials to perform a broad search through low-resolution structures. the most widely used methods include metropolis monte carlo search, genetic algorithms and generalized ensemble methods, which include the currently best-performing algorithms for ab initio protein structure prediction. this last class of algorithms is based on the observation that canonical monte carlo methods sample conformations according to boltzmann probabilities. for typical distributions of states over energy levels this means that very high and, more importantly, very low energy conformations are rarely sampled. generalized ensemble monte carlo methods attempt to overcome this problem by striving to perform a random walk in energy space by computing the density of states, by sampling expanded range of temperatures or by computing other physical quantities affecting transitions between the states during search. currently, the best-performing generalized ensemble method for ab initio protein structure prediction is replica exchange monte carlo search, also known as the multiple markov chain method or parallel tempering. in remc, a number of non-interacting copies of the given protein sequence are folded independently and at different temperature settings of the underlying canonical monte carlo search. every few steps, pairs of replicas are exchanged with a probability that depends on the energies of the respective conformations. while other generalized ensemble methods, such as multicanonical monte carlo search, maintain only one conformation at any given time, the number of replicas required in remc increases as the square root of the number of degrees of freedom. improvements of remc introduced in the literature include hybrid approaches between remc and muca, or simulated tempering production runs. the parallel-hat tempering monte carlo method utilizes an additional weight factor based on the histogram of energies sampled by each temperature replica to achieve an exponential increase in the acceptance probabilities for high- and low-energy conformations, which increases the efficiency of the search process by allowing it to effectively overcome higher energy barriers and to explore a wider range of conformations for each replica. the following algorithms have been implemented and empirically evaluated for the fcc lattice model with the β-sheet energy function considered in this work: canonical metropolis monte carlo search, muca, remc and phat. of these, phat is the best-performing conformation search method for the ab initio prediction of protein structures on the fcc lattice using the β-sheet potential. bin framework monte carlo search the key idea behind our adaptive bin framework is to improve the effectiveness of a given search process, such as canonical monte carlo search, by making it adaptive and augmenting it with a mechanism for storing and retrieving promising conformations. this is achieved by using a series of bins each of which holds a set of conformations within a certain energy range and an adaptive strategy for restarting a given search process with a conformation retrieved from these bins when the search stagnates. by varying the search strategy according to a priori defined transition probabilities, this approach leads to an algorithm that sacrifices an exact relationship with the canonical ensemble for search efficiency. this method effectively reduces the slow convergence, or quasi-ergodicity, in rugged energy landscapes; it is therefore very useful when the main interest is in finding global minima, rather than in obtaining other physical properties from canonical ensembles. conformations are added to the bins in a way that is aimed at maintaining a diverse set of low-energy conformations. to achieve this we define energy and diversity thresholds for each bin, which are dynamically modified during the search process. with each bin i the following properties are associated: • the capacity of the bin, capi, i.e., the maximal number of conformations that can be stored in the bin at any given time. • the current number of conformations stored in the bin, numi. these conformations themselves are stored in a list that is sorted according to energy, to facilitate efficient retrieval of low-energy conformations. • the width of the bin's maximal energy range, Δei. • the bin's energy threshold, ei+ mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacqwgfbqrdaqhaawcbagaemyaakgabagaey4kascaaaaa@3029@. this is the highest energy that a conformation can reach and still be placed into bin i if the respective diversity threshold is satisfied. • the diversity threshold, which determines how different a conformation has to be from other conformations already stored at the same energy level in order for the new conformation to be accepted into the bin. the pairwise diversity of conformations is measured using a distance measure that depends on the protein model under consideration. here, we use the normalized average hamming distance, hd, between the β-sheet energy sequence of a newly considered conformation c and all β-sheet energy sequences for the set c' of all conformations with the same energy that are already in the bin, see methods section for details. furthermore, the overall bin framework has the following parameters: • the total number of bins, numbins. • the energy range of interest, Δe. together with the current estimate of the ground state energy, e^ mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacuwgfbqrgaqcaaaa@2dcf@, which is modified throughout the search to always represent the lowest energy encountered so far, Δe controls the energy interval into which conformations must fall in order to be accepted into any bin. this range represents the estimate of the maximal barrier height that needs to be surmounted to reach lower energy conformations. • the temperature tbin, which controls the retrieval of conformations from bins. the general bin framework search mechanism is outlined in figure procedure initalizebins is used to set all bin parameters to their initial values. bins are numbered... numbins, and for every bin i, Δei and ei+ mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacqwgfbqrdaqhaawcbagaemyaakgabagaey4kascaaaaa@3029@ are always assigned such that ei+<ei−1+−Δei−1+1 mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacqwgfbqrdaqhaawcbagaemyaakgabagaey4kascaaogaeyipawjaemyrau0aa0baasqaaiabdmgapjabgkhitiabigdaxaqaaiabgucaraaakiabgkhitiabfs5aejabdweafnaabaaaleaacqwgpbqacqghsislcqaixaqmaeqaaogaey4kasiaegymaedaaa@3f41@, i.e., the energy intervals [ei+,ei+−Δei) mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacqggbbwwcqwgfbqrdaqhaawcbagaemyaakgabagaey4kascaaogaeiilawiaemyrau0aa0baasqaaiabdmgapbqaaiabgucaraaakiabgkhitiabfs5aejabdweafnaabaaaleaacqwgpbqaaeqaaogaeiykakcaaa@3ba9@ for different bins never overlap. furthermore, the energy bounds are always assigned such that ei+>e2+>⋯>enumbins+ mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacqwgfbqrdaqhaawcbagaemyaakgabagaey4kascaaogaeyopa4jaemyrau0aa0baasqaaiabikdayaqaaiabgucaraaakiabg6da+iabl+uimjabg6da+iabdweafnaadaaaleaacqwgubgbcqwg1bqdcqwgtbqbcqwgcbgqcqwgpbqacqwgubgbcqwgzbwcaeaacqghrawkaaaaaa@43f0@, i.e., bin always has the highest energy interval, while bin numbins stores the lowest energy conformations. procedure subsearchstep performs one step of a subsidiary search procedure on a given conformation c and returns the resulting conformation c'. this step involves a single proposal of the move from the given move set and its subsequent acceptance or rejection. the two procedures considerstoringinbin and retrievefrombin control the storage of conformations in the bin system and the retrieval of previously stored conformations. note that conformations will only be stored in a bin if they satisfy the corresponding energy and diversity thresholds. storing a conformation may lead to adjustments of the energy thresholds for the corresponding bin or addition of a new bin. finally, a stagnation criterion is used to decide when to retrieve a conformation from the bin system in order to overcome search stagnation, and a termination condition is used to determine when the search process should terminate. in the following, we will describe the specific instantiation of this framework on which the remainder of our study is focused: the binmc algorithm. in binmc, for simplicity all bin capacities capi are set to the same value, and this value is kept constant during the search. the same holds for the energy ranges Δei. finally, for simplicity we also keep the number of bins, numbins, constant during the run of the algorithm. this number is determined by the interval of energies of interest and the energy window width used: numbins = ⌈Δe/Δei⌉. at the beginning of the search process, the energy threshold for each bin i is set to ei+ mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacqwgfbqrdaqhaawcbagaemyaakgabagaey4kascaaaaa@3029@:= -·Δei. initially, the energy intervals of all bins form a partition of the interval [ numbins·Δei), note that this interval is larger than or equal to the desired interval [ Δe); it is larger if Δe does not divide evenly by Δei. it should be noted that is the highest energy possible under the model chosen in this work and all the energies are integer values; in the general case energy thresholds can be adjusted initially to store the highest energy conformations under the protein model considered. the bin energy bounds are adjusted during the search, as will be explained later. the diversity thresholds for the bins, hdi, are determined based on the following formula: hdi = hdmin + ·/, where hdmin and hdmax are parameters of the algorithm that determine the diversity threshold of the lowest and highest energy bins, respectively. this choice is based on the experimental observation that fewer protein conformations exist for lower energies, and therefore, the set of of conformations to be found at low energy levels can be expected to be less diverse. figure depicts some of the properties of bins and conformations in a bin and the overall relationship of conformations stored in the framework to the energy landscape. mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacuwgfbqrgaqcaaaa@2dcf@ is the best solution quality found so far and serves as an estimate of the ground state energy, Δe is the energy range of interest, and conformations within this range are binned. each bin i has energy threshold ei+ mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacqwgfbqrdaqhaawcbagaemyaakgabagaey4kascaaaaa@3029@, diversity threshold hdi, and energy window Δei. binmc uses a standard canonical monte carlo search procedure running at a constant inverse temperature βmc:= 1/, that controls the probability with which worsening search steps are accepted. our canonical monte carlo procedure for the fcc lattice is based on the same search neighbourhood as used by gront et al. and by zhang and skolnick. in each search step, either a double-bond move or a chain-end move is attempted. a double-bond move involves the modification of two successive bond angles, whose position in the chain is chosen uniformly at random. similarly, in a chain-end move, the location of the first or the last residue is changed. for efficiency and speed, double-bond moves are pre-computed in a table, as done by gront et al. and by zhang & skolnick. the search proceeds in phases, each of which starts with two attempts at chain-end moves followed by n/ successive attempts at double-bond moves any number of which may be accepted. procedure subsearchstep in figure performs a single step of this simple subsidiary search process by attempting one move, starting from conformation c and resulting in conformation c'; the attempted moves are chosen such that the previously described phasing of chain-end and double-bond moves is ensured. after a new conformation has been accepted by the subsidiary mc procedure, it is considered for placement into a bin. if the new conformation c' has lower energy then any other conformation encountered so far, i.e., if e <e^ mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacuwgfbqrgaqcaaaa@2dcf@, it is always accepted into the bin framework and the current estimate of the ground state, e^ mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacuwgfbqrgaqcaaaa@2dcf@, is updated. if e falls outside the energy range currently represented by the bin framework, before accepting the new conformation, a new bin is created and the first bin storing conformations with high energies is deleted as follows:: we add a new bin numbins + and delete all conformations from bin along with bin itself. we also shift bin numbers by - such that bin becomes bin and bin numbins + becomes bin numbins. the energy threshold enumbins+ mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacqwgfbqrdaqhaawcbagaemoba4maemydaunaemyba0maemoqaikaemyaakmaemoba4maem4camhabagaey4kascaaaaa@3845@ for the newly added bin is set to enumbins−1+−Δenumbins−1+1 mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacqwgfbqrdaqhaawcbagaemoba4maemydaunaemyba0maemoqaikaemyaakmaemoba4maem4camnaeyoei0iaegymaedabagaey4kascaaogaeyoei0iaeuildqkaemyrau0aasbaasqaaiabd6gaujabdwha1jabd2gatjabdkeacjabdmgapjabd6gaujabdohazjabgkhitiabigdaxaqabagccqghrawkcqaixaqmaaa@4aee@. the diversity thresholds are not shifted with the bins, such that hdmax and hdmin remain associated with the first and the last bin, respectively. if conformation e falls within the energy interval of a bin i that is not yet filled to capacity, and c' satisfies the diversity criterion for that bin – i.e., the hamming distance between the conformation c' and other conformations c" with the same energy e should be larger or equal to hdi – c' is added to that bin, and numi is incremented by one. finally, if e falls within the energy interval of a bin i that is already filled to capacity and it satisfies the diversity criterion for that bin, c' is added to the content of bin i and the highest energy conformation is removed. at the same time, e^ mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacuwgfbqrgaqcaaaa@2dcf@ is set to the energy of the conformation that is currently the highest in the bin; as a consequence, conformations with energy above the updated e^ mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacuwgfbqrgaqcaaaa@2dcf@ will not be accepted into bin i in the future, and therefore, the energy ranges of bins i - and i are now may no longer be adjacent. the stagnation detection mechanism used in binmc is quite simple: the search is considered to be stagnated when no improvement on the lowest energy has been achieved for noimprretrieve search steps, where noimprretrieve is a parameter of the algorithm. to retrieve a conformation from the bin system, binmc uses a two-phase procedure that first selects a bin and then chooses one of the conformations stored in that bin. in the first phase, the probability of selecting a bin i depends on the difference between its upper energy threshold e^ mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacuwgfbqrgaqcaaaa@2dcf@ and the best energy reached so far, and is proportional to: e−βbin mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacqwglbqzdaahaawcbeqaaiabgkhitggaciab=j7ainaabaaameaacqwgibgycqwgpbqacqwgubgbaeqaasgaeiikagiaemyrau0aa0baawqaaiabdmgapbqaaiabgucaraaaliabgkhitiqbdweafzaajagaeiykakcaaaaa@3c51@ where βbin = 1/, kb denotes the boltzmann constant, and tbin is binmc's temperature parameter. in the second phase, the probability of choosing a conformation c from that bin is analogously proportional to: e−βbin⋅−e^) mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacqwglbqzdaahaawcbeqaaiabgkhitggaciab=j7ainaabaaameaacqwgibgycqwgpbqacqwgubgbaeqaasgaeyyxictaeiikagiaemyraukaeiikagiaem4yammaeiykakiaeyoei0iafmyraukbakaacqggpaqkaaaaaa@3f26@ in general, conformations could be chosen with or without replacement; here we limited ourselves to choosing conformation with replacement, since the same conformation can yield a different fold each time it is picked. as in the stochastic tunneling approach, to lessen exponential decay of the probability function we used boltzmann-based modified weights proportional to e−β mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacqwglbqzdaahaawcbeqaaiabgkhitggaciab=j7aijabcicaoiabdweafjabgkhitiqbdweafzaajagaeiykakcaaaaa@3596@. this weighting preserves the location of all minima, but maps the entire energy space from e^ mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaacuwgfbqrgaqcaaaa@2dcf@ to the maximum energy onto the interval. the dynamic process following the boltzmann distribution can therefore pass through energy barriers of an arbitrary height. overall, this retrieval procedure ensures that lower energy conformations are selected with higher probability, which is in accordance with the belief that the energy landscapes of real proteins are funneled. the search is terminated when the target energy level has been reached or when a user-specified number of steps has been executed.  in this section, we present empirical performance results for binmc as compared to the best-performing algorithms known from the literature. mc, remc and phat have been tested by their original authors on the homopolymers of length and but only results for the homopolymer of length have been published. for the protein of length gront et al. believed the lowest energy they had reached, - to correspond to a ground state conformation; however, zhang and skolnick later reported a conformation with energy - for this system. analogous with the results of gront et al. for mc and remc and of zhang and skolnick for phat, in table we provide results averaged over independent runs of each algorithm. it should be noted that several details were not evident from the published descriptions of these algorithms. from personal communication with d. gront, we learned that their mc procedure was run with temperatures from to. since we could not determine the exact annealing schedule used in their study, we chose a constant temperature of for our mc procedure. therefore, the results for the mcsa algorithm of gront et al. may not be exactly comparable with that of our implementation of pure mc. since the number of iterations performed within a given amount of time varies significantly based on implementation details, we used the average cpu times reported by gront et al. and by zhang and skolnick as the cut-off time for our algorithms. comparison of the energy levels reached for the homopolymer of length n = by monte carlo simulated annealing, the replica exchange monte carlo algorithm with a linear set of temperatures and the parallel-hat tempering algorithm with our implementation of monte carlo, remc and phat, as well as with our new bin framework monte carlo algorithm. the run-time reported for mcsa and remc has been conservatively adjusted to our ghz reference machine. the same was done for the run-times for phat. as seen from table our implementations of mc and remc show comparable performance to that of mcsa and remc by gront et al.. however, our implementation of phat did not reach the performance reported in the literature. therefore, we contacted y. zhang to check unpublished details of their algorithm, but unfortunately, those details along with the precise information on the best conformation reported in their paper were no longer available due to data loss. our novel binmc algorithm performs better than mc and remc, and than our implementation of phat. we used the following set of parameters for the bin framework for the homopolymer of length 64: Δe =, Δei =, tmc =, tbin =, bincapacity = hdmax =, hdmin =, noimprretrieve = steps. these settings were determined in a series of experiments in which we studied the influence of different parameter settings; these will be further discussed in discussion section. the lowest energy level for the homopolymer of length reached by our binmc algorithm is -391; this is lower than the energy of any conformation previously reported in the literature. conformations with energy - were found in out of runs, each with a cpu hour cut-off on our reference machine, after and cpu hours, respectively. one of the two resulting conformations is shown in figure the other is its exact mirror image. conformations with energies of - and -, were found multiple times by binmc within a cpu time cut-off of hours on our reference machines. to extend our comparison of the re-implemented methods from the literature with binmc, we tested these methods on instances of length and again, we performed independent runs of each algorithm on every problem instance, measuring the mean as well as the standard deviation of the energy levels reached after a run-time of cpu hour. for binmc when applied to the homopolymers of length and we used the following parameter settings: Δe =, Δei =, tmc =, tbin =, bincapacity = hdmax =, hdmin = and noimprretrieve = steps, whereas on the homopolymer of length we set the parameters to: Δe =, Δei =, tmc =, tbin =, bincapacity = hdmax =, hdmin = and noimprretrieve = steps. as can be seen from our results presented in table all methods find what appears to be the lowest energy for the homopolymer of length in less than cpu second on our reference machine. for the homopolymer of length we are starting to see differences among the algorithms: binmc slightly outperforms all other algorithms in terms of cpu time required for reaching an energy of - which we believe to be the global minimum for this problem instance. mc is the next best method in terms of performance, followed by phat and remc. the performance results for remc and phat are worse than for mc because this homopolymer is too short for the additional time invested in exchanges between replicas to be amortized. for the homopolymer of length binmc outperforms the other algorithms by obtaining lower average energy, followed by phat, remc and finally mc. we show minimum energy conformations for the polymers of length and in figure these solutions appear to be unique in terms of short-range and long-range energy values, since all of the conformations found by any of the algorithms we ran show the same short- vs long-range energy interplay. comparison of the average energy level obtained and the average time required for the homopolymers of lengths n = for the re-implemented mc, remc, phat, and binmc. the time cut-off used was cpu hour on our ghz reference machine, and all statistics were calculated from independent runs. the temperature sets used for our implementations of mc, remc and are the same as in table the p-values reported in the last column were determined using the mann-whitney u test to test the null hypothesis that the mean run-time and the mean energies reached by the respective algorithm vs binmc, respectively, are identical; p-values marked with an asterisk correspond to cases in which the null hypothesis is rejected at a standard significance level of, and therefore indicate statistically significant performance differences. additionally, to see to which extent the results reported in tables and could be further improved, we carried out long independent runs for the homopolymers of length and using a cut-off time of cpu hours on our reference machine. the results of this experiment are shown in table 3; clearly, binmc outperforms our implementation of the state-of-the-art remc and phat algorithms as well as the canonical mc algorithm in terms of the solution quality reached in these long runs, with remc ranking second, followed by phat and mc. comparison of the energy levels reached for the homopolymers of length and by our implementations of mc, remc, phat, and the new binmc algorithm in independent runs of cpu hours each on our ghz reference machine. the p-values reported in the last column were determined using the mann-whitney u test to test the null hypothesis that the mean energies reached by the respective algorithm and binmc are identical; p-values marked with an asterisk correspond to cases in which the null hypothesis is rejected at a standard significance level of, and therefore indicate statistically significant performance differences. next, we conducted a more thorough performance comparison of the algorithms based on run-time distributions measured on the homopolymers of length and the goal of this analysis was to analyze the variability between independent runs on the same problem instance, which is known to reflect the parallelization efficiency of an algorithm and can also reveal detrimental stagnation behavior. in order to be able to perform independent runs of each algorithm on both sequences within a reasonable overall computation time using our reference machine, we used sub-optimal energy levels of - and - for n = and n = respectively. the resulting empirical rtds are shown in figure in the form of the respective cumulative distribution functions. for the homopolymer of length binmc and mc outperform remc and phat in terms of the time required to reach the sub-optimal solution quality of - for the homopolymer of length binmc performs best in terms of the time required to reach the sub-optimal solution quality of - followed by mc, remc and phat. as can be seen from the graphs in figure the rtds of all four algorithms closely resemble exponential distributions. this indicates that for reaching the energy levels considered here, none of the algorithms stagnates and all of them can be parallelized efficiently by concurrently executing independent runs. it may come as a surprise that mc performs better than remc and phat. however, it is important to note that the rtds reported in figure are for sub-optimal qualities only. since mc at a low temperature is "greedier" and does not run multiple chains at different temperatures nor attempts exchanges between them, it gets to sub-optimal energies faster. after reaching them, however, it stagnates; this is reflected in the observation that solution quality does not improve when running mc for a long time for the homopolymers of length and as shown in table we also investigated the scaling behaviour of remc and binmc with homopolymer length. we measured the median run-time to reach the global minimum over runs for sequences of length and amino acids. the resulting sets of three data points for each algorithm were each fitted with a line in a semi-logarithmic plot. based on this analysis, the median run-time required for finding conformations appears to scale as ·n- for remc and as ·n- for binmc. finally, we inspected the distribution of energies sampled by each method for the long homopolymer of length based on approximately × conformations each. as seen in figure remc and phat show typical energy distributions for each replica, as reported by zhang and skolnick; as expected, in the case of phat, the probabilities of encountering low and high energies are elevated. interesting differences are observed when examining the distribution of energies visited by mc and binmc: while our new algorithm samples energies according to the boltzmann probability density function, the distributions are shifted towards lower energy values, reflecting the fact that binmc tends to reach lower-energy conformations more efficiently. discussion similar to the model-based search method introduced for off-lattice fragment insertion as used in the rosetta algorithm, our bin framework stores promising candidate solutions for future reuse. however, unlike mbs, we developed and tested an adaptive diversification mechanism that varies based on the energy level considered and takes into account how different a conformation is from other conformations with the same energy. additionally, the energy level of interest, which determines the highest energy conformations stored in the bin framework are allowed to have, and individual hamming distance criteria used for each bin, are adapted according to the current estimate of the ground state energy. mbs does not have a mechanism comparable to our diversity criteria between stored conformations. in mbs, a number of elite conformations are stored, whose quality is measured using a score determined from their energies and the radius of the local minimum represented by them. another important distinction between binmc and mbs is that in binmc, the model is updated during the search and influences the choice of a new candidate solution every noimprretrieve steps, when search stagnation is detected. on the other hand, in mbs for the discrete off-lattice model with structural fragment insertion as described by brunette and brock, the choice of a new candidate solution is influenced at every step by the pool of conformations stored. thus, mbs exploration of the search space is only dependent on the conformations stored. therefore, regions that are pruned based on the model are eliminated and not explored any further. in contrast, the bin framework provides only a subsidiary mechanism for generating candidate solutions when search stagnation is detected, and does not completely eliminate unexplored regions of the search space. this is achieved by running a non-model-based search for a sufficiently long time to allow it to explore other regions of the search space. the bin framework sorts conformations into bins representing different energy levels to make sure that the model contains as many energy levels of interest as possible while still reducing the search space. this aspect of the search is conceptually related to histogram-based sampling and search methods such as multicannonical algorithm and energy landscape paving method. it should be noted, however, that our bin framework is a non-parametric model of the search space that consists of a diverse set of promising candidate conformations stored in the bins. muca, on the other hand, and to some degree elp, are based on a parametric model of sampling all energy levels with the same probability without emphasis on low energies. in addition, our bin framework uses hamming distance criteria that are based on the energy level of each bin to ensure that the respective sets of conformations stored are diverse and capture the overall funnel-like structure of the landscape. up to this point, we have focused on comparing binmc with existing algorithms. we now turn our attention to the question how the performance of the binmc algorithm depends on its parameters and the algorithm components controlled by them, and to the determination of good settings for these parameters. we conducted this investigation for the homopolymer of length since reaching its best known energy level of - is challenging, but not too computationally expensive to preclude performing multiple successful runs for a large number of parameter settings. for each parameter configuration, we conducted independent runs on our reference machine and recorded the time required in each of these to reach an energy of -161; from these runs, we then determined the average cpu time required to reach this target energy. to study the influence of the different parameters on algorithm performance, we varied one of them at a time, while keeping all other parameter values fixed. unless indicated otherwise, the parameters kept fixed in these experiments were set to the following values: Δe =, Δei =, tmc =, tbin =, bincapacity = hdmax =, hdmin =, noimprretrieve = steps. here, we summarize the results of this study; details are provided in the supplementary material, see additional file the impact of the parameters on the performance of binmc can be ranked as follows: the number of non-improving steps that are performed before reaching into a bin and replacing the current conformation in the monte carlo run, noimprretrieve; the ratio between the width of the energy of interest considered for binning, Δe, and the bin temperature, tbin; the diversity criteria used during binning high- and low-energy conformations, values of hdmin = and hdmax = guarantee that we are selective enough when storing promising conformations at low and high energy levels correspondingly and result in the best performance; the width of the energy window considered by each bin; and the capacity of bins, capi. furthermore, we made the following observations regarding parameter settings of our algorithm for the longer homopolymer of length 64: a higher value of noimprretrieve should be used, which indicates that longer search times are required to effectively explore the neighbourhood of the current conformation before reaching into the bin framework and replacing it with another promising conformation; Δe should be increased, which is consistent with the common belief that the barrier heights for longer homopolymers are higher, and tbin should be adjusted such that the ratio Δe/tbin remains the same as for length 32; Δei should be increased to ei = which suggests that a coarser search space discretization may be beneficial for longer homopolymers; note that the combination of increases in Δe and Δei results in only a slight increase in the total number of bins, numbins; the same values for hdmin, hdmax and capi can be used as in the case of length finally, our empirical results presented in additional file show that the binmc algorithm performs substantially better than the simple restart strategy and than the pure monte carlo on which it is based. we also determined that all components of our algorithm are important for its efficiency, see additional file for example, the average time required for finding purportedly optimal conformations increases significantly when increasing noimprretrieve until bin framework retrieval is performed very infrequently, when decreasing Δe or capi or when increasing the diversity thresholds hdmin and hdmax, resulting in very few conformations being stored, or when reducing the number of bins.  the bin framework introduced in this work is a general approach that can be used to augment existing conformation search methods in order to increase their ability to focus on promising regions of the search phase and to effectively overcome stagnation in regions of sub-optimal conformations. as shown by our computational experiments, even very simple instantiations of the general bin framework can result in highly effective search algorithms. in particular, our novel bin framework monte carlo algorithm surpasses replica exchange monte carlo search and its heuristic variant, parallel-hat tempering, in its ability to find minimum energy conformations for β-sheet homopolymers on the fcc lattice. furthermore, using our new algorithm we have improved the best known solution for the homopolymer of length from - to - in future work, we plan to consider more advanced adaptive bin framework strategies that control search diversification and intensification reactively during the search, based on observed features of the search landscape. additionally, we are planning to generalize our bin framework to work on partial as well as complete conformations, producing an efficient generalized framework that combines two distinct search strategies. finally, we would like to extend our bin framework to address other models of protein structure, such as the fcc model with a more complex energy function or other discrete and continuous off-lattice models. given the results for β-sheet homopolymers on the fcc lattice achieved in this work, we believe that further investigation of our adaptive bin framework and its application to other protein structure prediction problems holds much promise. 
the problem of protein structure prediction consists of predicting the functional or native structure of a protein given its linear sequence of amino acids. this problem plays an important role in the analysis of systems with complex search landscapes, and particularly in the context of ab initio protein structure prediction. we show that our bin framework combined with a widely used optimization method, monte carlo search, achieves significantly better performance than state-of-the-art generalized ensemble methods for a well-known protein-like homopolymer model on the face-centered cubic lattice. our work focuses on the problem of searching an exponentially large space of possible conformations as efficiently as possible, with the goal of finding a global optimum with respect to a given energy function. in this work, we introduce a novel approach for solving this conformation search problem based on the use of a bin framework for adaptively storing and retrieving promising locally optimal solutions. here, we introduce adaptive mechanisms for choosing which conformations should be stored, based on the set of conformations already stored in memory, and for biasing choices when retrieving conformations from memory in order to overcome search stagnation.
 the problem of protein structure prediction consists of predicting the functional or native structure of a protein given its linear sequence of amino acids. this problem has played a prominent role in the fields of biomolecular physics and algorithm design for over years. additionally, its importance increases continually as a result of an exponential growth over time in the number of known protein sequences in contrast to a linear increase in the number of determined structures. our work focuses on the problem of searching an exponentially large space of possible conformations as efficiently as possible, with the goal of finding a global optimum with respect to a given energy function. this problem plays an important role in the analysis of systems with complex search landscapes, and particularly in the context of ab initio protein structure prediction.  in this work, we introduce a novel approach for solving this conformation search problem based on the use of a bin framework for adaptively storing and retrieving promising locally optimal solutions. our approach provides a rich and general framework within which a broad range of adaptive or reactive search strategies can be realized. here, we introduce adaptive mechanisms for choosing which conformations should be stored, based on the set of conformations already stored in memory, and for biasing choices when retrieving conformations from memory in order to overcome search stagnation.  we show that our bin framework combined with a widely used optimization method, monte carlo search, achieves significantly better performance than state-of-the-art generalized ensemble methods for a well-known protein-like homopolymer model on the face-centered cubic lattice. 