recency_proportional_resolution_algo

Provide log space complexity and recency-proportional strata spacing.

The MRCA-recency-proportional resolution policy ensures estimates of MRCA rank will have uncertainty bounds less than or equal to a user-specified proportion of the actual number of generations elapsed since the MRCA and the deepest of the compared columns. MRCA rank estimate uncertainty scales in the worst case scales as O(n) with respect to the greater number of strata deposited on either column. However, with respect to estimating the rank of the MRCA when lineages diverged any fixed number of generations ago, uncertainty scales as O(1).

Under the MRCA-recency-proportional resolution policy, the number of strata retained (i.e., space complexity) scales as O(log(n)) with respect to the number of strata deposited.

This functor’s retention policy implementation guarantees that columns will retain appropriate strata so that for any two columns with m and n strata deposited, the rank of the most recent common ancestor at rank k can be determined with uncertainty of at most

bound = floor(

max(m - k, n - k) / recency_proportional_resolution

)

ranks.

How does the predicate work and how does it guarantee this resolution?

To begin, let’s consider setting up just the first rank of the stratum after the root ancestor we will retain.

root ancestor extant individual | | | num_strata_deposited | | ___________________________/_________________________________ | |/ \| |-------------------|#############################################|

_______ ________/|____________________ ______________________/

/ | /

max_uncertainty | worst_case_mrca_depth

proposed retention rank

To provide guaranteed resolution, max_uncertainty must be leq than

worst_case_mrca_depth // guaranteed_resolution

So, to find the largest permissible max_uncertainty we must solve

max_uncertainty = worst_case_mrca_depth // guaranteed_resolution

By construction we have

worst_case_mrca_depth = num_strata_deposited - max_uncertainty

Substituting into the above expression gives

max_uncertainty = (num_strata_deposited - max_uncertainty) // guaranteed_resolution

Solving for max_uncertainty yields

max_uncertainty = num_strata_deposited // (guaranteed_resolution + 1)

We now have an upper bound for the rank of the first stratum rank we must retain. We can repeat this process recursively to select ranks that give adequate resolution proportional to worst_case_mrca_depth.

However, we must guarantee that these ranks are actually available for us to retain (i.e., it hasn’t been purged out of the column at a previous time point as the column was grown by successive deposition). We will do this by picking the rank that is the highest power of 2 less than or equal to our bound. If we repeat this procedure as we recurse, we are guaranteed that this rank will have been preserved across all previous timepoints.

This is because a partial sum sequence where all elements are powers of 2 and elements in the sequence are will include all multiples of powers of 2 greater than or equal to the first element that are less than or equal to the sum of the entire sequence.

An example is the best way to convince yourself. Thinking analogously in base 10,

100 + 10… + 1…

the partial sums of any sequence of this form will always include all multiples of powers of 100, 1000, etc. that are less than or equal to the sum of the entire sequence.

In our application, partial sums represent retained ranks. So, all ranks that are perfect powers of 2 measuring from the root ancestor will have been retained after being deposited. This property generalizes recursively.

Classes

CalcMrcaUncertaintyAbsExact	Functor to provide member function implementation in Policy class.
CalcMrcaUncertaintyAbsUpperBound	Functor to provide member function implementation in Policy class.
CalcMrcaUncertaintyAbsUpperBoundAtPessimalRank
CalcMrcaUncertaintyAbsUpperBoundPessimalRank	Functor to provide member function implementation in Policy class.
CalcMrcaUncertaintyRelExact
CalcMrcaUncertaintyRelUpperBound	Functor to provide member function implementation in Policy class.
CalcMrcaUncertaintyRelUpperBoundAtPessimalRank
CalcMrcaUncertaintyRelUpperBoundPessimalRank	Functor to provide member function implementation in Policy class.
CalcNumStrataRetainedExact	Functor to provide member function implementation in Policy class.
CalcNumStrataRetainedUpperBound	Functor to provide member function implementation in Policy class.
CalcRankAtColumnIndex	Functor to provide member function implementation in Policy class.
GenDropRanks	Functor to implement the recency-proportional resolution stratum retention policy, for use with HereditaryStratigraphicColumn.
IterRetainedRanks
Policy	alias of Policy
PolicySpec	Contains all policy parameters, if any.

class CalcMrcaUncertaintyAbsExact

Functor to provide member function implementation in Policy class.

__call__(policy: PolicyCouplerBase, first_num_strata_deposited: int, second_num_strata_deposited: int, actual_rank_of_mrca: int) → int

Exactly how much uncertainty to estimate rank of MRCA?

__init__(policy_spec: PolicySpec | None) → None

class CalcMrcaUncertaintyAbsUpperBound

Functor to provide member function implementation in Policy class.

__call__(policy: PolicyCouplerBase, first_num_strata_deposited: int, second_num_strata_deposited: int, actual_rank_of_mrca: int) → int

At most, how much uncertainty to estimate rank of MRCA? Inclusive.

__init__(policy_spec: PolicySpec | None) → None

class CalcMrcaUncertaintyAbsUpperBoundAtPessimalRank

