A novel clustering method via nucleotide-based Fourier power spectrum analysis

Abstract

A novel clustering method is proposed to classify genes or genomes. This method uses a natural representation of genomic data by binary indicator sequences of each nucleotide (adenine (A), cytosine (C), guanine (G), and thymine (T)). Afterwards, the discrete Fourier transform is applied to these indicator sequences to calculate spectra of the nucleotides. Mathematical moments are calculated for each of these spectra to create a multidimensional vector in a Euclidean space for each gene or genome sequence. Thus, each gene or genome sequence is realized as a geometric point in the Euclidean space. Finally, pairwise Euclidean distances between these points (i.e. genome sequences) are calculated to cluster the gene or genome sequences. This method is applied to three sets of data. The first is 34 strains of coronavirus genomic data, the second is 118 of the known strains of Human rhinovirus (HRV), and the third is 30 bacteria genomes. The distance matrices are computed based on the three sets, showing the distances from each point to the others. We used the complete linkage clustering algorithm to build phylogenetic trees to indicate how the distances among these sequence correspond to the evolutionary relationship among these sequences. This genome representation provides a powerful and efficient method to classify genomes and is much faster than the widely acknowledged multiple sequence alignment method.

Fig. 1

These phylogenetic trees show the 30 coronavirus genomes as well as the four outgroup genomes. Our method has split them into the correct groups: outgroup and Groups 1-5.

Fig. 2

These phylogenetic trees show the 116 human rhinovirus genomes as well as the three outgroup genomes. Our method has split them into the correct groups (HRV-A, HRV-B, HRV-C, and HEV-C (outgroup)) in complete linkage clustering, but there are seven misplaced HRV-A genomes in the tree created by average linkage clustering.

Fig. 3

These phylogenetic trees show the 30 bacteria genomes. Our method has split them into the correct families: Enterobacteriaceae, Staphylococcaceae, Rhodobacteriaceae, Burkholderiaceae, Bacilleceae, Spirochaetaceae, Clostridiaceae, and Desulfovibrionaceae.