Glossary and Terminological Reference

ancestor nodes

On a tree, the full set of nodes from which a given node has descended (i.e., the given node’s parent, parent’s parent, parent’s parent’s parent, and so on until the root or the seed node of the tree, inclusive).

basal
basal node

On a tree, a node that is ancestral with respect to another node. Leaf or tip nodes can never be basal, except if the tree consists of only a single node (i.e., the seed node is a leaf node). The basal-most node of a tree is the seed or root node.

basal bifurcation

On a tree, a seed or root which has exactly two child nodes. On a rooted tree this (can) reflect actual information, but on an unrooted tree, this is actually an artifact, as the seed or root does not actually exist as it is just an algorithmic contrivance. In practical terms, this means that bipartition calculations and operations on unrooted trees with basal bifurcations may result in undetermined and errorenous behavior. Thus, typically, on unrooted trees the basal bifurcation is collapsed to yield a basal trifurcation.

basal trifurcation

On a tree, a seed or root which has exactly three child nodes. While this might occur in both rooted and unrooted trees, this is typically the result of collapsing a basal bifurcation on unrooted trees.

bifurcating tree

A tree in which all nodes are bifurcating.

bifurcation
bifurcating node

On a tree, a node with exactly two child nodes. Also known as an “out-degree two” node.

bipartition
split

On a tree, a partition of the leaf set of a tree into two mutually-exclusive and collectively-comprehensive subsets. It corresponds to an edge of a tree: if we imagine “splitting” or cutting a tree into two trees at a given edge, the leaf sets of each of the new trees form the two subsets of the partitioning. A bipartition is often referred to as a split, especially in the context of unrooted trees. Bipartitions are described in detail in the DendroPy Primer.

child node

On a tree, a node descending from another node. A node on a tree may have zero or more child nodes. A node with zero child nodes is termed a leaf node.

descendent nodes

On a tree, the full set of nodes that are descended from a given node (i.e., the given node’s children and children’s children and children’s children’s children, and so on, until the leaf nodes of the tree, inclusive).

edge
branch

A connection between two nodes on a tree, modeled in DendroPy by the Edge class. A synonym for “branch” in the context of phylogenetic trees.

An edge connects a “tail node” (also called an origin or source node) to a “head node” (also called a target or destination node). The tail node is called the “parent” of the head node, while the head node is called the “child” of the tail node.

An edge is said to subtend or be incident to the node to which an edge connects, i.e., the head node. Conversely, the edges connecting a node to its children are called outgoing edges with respect to the tail node.

On a tree, every node has one and exactly one incident edge, and every edge has a head node. On the other hand, not every node may have outgoing edges (e.g, leaf nodes), and not every edge has a tail node (e.g., root nodes). As such, edges can be thought of “belonging” to their head nodes, due to this one-to-one relationship.

Edges can have any number of properties or attributes associated with them, representing a diverse range of phenomena, but the most important one is the edge length or weight.

edge length
edge weight

A (typically) quantitative value associated with an edge. This value may represent any number of things, but most typically is used to model time, evolutionary distance, or expected rates of substitution on a phylogenetic tree. An edge may have many values, quantitative or otherwise, associated with it, but the length or weight is special as it usually denotes the relationship between the tail node and head node related by an edge.

head node
target node
destination node

On an edge connecting two nodes, the node to which the edge extends to link from the other node, termed the tail node. The head node is the child node of the tail node, and the tail node is the parent node of the head node. The edge is said to subtend, or be incident, to the head node.

incident edge
subtending edge

An edge that connects to a particular node is termed the incident or subtending edge of that node.

internal edge

An edge that has an internal node as a head node.

internal node

A node that has child nodes. Also known as an inner node or branch node.

leaf edge
terminal edge
external edge
outer edge

An edge that has an leaf node as a head node.

leaf node
tip node
terminal node
external node
outer node

A node that does not have any child nodes descending from it. Also known as a tip, outer node, external node, or terminal node.

node

An fundamental element of information or data on a tree, connected to other such elements in a parent-child relationshop by edges. In DendroPy, a node is modeled by the Node class. A node has at most one parent, to which it is connected by its incident or subtending edge. A node may have zero or more children, to each of which it is connected by an independent outgoing edge edge. A node can be associated with zero or more informational or data values. In a phylogenetic tree, one of these values is often a taxon, but many other aspects of information can be modeled.

node depth

On a tree, the depth of a node is the length of the path to its root (i.e., its root path). The root node has a depth zero.

