search

YosefLab / Cassiopeia

A Package for Cas9-Enabled Single Cell Lineage Tracing Tree Reconstruction
https://cassiopeia-lineage.readthedocs.io/en/latest/
MIT License
75 stars 24 forks source link

Leaf Subsampler Speedup #228

Closed colganwi closed 11 months ago

colganwi commented 11 months ago

This PR makes the UniformLeafSubsampler ~50X faster for large trees by improving remove_leaves_and_prune_lineages. Specifically, instead of checking internal nodes many times, we are now using a heap to check internal nodes in order from the bottom of the tree to the top. Additionally, the __network now is modified directly which avoids repeated calls to __check_network_initialized().

codecov[bot] commented 11 months ago

Codecov Report

All modified lines are covered by tests :white_check_mark:

Comparison is base (d53e6d9) 79.49% compared to head (cf2cbc2) 79.53%.

Additional details and impacted files ```diff @@ Coverage Diff @@ ## master #228 +/- ## ========================================== + Coverage 79.49% 79.53% +0.04% ========================================== Files 89 89 Lines 8050 8064 +14 ========================================== + Hits 6399 6414 +15 + Misses 1651 1650 -1 ``` | [Files](https://app.codecov.io/gh/YosefLab/Cassiopeia/pull/228?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=YosefLab) | Coverage Δ | | |---|---|---| | [cassiopeia/data/CassiopeiaTree.py](https://app.codecov.io/gh/YosefLab/Cassiopeia/pull/228?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=YosefLab#diff-Y2Fzc2lvcGVpYS9kYXRhL0Nhc3Npb3BlaWFUcmVlLnB5) | `92.09% <100.00%> (+0.30%)` | :arrow_up: |

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

colganwi commented 11 months ago

Also, speeds up the BirthDeathFitnessSimulator since a large proportion of this simulations time is spent cleaning up dead lineages.