Skip to content

Trees

Newick I/O and the quarimo array-layout tree representation.

HifukuTree dataclass

Unrooted binary phylogenetic tree, stored as parallel numpy arrays.

Node indices follow the quarimo layout:

  • Leaves occupy indices 0 to n_leaves - 1, in left-first DFS order.
  • Non-root internal nodes occupy indices n_leaves to n_nodes - 2.
  • The root occupies index n_nodes - 1.

Parsing binarizes every multifurcation. Each k-ary node (k > 2) becomes a chain of binary nodes, joined by zero-length edges.

Attributes:

Name Type Description
parent ndarray

int32, shape (n_nodes,). Parent index of each node. The root has -1.
left_child ndarray

int32, shape (n_nodes,). Left child index. Leaf nodes have -1.
right_child ndarray

int32, shape (n_nodes,). Right child index. Leaf nodes have -1.
edge_len ndarray

float64, shape (n_nodes,). Length of the edge from the node to its parent. The root has NaN, because it has no parent edge.
names list[str]

Length n_nodes, one entry per node. Leaf entries hold the taxon label. Internal entries hold the empty string. This length equals n_nodes, not n_leaves. To get the taxon count, use n_leaves, n_taxa, or leaf_labels, not len(names).
n_nodes int

Total number of nodes: leaves, plus internal nodes, plus the root.
n_leaves int

Number of leaf (tip) nodes. This is the taxon count.
root int

Index of the root node. This index always equals n_nodes - 1.
had_multifurcations bool

True if the input Newick string had a polytomy. Parsing binarizes every polytomy, so this flag is the only record that one existed.
global_leaf_indices ndarray or None

int32, shape (n_nodes,). For leaf nodes 0 to n_leaves - 1, the global TaxonTable index of that leaf's taxon. Internal nodes and the root hold -1. read_tree sets this field, and restrict carries it forward. Globally consistent CBS clade hashes need this field.
Notes
  • Ref: quarimo (array layout and iterative parser pattern).
  • Minh et al. (2020) : zero-length branch convention for polytomies.
