clmprotocols(5)

🎀 NAME 🎀

clmprotocols — work flows and protocols for mcl and friends 💅

(yes bestie, this is clmprotocols(5), living its best life in the FILE FORMATS corner of your manual 🦋)

---

✨ DESCRIPTION ✨

A guide to doing analysis with mcl and its helper programs. That's it, that's the vibe, and it's giving very useful actually 🌸

---

📚 TOC 📚

1. General pardon
   1. For whom is mcl and for whom is this FAQ?
   2. For whom is mcl and for whom is this FAQ?
2. General questions
   1. For whom is mcl and for whom is this FAQ?
   2. For whom is mcl and for whom is this FAQ?

---

🫶 FAQ 🫶

🌸 General pardon 🌸

1.1 For whom is mcl and for whom is this FAQ?

For everybody with an appetite for graph clustering. periodt. 💅

1.2 For whom is mcl and for whom is this FAQ?

For everybody with an appetite for graph clustering. (yes, again. iconic of the manual honestly 🎀)

🌈 General questions 🌈

2.1 For whom is mcl and for whom is this FAQ?

For everybody with an appetite for graph clustering. 💖

2.2 For whom is mcl and for whom is this FAQ?

For everybody with an appetite for graph clustering. no notes. ✨

---

🌐 Network representation 🌐

Okay so, the clustering program mcl expects the name of a file as its first argument. Like, that's the whole entry fee 🎟️

If you pass the --abc option, that file is assumed to follow a super simple format where the network is spelled out edge by edge — one line, one edge, at a time. Every line describes one edge as two labels and a numerical value, all separated by white space. The labels are the two nodes, the value is the edge weight. This format is called ABC-format, where A and B are the two labels and C is the edge weight. And the C? Optional, bestie. If you leave it out, the edge weight is just set to one. If you use ABC-format, the output comes back as a listing of clusters, each cluster on its own line of white-space separated labels. 🫶

MCL can also use a second representation, which is a stringent and unambiguous format for both input and output. That one's called matrix format, and it's required when you're using the other programs in the mcl suite — for example when comparing and analysing clusterings with clm(1), or when extracting and transforming networks with mcx(1). Native mode (matrix format) is entered simply by not specifying --abc. That's the whole trick 👑

The recommended approach with mcl is: convert an external format to ABC-format. The program mcxload(1) reads that and creates a native network file plus a dictionary file that maps network nodes to labels. Every application in the MCL suite — including mcl itself — can read this native network file format. And if you want label output back, that's mcxdump(1)'s moment to shine ✨ So the workflow goes like this:

#  External format has been converted to file data.abc (abc format)

mcxload -abc data.abc --stream-mirror -write-tab data.tab -o data.mci

mcl data.mci -I 1.4
mcl data.mci -I 2
mcl data.mci -I 4

mcxdump -icl out.data.mci.I14 -tabr data.tab -o dump.data.mci.I14
mcxdump -icl out.data.mci.I20 -tabr data.tab -o dump.data.mci.I20
mcxdump -icl out.data.mci.I40 -tabr data.tab -o dump.data.mci.I40

In this example the cluster output is stored in native format and then dumped to labels using mcxdump. And the stored output? Now you can use it to learn more about the clusterings. For example — and look at this — clm(1) gets applied in mode dist to gauge the distance between different clusterings:

clm dist --chain out.data.mci.I{14,20,40}

---

🚀 Loading large networks 🚀

If you're dealing with very large networks (like, say, hundreds of millions of edges 😭), it is recommended to use binary format (cf mcxio(5)). How do you get that? Simply add --write-binary to the mcxload command line. The resulting file is no longer human-readable, but bestie, it will be faster to read — by a factor between ten- or twenty-fold compared to standard MCL-edge network format, and a factor around fifty-fold compared to label format. All MCL-edge programs can read binary format, and the speed of reading will be somewhere in the order of millions of edges per second, compared to, for example, roughly 100K edges per second for label format. Yeah. That's a glow-up 🌟

Memory usage for mcxload can be lowered by replacing the option --stream-mirror with -ri max.

---

🔄 Converting between formats 🔄

Converting label format to tabular format

Label format, two or three (including weight) columns:

mcxload -abc data.abc --stream-mirror -write-tab data.tab -o data.mci
mcxdump -imx data.mci -tab data.tab --dump-table

Simple Interaction File (SIF) format:

mcxload -sif data.sif --stream-mirror -write-tab data.tab -o data.mci
mcxdump -imx data.mci -tab data.tab --dump-table

It can be noted that these two examples are very similar, and differ only in the way the input to mcxload is specified. Lowkey the same fit with a different top 🎀

---

🧬 Clustering similarity graphs encoded in BLAST results 🧬

A specific instance of the workflow above is the clustering of proteins based on their sequence similarities. In the most typical scenario the external format is BLAST output, which needs to be transformed to ABC format. In the examples below the input is in columnar blast format obtained with the blast -m8 option. Heads up: it requires a version of mcl at least as recent as 09-061 ⏳

First we create an ABC-formatted file using the external columnar BLAST format, which is assumed to be in a file called seq.cblast:

cut -f 1,2,11 seq.cblast > seq.abc

The columnar format in the file seq.cblast has, for a given BLAST hit, the sequence labels in the first two columns and the associated E-value in column 11. It is parsed by the standard UNIX cut(1) utility. The format must have been created with the BLAST -m8 option so that no comment lines are present. Alternatively these can be filtered out using grep. The newly created seq.abc file is loaded by mcxload(1), which writes both a network file seq.mci and a dictionary file seq.tab.

