API Reference

Library usage not recommended

I recommend using TACT mainly via its console commands for stability and best results. To get started, see the Tutorial.

While TACT can be used as a Python library, its internal interface is subject to change at any time, even for minor or patch versions. This API documentation is provided merely for the sake of completeness.

Numerical functions

Functions in tact/lib.py.

Functions to handle various numerical operations, including optimization.

crown_capture_probability(n: int, k: int) -> float

Calculate probability of observing the crown node in an incomplete sample.

Probability that a random sample of k taxa from a clade of n total taxa includes the crown (root) node, under a Yule process.

Reference: Sanderson (1996), Systematic Biology 45:168-173.

Parameters:

Name	Type	Description	Default
n	int	Total number of taxa in the clade.	required
k	int	Number of sampled taxa.	required

Returns:

Type	Description
float	Probability of crown node inclusion.

Raises:

Type	Description
Exception	If n < k.

Source code in tact/lib.py

def crown_capture_probability(n: int, k: int) -> float:
    """Calculate probability of observing the crown node in an incomplete sample.

    Probability that a random sample of `k` taxa from a clade of `n` total taxa
    includes the crown (root) node, under a Yule process.

    Reference: Sanderson (1996), Systematic Biology 45:168-173.

    Args:
        n: Total number of taxa in the clade.
        k: Number of sampled taxa.

    Returns:
        Probability of crown node inclusion.

    Raises:
        Exception: If `n < k`.
    """
    if n < k:
        raise Exception(f"n must be greater than or equal to k (n={n}, k={k})")
    if n == 1 and k == 1:
        return 0.0  # not technically correct but it works for our purposes
    return 1 - 2 * (n - k) / ((n - 1) * (k + 1))

get_bd(r: float, a: float) -> tuple[float, float]

Convert turnover and relative extinction to birth and death rates.

Parameters:

Name	Type	Description	Default
r	float	Turnover rate (net diversification, birth - death).	required
a	float	Relative extinction rate (death / birth).	required

Returns:

Type	Description
tuple[float, float]	Tuple of (birth rate, death rate).

Source code in tact/lib.py

def get_bd(r: float, a: float) -> tuple[float, float]:
    """Convert turnover and relative extinction to birth and death rates.

    Args:
        r: Turnover rate (net diversification, birth - death).
        a: Relative extinction rate (death / birth).

    Returns:
        Tuple of (birth rate, death rate).
    """
    return -r / (a - 1), -a * r / (a - 1)

get_new_times(ages: list[float], birth: float, death: float, missing: int, told: float | None = None, tyoung: float | None = None) -> list[float]

Simulate new speciation event times in an incomplete phylogeny.

Simulates missing speciation events under a constant-rate birth-death process. Adapted from TreeSim::corsim by Tanja Stadler. Reference: Cusimano et al. (2012), Systematic Biology 61(5):785-792.

Parameters:

Name	Type	Description	Default
ages	list[float]	List of existing waiting times (will be sorted in place).	required
birth	float	Birth rate.	required
death	float	Death rate.	required
missing	int	Number of missing taxa to simulate.	required
told	float | None	Maximum simulated age. Defaults to max(ages).	None
tyoung	float | None	Minimum simulated age. Defaults to 0.	None

Returns:

Type	Description
list[float]	List of simulated waiting times, sorted in descending order.

Raises:

Type	Description
Exception	If zero or negative branch lengths are detected.

Source code in tact/lib.py

def get_new_times(
    ages: list[float],
    birth: float,
    death: float,
    missing: int,
    told: float | None = None,
    tyoung: float | None = None,
) -> list[float]:
    """Simulate new speciation event times in an incomplete phylogeny.

    Simulates missing speciation events under a constant-rate birth-death process.
    Adapted from `TreeSim::corsim` by Tanja Stadler. Reference: Cusimano et al.
    (2012), Systematic Biology 61(5):785-792.

    Args:
        ages: List of existing waiting times (will be sorted in place).
        birth: Birth rate.
        death: Death rate.
        missing: Number of missing taxa to simulate.
        told: Maximum simulated age. Defaults to `max(ages)`.
        tyoung: Minimum simulated age. Defaults to 0.

    Returns:
        List of simulated waiting times, sorted in descending order.

    Raises:
        Exception: If zero or negative branch lengths are detected.
    """
    if told is None:
        told = max(ages)
    if len(ages) > 0:
        if max(ages) > told and abs(max(ages) - told) > sys.float_info.epsilon:
            raise Exception("Zero or negative branch lengths detected in backbone phylogeny")
    if tyoung is None:
        tyoung = 0

    ages.sort(reverse=True)
    times = [x for x in ages if told >= x >= tyoung]
    times = [told, *times, tyoung]
    ranks = range(0, len(times))
    only_new = []
    while missing > 0:
        if len(ranks) > 2:
            distrranks = []
            for i in range(1, len(ranks)):
                temp = ranks[i] * (intp1(times[i - 1], birth, death) - intp1(times[i], birth, death))
                distrranks.append(temp)
            try:
                dsum = sum(distrranks)
                distrranks = [x / dsum for x in distrranks]
                for i in range(1, len(distrranks)):
                    distrranks[i] = distrranks[i] + distrranks[i - 1]
                r = random.uniform(0, 1)
                addrank = min([idx for idx, x in enumerate(distrranks) if x > r])
            except ZeroDivisionError:
                addrank = 0
            except ValueError:
                addrank = 0
        else:
            addrank = 0
        r = random.uniform(0, 1)
        const = intp1(times[addrank], birth, death) - intp1(times[addrank + 1], birth, death)
        try:
            temp = intp1(times[addrank + 1], birth, death) / const
        except ZeroDivisionError:
            temp = 0.0
        xnew = 1 / (death - birth) * log((1 - (r + temp) * const * birth) / (1 - (r + temp) * const * death))
        only_new.append(xnew)
        missing -= 1
    only_new.sort(reverse=True)
    return only_new

get_ra(b: float, d: float) -> tuple[float, float]

Convert birth and death rates to turnover and relative extinction.

Parameters:

Name	Type	Description	Default
b	float	Birth rate.	required
d	float	Death rate.	required

Returns:

Type	Description
tuple[float, float]	Tuple of (turnover rate, relative extinction rate).

Source code in tact/lib.py

def get_ra(b: float, d: float) -> tuple[float, float]:
    """Convert birth and death rates to turnover and relative extinction.

    Args:
        b: Birth rate.
        d: Death rate.

    Returns:
        Tuple of (turnover rate, relative extinction rate).
    """
    return (b - d, d / b)

intp1(t: float, l: float, m: float) -> float

Compute integration constant for sampling missing speciation event times.

This is a portion of the cdf used to perform inverse-transform sampling of missing speciation event times under a constant-rate birth-death model. It is the c_2 term from equation A.2 in Cusimano et al. (2012), Systematic Biology 61(5):785-792. Originally implemented as TreeSim:::intp1.

Parameters:

Name	Type	Description	Default
t	float	Time before present.	required
l	float	Birth rate (lambda).	required
m	float	Death rate (mu).	required

Returns:

Type	Description
float	Integration constant value.

Source code in tact/lib.py

def intp1(t: float, l: float, m: float) -> float:  # noqa: E741
    """Compute integration constant for sampling missing speciation event times.

    This is a portion of the cdf used to perform inverse-transform sampling of missing speciation event times
    under a constant-rate birth-death model. It is the c_2 term from equation A.2 in Cusimano et al. (2012),
    Systematic Biology 61(5):785-792. Originally implemented as `TreeSim:::intp1`.

    Args:
        t: Time before present.
        l: Birth rate (lambda).
        m: Death rate (mu).

    Returns:
        Integration constant value.
    """
    try:
        return (1 - exp(-(l - m) * t)) / (l - m * exp(-(l - m) * t))
    except OverflowError:
        return float(intp1_exact(t, l, m))

intp1_exact(t: float, l: float, m: float) -> D

Compute intp1 using exact Decimal arithmetic.

Used as fallback when floating-point arithmetic fails due to overflow.

Parameters:

Name	Type	Description	Default
t	float	Time before present.	required
l	float	Birth rate (lambda).	required
m	float	Death rate (mu).	required

Returns:

Type	Description
Decimal	Integration constant as a Decimal.

Source code in tact/lib.py

def intp1_exact(t: float, l: float, m: float) -> D:  # noqa: E741
    """Compute intp1 using exact Decimal arithmetic.

    Used as fallback when floating-point arithmetic fails due to overflow.

    Args:
        t: Time before present.
        l: Birth rate (lambda).
        m: Death rate (mu).

    Returns:
        Integration constant as a Decimal.
    """
    l_dec = D(l)
    m_dec = D(m)
    t_dec = D(t)
    num = D(1) - (-(l_dec - m_dec) * t_dec).exp()
    denom = l_dec - m_dec * (-(l_dec - m_dec) * t_dec).exp()
    return num / denom

lik_constant(vec: tuple[float, float], rho: float, t: list[float], root: int = 1, survival: int = 1, p1: Callable[[float, float, float, float], float] = p1) -> float

Calculate likelihood of a constant-rate birth-death process.

Likelihood conditioned on waiting times and incomplete sampling. Based on TreePar::LikConstant by Tanja Stadler. Reference: Stadler (2009), Journal of Theoretical Biology 261:58-66.

Parameters:

