Design and Implementation of Evolutionary Computation based Clustering Algorithm and its Application to Biological Sequence Analysis

Abstract

The present research work provides new insights into the applications of evolutionary computation based clustering algorithms to address various issues of biological sequence analysis. A novel nature-inspired adaptive evolutionary clustering algorithm called AEC-RAM has been proposed. This algorithm uses two novel gen eti c oper ators Rejecti on and Mi grati on . Th e Empi rical stud y suggests that AEC-RAM tend to automatically search more accurate clusters than classical K-Means and evolutionary clustering algorithm, without providing prior details about the number of clusters and relieve the necessitate to seed the initial centroids. The clustering process using AEC-RAM algorithm can discover more accurate clusters from multivariate datasets than the other algorithms. This could be due to the adaptive process taken up in the algorithm. In this process, each item in the dataset is migrated until it gets adapted in a cluster and simultaneously the algorithm adapts for its inter-cluster distance. Inter-cluster distance is represented as the average difference of fitment factor of clusters under investigation. The time complexity of AEC-RAM is O(n+logn). The biological sequence analysis issues such as pairwise sequence alignment, multiple sequence alignment, local alignment, and gene prediction were solved by using the proposed adaptive evolutionary algorithm for clustering by using a dynamic programming approach. A novel algorithm called MPSAGA has been proposed for pairwise sequence alignment of biological sequences. A benchmarking of the proposed algorithm has been performed with other popular pairwise sequence alignment algorithms. A new biological sequence representation method called positional matrix representation has also been introduced in the present work. The proposed MPSAGA aligner was implemented with and without positional matrix-based sequence representation and an empirical study has been performed to compare the effectiveness of the proposed biological sequence representation method.