search

LeopoldC / Boost-HiC

MIT License
6 stars 6 forks source link

Is there a faster algorithm for computing fastFloyd? #1

Open hhxy03 opened 5 years ago

hhxy03 commented 5 years ago

As tested in different size of input matrix, profiling the running time of function fastFloyd, I found that its time complexity is extremely high at about O(n^5).

Here is the test result

matrix size running time
1000 * 1000 5s
2000 * 2000 126s
3000 * 3000 1000s

So if I want to boost the Hi-C data in chromosome 1, It nearly costs 80 hours.

Is there anyway to accelerate this function, parallelizing or writing in C?

LeopoldC commented 5 years ago

Hey, there is several way to optimize the FloydWashall algorithm: -maybe this one is a good option https://www.ijarse.com/images/fullpdf/1371224241_SHORTEST_PATH_USING_NEURAL_NETWORK.pdf

-this other repository seems to be good start, just need to optimize it for this specific case issue and win a x2 ratio. https://github.com/mosco/floyd-warshall-cython

Unfortunately, I never had the time to test and implement those kind of option for now.

If you need fast result, I'm always run boost hic by centromeric arm on human dataset, for compartment result seems to be nice like this. It's depending of what you need. If you want to run boost hic only once, I advise you an alpha close to 0.2 by default