Name	Type	Description	Default
vec	tuple[float, float]	Tuple of (birth rate, death rate).	required
rho	float	Sampling fraction.	required
t	list[float]	List of waiting times (will be sorted in place).	required
root	int	Include root contribution (1) or not (0). Default: 1.	1
survival	int	Assume process survival (1) or not (0). Default: 1.	1
p1	Callable[[float, float, float, float], float]	Function to compute p1 probability (default: p1).	p1

Returns:

Type	Description
float	Negative log-likelihood value.

Source code in tact/lib.py

def lik_constant(
    vec: tuple[float, float],
    rho: float,
    t: list[float],
    root: int = 1,
    survival: int = 1,
    p1: Callable[[float, float, float, float], float] = p1,
) -> float:
    """Calculate likelihood of a constant-rate birth-death process.

    Likelihood conditioned on waiting times and incomplete sampling. Based on
    `TreePar::LikConstant` by Tanja Stadler. Reference: Stadler (2009), Journal
    of Theoretical Biology 261:58-66.

    Args:
        vec: Tuple of (birth rate, death rate).
        rho: Sampling fraction.
        t: List of waiting times (will be sorted in place).
        root: Include root contribution (1) or not (0). Default: 1.
        survival: Assume process survival (1) or not (0). Default: 1.
        p1: Function to compute p1 probability (default: `p1`).

    Returns:
        Negative log-likelihood value.
    """
    l = vec[0]  # noqa: E741
    m = vec[1]
    t.sort(reverse=True)
    lik = (root + 1) * log(p1(t[0], l, m, rho))
    for tt in t[1:]:
        lik += log(l) + log(p1(tt, l, m, rho))
    if survival == 1:
        lik -= (root + 1) * log(1 - p0(t[0], l, m, rho))
    return -lik

optim_bd(ages: list[float], sampling: float, min_bound: float = 1e-09) -> tuple[float, float]

Optimize birth and death rates from node ages under a birth-death model.

Uses maximum likelihood estimation with the Magallon-Sanderson crown estimator for initial values.

Parameters:

Name	Type	Description	Default
ages	list[float]	List of node ages (splitting times).	required
sampling	float	Sampling fraction in (0, 1].	required
min_bound	float	Minimum allowed birth rate (default: 1e-9).	1e-09

Returns:

Type	Description
tuple[float, float]	Tuple of (optimized birth rate, optimized death rate).

Source code in tact/lib.py

def optim_bd(ages: list[float], sampling: float, min_bound: float = 1e-9) -> tuple[float, float]:
    """Optimize birth and death rates from node ages under a birth-death model.

    Uses maximum likelihood estimation with the Magallon-Sanderson crown estimator
    for initial values.

    Args:
        ages: List of node ages (splitting times).
        sampling: Sampling fraction in (0, 1].
        min_bound: Minimum allowed birth rate (default: 1e-9).

    Returns:
        Tuple of (optimized birth rate, optimized death rate).
    """
    if max(ages) < 0.000001:
        init_r = 1e-3
    else:
        # Magallon-Sanderson crown estimator
        init_r = (log((len(ages) + 1) / sampling) - log(2)) / max(ages)
        init_r = max(1e-3, init_r)
    bounds = ((min_bound, 100), (0, 1 - min_bound))
    result = two_step_optim(wrapped_lik_constant, x0=(init_r, min_bound), bounds=bounds, args=(sampling, ages))
    return get_bd(*result)

optim_yule(ages: list[float], sampling: float, min_bound: float = 1e-09) -> tuple[float, float]

Optimize birth rate under a Yule (pure birth) model.

Assumes zero extinction rate.

Parameters:

Name	Type	Description	Default
ages	list[float]	List of node ages (splitting times).	required
sampling	float	Sampling fraction in (0, 1].	required
min_bound	float	Minimum allowed birth rate (default: 1e-9).	1e-09

Returns:

Type	Description
tuple[float, float]	Tuple of (optimized birth rate, 0.0).

Raises:

Type	Description
Exception	If optimization fails.

Source code in tact/lib.py

def optim_yule(ages: list[float], sampling: float, min_bound: float = 1e-9) -> tuple[float, float]:
    """Optimize birth rate under a Yule (pure birth) model.

    Assumes zero extinction rate.

    Args:
        ages: List of node ages (splitting times).
        sampling: Sampling fraction in (0, 1].
        min_bound: Minimum allowed birth rate (default: 1e-9).

    Returns:
        Tuple of (optimized birth rate, 0.0).

    Raises:
        Exception: If optimization fails.
    """
    bounds = (min_bound, 100)
    result = minimize_scalar(wrapped_lik_constant_yule, bounds=bounds, args=(sampling, ages), method="Bounded")
    if result["success"]:
        return (float(result["x"]), 0.0)

    raise Exception(f"Optimization failed: {result['message']} (code {result['status']})")

p0(t: float, l: float, m: float, rho: float) -> float

Compute the probability of no sampled descendants.

Probability that an individual alive at time t before present has no sampled descendants (extant or extinct), assuming no past sampling. Falls back to exact Decimal arithmetic if floating-point overflow occurs.

Reference: Stadler (2010), Journal of Theoretical Biology 267(3):396-404, remark 3.2. Originally implemented as TreePar:::p0.

Parameters:

Name	Type	Description	Default
t	float	Time before present.	required
l	float	Birth rate (lambda).	required
m	float	Death rate (mu).	required
rho	float	Sampling fraction.	required

Returns:

Type	Description
float	Probability of no sampled descendants.

Source code in tact/lib.py

def p0(t: float, l: float, m: float, rho: float) -> float:  # noqa: E741
    """Compute the probability of no sampled descendants.

    Probability that an individual alive at time `t` before present has no sampled
    descendants (extant or extinct), assuming no past sampling. Falls back to
    exact Decimal arithmetic if floating-point overflow occurs.

    Reference: Stadler (2010), Journal of Theoretical Biology 267(3):396-404,
    remark 3.2. Originally implemented as `TreePar:::p0`.

    Args:
        t: Time before present.
        l: Birth rate (lambda).
        m: Death rate (mu).
        rho: Sampling fraction.

    Returns:
        Probability of no sampled descendants.
    """
    try:
        return 1 - rho * (l - m) / (rho * l + (l * (1 - rho) - m) * exp(-(l - m) * t))
    except FloatingPointError:
        return float(p0_exact(t, l, m, rho))

p0_exact(t: float, l: float, m: float, rho: float) -> D

Compute p0 using exact Decimal arithmetic.

Used as fallback when floating-point arithmetic fails due to overflow.

Parameters:

Name	Type	Description	Default
t	float	Time before present.	required
l	float	Birth rate (lambda).	required
m	float	Death rate (mu).	required
rho	float	Sampling fraction.	required

Returns:

Type	Description
Decimal	Probability of no sampled descendants as a Decimal.

Source code in tact/lib.py

def p0_exact(t: float, l: float, m: float, rho: float) -> D:  # noqa: E741
    """Compute p0 using exact Decimal arithmetic.

    Used as fallback when floating-point arithmetic fails due to overflow.

    Args:
        t: Time before present.
        l: Birth rate (lambda).
        m: Death rate (mu).
        rho: Sampling fraction.

    Returns:
        Probability of no sampled descendants as a Decimal.
    """
    t_dec = D(t)
    l_dec = D(l)
    m_dec = D(m)
    rho_dec = D(rho)
    return D(1) - rho_dec * (l_dec - m_dec) / (
        rho_dec * l_dec + (l_dec * (D(1) - rho_dec) - m_dec) * (-(l_dec - m_dec) * t_dec).exp()
    )

p1(t: float, l: float, m: float, rho: float) -> float

Compute the probability of exactly one sampled descendant.

Probability that an individual alive at time t before present has precisely one sampled extant descendant and no sampled extinct descendants, assuming no past sampling. Optimized version using common subexpression elimination.

Reference: Stadler (2010), Journal of Theoretical Biology 267(3):396-404, remark 3.2. Originally implemented as TreePar:::p1.

Parameters:

Name	Type	Description	Default
t	float	Time before present.	required
l	float	Birth rate (lambda).	required
m	float	Death rate (mu).	required
rho	float	Sampling fraction.	required

Returns:

Type	Description
float	Probability of exactly one sampled descendant.

Source code in tact/lib.py

def p1(t: float, l: float, m: float, rho: float) -> float:  # noqa: E741
    """Compute the probability of exactly one sampled descendant.

    Probability that an individual alive at time `t` before present has precisely
    one sampled extant descendant and no sampled extinct descendants, assuming
    no past sampling. Optimized version using common subexpression elimination.

    Reference: Stadler (2010), Journal of Theoretical Biology 267(3):396-404,
    remark 3.2. Originally implemented as `TreePar:::p1`.

    Args:
        t: Time before present.
        l: Birth rate (lambda).
        m: Death rate (mu).
        rho: Sampling fraction.

    Returns:
        Probability of exactly one sampled descendant.
    """
    try:
        ert = np.exp(-(l - m) * t, dtype=np.float64)
        num = rho * (l - m) ** 2 * ert
        denom = (rho * l + (l * (1 - rho) - m) * ert) ** 2
        res: float = num / denom
    except (OverflowError, FloatingPointError):
        res = float(p1_exact(t, l, m, rho))
    if res == 0.0:
        return sys.float_info.min
    return res

p1_exact(t: float, l: float, m: float, rho: float) -> D

