search

lh3 / hickit

TAD calling, phase imputation, 3D modeling and more for diploid single-cell Hi-C (Dip-C) and general Hi-C
100 stars 11 forks source link

Where can I find the algorithmic details? #22

Closed renxwise closed 4 years ago

renxwise commented 4 years ago

3D reconstruction from contacts is nontrivial, so where can I find the algorithmic details behind hickit?

lh3 commented 4 years ago

Similar to nuc_dynamics, which is published.

tanlongzhi commented 4 years ago

The detailed design of nuc_dynamics can be found in the Supplementary Information (PDF) of Stevens et al. Nature 2017 (paper).

A major speed improvement of this repo is to use AVL tree to calculate repulsive forces (i.e. volume exclusion). This implementation can be found starting from this line in fdg.c. The nuc_dynamics counterpart can be found starting from this line of their code. As a result, 3D modeling is very fast in this repo.

renxwise commented 4 years ago

Thanks for your replies. The speed acceleration is impressing.

renxwise commented 4 years ago

Following your guide, I have gotten the main idea of the algorithm. But I still have a question. Is the repulsive force calculated for each pair of particles so that the replacement of AVL tree greatly accelerates the speed? Am I correct?

lh3 commented 4 years ago

Repulsive force is only calculated for particles close enough.

renxwise commented 4 years ago

Thanks. I did not state clearly my point in the last comment. What I mean is that in nuc_dynamics each pair of particles are examined. But in hickit AVL tree is used to calculate only particles close enough. Is my guess correct?

lh3 commented 4 years ago

nuc_dynamics uses a kd-tree. I don't now why nuc_dynamics is slower.