A Novel Method to Predict Genomic Islands Based on Mean Shift Clustering Algorithm

Abstract

Genomic Islands (GIs) are regions of bacterial genomes that are acquired from other organisms by the phenomenon of horizontal transfer. These regions are often responsible for many important acquired adaptations of the bacteria, with great impact on their evolution and behavior. Nevertheless, these adaptations are usually associated with pathogenicity, antibiotic resistance, degradation and metabolism. Identification of such regions is of medical and industrial interest. For this reason, different approaches for genomic islands prediction have been proposed. However, none of them are capable of predicting precisely the complete repertory of GIs in a genome. The difficulties arise due to the changes in performance of different algorithms in the face of the variety of nucleotide distribution in different species. In this paper, we present a novel method to predict GIs that is built upon mean shift clustering algorithm. It does not require any information regarding the number of clusters, and the bandwidth parameter is automatically calculated based on a heuristic approach. The method was implemented in a new user-friendly tool named MSGIP--Mean Shift Genomic Island Predictor. Genomes of bacteria with GIs discussed in other papers were used to evaluate the proposed method. The application of this tool revealed the same GIs predicted by other methods and also different novel unpredicted islands. A detailed investigation of the different features related to typical GI elements inserted in these new regions confirmed its effectiveness. Stand-alone and user-friendly versions for this new methodology are available at http://msgip.integrativebioinformatics.me.

Fig 1. Mean shift algorithm procedure for a data point x_i.

The bold filled circles with arrows represent the iteration, while the pointed circles represent the window used in density estimation until the convergence is achieved at the nth iteration.

Fig 2. Graphics representing the z′ curves for following six different bacteria genomes.

(A) Corynebacterium glutamicum ATCC 13032, (B) Vibrio vulnificus CMCP6 chromosome I, (C) Rhodopseudomonas palustris CGA009, (D) Streptococcus mutans UA159, (E) Vibrio cholerae chromosome II e (F) Vibrio vulnificus YJ016 chromosome I. Black lines represents the genomic islands identified by the mean shift method.