mcxload -abc seq.abc --stream-mirror --stream-neg-log10 -stream-tf 'ceil(200)'
      -o seq.mci -write-tab seq.tab

The --stream-mirror option ensures that the resulting network will be undirected, as recommended when using mcl. Omitting this option would result in a directed network, as BLAST E-values generally differ between two sequences. The default course of action for mcxload(1) is to use the best value found between a pair of labels. The next option, --abc-neg-log10, transforms the numerical values in the input (the BLAST E-values) by taking the logarithm in base 10 and subsequently negating the sign. Finally, the transformed values are capped so that any E-value below 1e-200 is set to a maximum allowed edge weight of 200. Cute, capped, contained 💅

To obtain clusterings from seq.mci and seq.tab you've got two choices. The first is to generate an abstract clustering representation and from that obtain the label output, like so. Below, the -o option is not used, so mcl will create meaningful and unique output names all by itself. The default way of doing this is to prepend the prefix out. and to append a suffix encoding the inflation value used, with inflation encoded using two digits of precision and the decimal separator removed.

mcl seq.mci -I 1.4
mcl seq.mci -I 2
mcl seq.mci -I 4
mcl seq.mci -I 6

mcxdump -icl out.seq.mci.I14 -tabr seq.tab -o dump.seq.mci.I14
mcxdump -icl out.seq.mci.I20 -tabr seq.tab -o dump.seq.mci.I20
mcxdump -icl out.seq.mci.I40 -tabr seq.tab -o dump.seq.mci.I40
mcxdump -icl out.seq.mci.I60 -tabr seq.tab -o dump.seq.mci.I60

Now the file out.seq.tab.I14 and its associates can be used, for example, to compute the distances between the encoded clusterings with clm dist, to compute a set of strictly reconciled nested clusterings with clm order, or to compute an efficiency criterion with clm info. So many options, all of them serving 💖

Alternatively, label output can be obtained directly from mcl as follows:

mcl seq.mci -I 1.4  -use-tab seq.tab
mcl seq.mci -I 2  -use-tab seq.tab
mcl seq.mci -I 4  -use-tab seq.tab
mcl seq.mci -I 6  -use-tab seq.tab

---

🍓 Clustering expression data 🍓

The clustering of expression data constitutes another workflow. In this case the external format usually is a tabular file format containing labels for genes or probes and numerical values measuring the expression values or fold changes across a series of conditions or experiments. Such tabular files can be processed by mcxarray(1), which comes installed with mcl. The program computes correlations (either Pearson or Spearmann) between genes, and creates an edge between genes if their correlation exceeds the specified cutoff. From this, mcxarray(1) creates both a network file and a dictionary file. In the example below, the file expr.data is in tabular format with one row of column headers (e.g. tags for experiments) and one column of row identifiers (e.g. probe or gene identifiers).

mcxarray -data expr.data -skipr 1 -skipc 1 -o expr.mci -write-tab expr.tab --pearson -co 0.7 -tf 'abs(),add(-0.7)'

This uses the Pearson correlation, ignoring values below 0.7. The remaining values in the interval [0.7-1] are remapped to the interval [0-0.3]. This is recommended so that the edge weights will have increased contrast between them, as mcl is affected by relative differences (ratios) between edge weights rather than absolute differences. To illustrate this, values 0.75 and 0.95 are mapped to 0.05 and 0.25, with respective ratios 0.79 and 0.25. The network file expr.mci and the dictionary file expr.tab can now be used as before. ✨

It is possible to investigate the effect of the correlation cutoff as follows. First a network is generated at a very low threshold, and this network is analysed using mcxquery.

mcxarray -data expr.data -skipr 1 -skipc 1 -o expr20.mcx --write-binary --pearson -co 0.2 -tf 'abs()'
mcx query -imx expr20.mcx --vary-correlation

Okay so bestie, the output is in a tabular format describing the properties of the network at increasing correlation thresholds. 💅 Examples are the size of the biggest component, the number of orphan nodes (not connected to any other node 😭), and the mean and median node degrees. A good way to choose the cutoff is to balance the number of singletons and the median node degree. Both should preferably not be too high. For example the number of orphan nodes should be less than ten percent of the total number of nodes, and the median node degree should be at most one hundred neighbours. No cap. ✨

💅 Reducing node degrees in the graph 💅

A good way to lower node degrees in a network is to require that an edge is among the best k edges (those of highest weight) for both nodes incident to the edge, for some value of k. This is achieved by using knn(k) in the argument to the -tf option to mcl or mcx alter. 🫶

To give an example, a graph was formed on translations in Ensembl release 57 on 2.6M nodes. The similarities were obtained from BLAST scores, leading to a graph with a total edge count of 300M, with best-connected nodes of degree respectively 11148, 9083, 9070, 9019 and 8988, and with mean node degree 233. These degrees are unreasonable. 😭 The graph was subjected to mcx query to investigate the effect of varying k-NN parameters. A good heuristic is to choose a value that does not significantly change the number of singletons in the input graph. In the example it meant that -tf 'knn(160)' was feasible, leading to a mean node degree of 98. Periodt. 💖

A second approach to reduce node degrees is to employ the -ceil-nb option. This ranks nodes by node degree, highest first. Nodes are considered in order of rank, and edges of low weight are removed from the graph until a node satisfies the node degree threshold specified by -ceil-nb. Slay. ✨

---

🌈 SEE ALSO 🌈

mcxio(5).

👑 AUTHOR 👑

Stijn van Dongen.

This page is clmprotocols version 22-282, dated 9 Oct 2022, and it's literally iconic. Bye bestie! 💖✨🎀