Compute p1 using exact Decimal arithmetic.

Used as fallback when floating-point arithmetic fails due to overflow.

Parameters:

Name	Type	Description	Default
t	float	Time before present.	required
l	float	Birth rate (lambda).	required
m	float	Death rate (mu).	required
rho	float	Sampling fraction.	required

Returns:

Type	Description
Decimal	Probability of exactly one sampled descendant as a Decimal.

Source code in tact/lib.py

def p1_exact(t: float, l: float, m: float, rho: float) -> D:  # noqa: E741
    """Compute p1 using exact Decimal arithmetic.

    Used as fallback when floating-point arithmetic fails due to overflow.

    Args:
        t: Time before present.
        l: Birth rate (lambda).
        m: Death rate (mu).
        rho: Sampling fraction.

    Returns:
        Probability of exactly one sampled descendant as a Decimal.
    """
    t_dec = D(t)
    l_dec = D(l)
    m_dec = D(m)
    rho_dec = D(rho)
    num = rho_dec * (l_dec - m_dec) ** D(2) * (-(l_dec - m_dec) * t_dec).exp()
    denom = (rho_dec * l_dec + (l_dec * (D(1) - rho_dec) - m_dec) * (-(l_dec - m_dec) * t_dec).exp()) ** D(2)
    return num / denom

p1_orig(t: float, l: float, m: float, rho: float) -> float

Original implementation of p1 for testing and comparison.

Parameters:

Name	Type	Description	Default
t	float	Time before present.	required
l	float	Birth rate (lambda).	required
m	float	Death rate (mu).	required
rho	float	Sampling fraction.	required

Returns:

Type	Description
float	Probability of exactly one sampled descendant.

Source code in tact/lib.py

def p1_orig(t: float, l: float, m: float, rho: float) -> float:  # noqa: E741
    """Original implementation of p1 for testing and comparison.

    Args:
        t: Time before present.
        l: Birth rate (lambda).
        m: Death rate (mu).
        rho: Sampling fraction.

    Returns:
        Probability of exactly one sampled descendant.
    """
    try:
        num = rho * (l - m) ** 2 * np.exp(-(l - m) * t)
        denom = (rho * l + (l * (1 - rho) - m) * np.exp(-(l - m) * t)) ** 2
        res: float = num / denom
    except (OverflowError, FloatingPointError):
        res = float(p1_exact(t, l, m, rho))
    if res == 0.0:
        return sys.float_info.min
    return res

replicate_seed(seed: int, replicate: int) -> int

Derive the seed of one replicate from the seed of a run.

Parameters:

Name	Type	Description	Default
seed	int	Seed of the run.	required
replicate	int	Index of the replicate.	required

Returns:

Type	Description
int	A seed for seed_rngs that differs between replicates and does not depend on the process that runs them.

Source code in tact/lib.py

def replicate_seed(seed: int, replicate: int) -> int:
    """Derive the seed of one replicate from the seed of a run.

    Args:
        seed: Seed of the run.
        replicate: Index of the replicate.

    Returns:
        A seed for `seed_rngs` that differs between replicates and does not depend on the process that runs them.
    """
    return int(np.random.SeedSequence([seed, replicate]).generate_state(1)[0])

seed_rngs(seed: int) -> None

Seed all random number generators.

Parameters:

Name	Type	Description	Default
seed	int	Seed for Python's random module and NumPy's global state.	required

Source code in tact/lib.py

def seed_rngs(seed: int) -> None:
    """Seed all random number generators.

    Args:
        seed: Seed for Python's `random` module and NumPy's global state.
    """
    random.seed(seed)
    np.random.seed(seed)  # noqa: NPY002

two_step_optim(func: Callable[..., float], x0: tuple[float, ...], bounds: tuple[tuple[float, float], ...], args: tuple[Any, ...]) -> list[float]

Optimize a function using a two-step approach.

First attempts L-BFGS-B (fast gradient-based method), then falls back to simulated annealing if L-BFGS-B fails.

Parameters:

Name	Type	Description	Default
func	Callable[..., float]	Objective function to minimize.	required
x0	tuple[float, ...]	Initial parameter values.	required
bounds	tuple[tuple[float, float], ...]	Parameter bounds as tuples of (min, max) for each parameter.	required
args	tuple[Any, ...]	Additional arguments to pass to the objective function.	required

Returns:

Type	Description
list[float]	Optimized parameter values as a list.

Raises:

Type	Description
Exception	If both optimization methods fail.

Source code in tact/lib.py

def two_step_optim(
    func: Callable[..., float], x0: tuple[float, ...], bounds: tuple[tuple[float, float], ...], args: tuple[Any, ...]
) -> list[float]:
    """Optimize a function using a two-step approach.

    First attempts L-BFGS-B (fast gradient-based method), then falls back to
    simulated annealing if L-BFGS-B fails.

    Args:
        func: Objective function to minimize.
        x0: Initial parameter values.
        bounds: Parameter bounds as tuples of (min, max) for each parameter.
        args: Additional arguments to pass to the objective function.

    Returns:
        Optimized parameter values as a list.

    Raises:
        Exception: If both optimization methods fail.
    """
    try:
        result = minimize(func, x0=x0, bounds=bounds, args=args, method="L-BFGS-B")
        if result["success"]:
            return [float(x) for x in result["x"]]
    except FloatingPointError:
        pass

    result = dual_annealing(func, x0=x0, bounds=bounds, args=args)
    if result["success"]:
        return [float(x) for x in result["x"]]

    raise Exception(f"Optimization failed: {result['message']} (code {result['status']})")

wrapped_lik_constant(x: tuple[float, float], sampling: float, ages: list[float]) -> float

Wrapper for birth-death likelihood function for optimization.

Converts turnover and relative extinction parameters to birth/death rates before computing the likelihood.

Parameters:

Name	Type	Description	Default
x	tuple[float, float]	Tuple of (turnover, relative extinction).	required
sampling	float	Sampling fraction in (0, 1].	required
ages	list[float]	List of node ages.	required

Returns:

Type	Description
float	Negative log-likelihood value.

Source code in tact/lib.py

def wrapped_lik_constant(x: tuple[float, float], sampling: float, ages: list[float]) -> float:
    """Wrapper for birth-death likelihood function for optimization.

    Converts turnover and relative extinction parameters to birth/death rates
    before computing the likelihood.

    Args:
        x: Tuple of (turnover, relative extinction).
        sampling: Sampling fraction in (0, 1].
        ages: List of node ages.

    Returns:
        Negative log-likelihood value.
    """
    return lik_constant(get_bd(*x), sampling, ages)

wrapped_lik_constant_yule(x: float, sampling: float, ages: list[float]) -> float

Wrapper for Yule model likelihood function for optimization.

Assumes zero extinction (pure birth process).

Parameters:

Name	Type	Description	Default
x	float	Birth rate.	required
sampling	float	Sampling fraction in (0, 1].	required
ages	list[float]	List of node ages.	required

Returns:

Type	Description
float	Negative log-likelihood value.

Source code in tact/lib.py

def wrapped_lik_constant_yule(x: float, sampling: float, ages: list[float]) -> float:
    """Wrapper for Yule model likelihood function for optimization.

    Assumes zero extinction (pure birth process).

    Args:
        x: Birth rate.
        sampling: Sampling fraction in (0, 1].
        ages: List of node ages.

    Returns:
        Negative log-likelihood value.
    """
    return lik_constant((x, 0.0), sampling, ages)

Tree functions

Functions in tact/tree_util.py.

Functions specifically to handle DendroPy tree objects.

compute_node_depths(tree: dendropy.Tree) -> dict[str, int]

Compute node depths for all labeled nodes.

Depth is defined as the number of labeled ancestor nodes.

Parameters:

Name	Type	Description	Default
tree	Tree	DendroPy tree object.	required

Returns:

Type	Description
dict[str, int]	Dictionary mapping tip labels to their node depths.

Source code in tact/tree_util.py

def compute_node_depths(tree: dendropy.Tree) -> dict[str, int]:
    """Compute node depths for all labeled nodes.

    Depth is defined as the number of labeled ancestor nodes.

    Args:
        tree: DendroPy tree object.

    Returns:
        Dictionary mapping tip labels to their node depths.
    """
    res: dict[str, int] = {}
    for leaf in tree.leaf_node_iter():
        cnt = 0
        for anc in leaf.ancestor_iter():
            if anc.label:
                cnt += 1
        res[leaf.taxon.label] = cnt
    return res

count_newick_trees(path: str) -> int

Count the trees in a Newick file by their terminating semicolons.

Parameters:

Name	Type	Description	Default
path	str	File path to the tree file.	required

Returns:

Type	Description
int	Number of trees in the file.

Source code in tact/tree_util.py

def count_newick_trees(path: str) -> int:
    """Count the trees in a Newick file by their terminating semicolons.

    Args:
        path: File path to the tree file.

    Returns:
        Number of trees in the file.
    """
    with open(path, encoding="utf-8") as fh:
        text = fh.read()
    return _NEWICK_QUOTES_AND_COMMENTS.sub("", text).count(";")

edge_iter(node: dendropy.Node, filter_fn: Callable[[dendropy.Edge], bool] | None = None) -> Iterator[dendropy.Edge]

Iterate over edges in a subtree.

Parameters:

Name	Type	Description	Default
node	Node	DendroPy node representing the root of the subtree.	required
filter_fn	Callable[[Edge], bool] | None	Optional function to filter edges. Default: None.	None