Source code in src/hifuku/tree_io.py 
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
@dataclass
class HifukuTree:
    """
    Unrooted binary phylogenetic tree, stored as parallel numpy arrays.

    Node indices follow the quarimo layout:

    - Leaves occupy indices ``0`` to ``n_leaves - 1``, in left-first DFS
      order.
    - Non-root internal nodes occupy indices ``n_leaves`` to ``n_nodes - 2``.
    - The root occupies index ``n_nodes - 1``.

    Parsing binarizes every multifurcation. Each k-ary node (k > 2) becomes
    a chain of binary nodes, joined by zero-length edges.

    Attributes
    ----------
    parent : np.ndarray
        int32, shape (n_nodes,). Parent index of each node. The root has -1.
    left_child : np.ndarray
        int32, shape (n_nodes,). Left child index. Leaf nodes have -1.
    right_child : np.ndarray
        int32, shape (n_nodes,). Right child index. Leaf nodes have -1.
    edge_len : np.ndarray
        float64, shape (n_nodes,). Length of the edge from the node to its
        parent. The root has NaN, because it has no parent edge.
    names : list[str]
        Length n_nodes, one entry per node. Leaf entries hold the taxon
        label. Internal entries hold the empty string. This length equals
        n_nodes, not n_leaves. To get the taxon count, use n_leaves,
        n_taxa, or leaf_labels, not len(names).
    n_nodes : int
        Total number of nodes: leaves, plus internal nodes, plus the root.
    n_leaves : int
        Number of leaf (tip) nodes. This is the taxon count.
    root : int
        Index of the root node. This index always equals n_nodes - 1.
    had_multifurcations : bool
        True if the input Newick string had a polytomy. Parsing binarizes
        every polytomy, so this flag is the only record that one existed.
    global_leaf_indices : np.ndarray or None
        int32, shape (n_nodes,). For leaf nodes 0 to n_leaves - 1, the
        global TaxonTable index of that leaf's taxon. Internal nodes and
        the root hold -1. ``read_tree`` sets this field, and ``restrict``
        carries it forward. Globally consistent CBS clade hashes need this
        field.

    Notes
    -----
    - Ref: quarimo (array layout and iterative parser pattern).
    - Minh et al. (2020) : zero-length branch convention for polytomies.
    """

    parent: np.ndarray
    left_child: np.ndarray
    right_child: np.ndarray
    edge_len: np.ndarray

    names: list[str]
    n_nodes: int
    n_leaves: int
    root: int
    had_multifurcations: bool = False
    global_leaf_indices: Optional[np.ndarray] = None
    node_order: Optional[np.ndarray] = None
    """int32, shape (n_nodes - n_leaves - 1,). Holds the non-root internal
    nodes in DFS post-order, with each child listed before its parent. The
    Felsenstein peeling traversal uses this order."""

    def compute_node_order(self) -> np.ndarray:
        """
        Compute the non-root internal nodes in DFS post-order.

        This method lists each child before its parent. It walks the tree
        using the left_child and right_child pointers, so the result is
        correct for any node index assignment.

        Returns
        -------
        np.ndarray
            int32, shape (n_nodes - n_leaves - 1,). Non-root internal nodes
            in DFS post-order.
        """
        result: list[int] = []
        stack: list[tuple[int, bool]] = [(self.root, False)]
        while stack:
            nd, ready = stack.pop()
            if ready:
                if nd != self.root:
                    result.append(nd)
            else:
                lc = int(self.left_child[nd])
                rc = int(self.right_child[nd])
                stack.append((nd, True))
                if rc >= self.n_leaves:
                    stack.append((rc, False))
                if lc >= self.n_leaves:
                    stack.append((lc, False))
        return np.array(result, dtype=np.int32)

    @property
    def leaf_labels(self) -> list[str]:
        """Taxon labels for the leaf nodes, in index order 0 to n_leaves - 1."""
        return [self.names[i] for i in range(self.n_leaves)]

    @property
    def n_taxa(self) -> int:
        """Number of taxa in the tree. This equals n_leaves."""
        return self.n_leaves

    def as_newick(self) -> str:
        """Serialize the tree to a Newick string, with a trailing semicolon."""
        return _arrays_to_newick(self) + ";"

    def write_newick(self, path: Union[str, Path]) -> None:
        """Write the tree to *path* as a UTF-8 Newick file."""
        Path(path).write_text(self.as_newick() + "\n", encoding="utf-8")

    def restrict(self, labels: list[str]) -> "HifukuTree":
        """
        Return a new HifukuTree pruned to the taxa in *labels*.

        Pruning can leave degree-2 internal nodes. This method removes each
        one and adds its edge length to the surviving child's edge.

        Parameters
        ----------
        labels : list[str]
            Taxon labels to keep. Every label must already be a leaf label
            in this tree.

        Returns
        -------
        HifukuTree
            A new, independent tree that contains only the given taxa.

        Raises
        ------
        ValueError
            If a label in *labels* is not a leaf label in this tree.

        Notes
        -----
        - Sukumaran & Holder (2010) : restriction semantics.
        """
        keep = set(labels)
        missing = keep - set(self.leaf_labels)
        if missing:
            raise ValueError(f"Labels not in tree: {sorted(missing)}")
        newick = _restrict_to_newick(self, keep)
        new_tree = _parse_newick(newick)
        if self.global_leaf_indices is not None:
            label_to_global = {
                self.names[i]: int(self.global_leaf_indices[i])
                for i in range(self.n_leaves)
            }
            glidx = np.full(new_tree.n_nodes, -1, dtype=np.int32)
            for i in range(new_tree.n_leaves):
                glidx[i] = label_to_global[new_tree.names[i]]
            new_tree.global_leaf_indices = glidx
        return new_tree

    def __repr__(self) -> str:
        return f"HifukuTree(n_taxa={self.n_leaves}, n_nodes={self.n_nodes})"

node_order class-attribute instance-attribute 

node_order: Optional[ndarray] = None

int32, shape (n_nodes - n_leaves - 1,). Holds the non-root internal nodes in DFS post-order, with each child listed before its parent. The Felsenstein peeling traversal uses this order.

leaf_labels property 

leaf_labels: list[str]

Taxon labels for the leaf nodes, in index order 0 to n_leaves - 1.

n_taxa property 

n_taxa: int

Number of taxa in the tree. This equals n_leaves.

compute_node_order 

compute_node_order() -> np.ndarray

Compute the non-root internal nodes in DFS post-order.

This method lists each child before its parent. It walks the tree using the left_child and right_child pointers, so the result is correct for any node index assignment.

Returns:

Type Description
ndarray

int32, shape (n_nodes - n_leaves - 1,). Non-root internal nodes in DFS post-order.
Source code in src/hifuku/tree_io.py 
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
def compute_node_order(self) -> np.ndarray:
    """
    Compute the non-root internal nodes in DFS post-order.

    This method lists each child before its parent. It walks the tree
    using the left_child and right_child pointers, so the result is
    correct for any node index assignment.

    Returns
    -------
    np.ndarray
        int32, shape (n_nodes - n_leaves - 1,). Non-root internal nodes
        in DFS post-order.
    """
    result: list[int] = []
    stack: list[tuple[int, bool]] = [(self.root, False)]
    while stack:
        nd, ready = stack.pop()
        if ready:
            if nd != self.root:
                result.append(nd)
        else:
            lc = int(self.left_child[nd])
            rc = int(self.right_child[nd])
            stack.append((nd, True))
            if rc >= self.n_leaves:
                stack.append((rc, False))
            if lc >= self.n_leaves:
                stack.append((lc, False))
    return np.array(result, dtype=np.int32)

