Biogeography-based Optimization Alogrithm And Application On Biological Sequence Motif Discovery

Motif discovery of biological sequences is one of the most important research topics in life science. It is also important to understand the function and regulation of gene. The methods based on string analysis and probability theory have achieved great success, but these methods also have some problems. For example, the string analysis methods can only work well for short and constrained motifs, and have bad performance with long sequences. On the other hand, the probability methods are sensitive to the initial data and cannot guarantee the global optimal solution.With the rapid development of computational intelligent technology, evolutionary computing has attracted more and more attentions for the features of strong global search ability, low sensitivity to initial conditions, and independence of domain knowledge. As a new type of evolutionary algorithms, the Biogeography-Based Optimization(BBO) algorithm which imitates the natural biological species’ migration process has gained great success in many applications. In this dissertation we study and design several improved biogeography optimization algorithm for motif discovery problem, providing a new approach for motif discovery in biological sequences.Firstly, we classify the BBO algorithm as a swarm intelligence algorithm, design the patterns and framework model of BBO algorithm based on a unified framework of swarm intelligence. Classifying the BBO algorithm into swarm intelligence framework has important significance for the research of BBO algorithm. Meanwhile, it is beneficial for the development of intelligent algorithms, including evolutionary algorithms.Secondly, to improve the accuracy and efficiency of the traditional methods for motif discovery in biological sequences, an improved biogeography-based optimization algorithm is proposed. The migration operators and mutation operators of BBO algorithm are modified to better meet the requirements of motif discovery. Furthermore, an integrated mechanism for the generation of initial populations was designed. The proposed algorithm can gain meaningful motifs with a fast convergence rate. The experiment results on two commonly used datasets demonstrated that the validity and effectiveness of the proposed algorithm.Thirdly, in order to enhance the ability of global and local exploration of the BBO algorithm, we proposed a hybrid optimization algorithm called BBO/DE/GEN(Biogeography-Based Optimization/Differential Evolution/Generation) algorithm, based on both the Biogeography Optimization and DE(Differential Evolution) algorithm with enhancement operator. The BBO/DE/GEN algorithm combines the exploitation of BBO with the exploration of DE effectively; the mutation operators of BBO are modified based on differential evolution algorithm, and the migration operators of BBO are modified based on the number of iterations. To verify the performance of BBO/DE/GEN algorithm, it is applied to the global numerical optimization problem and the sequence pattern discovery problem respectively. Six benchmark functions with a wide range of dimensions and diverse complexities are employed for global numerical optimization problem. Experimental results indicate that the improved algorithm is efficient. Compared with BBO and BBO/DE(Biogeography-Based Optimization/Differential Evolution), BBO/DE/GEN performs better, at least equally, in terms of the mean and the optimal value of the final solutions. For sequence pattern discovery problem, it can generate the promising candidate solutions. Statistical comparisons with some typical existing approaches on three commonly used datasets are provided, which demonstrates that the validity and effectiveness of the BBO/DE/GEN algorithm in terms of the quality of the final solutions and the convergence rate.Finally, to further improve the accuracy of predicting motif in biological sequences, we proposed a hybridization of adaptive parameter BBO algorithm and DE algorithm, namely ABBO/DE/GEN algorithm. ABBO/DE/GEN adaptively changes migration probability and mutation probability based on the relation between the cost of fitness function and average cost every generation, and the mutation operators of BBO were modified based on DE algorithm and the migration operators of BBO were modified based on number of iteration to improve performance. And hence it can generate the promising candidate solutions. To verify the performance of ABBO/DE/GEN, eight benchmark functions with a wide range of dimensions and diverse complexities are employed. ABBO/DE/GEN performs better compared with BBO/DE/GEN in terms of the quality of the final solutions and the convergence rate. Experiment results indicate its effectiveness and efficiency. Statistical comparisons with some typical existing approaches on three commonly-used datasets are provided, The experimental results on motif discovery problem in biological sequences also show that ABBO/DE/GEN algorithm have good performance for predicting motif in long sequences.