Yields:

Type	Description
Edge	DendroPy edge objects in the subtree.

Source code in tact/tree_util.py

def edge_iter(
    node: dendropy.Node, filter_fn: Callable[[dendropy.Edge], bool] | None = None
) -> Iterator[dendropy.Edge]:
    """Iterate over edges in a subtree.

    Args:
        node: DendroPy node representing the root of the subtree.
        filter_fn: Optional function to filter edges. Default: None.

    Yields:
        DendroPy edge objects in the subtree.
    """
    stack = list(node.child_edge_iter())
    while stack:
        edge = stack.pop()
        if filter_fn is None or filter_fn(edge):
            yield edge
        stack.extend(edge.head_node.child_edge_iter())

encode_leafset_bitmasks(node: dendropy.Node, taxon_namespace: dendropy.TaxonNamespace) -> int

Compute and store leafset bitmasks for every edge in a subtree.

Parameters:

Name	Type	Description	Default
node	Node	Node representing the root of the subtree.	required
taxon_namespace	TaxonNamespace	Taxon namespace that the leaves of the subtree belong to.	required

Returns:

Type	Description
int	Bitmask of the taxa in the subtree.

Source code in tact/tree_util.py

def encode_leafset_bitmasks(node: dendropy.Node, taxon_namespace: dendropy.TaxonNamespace) -> int:
    """Compute and store leafset bitmasks for every edge in a subtree.

    Args:
        node: Node representing the root of the subtree.
        taxon_namespace: Taxon namespace that the leaves of the subtree belong to.

    Returns:
        Bitmask of the taxa in the subtree.
    """
    bitmask = 0
    for nd in node.postorder_iter():
        if nd.is_leaf():
            bitmask = taxon_namespace.taxon_bitmask(nd.taxon)
        else:
            bitmask = 0
            for child in nd.child_node_iter():
                bitmask |= child.edge.bipartition.leafset_bitmask
        set_leafset_bitmask(nd, bitmask)
    return bitmask

get_age_intervals(node: dendropy.Node) -> portion.Interval

Get the age interval for possible grafts in a clade.

Computes the union of all age intervals from unlocked edges, which represents all possible ages where a graft could be placed.

Parameters:

Name	Type	Description	Default
node	Node	Node representing the root of the clade.	required

Returns:

Type	Description
Interval	Portion interval (possibly disjoint) representing valid graft ages.

Source code in tact/tree_util.py

def get_age_intervals(node: dendropy.Node) -> portion.Interval:
    """Get the age interval for possible grafts in a clade.

    Computes the union of all age intervals from unlocked edges, which
    represents all possible ages where a graft could be placed.

    Args:
        node: Node representing the root of the clade.

    Returns:
        Portion interval (possibly disjoint) representing valid graft ages.
    """
    acc = portion.empty()
    for edge in edge_iter(node, lambda x: x.label != "locked"):
        acc = acc | portion.closed(edge.head_node.age, edge.tail_node.age)
    return acc

get_ages(node: dendropy.Node, include_root: bool = False) -> list[float]

Get list of node ages in a subtree.

Parameters:

Name	Type	Description	Default
node	Node	DendroPy node representing the root of the subtree.	required
include_root	bool	If True, include the root node's age. Default: False.	False

Returns:

Type	Description
list[float]	List of node ages, sorted in descending order.

Source code in tact/tree_util.py

def get_ages(node: dendropy.Node, include_root: bool = False) -> list[float]:
    """Get list of node ages in a subtree.

    Args:
        node: DendroPy node representing the root of the subtree.
        include_root: If True, include the root node's age. Default: False.

    Returns:
        List of node ages, sorted in descending order.
    """
    ages = [x.age for x in node.ageorder_iter(include_leaves=False, descending=True)]
    if include_root:
        ages += [node.age]
    return ages

get_birth_death_rates(node: dendropy.Node, sampfrac: float, yule: bool = False, include_root: bool = False) -> tuple[float, float]

Estimate birth-death rates from a subtree.

Computes maximum likelihood birth and death rates for the subtree descending from the given node, optionally using a Yule (pure birth) model.

Parameters:

Name	Type	Description	Default
node	Node	DendroPy node representing the root of the subtree.	required
sampfrac	float	Sampling fraction in (0, 1].	required
yule	bool	If True, use Yule model (zero extinction). Default: False.	False
include_root	bool	If True, include root node age in calculations. Default: False.	False

Returns:

Type	Description
tuple[float, float]	Tuple of (birth rate, death rate).

Source code in tact/tree_util.py

def get_birth_death_rates(
    node: dendropy.Node, sampfrac: float, yule: bool = False, include_root: bool = False
) -> tuple[float, float]:
    """Estimate birth-death rates from a subtree.

    Computes maximum likelihood birth and death rates for the subtree
    descending from the given node, optionally using a Yule (pure birth) model.

    Args:
        node: DendroPy node representing the root of the subtree.
        sampfrac: Sampling fraction in (0, 1].
        yule: If True, use Yule model (zero extinction). Default: False.
        include_root: If True, include root node age in calculations. Default: False.

    Returns:
        Tuple of (birth rate, death rate).
    """
    if yule:
        return optim_yule(get_ages(node, include_root), sampfrac)

    return optim_bd(get_ages(node, include_root), sampfrac)

get_min_age(node: dendropy.Node) -> float

Get the minimum possible age for a graft in a clade.

Computes the minimum age that could be generated by grafting into the clade, considering only unlocked edges.

Parameters:

Name	Type	Description	Default
node	Node	Node representing the root of the clade.	required

Returns:

Type	Description
float	Minimum possible age (0.0 if interval is empty).

Raises:

Type	Description
DisjointConstraintError	If the age interval is not atomic (disjoint).

Source code in tact/tree_util.py

def get_min_age(node: dendropy.Node) -> float:
    """Get the minimum possible age for a graft in a clade.

    Computes the minimum age that could be generated by grafting into the
    clade, considering only unlocked edges.

    Args:
        node: Node representing the root of the clade.

    Returns:
        Minimum possible age (0.0 if interval is empty).

    Raises:
        DisjointConstraintError: If the age interval is not atomic (disjoint).
    """
    interval = get_age_intervals(node)

    if not interval.atomic:
        raise DisjointConstraintError(f"Constraint on {node} implies disjoint interval {interval}")

    if interval.empty:
        return 0.0

    return float(interval.lower)

get_monophyletic_node(tree: dendropy.Tree, species: set[str]) -> dendropy.Node | None

Get the MRCA node if it forms a monophyletic group.

Parameters:

Name	Type	Description	Default
tree	Tree	DendroPy tree object.	required
species	set[str]	Set of taxon labels to check for monophyly.	required

Returns:

Type	Description
Node | None	MRCA node if all its descendants are in the species set, None otherwise.

Source code in tact/tree_util.py

def get_monophyletic_node(tree: dendropy.Tree, species: set[str]) -> dendropy.Node | None:
    """Get the MRCA node if it forms a monophyletic group.

    Args:
        tree: DendroPy tree object.
        species: Set of taxon labels to check for monophyly.

    Returns:
        MRCA node if all its descendants are in the species set, None otherwise.
    """
    mrca = tree.mrca(taxon_labels=species)
    if mrca and species.issuperset(get_tip_labels(mrca)):
        return mrca

    return None

get_short_branches(node: dendropy.Node) -> Iterator[dendropy.Edge]

Get edges with very short branch lengths.

Parameters:

Name	Type	Description	Default
node	Node	DendroPy node representing the root of the subtree.	required

Yields:

Type	Description
Edge	DendroPy edge objects with length <= 0.001.

Source code in tact/tree_util.py

def get_short_branches(node: dendropy.Node) -> Iterator[dendropy.Edge]:
    """Get edges with very short branch lengths.

    Args:
        node: DendroPy node representing the root of the subtree.

    Yields:
        DendroPy edge objects with length <= 0.001.
    """
    for edge in edge_iter(node):
        if edge.length <= 0.001:
            yield edge

get_tip_labels(tree_or_node: dendropy.Tree | dendropy.Node) -> set[str]

Get set of tip labels for a tree or node.

Parameters:

Name	Type	Description	Default
tree_or_node	Tree | Node	DendroPy tree or node object.	required

Returns:

Type	Description
set[str]	Set of taxon labels for all tips.

Source code in tact/tree_util.py

def get_tip_labels(tree_or_node: dendropy.Tree | dendropy.Node) -> set[str]:
    """Get set of tip labels for a tree or node.

    Args:
        tree_or_node: DendroPy tree or node object.

    Returns:
        Set of taxon labels for all tips.
    """
    if isinstance(tree_or_node, dendropy.Tree):
        return {x.taxon.label for x in tree_or_node.leaf_node_iter()}
    return {x.taxon.label for x in tree_or_node.leaf_iter()}

get_tree(path: str, namespace: dendropy.TaxonNamespace | None = None) -> dendropy.Tree

Load a DendroPy tree from a file path.

Loads a Newick-format tree and precalculates node ages and bipartition bitmasks for efficient operations.

Parameters:

Name	Type	Description	Default
path	str	File path to the tree file.	required
namespace	TaxonNamespace | None	Optional taxon namespace to use. Default: None.	None

Returns:

Type	Description
Tree	DendroPy tree object with ages and bipartitions calculated.

Source code in tact/tree_util.py