class CalcMrcaUncertaintyAbsUpperBoundPessimalRank

Functor to provide member function implementation in Policy class.

__call__(policy: PolicyCouplerBase, first_num_strata_deposited: int | None, second_num_strata_deposited: int | None) → int

Calculate rank for which upper bound on absolute MRCA uncertainty is pessimized.

__init__(policy_spec: PolicySpec | None) → None

class CalcMrcaUncertaintyRelExact

class CalcMrcaUncertaintyRelUpperBound

Functor to provide member function implementation in Policy class.

__call__(policy: PolicyCouplerBase, first_num_strata_deposited: int, second_num_strata_deposited: int, actual_rank_of_mrca: int) → float

At most, how much uncertainty to estimate rank of MRCA? Inclusive.

__init__(policy_spec: PolicySpec | None) → None

class CalcMrcaUncertaintyRelUpperBoundAtPessimalRank

class CalcMrcaUncertaintyRelUpperBoundPessimalRank

Functor to provide member function implementation in Policy class.

__call__(policy: PolicyCouplerBase, first_num_strata_deposited: int, second_num_strata_deposited: int) → int

Calculate rank for which upper bound on relative MRCA uncertainty is pessimized.

__init__(policy_spec: PolicySpec | None) → None

class CalcNumStrataRetainedExact

Functor to provide member function implementation in Policy class.

__call__(policy: PolicyCouplerBase, num_strata_deposited: int) → int

Exactly how many strata are retained after n deposited?

The calculation can be written mathematically as,

weight of binary expansion of n (i.e., #1’s set in binary repr) + sum(

floor( log2(n//r) ) for r from 1 to r inclusive

) + 1

where

n = num_strata_deposited - 1 r = resolution

This expression for exact number deposited was extrapolated from

• resolution = 0, <https://oeis.org/A063787>

• resolution = 1, <https://oeis.org/A056791>

and is unit tested extensively.

Note that the implementation must include a special case to account for n < r causing log2(0). In this case, the number of strata retained is equal to the number deposited (i.e., none have been discarded yet).

__init__(policy_spec: PolicySpec | None) → None

class CalcNumStrataRetainedUpperBound

Functor to provide member function implementation in Policy class.

__call__(policy: PolicyCouplerBase, num_strata_deposited: int) → int

At most how many strata are retained after n deposited? Inclusive.

__init__(policy_spec: PolicySpec | None = None) → None

class CalcRankAtColumnIndex

Functor to provide member function implementation in Policy class.

__call__(policy: PolicyCouplerBase, index: int, num_strata_deposited: int | None) → int

After n strata have been deposited, what will the rank of the stratum at column index k be?

Enables a HereditaryStratigraphicColumn using this predicate to optimize away storage of rank annotations on strata. Takes into the account the possibility for in-progress stratum depositions that haven’t been reflected in num_strata_deposited.

__init__(policy_spec: PolicySpec | None) → None

class GenDropRanks

Functor to implement the recency-proportional resolution stratum retention policy, for use with HereditaryStratigraphicColumn.

This functor enacts the recency-proportional resolution policy by specifying the set of strata ranks that should be purged from a hereditary stratigraphic column when the nth stratum is deposited.

__call__(policy: PolicyCouplerBase, num_stratum_depositions_completed: int, retained_ranks: Iterable[int] | None) → Iterator[int]

Decide which strata within the stratagraphic column should be purged.

Every time a new stratum is deposited, this method is called to determine which strata should be purged. All strata at ranks yielded from this functor are immediately purged from the column, meaning that for a stratum to persist it must not be yielded by this functor each and every time a new stratum is deposited.

Parameters

policy: Policy

Policy this functor enacts.

num_stratum_depositions_completedint

The number of strata that have already been deposited, not including the latest stratum being deposited which prompted the current purge operation.

retained_ranksiterator over int

An iterator over ranks of strata currently retained within the hereditary stratigraphic column. Not used in this functor.

Returns

iterator over int

The ranks of strata that should be purged from the hereditary stratigraphic column at this deposition step.

See Also

recency_proportional_resolution_algo:

For details on the rationale, implementation, and guarantees of the recency-proportional resolution stratum retention policy.

__init__(policy_spec: PolicySpec | None) → None

class IterRetainedRanks

Policy

alias of Policy

class PolicySpec

Contains all policy parameters, if any.

static GetAlgoIdentifier() → str

Get programatic name for underlying retention algorithm.

static GetAlgoTitle() → str

Get human-readable name for underlying retention algorithm.

GetEvalCtor() → str

GetRecencyProportionalResolution() → int

__init__(recency_proportional_resolution: int) → None

Construct the policy spec.

Parameters

recency_proportional_resolutionint, optional

The desired minimum number of intervals between the MRCA and the deeper compared column to be able to be distinguished between. The uncertainty of MRCA rank estimates provided under the MRCA-recency- proportional resolution policy will scale as the actual phylogenetic depth of the MRCA divided by recency_proportional_resolution.

__repr__() → str

Return repr(self).

__str__() → str

Return str(self).