A rotor search function used to find acceptable conformations of arbitrary backbone and helical parameter combinations. The main class of the proto-Nucleic Acid Builder.
More...
|
| void | SystematicSearch () |
| | Given a step size, the algorithm exhaustively searches over all the rotatable dihedral angles in the backbone. More...
|
| |
| void | RandomSearch (bool weighted) |
| | The algorithm randomly changes all the dihedral angles in the backbone and evaluates whether they are acceptable. More...
|
| |
| void | MonteCarloSearch (bool weighted) |
| | The algorithm utilizes the Metropolis Monte Carlo scheme to improve the choice of the dihedral angle. More...
|
| |
| void | GeneticAlgorithmSearch () |
| | This algorithm utilizes the genetic algorihtm procedure to improve the choice of the dihedral angle. More...
|
| |
| std::vector< std::piecewise_linear_distribution< double > > | WeightedDistributions () |
| | Produces weighted distributions for each rotatable dihedral angle in the backbone. More...
|
| |
| double | measureDistance (double *coords, unsigned head, unsigned tail) |
| | Compute the distance between the head backbone atom and the tail backbone atom of the next nucleotide. More...
|
| |
| void | reportData (PNAB::ConformerData &conf_data) |
| | A function to report the data on the accepted candidates. More...
|
| |
| void | printProgress (std::size_t search_index, std::size_t search_size) |
| | Prints the percentage of search completed and the best accepted candidate. More...
|
| |
A rotor search function used to find acceptable conformations of arbitrary backbone and helical parameter combinations. The main class of the proto-Nucleic Acid Builder.
The general algorithm follows the following steps:
- Define the input parameters:
- The three-dimensional structure of the backbone, the atoms that form the connection to the base, and the two atoms (head and tail) that link the backbone with two adjacent backbones.
- The helical configuration of the nucleobases.
- The runtime parameters:
- The specific search algorithm (see below).
- The distance and energy thresholds (see below).
- The sequence of the nucleobases and whether the system is single-stranded, a duplex, or a hexad.
- Connect the backbone with the first nucleobase in the sequence.
- Fix all the bond distances, bond angles, and the rigid dihedral angles in the backbone. Fix all the atoms of the nucleobase.
- Change the dihdedal angles in the backbone using one of the search algorithm.
- Translate and rotate the tail atom of the backbone using the given helical parameters.
- Measure the distance between the head and the tail atoms of the backbone.
- If the distance is greater than the distance threshold, go to 4. Else, proceed.
- Arrange the nucleobases using the given helical parameters. Replicate the backbone structure across all the nucleotides.
- Evaluate various energy terms for the system.
- If the energy terms are less than the energy thresholds, save the structure. Else, reject the structure.
- Repeat steps 4-10 or quit.
The various search algorithm differ in the implementation of step 4. Four classes of search algorithms are implemented here, namely:
- Systematic Search
- Random Search
- Monte Carlo Search
- Genetic Algorithm Search
Details on the specific implementation of each algorithm are discussed below.
- See also
- SystematicSearch
-
RandomSearch
-
MonteCarloSearch
-
GeneticAlgorithmSearch
-
HelicalParameters
-
RuntimeParameters
-
Backbone
-
BaseUnit
-
Chain
| void ConformationSearch::GeneticAlgorithmSearch |
( |
| ) |
|
|
private |
This algorithm utilizes the genetic algorihtm procedure to improve the choice of the dihedral angle.
In the genetic algorithm search, a population of rotamers is initialized with random dihedral angles. At each iteration (or generation), certain rotamers (parents) are chosen for reproduction based on their fitness. The offsprings are generated by allowing the two parents to exchange (crossover) one dihedral angle. Then, a random mutation (or a new value for the dihedral angle) may be introduced for one dihedral angle. The new population consisting of the offsprings then follow the same procedure. The algorithm finishes after the specified number of generations. The length of the search is proportional to the number of generations multiplied by the size of the population.
The fitness of the individuals is computed as the inverse of the distance between the head atom of the backbone and the tail atom of the adjacent backbone. The individuals in the population are ranked by their fitness score, and the probability of choosing individuals for mating is proportional to their ranking.
The exchange of the dihedral angles between the parents and the introduction of new dihedral angles is determined by the crossover and mutation probabilities.
The algorithm significantly accelerates the finding of dihedral angles that satisfy the distance threshold. However, the distance threshold only indicates that the candidate backbone configuration can form a periodic structure. It does not indicates whether the backbone configuration is low or high in energy. Therefore, introducing mutations with higher probability is useful in preventing the formation of a homogeneous population that has low distances but high energies.
The probability of choosing a random angle between 0 and 360° is uniform.
- See also
- RuntimeParameters::num_steps
-
RuntimeParameters::population_size
-
RuntimeParameters::crossover_rate
-
RuntimeParameters::mutation_rate
-
measureDistance
-
Chain::generateConformerData
| void ConformationSearch::MonteCarloSearch |
( |
bool |
weighted | ) |
|
|
private |
The algorithm utilizes the Metropolis Monte Carlo scheme to improve the choice of the dihedral angle.
At every iteration, this algorithm randomly chooses two dihedrals and set them to random values. If the new configuration decreases the distance between the head atom of the backbone and the tail atom of the adjacent backbone or if the new distance is less than 1 Angstrom, this step is accepted. If the new configuration does not decrease the distance, the step is provisionally accpeted if a random number between 0 and 1 is less than \(exp(\frac{E}{k_{B}T})\), where \(E\) is a penalty term based on the distance, and \(k_{B}T\) is the Boltzmann constant multiplied by the temperature. If the step is provisionally accepted, the system is constructed and the energy terms of the system are computed. If the energy terms are higher than the thresholds, the step is finally rejected. The algorithm finishes after the specified number of iterations.
The penalty term \(E\) is given by \(E=-k(\textrm{currrent distance} - \textrm{previous distance})^2\). \(k\) is a bond stretching constant fixed at 300 kcal/mol/Angstrom \(^2\). The temperature controls how agressively the algorithm should provisionally accept or reject steps. An infinite temperature will reduce the algorithm to a random search with two dihedral angles changed at every step.
The algorithm significantly accelerates the finding of dihedral angles that satisfy the distance threshold. However, the distance threshold only indicates that the candidate backbone configuration can form a periodic structure. It does not indicates whether the backbone configuration is low or high in energy. Therefore, the ultimate criteria for accepting or rejecting a step, if the distance is not decreased in the step, is whether it satisfies the energy thresholds.
The probability of choosing a random angle between 0 and 360° can be uniform or can be weighted. See the description in WeightedDistributions for an explanation on the weighting scheme for the dihedral angles.
- Parameters
-
| weighted | Whether to use a weighted distribution for the dihedral angles |
- See also
- RuntimeParameters::num_steps
-
RuntimeParameters::weighting_temperature
-
RuntimeParameters::monte_carlo_temperature
-
WeightedDistributions
-
measureDistance
-
Chain::generateConformerData
| void ConformationSearch::RandomSearch |
( |
bool |
weighted | ) |
|
|
private |
The algorithm randomly changes all the dihedral angles in the backbone and evaluates whether they are acceptable.
At every iteration, this algorithm sets all the dihedral angles in the backbone to random values. This algorithm is purely random and each iteration is completely independent from the previous iteration. This algorithm can sample the dihedral angle space much faster than the Systemtic Search algorithm. Therefore, it may find an acceptable candidate faster. However, it is not deterministic. As each iteration is completely independent, this algorithm does not become trapped in unfavorable configurations. Nevertheless, the search does not improve with time. The algorithm finishes after the specified number of iterations.
The probability of choosing a random angle between 0 and 360° can be uniform or can be weighted. See the description in WeightedDistributions for an explanation on the weighting scheme for the dihedral angles.
- Parameters
-
| weighted | Whether to use a weighted distribution for the dihedral angles |
- See also
- RuntimeParameters::num_steps
-
RuntimeParameters::weighting_temperature
-
WeightedDistributions
-
measureDistance
-
Chain::generateConformerData
| void ConformationSearch::SystematicSearch |
( |
| ) |
|
|
private |
Given a step size, the algorithm exhaustively searches over all the rotatable dihedral angles in the backbone.
The systematic search algorithm works by exhaustively rotating all the dihedral angles between 0 and 360° using the given step size. This is the simplest search algorithm. However, it is the most time-consuming as the time grows exponentially with the number of rotatable bonds. The number of steps required for the search is \((\frac{360.0}{\textrm{dihedral step}})^{\textrm{number of rotatable dihedrals}}\). This algorithm is deterministic and reproducible. It is guranteed to find an acceptable candidate, if any exists, to within the given resolution. This algorithm can be used to validate the results of the other algorithms and to determine whether the other algorithms found all the families of the acceptable candidates.
- See also
- RuntimeParameters::dihedral_step
-
measureDistance
-
Chain::generateConformerData
| std::vector< std::piecewise_linear_distribution< double > > ConformationSearch::WeightedDistributions |
( |
| ) |
|
|
private |
Produces weighted distributions for each rotatable dihedral angle in the backbone.
Instead of using a uniform distrbution for the dihedral angles between 0 and 360°, this function generates weighted distributions for each rotatable dihedral angle in the backbone. The energy of each dihedral angle in isolation is computed every 5°. Then, the probability for a given angle is computed as the \(\frac{exp(\frac{E_i}{k_{B}T})}{\sum_i exp(\frac{E_i}{k_{B}T})}\), where \(E_i\) is the dihedral energy at angle \(i\). The probability in each interval is the linear interpolation of the probabilities at the limits of the interval. The temperature controls how agressively the algorithm should weight the dihedral angles. An infinite temperature will reduce the probabilities to uniformly random distributions.
This weighting scheme is useful in increasing the sampling of the dihedral angles where the energy of the dihedral angle is low. However, the energy of the dihedral angle in isolation does not necessarily mean the nucleotide energy is going to be low. This weighting scheme may improve the search if the acceptable candidates adopt structures where the dihedral angles are not strained. However, it may worsen the search if the unstrained dihedral angles do not produce low-energy candidates.
- Returns
- A vector of the weighted distributions for each rotatable dihedral angle
- See also
- RuntimeParameters::weighting_temperature
-
RandomSearch
-
MonteCarloSearch
