mmore500 / hstrat-algorithm-analysis

Formal analysis of the hereditary stratigraphy algorithm
0 stars 0 forks source link

Maybe: somehow try to prove optimality, optimality within a factor, or otherwise reasonableness of approach #9

Open mmore500 opened 1 year ago

mmore500 commented 1 year ago

This might somehow involve an information theoretic approach. Perhaps thinking along the number of bits that are required to disambiguate a tree structure? But also to tell when nodes occur in time? Or somehow reducing all other annotation approaches to structurally equivalent to hereditary stratigraphy but worse (i.e., under bit drift consider random changes as "depositions")

rodsan0 commented 1 year ago

We can also compare against the time and space complexity of perfect phylogenetic tracking.