How to select the right inflation parameter for clustering?

[AmayAgrawal]

Hi everyone,

I am doing a pan-genome analysis for my study and for that I am using a Roary software which basically uses mcl for clustering the protein sequences. I read that on changing the value of the inflation parameter, the granularity of the clusters changes. It would be great if someone can suggest me as to how can I pick the right inflation parameter for clustering?

[micans]

Hi, good question.
It would be best to ask the Roary people for advice here, but I'll make some general points.

• the default value 2 works well generally.
• a set of values to try would be 1.4 1.6 2 3 4 .
• for evaluation, it depends on the domain. Sometimes just looking at the cluster sizes can be quite informative, both considering the size of the largest clusters (you'll see more of those at lower inflation values) and the number of small clusters/singletons (you'll see more of those at higher values).
• in some cases there can be some other yardstick or gold standard (on a subset of the data) to work with, but I appreciate this is not often the case and if it exists it implies more work.
• I'm currently working on a method to integrate clusterings at multiple levels of inflation that is close to release. This will generate two things - a set of resolution-based clusterings and a hierarchical clustering, so even with this there will still be choices.

[AmayAgrawal]

Hi,

Thanks for the suggestion. As you mentioned, I have tried clustering at different inflation parameter like 1.4, 2 and 4. Next I was looking if there are any ways to see clustering at which inflation parameter is better as compared to other inflation parameter. While looking at the mcl manual, I found that we can use certain cluster validation tools like clm dist, clm info and clm meet. I used clm info to compare my clustering and I get the output as a table shown below:

Inflation parameter	Efficiency	Massfrac	Areafrac	max	ctr	avg	min	DGI	TWI	TWL	sgl	qrt
1.5	0.81609	0.99191	0.00022	479	25.6	3.3	1	479	2715	8	20631	29029
2	0.83623	0.98388	0.00019	475	22.2	3.2	1	475	2951	8	20639	29609
4	0.84396	0.94924	0.00015	258	17.3	3.0	1	258	3550	6	21308	31307

Can someone suggest me as to how can I choose the right inflation parameter from the above table?

[micans]