def get_tree(path: str, namespace: dendropy.TaxonNamespace | None = None) -> dendropy.Tree:
    """Load a DendroPy tree from a file path.

    Loads a Newick-format tree and precalculates node ages and bipartition
    bitmasks for efficient operations.

    Args:
        path: File path to the tree file.
        namespace: Optional taxon namespace to use. Default: None.

    Returns:
        DendroPy tree object with ages and bipartitions calculated.
    """
    tree = dendropy.Tree.get_from_path(path, schema="newick", taxon_namespace=namespace, rooting="default-rooted")
    update_tree_view(tree)
    return tree

graft_node(graft_recipient: dendropy.Node, graft: dendropy.Node, stem: bool = False, taxon_namespace: dendropy.TaxonNamespace | None = None) -> dendropy.Node

Graft a node randomly into a subtree.

Grafts a node into the subtree below the recipient node, randomly selecting an eligible edge. The graft node's age must be set. Edge lengths are adjusted to maintain ultrametricity.

The eligible edge (above which the graft is placed) must satisfy:

1. Not be the crown node
2. Head node younger than graft node
3. Tail node older than graft node
4. Not be locked

If taxon_namespace is given, ensure that the tree is left ready for MRCA lookups without a subsequent call to update_tree_view. Prior to grafting, the bitmasks of the tree must be up-to-date, and every node in the grafted subtree must already have its age set.

• leafset bitmasks are computed for the grafted subtree
• new taxa are added to the bitmask of every edge between the graft and the root

Parameters:

Name	Type	Description	Default
graft_recipient	Node	Node representing the clade to graft into.	required
graft	Node	Node to graft (must have age attribute set).	required
stem	bool	If True, allow grafting on the stem edge. Default: False.	False
taxon_namespace	TaxonNamespace | None	If given, keep the leafset bitmasks of the tree up to date. Default: None.	None

Returns:

Type	Description
Node	The crown node of the clade (may be the graft if it becomes the new crown).

Raises:

Type	Description
Exception	If no eligible edge is found or negative branch lengths result.

Source code in tact/tree_util.py

def graft_node(
    graft_recipient: dendropy.Node,
    graft: dendropy.Node,
    stem: bool = False,
    taxon_namespace: dendropy.TaxonNamespace | None = None,
) -> dendropy.Node:
    """Graft a node randomly into a subtree.

    Grafts a node into the subtree below the recipient node, randomly selecting
    an eligible edge. The graft node's age must be set. Edge lengths are
    adjusted to maintain ultrametricity.

    The eligible edge (above which the graft is placed) must satisfy:

    1. Not be the crown node
    2. Head node younger than graft node
    3. Tail node older than graft node
    4. Not be locked

    If `taxon_namespace` is given, ensure that the tree is left ready for MRCA lookups
    without a subsequent call to `update_tree_view`. Prior to grafting, the bitmasks of
    the tree must be up-to-date, and every node in the grafted subtree must already have
    its age set.

    * leafset bitmasks are computed for the grafted subtree
    * new taxa are added to the bitmask of every edge between the graft and the root

    Args:
        graft_recipient: Node representing the clade to graft into.
        graft: Node to graft (must have age attribute set).
        stem: If True, allow grafting on the stem edge. Default: False.
        taxon_namespace: If given, keep the leafset bitmasks of the tree up to date. Default: None.

    Returns:
        The crown node of the clade (may be the graft if it becomes the new crown).

    Raises:
        Exception: If no eligible edge is found or negative branch lengths result.
    """

    def filter_fn(x: dendropy.Edge) -> bool:
        return x.head_node.age <= graft.age and x.head_node.parent_node.age >= graft.age and x.label != "locked"

    all_edges = list(edge_iter(graft_recipient))
    if stem:
        # also include the crown node's subtending edge
        all_edges.append(graft_recipient.edge)
    eligible_edges = [x for x in all_edges if filter_fn(x)]

    if not eligible_edges:
        raise Exception(f"could not place node {graft} in clade {graft_recipient}")

    focal_node = random.choice([x.head_node for x in eligible_edges])
    seed_node = focal_node.parent_node
    sisters = focal_node.sibling_nodes()

    # pick a child edge and detach its corresponding node
    #
    # DendroPy's Node.remove_child() messes with the edge lengths.
    # But, Node.clear_child_nodes() simply cuts that bit of the tree out.
    seed_node.clear_child_nodes()

    # set the correct edge length on the grafted node and make the grafted
    # node a child of the seed node
    graft.edge.length = seed_node.age - graft.age
    if graft.edge.length < 0:
        raise Exception("negative branch length")
    sisters.append(graft)
    seed_node.set_child_nodes(sisters)

    # make the focal node a child of the grafted node and set edge length
    focal_node.edge.length = graft.age - focal_node.age
    if focal_node.edge.length < 0:
        raise Exception("negative branch length")
    graft.add_child(focal_node)

    if taxon_namespace is not None:
        new_taxa = 0
        for child in graft.child_node_iter():
            if child is not focal_node:
                new_taxa |= encode_leafset_bitmasks(child, taxon_namespace)
        set_leafset_bitmask(graft, new_taxa | focal_node.edge.bipartition.leafset_bitmask)
        for ancestor in graft.ancestor_iter():
            set_leafset_bitmask(ancestor, new_taxa | ancestor.edge.bipartition.leafset_bitmask)

    # return the (potentially new) crown of the clade
    if graft_recipient.parent_node == graft:
        return graft
    return graft_recipient

is_binary(node: dendropy.Node) -> bool

Check if a subtree is fully bifurcating.

Parameters:

Name	Type	Description	Default
node	Node	DendroPy node representing the root of the subtree.	required

Returns:

Type	Description
bool	True if all internal nodes have exactly two children, False otherwise.

Source code in tact/tree_util.py

def is_binary(node: dendropy.Node) -> bool:
    """Check if a subtree is fully bifurcating.

    Args:
        node: DendroPy node representing the root of the subtree.

    Returns:
        True if all internal nodes have exactly two children, False otherwise.
    """
    for internal_node in node.preorder_internal_node_iter():
        if len(internal_node.child_nodes()) != 2:
            return False
    return True

is_fully_locked(node: dendropy.Node) -> bool

Check if all edges in a subtree are locked.

Parameters:

Name	Type	Description	Default
node	Node	Node representing the root of the subtree.	required

Returns:

Type	Description
bool	True if all edges are locked, False otherwise.

Source code in tact/tree_util.py

def is_fully_locked(node: dendropy.Node) -> bool:
    """Check if all edges in a subtree are locked.

    Args:
        node: Node representing the root of the subtree.

    Returns:
        True if all edges are locked, False otherwise.
    """
    return all(x.label == "locked" for x in edge_iter(node))

is_ultrametric(tree: dendropy.Tree, tolerance: float = 1e-06) -> tuple[bool, tuple[tuple[str, float], tuple[str, float]]]

Check if a tree is ultrametric within a specified tolerance.

Parameters:

Name	Type	Description	Default
tree	Tree	DendroPy tree object to check.	required
tolerance	float	Relative tolerance for ultrametricity check. Default: 1e-6.	1e-06

Returns:

Type	Description
bool	Tuple of (is_ultrametric, (min_tip, max_tip)) where min_tip and max_tip
tuple[tuple[str, float], tuple[str, float]]	are tuples of (label, root_distance) for the tips with minimum and
tuple[bool, tuple[tuple[str, float], tuple[str, float]]]	maximum root-to-tip distances.

Source code in tact/tree_util.py

def is_ultrametric(
    tree: dendropy.Tree, tolerance: float = 1e-6
) -> tuple[bool, tuple[tuple[str, float], tuple[str, float]]]:
    """Check if a tree is ultrametric within a specified tolerance.

    Args:
        tree: DendroPy tree object to check.
        tolerance: Relative tolerance for ultrametricity check. Default: 1e-6.

    Returns:
        Tuple of (is_ultrametric, (min_tip, max_tip)) where min_tip and max_tip
        are tuples of (label, root_distance) for the tips with minimum and
        maximum root-to-tip distances.
    """
    tree.calc_node_root_distances()
    lengths: dict[str, float] = {}
    for leaf in tree.leaf_node_iter():
        lengths[leaf.taxon.label] = leaf.root_distance
    t_min = min(lengths.items(), key=lambda x: x[1])
    t_max = max(lengths.items(), key=lambda x: x[1])
    return (math.isclose(t_min[1], t_max[1], rel_tol=tolerance), (t_min, t_max))

lock_clade(node: dendropy.Node, stem: bool = False) -> None

Lock a clade to prevent future grafts.

Marks all edges in the subtree as locked, preventing new grafts from being placed on them.

Parameters:

Name	Type	Description	Default
node	Node	Node representing the root of the clade to lock.	required
stem	bool	If True, also lock the stem edge. Default: False.	False

Source code in tact/tree_util.py

def lock_clade(node: dendropy.Node, stem: bool = False) -> None:
    """Lock a clade to prevent future grafts.

    Marks all edges in the subtree as locked, preventing new grafts from
    being placed on them.

    Args:
        node: Node representing the root of the clade to lock.
        stem: If True, also lock the stem edge. Default: False.
    """
    for edge in edge_iter(node):
        edge.label = "locked"
    if stem:
        node.edge.label = "locked"

node_age(node: dendropy.Node) -> float

Get the age of a node.

