Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Indices - implement exact NTI expected values for ultrametric trees #790

Closed
shawnlaffan opened this issue May 5, 2021 · 1 comment
Closed

Indices - implement exact NTI expected values for ultrametric trees #790

shawnlaffan opened this issue May 5, 2021 · 1 comment
Assignees
@shawnlaffan
Labels
indices
Milestone
Release_4.0

Comments

@shawnlaffan
Copy link
Owner

As described in Tsirogiannis et al. (2014) https://doi.org/10.1007/978-3-662-44753-6_15

Related to #789 and #786
@shawnlaffan shawnlaffan added this to the Release_4.0 milestone May 5, 2021
@shawnlaffan shawnlaffan self-assigned this May 5, 2021
shawnlaffan added a commit that referenced this issue May 12, 2021
@shawnlaffan
Add method to calculate exact MPD expected mean
35d141c 
Updates #790
shawnlaffan added a commit that referenced this issue May 12, 2021
@shawnlaffan
Implement exact NRI expected values
aeb4c20 
Uses the slower variant, so is O(n^2).
The faster implementation
can be done at a later date.

Code includes much debugging for purposes of posterity.
This will be cleaned up next.

Updates #790
shawnlaffan added a commit that referenced this issue May 12, 2021
@shawnlaffan
Add tests for NRI and NTI exact expected values
0f2e044 
Also return 0 for the SD when the requested
sample count equals the number of terminals.

Updates #790, and a late update to #789
shawnlaffan added a commit that referenced this issue May 12, 2021
@shawnlaffan
Fix botched NTI SD vals
b17c67b 
Neglected to take the sqrt

Updates #790
shawnlaffan added a commit that referenced this issue May 12, 2021
@shawnlaffan
update result sets for exact NTI expected vals
d7b5c80 
Updates #790
shawnlaffan added a commit that referenced this issue May 12, 2021
@shawnlaffan
Add Math::AnyNum to the cpanfile
5dad4f3 
If all goes well we will soon not need it...

Updates #790
shawnlaffan added a commit that referenced this issue May 12, 2021
@shawnlaffan
Avoid Math::AnyNum in binomial calcs
52bad54 
Binomials can be expressed using logs
generated from a cache of precalculated
values.

We lose some precision, but the results are
generally the same to 7dp, which is still
better than the permutation approach.

Math::AnyNum has several external dependencies
which it is simpler to avoid.

Updates #790
shawnlaffan added a commit that referenced this issue May 12, 2021
@shawnlaffan
remove Math::AnyNum from the cpanfile
c48908d 
updates #790
shawnlaffan added a commit that referenced this issue May 12, 2021
@shawnlaffan
Don't use state to declare a list
6722f08 
It is not supported until perl 5.28.

Updates #790
shawnlaffan added a commit that referenced this issue May 13, 2021
@shawnlaffan
Clean up some commented code
05318a6 
Updates #790
shawnlaffan added a commit that referenced this issue May 13, 2021
@shawnlaffan
NTI: work with ancestor hashes
947dfab 
These are faster to generate than
descendent hashes.  They are also
are cached by default since they
do not contain circular references
(which can mess up serialisation).

Updates #790
shawnlaffan added a commit that referenced this issue May 13, 2021
@shawnlaffan
NTI SD: refactor to run in O(n(n-1))
d1db2c7 
With some judicious rearrangement we
can do just the lower left of the
pairwise matrix.

A full speedup would use
the algorithm in PhyloMeasures.

Updates #790
shawnlaffan added a commit that referenced this issue May 13, 2021
@shawnlaffan
NTI SD: use more caching
d229a66 
Avoids many repeated method calls
to get the same answer.

Updates #790
shawnlaffan added a commit that referenced this issue May 13, 2021
@shawnlaffan
NTI SD: Add progress dialogue
372fdb5 
GUI only, and only for reasonable numbers of nodes.

This stops the GUI locking up.