node height

The height of a node is the length of the longest downward path to a leaf from that node. The height of the root is the height of the tree. The depth of a node is the length of the path to its root (i.e., its root path). The root node has depth zero, leaf nodes have height zero, and a tree with only a single node (hence both a root and leaf) has depth and height zero. Conventionally, an empty tree (tree with no nodes, if such are allowed) has depth and height 1.

outgoing edge

An edge that connects from a particular node (to, e.g., its children is said to be an outgoing edge for that node.

parent node
ancestor node

On a tree, a node from which a given node immediately descends.

path

The sequence of edges connecting two nodes on a tree.

path length
path weight
unweighted path
weighted path

The number or sum of lengths of the edges connecting two nodes on a tree. An unweighted path length is just the number of edges:, while a *weighted* path length or path weight is the sum of :term:`edge lengths.

postorder traversal

A process by which all nodes of a tree are visited, with a particular node being visited only after its children.

preorder traversal

A process by which all nodes of a tree are visited, with a particular node being visited before its children.

rooted tree

A state of a tree in which its seed node represents the most-recent common ancestor of all the leaf nodes on the tree. Rooted trees have a distinct directionality, and ancestor-descendent relationships are not invertible.

schema

The format or syntax of serialized phylogenetic or related data. Examples are NEXUS, NEWICk, Phylip, NeXML, etc. A “schema” is DendroPy-speak for “format” (we cannot use the argument name “format” because this is a Python built-in, and hence we adopted this terminology for consistency), and is typicallly specified using one of a set of predefined string values, known as “schema specification strings”. Supported reading (input) schemas are described here while supported writing (output) schemas are described here.

seed node
root node

The first or topmost node in a tree. This is also more commonly called the “root” or “root node” of the tree, though, in the strictest sense, this equivalence is only valid when the tree is explicitly rooted. Both rooted trees and unrooted trees have seed nodes. In rooted trees, the seed node is the root of the tree.

By definition, the seed node does not have a parent node. It is the node at which algorithms on the tree begin, since as a data structure, one can only pass from parent node to child nodes. If the tree is rooted, then the seed node is equivalent to the root of the tree.

sibling node
sister node

Two or more nodes that share the same parent node, i.e., are descended from the same node, are said to be siblings or sisters with respect to each other.

subtree

A subtree of a tree is a tree consisting of a node in the tree and all its descendents. Each node on a tree thus corresponds to the root of the subtree that it determines.

tail node
source node
origin node

On an edge connecting two nodes, the node from which the edge extends to link to the other node, termed the head node. The tail node is the parent node of the head node, and the head node is the child node of the tail node. The edge is said to be an outgoing node with respect to the tail node.

taxon
operational taxonomic unit
taxon concept
taxon name

A class of organisms being modeled represented by a string label or namethat is guaranteed to be unique within a particular taxon namespace.

taxon namespace

A set of distinct and unique labels, with each label mapping to one and exactly one or names that is used to relate data from across different data sources to each other by reference to a taxon concept.

tree
arborescence

A tree is a set of nodes connected to each other in parent-child relationships given by a set of edges. In DendroPy, a tree is modeled by the Tree class. A tree is a specialization of a graph, constrained such that:

1. All its edges are directional.
2. It has no directed cycles .
3. The directionality is from the root (or “seed node” in DendroPy’s parlance) to the tips.

The first and second constraints alone result in a directed acylic graph . The addition of the third constraint results in an arborescence, which is strictly synonymous with “tree”.

unifurcation
unifurcating node

On a tree, a node with exactly one child node. Also known as an “out-degree one” node. In some cases, unifurcations may be used to represent information (e.g., a change in some value associated with edges, such as population size or a rate of some kind), but they more typically arise as side-effect of tree manipulation operations, such as re-rooting or pruning. Though DendroPy has no problem in handling unifurcations, trees with unifurcating nodes are considered pathological in many contexts and operations, and DendroPy thus provides facilities for suppressing unifurcations, either on existing trees or as they occur as a side-effect of other operations.

unrooted tree

A state of a tree in which its seed node is an algorithmic artifact, and not necessarily represents the most-recent common ancestor of all the leaf nodes on the tree. In an unrooted trees, ancestor-descendent relationships are also algorithmic artifacts and can be (conceptually) inverted without changing the information represented by the tree, though this operation usually requires a fundamental restructuring of the computational representation of the tree.