SHIPS (Spectral Hierarchical clustering for the Inference of Population Structure) is a non-parametric clustering algorithm that clusters individuals from a population into genetically homogeneous sub-populations from genotype data. After computing a pairwise distance matrix, the algorithm progressively divides the original population in two sub-populations by the use of a spectral clustering algorithm. The process is then iterated in each of the two sub-populations and so on. This leads to the construction of a binary tree, where each node represents a group of individuals. To determine the final clusters a tree pruning procedure and an estimation of the optimal number of clusters, that is a gap statistic, are applied. In such an approach both the final clustering of the individuals and the number of clusters are estimated by the method.

The algorithm SHIPS is implemented with the software R that can be downloaded from the (CRAN web page) and is divided in several functions :

• ships.cluster constructing the tree and providing several clustering possibilities
• ships.gap that estimates the final number of clusters
• ships.plotCluster that provides a graphical representation of the clustering
• ships.plotGap that plots the criterion used to estimate the final number of clusters

• Source code: Ships.r
• R package: Ships.tar.gz
• Documentation: Documentation.pdf

• Inference of population structure in genetics studies with a novel divisive clustering strategy, M. Bouaziz et al. Statistical Methods for Post-Genomics Data 2011, Paris, France.

• SHIPS: Spectral Hierarchical Clustering for the Inference of Population Structure, M. Bouaziz et al. European Mathematical Genetics Meeting 2012, Göttingen, Germany.

Matthieu Bouaziz