DendroPy initializes Node.age to None, so this narrows it to a float for type checkers.

Parameters:

Name	Type	Description	Default
node	Node	DendroPy node with its age set.	required

Returns:

Type	Description
float	The age of the node.

Raises:

Type	Description
ValueError	If the node's age has not been set.

Source code in tact/tree_util.py

def node_age(node: dendropy.Node) -> float:
    """Get the age of a node.

    DendroPy initializes `Node.age` to None, so this narrows it to a float for type checkers.

    Args:
        node: DendroPy node with its age set.

    Returns:
        The age of the node.

    Raises:
        ValueError: If the node's age has not been set.
    """
    if node.age is None:
        raise ValueError(f"{node} has no age; have node ages been calculated?")
    return node.age

set_leafset_bitmask(node: dendropy.Node, bitmask: int) -> None

Set the leafset bitmask of the edge subtending a node.

Parameters:

Name	Type	Description	Default
node	Node	Node whose subtending edge should be updated.	required
bitmask	int	Bitmask of the taxa descending from the node.	required

Source code in tact/tree_util.py

def set_leafset_bitmask(node: dendropy.Node, bitmask: int) -> None:
    """Set the leafset bitmask of the edge subtending a node.

    Args:
        node: Node whose subtending edge should be updated.
        bitmask: Bitmask of the taxa descending from the node.
    """
    node.edge.bipartition = dendropy.Bipartition(
        leafset_bitmask=bitmask, compile_bipartition=False, is_mutable=True, is_rooted=True
    )

unlock_clade(node: dendropy.Node, stem: bool = False) -> None

Unlock a clade to allow future grafts.

Removes the locked label from all edges in the subtree.

Parameters:

Name	Type	Description	Default
node	Node	Node representing the root of the clade to unlock.	required
stem	bool	If True, also unlock the stem edge. Default: False.	False

Source code in tact/tree_util.py

def unlock_clade(node: dendropy.Node, stem: bool = False) -> None:
    """Unlock a clade to allow future grafts.

    Removes the locked label from all edges in the subtree.

    Args:
        node: Node representing the root of the clade to unlock.
        stem: If True, also unlock the stem edge. Default: False.
    """
    for edge in edge_iter(node):
        edge.label = ""
    if stem:
        node.edge.label = ""

update_tree_view(tree: dendropy.Tree) -> set[str]

Update a tree with node ages and bipartition bitmasks.

Performs in-place updates to calculate node ages and bipartition bitmasks, correcting for minor ultrametricity errors.

Parameters:

Name	Type	Description	Default
tree	Tree	DendroPy tree object to update.	required

Returns:

Type	Description
set[str]	Set of tip labels in the tree.

Source code in tact/tree_util.py

def update_tree_view(tree: dendropy.Tree) -> set[str]:
    """Update a tree with node ages and bipartition bitmasks.

    Performs in-place updates to calculate node ages and bipartition bitmasks,
    correcting for minor ultrametricity errors.

    Args:
        tree: DendroPy tree object to update.

    Returns:
        Set of tip labels in the tree.
    """
    tree.calc_node_ages(is_force_max_age=True)
    tree.update_bipartitions()
    return get_tip_labels(tree)

FastMRCA

Functions in tact/fastmrca.py.

Fast MRCA lookups by taxon label.

FastMRCA

MRCA lookups by taxon label on one tree.

TaxonNamespace.taxa_bitmask(labels=...) scans the whole namespace once per label, which is quadratic. This caches the bitmask of each label instead, and rebuilds the cache when taxa are added to or removed from the namespace.

Parameters:

Name	Type	Description	Default
tree	Tree	Tree to look up MRCAs in. Its bitmasks must be kept up to date, for example with update_tree_view, or by grafting with graft_node(..., taxon_namespace=...).	required

Source code in tact/fastmrca.py

class FastMRCA:
    """MRCA lookups by taxon label on one tree.

    `TaxonNamespace.taxa_bitmask(labels=...)` scans the whole namespace once per label, which
    is quadratic. This caches the bitmask of each label instead, and rebuilds the cache when taxa
    are added to or removed from the namespace.

    Args:
        tree: Tree to look up MRCAs in. Its bitmasks must be kept up to date, for example with
            `update_tree_view`, or by grafting with `graft_node(..., taxon_namespace=...)`.
    """

    def __init__(self, tree: dendropy.Tree) -> None:
        """See the class docstring for the arguments."""
        self.tree = tree
        # combined bitmask of the taxa carrying each label
        self._label_bitmasks: dict[str, int] = {}
        self._namespace_size = -1
        self._index_labels()

    def _index_labels(self) -> None:
        """Rebuild the label to bitmask index for the tree's taxon namespace."""
        tn = self.tree.taxon_namespace
        self._label_bitmasks.clear()
        for taxon in tn:
            if taxon.label is None:
                continue
            # normalize labels the same way DendroPy does when it matches them
            key = taxon.label if tn.is_case_sensitive else str(taxon.label).lower()
            self._label_bitmasks[key] = self._label_bitmasks.get(key, 0) | tn.taxon_bitmask(taxon)
        self._namespace_size = len(tn)

    def bitmask(self, labels: Iterable[str]) -> int:
        """Get a bitmask for the specified taxa labels.

        Intended to be equivalent to DendroPy's `TaxonNamespace.taxa_bitmask(labels=labels)`.

        * Labels that are not in the namespace are ignored
        * Case sensitivity of the namespace is respected

        Args:
            labels: Iterable of taxon labels.

        Returns:
            Bitmask representing the taxa.
        """
        tn = self.tree.taxon_namespace
        if len(tn) != self._namespace_size:
            # taxa were added to or removed from the namespace since the index was built
            self._index_labels()
        mask = 0
        if tn.is_case_sensitive:
            for label in labels:
                mask |= self._label_bitmasks.get(label, 0)
        else:
            for label in labels:
                mask |= self._label_bitmasks.get(str(label).lower(), 0)
        return mask

    def get(self, labels: Iterable[str]) -> dendropy.Node | None:
        """Get the MRCA node for the specified taxa.

        Returns the most recent common ancestor node if all descendants of that
        node are included in the label set, otherwise returns None.

        Args:
            labels: Iterable of taxon labels to find MRCA for.

        Returns:
            MRCA node if it forms a monophyletic group, None otherwise.
        """
        labels_set = set(labels)
        mrca = self.tree.mrca(leafset_bitmask=self.bitmask(labels_set))
        if mrca and labels_set.issuperset(get_tip_labels(mrca)):
            return mrca
        return None

tree = tree instance-attribute

__init__(tree: dendropy.Tree) -> None

See the class docstring for the arguments.

Source code in tact/fastmrca.py

def __init__(self, tree: dendropy.Tree) -> None:
    """See the class docstring for the arguments."""
    self.tree = tree
    # combined bitmask of the taxa carrying each label
    self._label_bitmasks: dict[str, int] = {}
    self._namespace_size = -1
    self._index_labels()

bitmask(labels: Iterable[str]) -> int

Get a bitmask for the specified taxa labels.

Intended to be equivalent to DendroPy's TaxonNamespace.taxa_bitmask(labels=labels).

• Labels that are not in the namespace are ignored
• Case sensitivity of the namespace is respected

Parameters:

Name	Type	Description	Default
labels	Iterable[str]	Iterable of taxon labels.	required

Returns:

Type	Description
int	Bitmask representing the taxa.

Source code in tact/fastmrca.py

def bitmask(self, labels: Iterable[str]) -> int:
    """Get a bitmask for the specified taxa labels.

    Intended to be equivalent to DendroPy's `TaxonNamespace.taxa_bitmask(labels=labels)`.

    * Labels that are not in the namespace are ignored
    * Case sensitivity of the namespace is respected

    Args:
        labels: Iterable of taxon labels.

    Returns:
        Bitmask representing the taxa.
    """
    tn = self.tree.taxon_namespace
    if len(tn) != self._namespace_size:
        # taxa were added to or removed from the namespace since the index was built
        self._index_labels()
    mask = 0
    if tn.is_case_sensitive:
        for label in labels:
            mask |= self._label_bitmasks.get(label, 0)
    else:
        for label in labels:
            mask |= self._label_bitmasks.get(str(label).lower(), 0)
    return mask

get(labels: Iterable[str]) -> dendropy.Node | None

Get the MRCA node for the specified taxa.

Returns the most recent common ancestor node if all descendants of that node are included in the label set, otherwise returns None.

Parameters:

Name	Type	Description	Default
labels	Iterable[str]	Iterable of taxon labels to find MRCA for.	required

Returns:

Type	Description
Node | None	MRCA node if it forms a monophyletic group, None otherwise.

Source code in tact/fastmrca.py

def get(self, labels: Iterable[str]) -> dendropy.Node | None:
    """Get the MRCA node for the specified taxa.

    Returns the most recent common ancestor node if all descendants of that
    node are included in the label set, otherwise returns None.

    Args:
        labels: Iterable of taxon labels to find MRCA for.

    Returns:
        MRCA node if it forms a monophyletic group, None otherwise.
    """
    labels_set = set(labels)
    mrca = self.tree.mrca(leafset_bitmask=self.bitmask(labels_set))
    if mrca and labels_set.issuperset(get_tip_labels(mrca)):
        return mrca
    return None

Validation

Functions in tact/validation.py.

Various validation functions for click classes and parameters.

NEXUS_TREE = 'this is a Nexus file! Use a Newick tree instead' module-attribute

