CN109524057B - Protein folding prediction method based on ant colony fish swarm algorithm - Google Patents
Protein folding prediction method based on ant colony fish swarm algorithm Download PDFInfo
- Publication number
- CN109524057B CN109524057B CN201811384813.XA CN201811384813A CN109524057B CN 109524057 B CN109524057 B CN 109524057B CN 201811384813 A CN201811384813 A CN 201811384813A CN 109524057 B CN109524057 B CN 109524057B
- Authority
- CN
- China
- Prior art keywords
- algorithm
- population
- ant
- artificial
- fish
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
- 238000004422 calculation algorithm Methods 0.000 title claims abstract description 117
- 241000251468 Actinopterygii Species 0.000 title claims abstract description 76
- 238000000034 method Methods 0.000 title claims abstract description 34
- 230000012846 protein folding Effects 0.000 title claims abstract description 33
- 239000003016 pheromone Substances 0.000 claims abstract description 16
- 241000257303 Hymenoptera Species 0.000 claims description 17
- 235000013305 food Nutrition 0.000 claims description 13
- 230000008569 process Effects 0.000 claims description 12
- 230000002688 persistence Effects 0.000 claims description 4
- 241000894007 species Species 0.000 claims description 4
- 230000000007 visual effect Effects 0.000 claims description 4
- 125000004122 cyclic group Chemical group 0.000 claims description 3
- 108090000623 proteins and genes Proteins 0.000 abstract description 41
- 102000004169 proteins and genes Human genes 0.000 abstract description 41
- 238000000455 protein structure prediction Methods 0.000 abstract description 6
- 238000004364 calculation method Methods 0.000 abstract description 5
- 238000005457 optimization Methods 0.000 description 11
- 230000006399 behavior Effects 0.000 description 5
- 230000008901 benefit Effects 0.000 description 5
- 238000012360 testing method Methods 0.000 description 5
- 125000003275 alpha amino acid group Chemical group 0.000 description 4
- 230000000694 effects Effects 0.000 description 4
- 238000013461 design Methods 0.000 description 3
- 201000010099 disease Diseases 0.000 description 3
- 208000037265 diseases, disorders, signs and symptoms Diseases 0.000 description 3
- 239000002245 particle Substances 0.000 description 3
- 208000024827 Alzheimer disease Diseases 0.000 description 2
- 230000003044 adaptive effect Effects 0.000 description 2
- 125000000539 amino acid group Chemical group 0.000 description 2
- 150000001413 amino acids Chemical class 0.000 description 2
- HVYWMOMLDIMFJA-DPAQBDIFSA-N cholesterol Chemical compound C1C=C2C[C@@H](O)CC[C@]2(C)[C@@H]2[C@@H]1[C@@H]1CC[C@H]([C@H](C)CCCC(C)C)[C@@]1(C)CC2 HVYWMOMLDIMFJA-DPAQBDIFSA-N 0.000 description 2
- 230000000295 complement effect Effects 0.000 description 2
- 230000007547 defect Effects 0.000 description 2
- 238000010586 diagram Methods 0.000 description 2
- 230000002068 genetic effect Effects 0.000 description 2
- 238000005511 kinetic theory Methods 0.000 description 2
- 230000000704 physical effect Effects 0.000 description 2
- 229910052700 potassium Inorganic materials 0.000 description 2
- 238000011160 research Methods 0.000 description 2
- 108010006519 Molecular Chaperones Proteins 0.000 description 1
- 102000005431 Molecular Chaperones Human genes 0.000 description 1
- 102000007079 Peptide Fragments Human genes 0.000 description 1
- 108010033276 Peptide Fragments Proteins 0.000 description 1
- 235000014676 Phragmites communis Nutrition 0.000 description 1
- 241001122315 Polites Species 0.000 description 1
- 206010037742 Rabies Diseases 0.000 description 1
- 206010039966 Senile dementia Diseases 0.000 description 1
- 238000005076 Van der Waals potential Methods 0.000 description 1
- 238000000137 annealing Methods 0.000 description 1
- 238000005452 bending Methods 0.000 description 1
- 230000009286 beneficial effect Effects 0.000 description 1
- 229910052799 carbon Inorganic materials 0.000 description 1
- 238000006243 chemical reaction Methods 0.000 description 1
- 235000012000 cholesterol Nutrition 0.000 description 1
- 230000000052 comparative effect Effects 0.000 description 1
- 238000012937 correction Methods 0.000 description 1
- 238000005516 engineering process Methods 0.000 description 1
- 238000011156 evaluation Methods 0.000 description 1
- 238000002474 experimental method Methods 0.000 description 1
- 230000004634 feeding behavior Effects 0.000 description 1
- 229910052731 fluorine Inorganic materials 0.000 description 1
- 230000004927 fusion Effects 0.000 description 1
- 201000011066 hemangioma Diseases 0.000 description 1
- 229910052739 hydrogen Inorganic materials 0.000 description 1
- 125000001165 hydrophobic group Chemical group 0.000 description 1
- 238000000338 in vitro Methods 0.000 description 1
- 230000006698 induction Effects 0.000 description 1
- 230000008316 intracellular mechanism Effects 0.000 description 1
- 238000004215 lattice model Methods 0.000 description 1
- 238000013178 mathematical model Methods 0.000 description 1
- 230000007246 mechanism Effects 0.000 description 1
- 239000011664 nicotinic acid Substances 0.000 description 1
- 229910052757 nitrogen Inorganic materials 0.000 description 1
- 229910052760 oxygen Inorganic materials 0.000 description 1
- 229910052698 phosphorus Inorganic materials 0.000 description 1
- 229920001184 polypeptide Polymers 0.000 description 1
- 238000005381 potential energy Methods 0.000 description 1
- 108090000765 processed proteins & peptides Proteins 0.000 description 1
- 102000004196 processed proteins & peptides Human genes 0.000 description 1
- 230000002441 reversible effect Effects 0.000 description 1
- 238000010845 search algorithm Methods 0.000 description 1
- 238000004088 simulation Methods 0.000 description 1
- 238000004611 spectroscopical analysis Methods 0.000 description 1
- 229910052717 sulfur Inorganic materials 0.000 description 1
- 230000009182 swimming Effects 0.000 description 1
- 230000007704 transition Effects 0.000 description 1
- XLYOFNOQVPJJNP-UHFFFAOYSA-N water Substances O XLYOFNOQVPJJNP-UHFFFAOYSA-N 0.000 description 1
- 229910052727 yttrium Inorganic materials 0.000 description 1
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
- G06N3/00—Computing arrangements based on biological models
- G06N3/004—Artificial life, i.e. computing arrangements simulating life
- G06N3/006—Artificial life, i.e. computing arrangements simulating life based on simulated virtual individual or collective life forms, e.g. social simulations or particle swarm optimisation [PSO]
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Physics & Mathematics (AREA)
- Data Mining & Analysis (AREA)
- General Health & Medical Sciences (AREA)
- Biomedical Technology (AREA)
- Biophysics (AREA)
- Computational Linguistics (AREA)
- Life Sciences & Earth Sciences (AREA)
- Evolutionary Computation (AREA)
- Artificial Intelligence (AREA)
- Molecular Biology (AREA)
- Computing Systems (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Mathematical Physics (AREA)
- Software Systems (AREA)
- Health & Medical Sciences (AREA)
- Management, Administration, Business Operations System, And Electronic Commerce (AREA)
Abstract
为了解决现有技术中对于蛋白质结构预测存在的精度低、计算时间长的问题，本发明记载了一种基于蚁群鱼群算法的蛋白质折叠预测的方法，涉及蛋白质结构预测领域，技术方案如下：步骤一：蚁群算法初始化设置，人工鱼群算法初始化设置，形成新的初始种群；步骤二：交替迭代生成新的初始解；步骤三：判断拥挤度；若拥挤，则种群保持原态，随机前进一步，重复执行步骤二，若不拥挤，则朝种群的中心位置方向前进一步，种群执行步骤四；步骤四：更新信息素浓度和公告栏信息；步骤五：计算适应度；步骤六：判断是否满足条件；若满足条件，输出结果，若不满足条件，返回至步骤二。本发明能够在运算精度高、搜索时间短的情况下搜索到蛋白质序列的最低能量值。
In order to solve the problems of low precision and long calculation time for protein structure prediction in the prior art, the present invention records a method for protein folding prediction based on ant colony fish swarm algorithm, which relates to the field of protein structure prediction, and the technical scheme is as follows: Step 1: Initialize settings of ant colony algorithm and artificial fish swarm algorithm to form a new initial population; Step 2: Alternate iteration to generate new initial solutions; Step 3: Judge the degree of crowding; Step forward, repeat step 2, if it is not crowded, move forward one step towards the center of the population, and perform step 4 for the population; step 4: update pheromone concentration and bulletin board information; step 5: calculate fitness; step 6: judge Whether the condition is met; if the condition is met, output the result; if the condition is not met, return to step 2. The invention can search for the lowest energy value of the protein sequence under the condition of high calculation precision and short search time.
Description
Technical Field
The invention belongs to the field of protein structure prediction, and particularly relates to a protein folding prediction method based on an ant colony fish swarm algorithm.
Background
The ant colony algorithm and the artificial fish colony algorithm are called as two emerging colony intelligent algorithms, although the birth time is short, the progress speed is high, and the ant colony algorithm and the artificial fish colony algorithm are tried to be applied to a plurality of fields by broad scholars and achieve good results. While a single algorithm has many advantages, it has various disadvantages.
The ant colony algorithm has good parallelism and high accuracy, which is a prominent advantage of the ant colony algorithm. The artificial ants can search the whole search space, and can exchange information among the artificial ants, so that the purpose of optimizing is finally achieved. In the ant colony algorithm, each artificial ant actually interacts with the environment, and each artificial ant is connected with each other by means of pheromone 'bridging'. For example: an artificial ant finds a food source, the artificial ant does not obviously yell other ant partners to say that food is provided at the position, but the artificial ant leaves pheromone on a path, and the 'polite' mode leads other ants to perceive the existence of the pheromone at the position when passing through nearby zones so as to successfully find the food. That is, when the ant does not find the food in the beginning, the pheromone left on the path is useless pheromone, which slows down the initial optimization speed, and is a prominent disadvantage of the ant colony algorithm, and the ant needs to find the food as soon as possible by the moving rule. Specifically, the method comprises the following steps: ants first need to have some inertia and keep a tendency to move forward, rather than move around in place. Secondly, ants keep a certain randomness after fixing the motion trend, and abstain from crazy linear motion like particles in the particle swarm optimization. By doing so, ants can try to move according to the original trend as much as possible, and can also try to generate a new search range. But ants also have errors and make mistakes, do not move to the place with high pheromone, and walk blindly, so that local optimal conditions are generated, which is also a disadvantage in the ant colony algorithm.
The artificial fish swarm algorithm is a swarm intelligent bionic algorithm for simulating the behavior of fish in nature. Local optimization is carried out by constructing four underwater behaviors of a single artificial fish, and finally global optimization is achieved. In the food searching behavior of the fish, fewer times of attempts are set, the probability of artificial fish random swimming is increased, the capability of local optimal solution can be avoided, and global optimal is obtained. The use of the crowdedness factor can limit the scale of fish shoal gathering, so that the artificial fish can be more freely optimized. The occurrence of the trailing behavior can enable the artificial fish to act towards a better state, and also enable the artificial fish trapped in the local optimum to escape from the local optimum area and move towards the global optimum direction. The design idea of the artificial fish swarm algorithm is different from that of the traditional optimization algorithm, but can be combined with the traditional design idea and applied to the NP problem. The algorithm has no special requirement on initial values, and is not very sensitive to parameter selection, which is also carefully introduced and studied in the above. In the algorithm, only the function value of the objective function is used, and the algorithm is not limited by other special information. This is also an advantage of the artificial fish swarm algorithm. The typical disadvantage of the artificial fish swarm algorithm is that the accuracy is not high.
Through the above description, the ant colony algorithm and the artificial fish colony algorithm have complementary relationship, and the two colony intelligent algorithms are improved, so that the performance and the efficiency of the algorithm can be improved through effective fusion. The improved group intelligent algorithm can avoid the defects of respective single algorithms, strengthen the advantages of the algorithms and form a more stable and comprehensive group intelligent algorithm.
Protein folding has been a focus of great concern. According to statistics of relevant departments, the protein of about 1/3 normal cells of a human body generates folding errors, but intracellular mechanisms can find the existence of the wrong protein in time and clear the wrong protein quickly, but when the folding errors of the protein are too large to be processed, various diseases can be caused, and the diseases are similar to Alzheimer disease (commonly known as senile dementia), spongiform hemangioma, familial hereditary cholesterol altitude disease, rabies and the like. Therefore, the study on protein folding is not only of great significance but also is very slow.
Protein folding refers to the process of folding a protein molecule from a loose chain into a high-order structure with activity. During folding, it is necessary to go through a number of intermediate structural states, i.e. partial folding of the protein, also called intermediate folds. By protein folding, we can understand how the amino acid sequence determines the spatial structure of the protein. The research shows that: the process of protein folding is very cumbersome and quite fast. Many theories are involved in the folding process, and the main theories are thermodynamic and kinetic theories. The thermodynamic theory of protein folding was first to say that all the information that stabilizes the native conformation of a protein is displayed in the amino acid sequence of the polypeptide chain, and that the protein itself can fold into the native conformation without the need for external energy induction. As research continues, more intensive studies have shown that in vitro proteins are not all reversible, and that in some species the proteins have very low recoverability, and the theory of kinetics has played a role here. Kinetic theory suggests that during protein folding, there is some force that prevents the protein from successfully completing its native conformation, thus leaving the protein structure in a second stable state. In summary, the protein folding process is kinetically controlled, but follows a thermodynamically speaking transition from a high energy state to a low energy state.
The theoretical significance of protein folding is that it uncovers the second genetic code in the organism. The reason for this is that amino acids are the basic unit of proteins, the primary structure of proteins is also the amino acid sequence, amino acid residues interact and entangle, and the structure can be changed to a higher order structure in a short time, but researchers cannot judge the structure of proteins in a short time according to the order of amino acid arrangement.
The results achieved at present are evident for protein folding. Strict corrections were made to the statement that the new peptide fragment folded spontaneously; protein structure equilibrium was analyzed in conjunction with spectroscopy; discovery of molecular chaperone recognition mechanism, etc. Meanwhile, there are many unknown and guesses for protein folding, there are about 170000 primary protein structures in the database, only 12000 proteins have been detected, the 12000 primary structures also include many homologous proteins, their structures are very similar, and the protein structures with completely different structures are only detected about 1000. This data is sufficient to show that the protein folding study requires more attention and also that the subject matter of the study is of great importance and significance.
The theory of protein structure prediction has been well developed for decades, but the prediction results have not been comparable to those collected in the protein structure database (PDB) by means of biochemical experiments. The ultimate goal of protein structure prediction is the protein folding problem. The problems of low precision and long calculation time of the structure of the protein predicted at present exist, and some search algorithms are easy to be trapped in local extreme points.
Disclosure of Invention
The invention aims to solve the problems of low precision and long calculation time of protein structure prediction in the prior art, and discloses a protein folding prediction method based on an ant colony fish swarm algorithm.
In order to achieve the purpose, the technical scheme adopted by the invention is as follows:
the method comprises the following steps: initializing and setting an ant colony algorithm, and initializing and setting an artificial fish colony algorithm to form a new initial population;
step two: alternately iterating to generate a new initial solution;
step three: judging the degree of congestion; if the population is crowded, the population keeps the original state, one step is carried out randomly, the step two is repeatedly executed, if the population is not crowded, the step one step is carried out towards the central position of the species group, and the step four is executed by the population;
step four: updating pheromone concentration and bulletin board information;
step five: calculating the fitness;
step six: judging whether the conditions are met; and if the conditions are met, outputting the result, and if the conditions are not met, returning to the step two.
Further, in the first step, initializing the number m of the artificial ants, a heuristic factor alpha, a hope heuristic factor beta, an information persistence factor rho and information intensity Q; the number M of the artificial fish, the step length step, the visual field range of the artificial fish and the crowding factor delta are initialized.
Further, in the second step, the ant colony algorithm and the artificial fish colony algorithm are alternately iterated, and the superiority or inferiority of the solution is determined by comparison; in the same problem, if the ant colony algorithm searches a preferred solution first, the preferred solution is randomly placed at the position of an artificial fish in the artificial fish colony; if the artificial fish swarm algorithm searches a preferred solution first, the preferred solution is randomly placed at the position of one artificial ant in the artificial ant swarm.
Further, in step three, if
If the center of the population has more food and is not crowded, the population is carried out in the direction of the central position of the population, the step four is carried out, and if the population is not crowded, the step four is carried out
If the population is crowded, keeping the population in the original state, randomly moving one step, and repeatedly executing the second step, wherein n in the formulafIndicating the number of groups in the current domain, ycFitness value, y, representing the center positioniA fitness value representing the current state.
Further, in step four according to
To update the pheromone density and to update the bulletin board information, where τij(t) pheromones from node i to j for the tth ant; when an ant k passes j from node i in this cycle,
otherwise, the value is 0, Q represents the information intensity, namely the amount of the released information of the artificial ants, lkRepresents the path length of the kth ant in the cyclic search process.
Further, in step five, the formula y is usedi＝f(xi) Finding the fitness where xiRepresenting the position vector, y, of the i-th artificial fishiExpressing the fitness value of the i-th artificial fish, wherein f (x)i) The method is characterized in that the optimal value of a single fish is obtained by taking the food concentration of the position of the artificial fish as the adaptive value of an objective function and taking the state of the single fish as the optimal value and bringing the optimal value into the optimal value.
Further, in the sixth step, whether a condition for ending the algorithm process is met is judged, the condition for ending the algorithm is that the maximum iteration number is reached or the error reaches the target precision requirement, if the condition is met, the optimal solution, namely the lowest value of the energy function of the three-dimensional Toy model, is output, the algorithm is ended, and if the condition is not met, the second step is returned to continue to execute the alternate iteration to generate a new initial solution.
Compared with the prior art, the invention has the beneficial effects that: the invention records a group intelligent algorithm which has better global convergence performance and faster rapid convergence capability, is easy to escape from local optimization and achieves global optimization. The convergence rate of the algorithm is greatly improved, the minimum energy value of the protein sequence can be searched under the conditions of high operation precision and short search time, and the obtained conformation diagram can basically reflect the physical properties of the real protein, so that the structure of the protein can be effectively predicted.
Drawings
FIG. 1 is a flow chart of an improved ant colony fish algorithm;
FIG. 2 is a three-dimensional Toy model structure;
fig. 3 is a line graph comparing experimental results with the prior art.
Detailed Description
Example 1
A protein folding prediction method based on an ant colony fish swarm algorithm comprises the following steps:
the method comprises the following steps: initializing and setting an ant colony algorithm, and initializing and setting an artificial fish colony algorithm to form a new initial population;
step two: alternately iterating to generate a new initial solution;
step three: judging the degree of congestion; if the population is crowded, the population keeps the original state, one step is carried out randomly, the step two is repeatedly executed, if the population is not crowded, the step one step is carried out towards the central position of the species group, and the step four is executed by the population;
step four: updating pheromone concentration and bulletin board information;
step five: calculating the fitness;
step six: judging whether the conditions are met; and if the conditions are met, outputting the result, and if the conditions are not met, returning to the step two.
Further, in the first step, initializing the number m of the artificial ants, a heuristic factor alpha, a hope heuristic factor beta, an information persistence factor rho and information intensity Q; the number M of the artificial fish, the step length step, the visual field range of the artificial fish and the crowding factor delta are initialized.
Further, in the second step, the ant colony algorithm and the artificial fish colony algorithm are alternately iterated, and the superiority or inferiority of the solution is determined by comparison; in the same problem, if the ant colony algorithm searches a preferred solution first, the preferred solution is randomly placed at the position of an artificial fish in the artificial fish colony; if the artificial fish swarm algorithm searches a preferred solution first, the preferred solution is randomly placed at the position of one artificial ant in the artificial ant swarm.
Further, in step three, if
If the center of the population has more food and is not crowded, the population is carried out in the direction of the central position of the population, the step four is carried out, and if the population is not crowded, the step four is carried out
If the population is crowded, keeping the population in the original state, randomly moving one step, and repeatedly executing the second step, wherein n in the formulafIndicating the number of groups in the current domain, ycFitness value, y, representing the center positioniA fitness value representing the current state.
Further, in step four according to
To update the pheromone density and to update the bulletin board information, where τij(t) denotes the t th leechPheromones when ants go from node i to node j; when an ant k passes j from node i in this cycle,
otherwise, the value is 0, Q represents the information intensity, namely the amount of the released information of the artificial ants, lkRepresents the path length of the kth ant in the cyclic search process.
Further, in step five, the formula y is usedi＝f(xi) Finding the fitness where xiRepresenting the position vector, y, of the i-th artificial fishiExpressing the fitness value of the i-th artificial fish, wherein f (x)i) The method is characterized in that the optimal value of a single fish is obtained by taking the food concentration of the position of the artificial fish as the adaptive value of an objective function and taking the state of the single fish as the optimal value and bringing the optimal value into the optimal value.
Further, in the sixth step, whether a condition for ending the algorithm process is met is judged, the condition for ending the algorithm is that the maximum iteration number is reached or the error reaches the target precision requirement, if the condition is met, the optimal solution, namely the lowest value of the energy function of the three-dimensional Toy model, is output, the algorithm is ended, and if the condition is not met, the second step is returned to continue to execute the alternate iteration to generate a new initial solution.
By analyzing the advantages and the disadvantages of the ant colony algorithm and the fish colony algorithm, the method adopts the complementary principle, improves and fuses the two colony intelligent algorithms, and calls the improved colony intelligent algorithm as an improved ant colony fish colony algorithm (ACO-AFSA for short). The improved ant colony fish swarm algorithm is applied to protein folding prediction, the performance of the colony intelligent algorithm is better than that of a single algorithm, and the optimal effect of a target problem can be achieved better.
The ant colony algorithm and the artificial fish colony algorithm have many commonalities. First, the artificial ants in the ant colony algorithm always return the food to the ant hole by the shortest path, and the artificial fish in the artificial fish colony algorithm is also the most abundant zone that likes to gather the food in water. Furthermore, the search behavior of artificial ants and the feeding behavior of artificial fish are also extremely striking similarities. Besides, the pheromone concentration in the ant colony algorithm and the bulletin board function in the artificial fish colony algorithm are the same.
The greatest difference between the artificial fish swarm algorithm and the ant swarm algorithm is the appearance of the crowdedness factor in the artificial fish swarm algorithm, and because the greatest difference is similar in many places, two independent swarm intelligence algorithms are improved and fused to form a new improved swarm intelligence algorithm, namely the ant swarm fish swarm algorithm (ACO-AFSA for short). The improved algorithm references the global convergence performance of the ant colony algorithm and the rapid convergence capability of the artificial fish colony, so that local optimization is easier to escape, global optimization is achieved, and the precision of the result is guaranteed.
In the calculation process, the ant colony algorithm and the artificial fish colony algorithm are alternately iterated, and whether the solution is excellent or not is determined through comparison. In the same problem, if the ant colony algorithm searches a preferred solution first, the preferred solution is randomly placed at the position of an artificial fish in the artificial fish colony, so that the aim of enriching the colony, improving the efficiency and improving the precision of the artificial fish colony algorithm is fulfilled. If an optimal solution is searched by the artificial fish swarm algorithm, the optimal solution is randomly placed at the position of an artificial ant in the artificial ant swarm, so that the purposes of enriching the swarm and accelerating the optimization are achieved.
The improved ant colony fish swarm algorithm has the capability of fast searching, maintains the global convergence and the result precision of the ant colony algorithm, successfully overcomes the defect that the ant colony algorithm is easy to fall into local optimum, greatly improves the convergence speed, and is satisfactory to the improved ACO-AFSA algorithm.
Protein folding prediction faces two major problems, one is how to convert a fussy protein structure into a simple mathematical model, so that the problem becomes simplified; another is how to find an efficient search method for efficient protein conformation searches. The current simplified protein structure models mainly comprise Toy models, HP lattice point models, three-dimensional cubic lattice models, hexagonal lattice point models and the like. The invention applies the improved ACO-AFSA group intelligent algorithm to the protein folding prediction problem of the three-dimensional Toy model in an important way to verify the effectiveness of the intelligent algorithm.
In IIIIn the dimension Toy model, not only the bond angle θ is involved, but also the included angle between two planes formed by three consecutive peptide bonds is considered, which is called the torsion angle and is marked as β3,β4,...,βN-1,βiE (-pi, pi). When the two-plane torsion angle formed by three peptide bonds is 0, the three peptide bond positions are shown to be in the same plane. The positive and negative values of β represent the clockwise and counterclockwise directions of the rotation. Fig. 2 shows the structure of the three-dimensional Toy model in space.
Regardless of the length of the amino acid sequence, their energy functions are the same, being the sum of the van der Waals attractive potential and the bending potential. The length of a protein sequence is N, and the van der Waals potential energy between separated residues is E1Comprises the following steps:
ξiand xijRepresents the kind of amino acid residue, and when the specified residue is A, the xi value is 1; when residue is B, ξ has a value of-1.
Its values are only three cases, 1/2, -1/2, 1. These three values represent strong attraction between AA, mutual repulsion between AB and weak attraction between BB, respectively, showing the properties of the protein from the side; r isijIndicates the distance between residues.
As can be seen from the formula: the van der waals attractive potential is determined by the hydrophobicity, polarity, and near-far distance of non-adjacent residues.
The two-dimensional Toy model is the basis of the three-dimensional Toy model, and the three-dimensional Toy model has one more torsion angle than the two-dimensional Toy model, so that the energy function is added with a dihedral angle potential energy on the basis of the deformation of the two-dimensional Toy model.
Therefore, the energy function of the three-dimensional Toy model is:
in the formula, k1And k2As a coefficient, it indicates the strength of the inter-residue effect, and the coefficient value is defined as 0.5 or-1.
In the three-dimensional Toy model, the study of the protein folding prediction can be translated into when the energy value of the evaluation function E is minimal, which can be expressed as:
although there are many similarities between the two-dimensional Toy model and the three-dimensional Toy model, it is clear that they are of both types. The three-dimensional Toy model creates a stereo network in space and becomes more complex. However, the protein folding prediction of the three-dimensional Toy model can more intuitively embody the spatial structure of the protein and has high exploration value.
Today, few researchers have tested true sequences using swarm intelligence algorithms for prediction of protein folding. To further illustrate that the improved algorithm of the design is prominent, this part will use the real protein sequence simulation test. For comparative and convincing purposes, the energy values obtained with the existing algorithm were compared, as shown in table 1.
TABLE 1 true protein sequences
Of the three true protein sequences, Q, R, D, N, S, K, E, Y, F, H, K, O, T is a polar residue; G. v, L, A, I, C, M, V, P is a hydrophobic group. In the prediction of protein folding in the three-dimensional Toy model, the actual protein sequence was reduced to a sequence containing B and a according to the method of the present application, i.e., the internationally widely used Fibonacci (Fibonacci) sequence, as shown in table 2.
TABLE 2 reduced A, B-containing sequences
The conversion of the true protein sequence to an AB aligned sequence can be predicted using the improved algorithm of the present application. The three sequences were tested using MATLAB7.0 software, still on an Intel (R) Core i32.40GHz CPU,2.00GB RAM and 32-bit operating system. Important parameters in the algorithm are set as follows: α is 2.0, β is 3.0, ρ is 0.65, Q is 100, and δ is 0.60. The maximum number of iterations is 80 and the number of attempts is 80. The selected M value for the first two sequences is 15, the selected M value for the last three sequences is 35, and the test results are shown in Table 3. In this table, the present application compares the test results with the existing results, and the comparison results are that the improved algorithms used in the present application all yield lower energy minima than the existing methods. The results of the comparison are shown in line 3. Especially for the protein sequence with the length of 13, the energy value obtained by the algorithm in the text is slightly better than that of the existing method; especially for the length 38 sequence, the effect is more obvious. The comparison of these visual data is significant enough to explain the improved algorithm designed by this application.
TABLE 3 test results
The application applies an improved group intelligence algorithm to a three-dimensional Toy model, tests a real protein sequence, compares the obtained result with the existing result, and gives a comparison line chart shown in figure 3. The result of the application is more excellent, and the conformation diagram can basically reflect the physical properties of the real protein, thereby further explaining the feasibility and the effectiveness of the group intelligent algorithm applied by the application.
In the present application, specific information of documents [65] and [66] is as follows:
[65] protein folding structure prediction [ C ] of Wuhan university of science and technology based on AB nong's model and genetic annealing algorithm 2007
[66] Zhanxiaong, litting, reed. multiple population particle population optimization algorithm based on TOY model protein folding prediction study [ J ]. computer science.2008, 35 (10): 230-235.
Claims (5)
1. A protein folding prediction method based on an ant colony fish swarm algorithm is characterized by comprising the following steps:
the method comprises the following steps: initializing and setting an ant colony algorithm, and initializing and setting an artificial fish colony algorithm to form a new initial population;
step two: alternate iterations generate new initial solutions: performing alternate iteration on the ant colony algorithm and the artificial fish colony algorithm, and determining whether the solution is optimal or not by comparison; in the same problem, if the ant colony algorithm searches a preferred solution first, the preferred solution is randomly placed at the position of an artificial fish in the artificial fish colony; if the artificial fish swarm algorithm searches a preferred solution first, the preferred solution is randomly placed at the position of one artificial ant in the artificial ant swarm;
step three: judging the degree of congestion; if the population is crowded, the population keeps the original state, one step is carried out randomly, the step two is repeatedly executed, if the population is not crowded, the step one step is carried out towards the central position of the species group, and the step four is executed by the population;
step four: updating pheromone concentration and bulletin board information;
step five: calculating the fitness by the formula yi＝f(xi) Finding the fitness where xiRepresenting the position vector, y, of the i-th artificial fishiRepresenting the fitness of the ith artificial fish;
step six: judging whether a condition for finishing the algorithm process is met; and if the conditions are met, outputting the result, and if the conditions are not met, returning to the step two.
2. The method for predicting protein folding based on ant colony fish swarm algorithm according to claim 1, wherein: in the first step, initializing the number m of artificial ants, a heuristic factor alpha, a hope heuristic factor beta, an information persistence factor rho and information intensity Q; the number M of the artificial fish, the step length step, the visual field range of the artificial fish and the crowding factor delta are initialized.
3. The method for predicting protein folding based on ant colony fish swarm algorithm according to claim 1, wherein: in step three, if
If the center of the population has more food and is not crowded, the population is carried out in the direction of the central position of the population, the step four is carried out, and if the population is not crowded, the step four is carried out
If the population is crowded, keeping the population in the original state, randomly moving one step, and repeatedly executing the second step, wherein n in the formulafIndicating the number of populations in the current neighborhood, ycDenotes the fitness of the center position, yiIndicating the fitness of the current state, and δ is a congestion factor.
4. The method for predicting protein folding based on ant colony fish swarm algorithm according to claim 1, wherein: in step four according to
To update the pheromone density and to update the bulletin board information, where τij(t) represents pheromone when the t-th ant goes from node i to j, rho is an information persistence factor, and m is the number of initialized artificial ants; when an ant k passes j from node i in this cycle,
otherwise, the value is 0, Q represents the information intensity, namely the amount of the released information of the artificial ants, lkRepresents the path length of the kth ant in the cyclic search process.
5. The method for predicting protein folding based on ant colony fish swarm algorithm according to claim 1, wherein: and step six, judging whether a condition for finishing the algorithm process is met, wherein the condition for finishing the algorithm is that the maximum iteration number is reached or the error reaches the target precision requirement, if the condition is met, outputting an optimal solution, namely the lowest value of the energy function of the three-dimensional Toy model, terminating the algorithm, and if the condition is not met, returning to the step two to continue to execute the alternate iteration to generate a new initial solution.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201811384813.XA CN109524057B (en) | 2018-11-20 | 2018-11-20 | Protein folding prediction method based on ant colony fish swarm algorithm |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201811384813.XA CN109524057B (en) | 2018-11-20 | 2018-11-20 | Protein folding prediction method based on ant colony fish swarm algorithm |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN109524057A CN109524057A (en) | 2019-03-26 |
| CN109524057B true CN109524057B (en) | 2021-12-17 |
Family
ID=65776667
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201811384813.XA Active CN109524057B (en) | 2018-11-20 | 2018-11-20 | Protein folding prediction method based on ant colony fish swarm algorithm |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN109524057B (en) |
Families Citing this family (3)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN110176278B (en) * | 2019-05-24 | 2021-09-28 | 河海大学 | Modeling method of continuous reaction kinetic model for generating dichloroacetonitrile by amino acid chlorination |
| CN110610742B (en) * | 2019-09-20 | 2023-12-19 | 福建工程学院 | Functional module detection method based on protein interaction network |
| CN111767978B (en) * | 2020-06-30 | 2024-02-06 | 苏州大学 | Brain white matter fiber tracking method based on bidirectional ant colony algorithm of communication mechanism |
Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101236616A (en) * | 2008-02-27 | 2008-08-06 | 中山大学 | Protein Folding Optimization Method Based on Ant Colony Algorithm |
| CN101436230A (en) * | 2008-12-25 | 2009-05-20 | 哈尔滨工程大学 | Snake simulating method in protein folding emulation |
| US8326547B2 (en) * | 2009-10-07 | 2012-12-04 | Nanjingjinsirui Science & Technology Biology Corp. | Method of sequence optimization for improved recombinant protein expression using a particle swarm optimization algorithm |
| CN102915407A (en) * | 2012-10-23 | 2013-02-06 | 福建师范大学 | Prediction method for three-dimensional structure of protein based on chaos bee colony algorithm |
-
2018
- 2018-11-20 CN CN201811384813.XA patent/CN109524057B/en active Active
Patent Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101236616A (en) * | 2008-02-27 | 2008-08-06 | 中山大学 | Protein Folding Optimization Method Based on Ant Colony Algorithm |
| CN101436230A (en) * | 2008-12-25 | 2009-05-20 | 哈尔滨工程大学 | Snake simulating method in protein folding emulation |
| US8326547B2 (en) * | 2009-10-07 | 2012-12-04 | Nanjingjinsirui Science & Technology Biology Corp. | Method of sequence optimization for improved recombinant protein expression using a particle swarm optimization algorithm |
| CN102915407A (en) * | 2012-10-23 | 2013-02-06 | 福建师范大学 | Prediction method for three-dimensional structure of protein based on chaos bee colony algorithm |
Non-Patent Citations (2)
| Title |
|---|
| Application of Improved Ant Colony Algorithm;Hongyan Shi等;《2008 Fourth International Conference on Natural Computation》;20081107;284-288 * |
| 基于智能算法的蛋白质折叠研究;于杨;《中国优秀硕士学位论文全文数据库基础科学辑》;20100615(第06期);A006-29 * |
Also Published As
| Publication number | Publication date |
|---|---|
| CN109524057A (en) | 2019-03-26 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Sivanandam et al. | Genetic algorithms | |
| CN109524057B (en) | Protein folding prediction method based on ant colony fish swarm algorithm | |
| Jiang et al. | Protein folding simulations of the hydrophobic–hydrophilic model by combining tabu search with genetic algorithms | |
| US10713565B2 (en) | Iterative feature selection methods | |
| Shi et al. | Skill-based model-based reinforcement learning | |
| Xu et al. | Multi-objective graph heuristic search for terrestrial robot design | |
| CN109241291A (en) | Knowledge mapping optimal path inquiry system and method based on deeply study | |
| Coates et al. | Exploring three-dimensional design worlds using lindenmayer systems and genetic programming | |
| CN113744799A (en) | End-to-end learning-based compound and protein interaction and affinity prediction method | |
| CN102915407B (en) | Prediction method for three-dimensional structure of protein based on chaos ant colony algorithm | |
| CN115933669B (en) | Mobile robot path planning method based on improved butterfly optimization algorithm | |
| Li et al. | Foldingzero: Protein folding from scratch in hydrophobic-polar model | |
| CN111611373A (en) | A Robot-Oriented Embodied Active Scene Description Method | |
| Abramovich et al. | Multi-objective topology and weight evolution of neuro-controllers | |
| Ji et al. | Ant colony optimization with multi-agent evolution for detecting functional modules in protein-protein interaction networks | |
| CN114995390B (en) | A mobile robot path planning method based on the mayfly algorithm with dynamic adaptive parameter adjustment | |
| Lin et al. | An efficient hybrid Taguchi-genetic algorithm for protein folding simulation | |
| Seyde et al. | Strength through diversity: Robust behavior learning via mixture policies | |
| CN117420832A (en) | Robot path planning method based on improved GTO | |
| Yu et al. | Deep reinforcement learning for protein folding in the hydrophobic-polar model with pull moves | |
| US20200143256A1 (en) | Iterative feature selection methods | |
| Zhang et al. | Improved particle swarm optimization algorithm for 2D protein folding prediction | |
| Ezgi | Elitist animal migration optimization for protein structure prediction based on 3D off-lattice model | |
| Boumedine et al. | Protein folding simulations in the hydrophobic-polar model using a hybrid cuckoo search algorithm | |
| CN109243525B (en) | A Phased Protein Structure Prediction Method Based on Population Entropy |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |