# From Trees to Barcodes and Back Again: Theoretical and Statistical Perspectives
## 2 Mathematical Background
### The TMD: From Trees to Barcodes  
The TMD (Topological Morphology Descriptor) is a many-to-one function from the set of geometric trees to the set of barcodes,  
\[\mathrm{TMD}:\mathcal{T}\to\mathcal{B},\]  
that encodes the overall shape of the tree, both the topology of the branching structure of a tree and its embedding in \(\mathbb{R}^{3}\)[13]. It is defined recursively as follows. Let \(T\) be a rooted tree with root \(r\) and set \(N\) of vertices, with subset \(L\) of leaves. Let \(\delta:N\to\mathbb{R}_{\geq 0}\) be the function that assigns to each vertex its Euclidean distance to the root \(r\). Intuitively, the output of the TMD algorithm is a barcode (For those used to thinking in terms of persistent homology, the TMD computes the \(0\)-dimensional barcode, or persistence diagram, of the distance function \(\delta\). Each bar \((b,d)\) corresponds to a connected component in the sublevel sets \(\delta^{-1}\big{(}[0,t)\big{)}\), that is, a branch of the tree. Note that the birth and death roles are reversed in the TMD algorithm compared to \"usual\" terminology in persistent homology: the birth corresponds to the bifurcation and the death to the termination of a branch. ), where each bar represents a branch of the  
Figure 2: A strict barcode belonging to the equivalence class \((2134)\). One bar \((b_{0},d_{0})\) contains all the others. The remaining bars are ordered by their birth times \((b_{1}<b_{2}<b_{3}<b_{4})\). Similarly, the deaths are ordered \(d_{2}>d_{1}>d_{3}>d_{4}\), leading to the notation \((2134)\). tree. The endpoints of a bar correspond to the distances to the root from the tip of the branch and from the point where the branch bifurcates from another, longer branch, see Figure 3. Table 1 summarizes the terminology used for the TMD algorithm. For each \(v\in N\smallsetminus L\), let \(L_{v}\) denote the set of leaves of the subtree of \(T\) with root at the branch point \(v\). Let \(\mu\colon N\to\mathbb{R}\) be the function defined by  
\[\mu(v)= \begin{cases}\max\{\delta(l)\,|\,l\in L_{v}\}&:v\in N\smallsetminus L,\\ \delta(v)&:v\in L.\end{cases} \]  
We order the children of any vertex of \(T\) by their \(\mu\)-value: if \(v_{1},v_{2}\in N\) are siblings, then \(v_{1}\) is younger than \(v_{2}\) if \(\mu(v_{1})<\mu(v_{2})\). The algorithm that extracts the TMD of a geometric tree \(T\) proceeds as follows (Figure 3). Start by creating a set \(A\) of _active vertices_, originally set equal to \(L\), and an empty barcode. For each leaf \(l\), the algorithm proceeds recursively along its unique path to the root \(r\). At each branch point \(b\), one applies the standard _Elder Rule_ from topological data analysis [22], removing from \(A\) all of the children of \(b\), and adding \(b\) to \(A\). One bar is added to the barcode for each child of \(b\) except (any one of) the longest. Each child removed from \(A\) corresponds to a path from some leaf \(l\) to \(b\), which is recorded in the barcode as a bar \(\left(\delta(b),\delta(l)\right)\). These operations are applied iteratively to all the vertices until the root \(r\) is reached, at which point \(A\) contains only \(r\) and a leaf \(l\) for which \(\mu\) is maximal among all leaves, which is recorded in the barcode as a bar \(\left(0,\delta(l)\right)\). If \(T\) is a digital reconstruction of a neuron, and the function \(\delta\) is the path distance from the soma, then TMD(\(T\)) is actually a strict barcode. Indeed, the probability for two branch points or leaves to be \begin{table}
\begin{tabular}{l l l} \hline \hline  & **TMD** & **TNS** \\ \hline Goal & Compute the barcode of a tree based on a distance function & \begin{tabular}{l} Grow a new tree from a barcode \\ From root to leaves \\ \end{tabular} \\ Dorellating & \
\begin{tabular}{l} (geometric trees) \(\longrightarrow\{\text{barcodes}\}) \\ \end{tabular} &
\begin{tabular}{l} (barcodes) \(\longrightarrow\{\text{geometric trees}\}) \\ \end{tabular} \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Summary and terminology of the TMD and TNS algorithms.