BackboneCommand

Bases: Command

Helper class to validate a Click Command that contains a backbone tree.

At a minimum, the Command must contain a backbone parameter, which is validated by validate_newick and checked to ensure it is a binary tree.

If the command also contains a taxonomy parameter, representing a taxonomic phylogeny, every tip of backbone must match a species in it, ignoring spaces, underscores and case, and the backbone is moved onto the taxonomy's TaxonNamespace. An optional outgroups parameter may add other taxa not in the taxonomy.

If the command also contains an ultrametricity_precision parameter, the ultrametricity of the backbone is also checked.

Source code in tact/validation.py

class BackboneCommand(click.Command):
    """Helper class to validate a Click Command that contains a backbone tree.

    At a minimum, the Command must contain a `backbone` parameter, which is validated by `validate_newick`
    and checked to ensure it is a binary tree.

    If the command also contains a `taxonomy` parameter, representing a taxonomic phylogeny,
    every tip of `backbone` must match a species in it, ignoring spaces, underscores and case,
    and the backbone is moved onto the taxonomy's TaxonNamespace. An optional `outgroups`
    parameter may add other taxa not in the `taxonomy`.

    If the command also contains an `ultrametricity_precision` parameter, the
    ultrametricity of the `backbone` is also checked.
    """

    def validate_backbone_variables(self, ctx: click.Context, params: dict[str, Any]) -> dict[str, Any]:
        """Validates variables related to the backbone and taxonomy files."""
        param = next(p for p in self.params if p.name == "backbone")
        backbone = validate_newick(ctx, param, params["backbone"])
        if "taxonomy" in params:
            tn = params["taxonomy"].taxon_namespace
            known = {name_key(taxon.label) for taxon in tn}
            tn.new_taxa(name for name in params.get("outgroups") or [] if name_key(name) not in known)
            tn.is_mutable = False
            missing, respelled = adopt_names(backbone, tn)
            if missing:
                msg = (
                    f"{len(missing)} tip{'s are' if len(missing) != 1 else ' is'} not in the taxonomy:\n"
                    f"{fmt_bullets(missing)}\n"
                    f"Add {'them' if len(missing) != 1 else 'it'} to the taxonomy, "
                    "or list outgroups that should stay out of it with --outgroups."
                )
                raise click.BadParameter(msg, ctx, param)
            if respelled:
                click.echo("Note: these backbone tips are spelled differently in the taxonomy, which TACT uses:")
                click.echo(fmt_bullets([f"{name} => {taxon}" for name, taxon in respelled.items()]))

        check_binary(ctx, param, backbone)
        check_branch_lengths(ctx, param, backbone)
        update_tree_view(backbone)

        if "ultrametricity_precision" in params:
            check_ultrametric(ctx, param, backbone, params["ultrametricity_precision"])

        params["backbone"] = backbone
        return params

    def make_context(
        self, info_name: str | None, args: list[str], parent: click.Context | None = None, **extra: object
    ) -> click.Context:
        """Set up the proper Click context for a command handler."""
        ctx = super().make_context(info_name, args, parent, **extra)
        ctx.params = self.validate_backbone_variables(ctx, ctx.params)
        return ctx

make_context(info_name: str | None, args: list[str], parent: click.Context | None = None, **extra: object) -> click.Context

Set up the proper Click context for a command handler.

Source code in tact/validation.py

def make_context(
    self, info_name: str | None, args: list[str], parent: click.Context | None = None, **extra: object
) -> click.Context:
    """Set up the proper Click context for a command handler."""
    ctx = super().make_context(info_name, args, parent, **extra)
    ctx.params = self.validate_backbone_variables(ctx, ctx.params)
    return ctx

validate_backbone_variables(ctx: click.Context, params: dict[str, Any]) -> dict[str, Any]

Validates variables related to the backbone and taxonomy files.

Source code in tact/validation.py

def validate_backbone_variables(self, ctx: click.Context, params: dict[str, Any]) -> dict[str, Any]:
    """Validates variables related to the backbone and taxonomy files."""
    param = next(p for p in self.params if p.name == "backbone")
    backbone = validate_newick(ctx, param, params["backbone"])
    if "taxonomy" in params:
        tn = params["taxonomy"].taxon_namespace
        known = {name_key(taxon.label) for taxon in tn}
        tn.new_taxa(name for name in params.get("outgroups") or [] if name_key(name) not in known)
        tn.is_mutable = False
        missing, respelled = adopt_names(backbone, tn)
        if missing:
            msg = (
                f"{len(missing)} tip{'s are' if len(missing) != 1 else ' is'} not in the taxonomy:\n"
                f"{fmt_bullets(missing)}\n"
                f"Add {'them' if len(missing) != 1 else 'it'} to the taxonomy, "
                "or list outgroups that should stay out of it with --outgroups."
            )
            raise click.BadParameter(msg, ctx, param)
        if respelled:
            click.echo("Note: these backbone tips are spelled differently in the taxonomy, which TACT uses:")
            click.echo(fmt_bullets([f"{name} => {taxon}" for name, taxon in respelled.items()]))

    check_binary(ctx, param, backbone)
    check_branch_lengths(ctx, param, backbone)
    update_tree_view(backbone)

    if "ultrametricity_precision" in params:
        check_ultrametric(ctx, param, backbone, params["ultrametricity_precision"])

    params["backbone"] = backbone
    return params

check_binary(ctx: click.Context | None, param: click.Parameter | None, tree: dendropy.Tree) -> None

Checks that every internal node of a tree has two children, naming those that do not.

Source code in tact/validation.py

def check_binary(ctx: click.Context | None, param: click.Parameter | None, tree: dendropy.Tree) -> None:
    """Checks that every internal node of a tree has two children, naming those that do not."""
    nodes = [node for node in tree.preorder_internal_node_iter() if len(node.child_nodes()) != 2]
    if not nodes:
        return
    problems = []
    for node in nodes:
        children = node.child_nodes()
        problem = f"{len(children)} branch{'es' if len(children) != 1 else ''} to "
        problem += fmt_species_list(first_tip(child) for child in children)
        if node is tree.seed_node:
            problem += " (at the root: if this tree is unrooted it must be rooted first)"
        problems.append(problem)
    msg = (
        f"the tree is not binary; {len(nodes)} node{'s have' if len(nodes) != 1 else ' has'} "
        f"other than two branches below {'them' if len(nodes) != 1 else 'it'}:\n{fmt_bullets(problems)}"
    )
    raise click.BadParameter(msg, ctx, param)

check_branch_lengths(ctx: click.Context | None, param: click.Parameter | None, tree: dendropy.Tree) -> None

Checks that every branch of a tree below its root has a length.

Source code in tact/validation.py

def check_branch_lengths(ctx: click.Context | None, param: click.Parameter | None, tree: dendropy.Tree) -> None:
    """Checks that every branch of a tree below its root has a length."""
    nodes = [node for node in tree.preorder_node_iter() if node is not tree.seed_node and node.edge.length is None]
    if not nodes:
        return
    example = next((node for node in nodes if node.is_leaf()), nodes[0])
    if example.is_leaf():
        where = example.taxon.label
    else:
        where = "the ancestor of " + fmt_species_list(first_tip(child) for child in example.child_nodes())
    verb = "has" if len(nodes) == 1 else "have"
    msg = (
        f"{len(nodes)} of {len(tree.nodes()) - 1} branches {verb} no length, such as the one to {where}; "
        "TACT needs a dated tree"
    )
    raise click.BadParameter(msg, ctx, param)

check_ultrametric(ctx: click.Context | None, param: click.Parameter | None, tree: dendropy.Tree, precision: float) -> None

Checks that all tips of a tree are the same distance from the root, within a relative precision.

Source code in tact/validation.py

def check_ultrametric(
    ctx: click.Context | None, param: click.Parameter | None, tree: dendropy.Tree, precision: float
) -> None:
    """Checks that all tips of a tree are the same distance from the root, within a relative `precision`."""
    ultra, ((short_tip, short), (long_tip, long)) = is_ultrametric(tree, precision)
    if ultra:
        return
    # is_ultrametric has set the root distances
    tips = tree.leaf_nodes()
    n_short = sum(not math.isclose(tip.root_distance, long, rel_tol=precision) for tip in tips)
    msg = (
        f"the tree is not ultrametric: tips are between {short} ({short_tip}) and {long} ({long_tip}) "
        f"from the root, and {n_short} of {len(tips)} tips are closer to it than {long_tip}\n"
        "Increase --ultrametricity-precision or use phytools::force.ultrametric in R."
    )
    raise click.BadParameter(msg, ctx, param)

first_tip(node: dendropy.Node) -> str

The label of the first tip below node.

Source code in tact/validation.py

def first_tip(node: dendropy.Node) -> str:
    """The label of the first tip below `node`."""
    return next(node.leaf_iter()).taxon.label

fmt_bullets(items: Sequence[str]) -> str

List items one per line, up to MAX_PROBLEMS of them, saying how many more there are.

Source code in tact/validation.py

def fmt_bullets(items: Sequence[str]) -> str:
    """List `items` one per line, up to `MAX_PROBLEMS` of them, saying how many more there are."""
    lines = [f"* {item}" for item in items[:MAX_PROBLEMS]]
    if len(items) > MAX_PROBLEMS:
        lines.append(f"* ... and {len(items) - MAX_PROBLEMS} more")
    return "\n".join(lines)