as_newick 

as_newick() -> str

Serialize the tree to a Newick string, with a trailing semicolon.

Source code in src/hifuku/tree_io.py 
152
153
154
def as_newick(self) -> str:
    """Serialize the tree to a Newick string, with a trailing semicolon."""
    return _arrays_to_newick(self) + ";"

write_newick 

write_newick(path: Union[str, Path]) -> None

Write the tree to path as a UTF-8 Newick file.

Source code in src/hifuku/tree_io.py 
156
157
158
def write_newick(self, path: Union[str, Path]) -> None:
    """Write the tree to *path* as a UTF-8 Newick file."""
    Path(path).write_text(self.as_newick() + "\n", encoding="utf-8")

restrict 

restrict(labels: list[str]) -> 'HifukuTree'

Return a new HifukuTree pruned to the taxa in labels.

Pruning can leave degree-2 internal nodes. This method removes each one and adds its edge length to the surviving child's edge.

Parameters:

Name Type Description Default
labels list[str]

Taxon labels to keep. Every label must already be a leaf label in this tree.

 required

Returns:

Type Description
HifukuTree

A new, independent tree that contains only the given taxa.

Raises:

Type Description
ValueError

If a label in labels is not a leaf label in this tree.
Notes
Source code in src/hifuku/tree_io.py 
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
def restrict(self, labels: list[str]) -> "HifukuTree":
    """
    Return a new HifukuTree pruned to the taxa in *labels*.

    Pruning can leave degree-2 internal nodes. This method removes each
    one and adds its edge length to the surviving child's edge.

    Parameters
    ----------
    labels : list[str]
        Taxon labels to keep. Every label must already be a leaf label
        in this tree.

    Returns
    -------
    HifukuTree
        A new, independent tree that contains only the given taxa.

    Raises
    ------
    ValueError
        If a label in *labels* is not a leaf label in this tree.

    Notes
    -----
    - Sukumaran & Holder (2010) : restriction semantics.
    """
    keep = set(labels)
    missing = keep - set(self.leaf_labels)
    if missing:
        raise ValueError(f"Labels not in tree: {sorted(missing)}")
    newick = _restrict_to_newick(self, keep)
    new_tree = _parse_newick(newick)
    if self.global_leaf_indices is not None:
        label_to_global = {
            self.names[i]: int(self.global_leaf_indices[i])
            for i in range(self.n_leaves)
        }
        glidx = np.full(new_tree.n_nodes, -1, dtype=np.int32)
        for i in range(new_tree.n_leaves):
            glidx[i] = label_to_global[new_tree.names[i]]
        new_tree.global_leaf_indices = glidx
    return new_tree

read_tree 

read_tree(source: Union[str, Path], taxon_table: TaxonTable, *, from_string: bool = False) -> HifukuTree

Parse a Newick tree and register its leaf taxa into taxon_table.

Parameters:

Name Type Description Default
source str or Path

Path to a Newick file, or a Newick string when from_string is True.

 required
taxon_table TaxonTable

Shared global TaxonTable; leaf taxa are registered (added if absent).

 required
from_string bool

If True, treat source as a Newick string rather than a file path.

 False

Returns:

Type Description
HifukuTree

Parsed tree with node_order set in DFS post-order.
Source code in src/hifuku/tree_io.py 
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
def read_tree(
    source: Union[str, Path],
    taxon_table: TaxonTable,
    *,
    from_string: bool = False,
) -> HifukuTree:
    """
    Parse a Newick tree and register its leaf taxa into *taxon_table*.

    Parameters
    ----------
    source : str or Path
        Path to a Newick file, or a Newick string when *from_string* is True.
    taxon_table : TaxonTable
        Shared global TaxonTable; leaf taxa are registered (added if absent).
    from_string : bool
        If True, treat *source* as a Newick string rather than a file path.

    Returns
    -------
    HifukuTree
        Parsed tree with node_order set in DFS post-order.
    """
    if from_string:
        newick = str(source).strip().rstrip(";")
    else:
        newick = Path(source).read_text(encoding="utf-8").strip().rstrip(";")

    tree = _parse_newick(newick)
    for lbl in tree.leaf_labels:
        taxon_table.require(lbl)
    glidx = np.full(tree.n_nodes, -1, dtype=np.int32)
    for i in range(tree.n_leaves):
        glidx[i] = taxon_table.index_of(tree.names[i])
    tree.global_leaf_indices = glidx
    return tree