Revisiting spectral clustering: assessments and extended capabilities

Many techniques are being used for biological sequence analysis. Among them, the efficiency of Clustering techniques has emerged in many recent research works. Spectral clustering in general, and Gaussian Mixture Models (GMMs) in particular, have a demonstrated efficiency in clustering biological sequences having unknown similarity ratios. The pipeline of a tool, implementing the spectral clustering technique, consists of the following steps: i- sequence alignment, ii- pairwise affinity computation of the sequences, iii- Laplacian Eigenmap embedding of the data and GMM-based clustering. The choice of a certain tool or method, for two initial steps, can affect the quality of the resulting clustering. In the present paper, we assess the effect of using different sequence alignment tools and applying different affinity matrix types on the accuracy of the results. Inputting heterogeneous sequences, or ones that are subjected to Horizontal Gene Transfers (HGTs), a natural factor that can lead to high divergence between related sequences, is also experimented with. Our main contribution is showing the most appropriate use cases for different alignment tools and affinity matrices. Moreover, the ability of the spectral clustering technique to handle heterogeneous sequences and HGTs has been demonstrated.