fmt_spellings(spellings: Sequence[str]) -> str

Join the spellings of a name, as A, B and C.

Source code in tact/validation.py

def fmt_spellings(spellings: Sequence[str]) -> str:
    """Join the spellings of a name, as `A, B and C`."""
    return ", ".join(spellings[:-1]) + " and " + spellings[-1]

is_nexus(text: str) -> bool

Whether text is the start of a Nexus file.

Source code in tact/validation.py

def is_nexus(text: str) -> bool:
    """Whether `text` is the start of a Nexus file."""
    return text.lstrip()[:6].upper() == "#NEXUS"

read_newick(ctx: click.Context | None, param: click.Parameter | None, text: str) -> dendropy.Tree

Read a Newick tree into a namespace of its own, with its names cleaned.

Names that differ only in spaces, underscores or case are an error, rather than being silently merged.

Source code in tact/validation.py

def read_newick(ctx: click.Context | None, param: click.Parameter | None, text: str) -> dendropy.Tree:
    """Read a Newick tree into a namespace of its own, with its names cleaned.

    Names that differ only in spaces, underscores or case are an error, rather than being silently merged.
    """
    if is_nexus(text):
        raise click.BadParameter(NEXUS_TREE, ctx, param)
    if not text.strip():
        raise click.BadParameter("the file is empty", ctx, param)
    if not text.rstrip().endswith(";"):
        # DendroPy suggests one of its own options for this
        raise click.BadParameter("this is not a Newick tree: it does not end with a semicolon", ctx, param)
    try:
        # Underscores and case are kept so that the names are compared and cleaned in one place
        tree = dendropy.Tree.get(
            data=text,
            schema="newick",
            rooting="default-rooted",
            preserve_underscores=True,
            case_sensitive_taxon_labels=True,
            taxon_namespace=dendropy.TaxonNamespace(is_case_sensitive=True),
        )
    except NewickReader.NewickReaderDuplicateTaxonError as e:
        # DendroPy puts the label at the end of a long explanation
        label = clean_name((e.message or "").rsplit(": ", 1)[-1])
        raise click.BadParameter(f"the tip {label} appears more than once", ctx, param) from None
    except DataParseError as e:
        msg = f"this is not a Newick tree: {e.message}"
        if e.line_num is not None:
            msg += f" (line {e.line_num}, column {e.col_num})"
        raise click.BadParameter(msg, ctx, param) from None
    tip_clashes, taxon_clashes = clean_tree_names(tree, keep=(ROOT,))
    problems = [f"tips {fmt_spellings(group)}" for group in tip_clashes]
    problems += [f"taxa {fmt_spellings(group)}" for group in taxon_clashes]
    if problems:
        msg = (
            f"{len(problems)} name{'s are' if len(problems) != 1 else ' is'} spelled more than one way, "
            f"differing only in spaces, underscores or case:\n{fmt_bullets(problems)}"
        )
        raise click.BadParameter(msg, ctx, param)
    # Now that no two tips differ only in case, looking them up by label can ignore it
    tree.taxon_namespace.is_case_sensitive = False
    return tree

validate_newick(ctx: click.Context | None, param: click.Parameter | None, value: IO[str]) -> dendropy.Tree

Validates a Newick tree, using appropriate defaults.

Source code in tact/validation.py

def validate_newick(ctx: click.Context | None, param: click.Parameter | None, value: IO[str]) -> dendropy.Tree:
    """Validates a Newick tree, using appropriate defaults."""
    return read_newick(ctx, param, value.read())

validate_newick_path(ctx: click.Context | None, param: click.Parameter | None, value: str) -> str

Validates that a path looks like a Newick tree, from its first characters, without reading the entire tree.

Source code in tact/validation.py

def validate_newick_path(ctx: click.Context | None, param: click.Parameter | None, value: str) -> str:
    """Validates that a path looks like a Newick tree, from its first characters, without reading the entire tree."""
    with open(value, encoding="utf-8-sig", errors="replace") as fh:
        start = fh.read(1024)
    if is_nexus(start):
        raise click.BadParameter(NEXUS_TREE)
    if start.lstrip()[:1] not in ("(", "["):
        msg = "this is not a Newick tree, which starts with '('"
        if param is not None and param.name == "taxonomy":
            msg += "; make one from a taxonomy CSV with tact_build_taxonomic_tree"
        raise click.BadParameter(msg)
    return value

validate_outgroups(ctx: click.Context | None, param: click.Parameter | None, value: str | Sequence[str] | None) -> list[str] | None

Validates an outgroups parameter, by splitting on commas and cleaning each name.

Source code in tact/validation.py

def validate_outgroups(
    ctx: click.Context | None, param: click.Parameter | None, value: str | Sequence[str] | None
) -> list[str] | None:
    """Validates an `outgroups` parameter, by splitting on commas and cleaning each name."""
    if value is None:
        return None
    if isinstance(value, str):
        value = value.split(",")
    return [clean_name(x) for x in value]

validate_output(ctx: click.Context | None, param: click.Parameter | None, value: str) -> str

Validates an output base name, checking that its directory exists so that writing to it later will work.

Make the parameter eager if other parameters' callbacks are slow, so that this runs before them.

Source code in tact/validation.py

def validate_output(ctx: click.Context | None, param: click.Parameter | None, value: str) -> str:
    """Validates an output base name, checking that its directory exists so that writing to it later will work.

    Make the parameter eager if other parameters' callbacks are slow, so that this runs before them.
    """
    directory = os.path.dirname(value) or "."
    if not os.path.isdir(directory):
        raise click.BadParameter(f"directory '{directory}' does not exist")
    if not os.access(directory, os.W_OK):
        raise click.BadParameter(f"directory '{directory}' is not writable")
    return value

validate_taxonomy_tree(ctx: click.Context | None, param: click.Parameter | None, value: str) -> dendropy.Tree

Validates a taxonomy, given either as a Newick tree or as a CSV file that is built into a tree in memory.

The format is sniffed from the first character of the file rather than taken from its extension, because taxonomy trees go by many extensions (.tre, .tree, .nwk, .txt) and a CSV need not end in .csv. A Newick tree starts with (, or [ for a comment such as [&R], which a CSV header row does not. Anything else is read as a CSV, so that a file that is neither gets the list of problems from read_taxonomy rather than a DendroPy parse error.

If the command has a fill_empty parameter, it must be eager so that it is set before this callback runs.

Source code in tact/validation.py

def validate_taxonomy_tree(ctx: click.Context | None, param: click.Parameter | None, value: str) -> dendropy.Tree:
    """Validates a taxonomy, given either as a Newick tree or as a CSV file that is built into a tree in memory.

    The format is sniffed from the first character of the file rather than taken from its extension, because
    taxonomy trees go by many extensions (.tre, .tree, .nwk, .txt) and a CSV need not end in .csv. A Newick
    tree starts with `(`, or `[` for a comment such as `[&R]`, which a CSV header row does not. Anything else
    is read as a CSV, so that a file that is neither gets the list of problems from `read_taxonomy` rather than
    a DendroPy parse error.

    If the command has a `fill_empty` parameter, it must be eager so that it is set before this callback runs.
    """
    fill_empty = bool(ctx and ctx.params.get("fill_empty"))
    # utf-8-sig drops the byte order mark that spreadsheet programs often add
    with open(value, encoding="utf-8-sig") as fh:
        text = fh.read()
    if is_nexus(text):
        raise click.BadParameter("this is a Nexus file; give a Newick tree or a CSV file instead")
    if text.lstrip()[:1] in ("(", "["):
        if fill_empty:
            raise click.BadParameter("--fill-empty only applies to a taxonomy CSV, not a tree")
        tree = read_newick(ctx, param, text)
    else:
        taxonomy = read_taxonomy(value, fill_empty)
        echo_changes(taxonomy)
        tree = read_newick(ctx, param, taxonomy.to_newick())
    return validate_tree_node_depths(ctx, param, tree)

validate_tree_node_depths(ctx: click.Context | None, param: click.Parameter | None, value: dendropy.Tree) -> dendropy.Tree

Validates a DendroPy tree, ensuring that the node depth is equal for all tips.

Source code in tact/validation.py

def validate_tree_node_depths(
    ctx: click.Context | None, param: click.Parameter | None, value: dendropy.Tree
) -> dendropy.Tree:
    """Validates a DendroPy tree, ensuring that the node depth is equal for all tips."""
    node_depths = compute_node_depths(value)
    stats: collections.defaultdict[int, int] = collections.defaultdict(int)
    for v in node_depths.values():
        stats[v] += 1
    if len(stats) > 1:
        msg = "The tips of your taxonomy tree do not have equal numbers of ranked clades in their ancestor chain:\n"
        for k in sorted(stats.keys()):
            msg += f"* {stats[k]} tips have {k} ranked ancestors\n"
        raise click.BadParameter(msg)
    return value

Exceptions

Functions in tact/exceptions.py.

Exceptions used by TACT.

DisjointConstraintError

Bases: TactError

Exception raised when a set of constraints lead to a disjoint implied age interval.

Source code in tact/exceptions.py

class DisjointConstraintError(TactError):
    """Exception raised when a set of constraints lead to a disjoint implied age interval."""

TactError

Bases: Exception

Base class for errors raised by TACT.

Source code in tact/exceptions.py

class TactError(Exception):
    """Base class for errors raised by TACT."""