# Clustering with constraints

I have a dataset of this form:

chrX posX labelX

where chrX refers to the chromosome number, posX refers to location, and labelX is a categorical variable with 3 labels. For example:

chr1 3223 1
chr1 3200 2
chr1 3100  1
chr1 1000 2
chr2 1000 1
chr1 3210 3


I want to be cluster these data with certain constraints (thus, this is no longer what 'clustering' typically is), such that, for each chromosome, the sites which are within, say $\pm 30$ positions are together, the constraint being they should have unique labels.

For example, an expected output would be:

chr1 : 3223(1) 3200(2) 3210(3) Notice how sites like chr1 3100 1 are not part of the 'cluster'.

One approach would be to simply calculate pairwise differences between all such sites, and grow the cluster taking care of unique labels.

Are there more elegant approaches to solve such problems?

• Could you clarify? Do you cluster chr1 and chr2 independently (then it could be ignored)? Do you want your clusters to be lists of positions, each within distance 30 from its neighbour, and each position of a different type? – Valentas Oct 9 '15 at 5:02
• Is the goal to create as many clusters of (1,2,3) as possible, leaving some unassigned? Or to create as many clusters of at least size 2 as possible? If there isn't a concrete metric you'd like to optimize, you will have trouble defining the problem as a clustering one. – jamesmf Nov 20 '15 at 14:52

Each clustering algorithm in my knwledge is based on distance, which is calculated as pairwise differences. So I'm not sure if it is easy to find a general more elegant approach.

In you case you can calculate the distance and than override it based on your constraint.

Here an simple example reduced to one numerical dimension with distance threshold 30.

 nlst <- c(1,3,5, 36,39,42, 1001,1003,1005, 1036,1039,1042)

d <- dist(nlst, method="euclidean")
dr <- as.dist(ifelse(as.matrix(d) > 30, NA, 0))

1  2  3  4  5  6  7  8  9 10 11
2   0
3   0  0
4  NA NA NA
5  NA NA NA  0
6  NA NA NA  0  0
7  NA NA NA NA NA NA
8  NA NA NA NA NA NA  0
9  NA NA NA NA NA NA  0  0
10 NA NA NA NA NA NA NA NA NA
11 NA NA NA NA NA NA NA NA NA  0
12 NA NA NA NA NA NA NA NA NA  0  0


A scan through the points collecting those with distance zero will give the result clustering.

This should be always possible if your constraints are local (i.e. depending only on the two points for which you calculate the distance).