Hi, this is a subject close to my heart. Although this table is somewhat informative (I'll get to that), I don't really see clustering as an optimisation problem - any optimisation criterion will almost certainly favour a certain range of granularity/resolution. For example, 'efficiency' tends to favour higher inflation values (as it does here), whereas 'modularity' (will be part of clm info in forthcoming release) favours lower inflation values.

This table is quite striking at first sight, as the clusterings seem fairly consistent across different inflation values; the number of singletons does not change drastically and neither do area frac and mass frac. So I'd go with the default value 2 for inflation. You could also do

clm dist <list-of-cluster-file-names>

This will say a bit more about how close/different the clusterings are - I'm happy to comment on that. The largest cluster size at inflation 2 is 475 and a randomly chosen node has expected cluster size 222 (the ctr column). If cluster sizes are informative you can do e.g.

clxdo granularity_largest 50 <list-of-cluster-file-names>

to check sizes of largest clusters (this is for release mcl-14-137).

[AmayAgrawal]

Hi,

Thanks for the explanation. As you mentioned in the previous comment that 'efficiency' tends to favour higher inflation values and it was also the case in previous table, I wanted to see how efficiency pans out over a large range of inflation parameter value. For this I performed clustering at various inflation paramters like 1.5, 2, 2.5... like this upto 7 in the step size of 0.5, and the results are quite interesting to me. Below is the clm info output for different inflation parameters:

Inflation parameter	Efficiency	Massfrac	Areafrac	max	ctr	avg	min	DGI	TWI	TWL	sgl	qrt
1.5	0.82200	0.99065	0.00022	479	24.9	3.2	1	479	2783	8	20631	29123
2	0.83626	0.98387	0.00019	475	22.2	3.2	1	475	2951	8	20639	29610
2.5	0.84274	0.97591	0.00017	258	19.8	3.2	1	258	3104	7	20693	29977
3	0.84552	0.96609	0.00016	258	18.8	3.1	1	258	3276	7	20882	30465
3.5	0.84555	0.95709	0.00015	258	17.8	3.1	1	258	3414	7	21106	30935
4	0.84397	0.94924	0.00015	258	17.3	3.0	1	258	3550	6	21308	31307
4.5	0.84205	0.94226	0.00014	258	16.8	3.0	1	258	3657	6	21496	31627
5	0.84119	0.93676	0.00014	256	16.2	3.0	1	256	3745	6	21617	31869
5.5	0.83940	0.93079	0.00013	239	15.7	3.0	1	239	3833	6	21778	32094
6	0.83704	0.92536	0.00013	217	15.2	2.9	1	217	3908	6	21902	32285
6.5	0.83509	0.92090	0.00013	217	14.9	2.9	1	217	3967	6	22000	32453
7	0.83385	0.91731	0.00012	217	14.6	2.9	1	217	4012	6	22093	32607

Looking at the above table, I can observe that 'efficiency' increases till a certain inflation parameter (3.5 in this case) and then it decreases after that point. Does that mean that 3.5 is a good inflation parameter as compared to other inflation parameters?

Also, I came across this where they have used 'modularity' as a measure to pick the best cluster inflation value among the range of inflation values. It would be good I think for my analysis also once it is available in the forthcoming release.

[micans]

Sometimes people consider it a less desirable trait of mcl that it generates quite a few singletons and small clusters. In this case I notice that from 2.5 upwards there seems to be a phase of stability where the largest cluster size remains the same. I would be tempted to thus pick 2.5. The logic is that stability of clustering across a range suggests stable/strong cluster structure; then to pick the smallest value so to have fewer small clusterings. On the other hand in your specific case (pangenome) there may be an issue of noisy data and you may not care about losing small clusters if they are likely to correlate with lower-quality data (I don't know).
Anyway, I think the stability/plateau criterion is more useful.

In the book chapter 'Using MCL to extract clusters from networks' we clustered proteins from a large set bacterial genomes: "Notice that at any inflation value there is a large number of clusters of size 28. These represent well defined groups of orthologs, containing one protein from each species." The point is that any inflation value, unfortunately, there may be both clusters that should still merge (in some sense of should) and also clusters that have already broken up (i.e. a set of nodes formed a meaningful cluster at a lower level of inflation and is split at the current level). This is an issue of clustering in general and of meaning existing at different resolution levels, and is not particular to mcl. Meaningful clusters at a high resolution (more granular) level will indicate tighter clusters, representing quite likely more recent orthology/paralogy relationships. Meaningful clusters at lower resolution (coarser) level likely represent more distant relationships. I hope to release something soonish to integrate multiple mcl clusterings into a single view.

It's completely understandable to seek to use modularity or efficiency to pick clusterings as it represents a somewhat agnostic choice. Nonethless, each criterion will consistenly favour a particular spot in the range of resolutions. I'd like, if possible, to make a choice that's more informed by external knowledge/requirements. It could be useful to have a few protein families (if that's what you're working with) as a yardstick and see how they fare in the different clusterings. Failing that, I'd favour a criterion like considering plateauing/stability of clusterings across a range of inflation (in the case of mcl).

[AmayAgrawal]

Hi,

Thanks a lot for a good insight on the data. I agree with the idea of considering stability of clusterings across a range of inflation parameter values. I looked at one of your previous comments where you mentioned that we can also use 'clm dist' to calculate the distance between different clusterings as this will give us a idea about how close/different the clusterings are. I think this will also further help us to determine whether we have a stable clustering in our data or not. Below is the table showing distances between different clustering at various inflation parameters generated using clm dist:

	2	2.5	3	3.5	4	4.5	5	5.5	6	6.5	7
1.5	2996	4811	6312	7439	8397	9183	9840	10502	11059	11509	11898
2		2277	4062	5375	6439	7285	7997	8696	9284	9768	10188
2.5			2145	3673	4803	5707	6543	7336	7973	8477	8910
3				1900	3137	4103	4995	5803	6473	7009	7470
3.5					1530	2647	3615	4502	5211	5794	6276
4						1358	2432	3385	4132	4752	5259
4.5							1305	2307	3123	3805	4341
5								1205	2090	2823	3396
5.5									1014	1817	2432
6										941	1628
6.5											762

I tried to look at the clm dist manual but did not get much idea about how to interpret these distances. It would be great if you can comment about the distances in the above table.

[micans]

Hello, would it be possible to run something like the following and share the output:
clm dist --chain LIST-OF-CLUSTERINGS | cut -f 1-3
where the LIST is ordered by inflation, e.g. from low to high. Normally specifying out.<network-name>* works; also it would be useful to know the total number of nodes in the network.

[AmayAgrawal]

Below is the table as you requested:

d	d1	d2	name1	name2
2996	2776	220	out.blast_90.mci.I15	out.blast_90.mci.I20
2277	2100	177	out.blast_90.mci.I20	out.blast_90.mci.I25
2145	1922	223	out.blast_90.mci.I25	out.blast_90.mci.I30
1900	1635	265	out.blast_90.mci.I30	out.blast_90.mci.I35
1530	1282	248	out.blast_90.mci.I35	out.blast_90.mci.I40
1358	1100	258	out.blast_90.mci.I40	out.blast_90.mci.I45
1305	1047	258	out.blast_90.mci.I45	out.blast_90.mci.I50
1205	951	254	out.blast_90.mci.I50	out.blast_90.mci.I55
1014	820	194	out.blast_90.mci.I55	out.blast_90.mci.I60
941	705	236	out.blast_90.mci.I60	out.blast_90.mci.I65
762	589	173	out.blast_90.mci.I65	out.blast_90.mci.I70

Also. the total number of nodes in the network are 110369

[micans]

As indicated somewhere in the tangled mass of documentation, you can roughly think of d/2N as the percentage of nodes that need adjusting to go from one cluster to the other. The smallest of d1/d2 indicates how close one is to being a subclustering of the other, again in the number of nodes that need adjusting.
Looking at the earlier table, the distance between inflation 1.5 and 7 is 11898, this translates to about 6% of nodes. Between 2.5 and 3 it is 2145 or about 1% of nodes, with 2.5 being 0.1% away from being a subclustering of 3 (that set of 0.1% nodes are generally what I would call peripheral or volatile nodes - difficult to cluster, living on the edge). I would go for either 2.0 (default mcl value) or 2.5, seeing that the largest cluster size remains constant for a while for inflation values above. All in all it looks like this data clusters quite consistently across the whole range and doesn't change that much. I wouldn't worry about picking the optimal inflation value. Even apart from resolution considerations mentioned before, especially in this case there does not seem to be that much difference.