# A Method for Degenerate Primer Design Based on Artificial Bee Colony Algorithm
## 3 The Proposed Algorithm
### Algorithm Description  
In order to solve the problem of degenerate primer design, the DPD-HABC algorithm includes four processes: initialization, employed bee foraging, onlooker bee foraging, and scout bee foraging. In the initialization stage, the pheromone matrix and the identity matrix contained in the algorithm are initialized. The value of each element in the pheromone matrix is set to the maximum value, max, and each element in the identity matrix is set to 0. of the method for calculating the probability of attracting onlooker bees and the method for allocating onlooker bees are the same as in the standard artificial colony algorithm. The specific process of the algorithm is shown in Algorithm 1.  
```
Input f: the fitness evaluation function \(\Omega\):constraint condition of degenerate primer design Output \(S_{bs}\): the optimal primer pairs 1. Begin // Initialization process 2. Initialize food sources and pheromone trails and heuristic information 3. repeat //employed bee foraging process 4. for each employed bee do 5. Initialize its local phoneme matrix and the Lmark matrix 6. Generate a new candidate food source \(S\) and evaluate it 7. Construct a complete primer pairs \(S\) generated by Equation (13) if\((S)<t(S_{bs})\)then 9. \(S_{bs}\gets S\) 10. end if //onlooker bee foraging process 12. for each onlooker bee do 13. produce the new solutions \(v_{i}\) from the solutions \(S_{bs}\) generated by Equation (15) 14. apply the greedy selection process between \(v_{i}\) and \(S_{bs}\) 15. end for //scout bee foraging process 16. for each scout bee do 17. if existing the abandoned solution \(S\) then 18. Send scouts based on the scout foraging strategy generated by Equation (16) 19. end if 20. end for 21. for each component \(i\) in graph do 22. \(\tau_{ij}\leftarrow\) update pheromone 23. end for 24. Memorize the best food source positions (solutions) 25. until maximum fitness evolution number reached or other termination condition met 26. return \(S_{bs}\) 27. End
```  
**Algorithm 1** DPD-HABC Algorithm for Degenerate Primer Design  
The analysis of the time complexity and space complexity of the DPD-HABC algorithm for solving the problem of degenerate primer design is as follows: O(\(n\)+\(m\)) operations are required when the employed bees conduct a neighborhood search, based on the location of the food source in their memory, to find a better food source attached to the food source; the onlooker bees choose a certain food according to the dance of the employed bees in the hive, and it takes O(\(n*m\)) operations to calculate the probability formula. It takes O(\(n\)) operations for the scout bee to randomly select a food item. Thus, the total time complexity can be calculated as shown in Formula (17).  
\[T(n)=O(N_{c}*n^{2}*m) \tag{17}\]  
where \(N_{c}\) is the number of cycles, \(n\) is the number of base pair combinations run, and m is the total number of bees. Thus, the time complexity increases with increasing DNA template size. The total space complexity is shown in Formula (18).  
\[S(n)=O(n^{2})+O(n*m) \tag{18}\]