Updates #790
shawnlaffan added a commit that referenced this issue May 13, 2021
@shawnlaffan
NTI SD: Update progress text
3d6f823 
Updates #790
shawnlaffan added a commit that referenced this issue May 13, 2021
@shawnlaffan
NTI SD: cache node names as well
41b21b2 
Updates #790
shawnlaffan added a commit that referenced this issue May 13, 2021
@shawnlaffan
NTI SD: modify progress text
18f824d 
Updates #790
shawnlaffan added a commit that referenced this issue May 13, 2021
@shawnlaffan
NTI SD: avoid last-if condition in inner loop
3129170 
Also avoids a list slice, which can become expensive.

Updates #790
shawnlaffan added a commit that referenced this issue May 18, 2021
@shawnlaffan
NTI SD: Initial work on faster NTI SD
db491eb 
sum_subtract is a work in progress,
possibly to do with the bnok ratios.

Updates #790
shawnlaffan added a commit that referenced this issue May 18, 2021
@shawnlaffan
NTI SD: faster calc: sum_subtree and sum_subtract appear to work
4a9fda9 
At least in comparison with PhyloMeasures outputs

Updates #790
shawnlaffan added a commit that referenced this issue May 18, 2021
@shawnlaffan
NTI SD fast: keep iterating to a solution
6f82a8b 
Updates #790
shawnlaffan added a commit that referenced this issue May 18, 2021
@shawnlaffan
NTI SD: fast variant seems to work now
05284f9 
Updates #790
shawnlaffan added a commit that referenced this issue May 18, 2021
@shawnlaffan
NTI SD: remove debug comments
3aea9fe 
Updates #790
shawnlaffan added a commit that referenced this issue May 18, 2021
@shawnlaffan
NRI SD: cache the sorted %by_se keys
77d59e3 
Updates #790
shawnlaffan added a commit that referenced this issue May 18, 2021
@shawnlaffan
Remove more debug comments
a3ed776 
Updates #790
shawnlaffan added a commit that referenced this issue May 18, 2021
@shawnlaffan
NTI SD: avoid expensive descendent search
0442527 
Also reduces the calcs somewhat as we
index by tip count, so get some aggregations.

Updates #790
shawnlaffan added a commit that referenced this issue May 18, 2021
@shawnlaffan
NTI SD: update test expectation
451e54a 
Difference is at fifth decimal place,
where 3dp should be sufficent in most cases.

Updates #790
shawnlaffan added a commit that referenced this issue May 18, 2021
@shawnlaffan
NTI SD: switch over to fast algorithm
1683359 
Updates #790
shawnlaffan added a commit that referenced this issue May 18, 2021
@shawnlaffan
NTI SD: Update more test expectations given new algorithm
9264f1e 
Updates #790
shawnlaffan added a commit that referenced this issue May 18, 2021
@shawnlaffan
NTI SD: pass the "s" parameter to the sum_subtree and sum_subtract me…
c423b0e 
…thod

Updates #790
shawnlaffan added a commit that referenced this issue May 18, 2021
@shawnlaffan
get_nti_expected_mean: use cached tip counts
170e15b 
Updates #790
shawnlaffan added a commit that referenced this issue May 18, 2021
@shawnlaffan
NTI SD: avoid potentially expensive grep
9e1b2ad 
Updates #790
shawnlaffan added a commit that referenced this issue May 18, 2021
@shawnlaffan
NTI SD: remove unused cache entry
0c3664e 
Updates #790
shawnlaffan added a commit that referenced this issue May 18, 2021
@shawnlaffan
NTI SD: delete commented code
d53183b 
Updates #790
@shawnlaffan
Copy link
Owner Author

Mark as fixed.

There are still sections of the code that can be modified. For example recursive algorithms in TreeNode.pm can be linearised and moved into Tree.pm, and the bnok ratio code can be refactored to use callbacks or similar. These can be done under separate issues, though.

This was referenced May 18, 2021
Closed
Closed
shawnlaffan added a commit that referenced this issue Jul 10, 2021
@shawnlaffan
ultrametric tree check: Use the same min difference as phylomeasures
8f40d56 
A late update related to #790
@shawnlaffan shawnlaffan mentioned this issue Jul 10, 2021
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@shawnlaffan shawnlaffan

Labels
indices
Projects
None yet
Milestone
Release_4.0
Development

No branches or pull requests
1 participant
@shawnlaffan