Chromosight quantification time complexity

[PerrineLacour]

Chromosight quantification time complexity

[cmdoret]

Hi @PerrineLacour,

The main determining factor in Chromosight runtime is the maximum scanning distance.
When running in detect mode, you can just set it with a parameter. However, quantify willl read the list of input coordinates (your loops) and set the max scanning distance based on the largest loop.

One possibility is that you have huge loops in your list of coordinates. Removing those would greatly reduce runtime.
In theory, the time complexity should be: D* (N**2 - (N-M)**2) / 2
Where:

• N: Matrix dimension
• M: Max scanning distance (your largest loop, here)
• D: Density (proportion of pixels > 0)
  

D is always between 0 and 1, so D << N.
Since usually D << M << N, the big O notation would be: O(N).
But when M approaches N, it becomes: O(MN)

So basically, runtime is linear with matrix dimension for small M, but as M approaches N, runtime becomes quadratic.

Although the command line tool would take too much time to run, you could still use the API with bunch of python scripting.
If you have already subsetted the matrix around a coordinate, you can call chromosight quantification algorithm like this:

import numpy as np
import cooler
import chromosight.kernels as ck
import chromosight.utils.detection as cud
import chromosight.utils.preprocessing as cup

# Load and preprocess Hi-C data
clr = cooler.Cooler('sample.cool')
chrom_mat = clr.matrix(balance=True, sparse=True).fetch('chrom')
obs_exp = cup.detrend(chrom_mat)

# Subset Hi-C data for specific loop
x, y = 300, 450 # Coordinate of loop in chromosome matrix
width = 100
centered_mat = obs_exp[x-width: x+width, y-width:y+width]

# Run chromosight on that loop matrix region
kernel = np.array(ck.loops['kernels'][0])
conv_center, _ = cud.normxcorr2(centered_mat, kernel)
result = conv[width, width] # This is the quantify score

You could implement this in a function and get it to loop over your 140 coordinates.

[PerrineLacour]

Thank you a lot for your answer,

There is still something that I don't understand, why is M still important for quantify? I thought that chromosight only looked at the coordinates provided.

Can the scaling of the kernel also have an impact on the computation time? Since the correlation has to be computed on a matrix that is 4 or 9 times bigger (for a factor of 2 or 3).

[cmdoret]

So, in earlier versions chromosight looked only at the regions around coordinates, but in most real life use cases (> 10k coordinates on large matrices), slicing the matrix so many times would be orders of magnitude slower than just scanning it once.

In practice the best approach would be to automatically choose between 2 approaches:

• If M is large or there are few coordinates: look at each coordinates
• If there are many coordinates or M is large: scan the whole matrix at once.

But I have not had time to implement that yet.

Kernel size also has a (quadratic) impact on computation time, sure, but since it is usually very small it's not too bad. If you are using a large kernel, I recommend using the tsvd option to decompose the kernel (see supp. materials of the paper).

[PerrineLacour]

Ok, that makes sense. Thank you for your help!