Next Article in Journal
Feature Selection from Lyme Disease Patient Survey Using Machine Learning
Previous Article in Journal
Applying Neural Networks in Aerial Vehicle Guidance to Simplify Navigation Systems
Previous Article in Special Issue
Lumáwig: An Efficient Algorithm for Dimension Zero Bottleneck Distance Computation in Topological Data Analysis
 
 
Font Type:
Arial Georgia Verdana
Font Size:
Aa Aa Aa
Line Spacing:
Column Width:
Background:
Article

From Trees to Barcodes and Back Again: Theoretical and Statistical Perspectives

1
Blue Brain Project, École Polytechnique Fédérale de Lausanne (EPFL), Campus Biotech, 1202 Geneva, Switzerland
2
Laboratory for Topology and Neuroscience, Brain Mind Institute, École Polytechnique Fédérale de Lausanne (EPFL), 1015 Lausanne, Switzerland
*
Author to whom correspondence should be addressed.
Submission received: 30 September 2020 / Revised: 3 December 2020 / Accepted: 4 December 2020 / Published: 11 December 2020
(This article belongs to the Special Issue Topological Data Analysis)

Abstract

:
Methods of topological data analysis have been successfully applied in a wide range of fields to provide useful summaries of the structure of complex data sets in terms of topological descriptors, such as persistence diagrams. While there are many powerful techniques for computing topological descriptors, the inverse problem, i.e., recovering the input data from topological descriptors, has proved to be challenging. In this article, we study in detail the Topological Morphology Descriptor (TMD), which assigns a persistence diagram to any tree embedded in Euclidean space, and a sort of stochastic inverse to the TMD, the Topological Neuron Synthesis (TNS) algorithm, gaining both theoretical and computational insights into the relation between the two. We propose a new approach to classify barcodes using symmetric groups, which provides a concrete language to formulate our results. We investigate to what extent the TNS recovers a geometric tree from its TMD and describe the effect of different types of noise on the process of tree generation from persistence diagrams. We prove moreover that the TNS algorithm is stable with respect to specific types of noise.

1. Introduction

Although geometric approaches to analyzing data have been extensively used for many years, the first topological methods for data analysis were developed only recently, e.g., [1,2,3,4,5,6]. Topological Data Analysis (TDA) is a fairly new field at the intersection of data science and algebraic topology, the aim of which is to provide robust mathematical, statistical, and algorithmic methods to infer and analyze the topological and geometric structures underlying complex data. These data are often represented as point clouds in Euclidean or metric spaces, though TDA methods have also been generalized to geometric objects and graphs. TDA has proved its utility in a wide range of applications in biology [7,8,9,10], material science [11], and climate science [12], among other fields. Although it is still rapidly evolving, TDA now provides a set of powerful and efficient tools that can be used in combination with or as complements to other data science tools.
One of the most promising applications of TDA is to the study of the brain, where it has served to analyze neuronal morphologies [13], brain networks [13,14,15], and brain functionality [16]. Motivated by the desire to objectively classify neuronal morphologies, in a previous publication (Kanari and Hess in [13]), we designed a topological signature for trees, the Topological Morphology Descriptor (TMD), that assigns a barcode (i.e., a multi-set of open intervals—called bars—in the real line) to any geometric tree (i.e., any finite binary tree embedded in R 3 ). We showed that the TMD algorithm effectively determines the reliability of the clustering of random and neuronal trees. Moreover, using the TMD algorithm, we performed an objective, stable classification of pyramidal cells in the rat neocortex [17], based only on the shape of their dendrites.
A frequent topic of discussion in the context of TDA is how to define an inverse to the process of associating a particular topological descriptor to a dataset, i.e., how to design a practical algorithm to recover the input data from a topological descriptor, such as a barcode. Oudot and Solomon [18] and Curry et al. [19] have proposed partial solutions to this problem. The main obstacle that renders this endeavor particularly challenging has proven to be the computational complexity of the space of inputs considered. To avoid this obstacle, it is reasonable to constrain the input space and search only for an inverse transformation that is relevant in a specific context, for instance to look for solutions only in the space of embedded graphs, as in [20].
In the context of geometric trees, we have designed an algorithm to reverse-engineer the TMD [21], in order to digitally generate artificial neurons, to compensate for the dearth of available biological reconstructions. This algorithm, called Topological Neuron Synthesis (TNS), stochastically generates a geometric tree from a barcode, in a biologically grounded manner. As shown in [21], the synthesized neurons are statistically indistinguishable from the corresponding reconstructed neurons in terms of both their morphological characteristics and the networks they form.
In this article, we further study the properties of this generative algorithm, from mathematical and statistical perspectives. We perform a theoretical and computational analysis of the TMD and TNS algorithms and their mathematical properties, in which symmetric groups play a key role. In particular, we investigate in detail the extent to which the TNS provides an inverse to the TMD.
First, we carefully define our objects of study—geometric trees, barcodes, and persistence diagrams—and then recall the TMD and TNS algorithms. We also introduce two distinct classifications of geometric trees: into combinatorial types and into TMD-types. The symmetric groups play an important role in our classification of trees into TMD-types. These complementary descriptions provide us with a language in which to formulate our results on the relationship between the TMD and the TNS.
In the next section, we introduce tools to describe the set of geometric trees that realize a specific barcode, i.e., whose TMD is equal to that barcode. In particular, we establish an explicit formula for the cardinality of this set, which we use to describe how the cardinality changes when a new bar is added to a barcode or two bars of a barcode permuted. Cayley graphs of symmetric groups provide a useful visualization of these effects.
We then study the composite of the TNS and TMD algorithms from a theoretical perspective, to quantify the extent to which the TNS acts as an inverse to the TMD. For a given barcode B, we show that, for a reasonable choice of parameter in the TNS, the probability that the bottleneck distance between the barcodes B and TMD TNS ( B ) is greater than ε decreases with ε , thus establishing a form of stability for the TNS. We prove, moreover, that the probability that two bars of a barcode B will be permuted by applying TMD TNS decreases exponentially with the distance between the terminations of the two bars, which is another form of stability. Together, these stability results imply that the TNS is an excellent approximation to a (right) inverse to the TMD.
In the final section, we present computational results that illustrate the complex relationship between a barcode and its possible tree-realizations. In particular, we study the distinguishing characteristics of “biological” geometric trees, i.e., those that arise from digital reconstructions of neurons, as opposed to arbitrary geometric trees. We also show that both the combinatorial type and the TMD-type of a geometric tree can change significantly when applying the composite TNS TMD , from which it follows that the TNS is not a left inverse to the TMD (Figure 1).

2. Mathematical Background

Precisely what a mathematician means by the terms “tree” and “barcode” can vary depending on context. First, we specify what these terms mean in this article. We then recall biologically motivated algorithms for generating barcodes from trees [13] and trees from barcodes [21], the relation between which will be made clear in the following sections.

2.1. Trees

A finite rooted tree T is an acyclic, finite, directed graph such that each vertex is of degree at most 3, with a distinguished vertex r of degree 1, called the root. A vertex v of T is a parent of a vertex w if there is a directed edge from w to v; the vertex w is then a child of v. Each vertex of T has a single parent, except for the root r, which has no parent, and at most two children. The non-root vertices of degree 1 are called the leaves of T, and the vertices of degree 3 the branch points of T. A finite tree T is fully specified by its set of vertices, equipped with the partial order “is a parent of”.
Our main objects of study in this article are geometric trees, i.e., embeddings of finite rooted trees in R 3 , which are often used to model neurons. We assume, moreover, that, if a vertex v is the parent of a vertex w, then the distance from the root to v is less than that from the root to w (Much of the framework that we develop in this article could be extended to geometric trees equipped with a different distance function that does not necessarily satisfy this condition, at the price of a more involved combinatorial representation. Since our geometric trees of interest—digitally reconstructed neurons equipped with the path-distance from the root—do satisfy our extra assumption, we prefer to leave this extension to the interested reader.). Let T denote the set of geometric trees. We say that two geometric trees T and T are combinatorially equivalent, denoted T comb T , if they are embeddings of the same finite rooted tree. In other words, the combinatorial type of a geometric tree is independent of its embedding in R 3 .

2.2. Barcodes

A persistence barcode is a finite multi-set B = { ( b i , d i ) } i = 0 , , n of open intervals, called bars, in the real line, R . We call b i the birth time and d i the death time of the i th interval. For barcodes of geometric trees, generated with the TMD algorithm (cf. Section 2.3), the birth time b i is the distance from the first bifurcation of branch i to the root, while the death time d i is the distance from the branch termination to the root. Let B denote the set of all barcodes.
A persistence barcode can equivalently be represented as a multi-set of points in R 2 , called a persistence diagram, where a bar ( b i , d i ) corresponds to a point in R 2 with x-coordinate d i and y-coordinate b i (The inversion of the coordinates that we apply here is motivated by the TMD algorithm (cf. Section 2.3), which decomposes a geometric tree into bars, starting at the leaves and progressing down to the root.). If B is a barcode, we let PD ( B ) denote the associated persistence diagram. Note that, under this correspondence, the points of PD ( B ) lie below the diagonal, since b i is less than d i for every i.
We say that a barcode B = { ( b i , d i ) } i = 0 , , n is strict if the first bar ( b 0 , d 0 ) properly contains all the others, i.e., b 0 < b i and d i < d 0 for all i, and no bars are born or die at the same time, i.e., b i b j and d i d j for all i j . The birth times of a strict barcode admit a total ordering. Without loss of generality, we assume that the bars are ordered by birth value that is b 0 < b 1 < < b n . Let B st denote the set of strict barcodes, and let B n st denote the subset of those strict barcodes with n + 1 bars.
We say that two strict barcodes B = { ( b i , d i ) } i = 0 , , n and B = { ( b i , d i ) } i = 0 , , n with the same number of bars are equivalent, denoted B bar B , if their deaths occur in the same order ( d i > d j d i > d j ), which clearly defines an equivalence relation on B n st . There is a bijection from the set of equivalence classes of strict barcodes with n + 1 bars to the symmetric group S n on n letters, taking the equivalence class of a barcode B = { ( b i , d i ) } i = 0 , , n to the permutation σ B : { 1 , , n } { 1 , , n } , where σ B ( i ) = # { j d j d i } .
We denote the equivalence class containing a strict barcode B = { ( b i , d i ) } i = 0 , , n by ( i 1 i n ) , where d i k > d i k + 1 for all 1 k < n . For example, ( 2134 ) corresponds to the barcode with five bars shown in Figure 2.

2.3. 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,
TMD : T B ,
that encodes the overall shape of the tree, both the topology of the branching structure of a tree and its embedding in 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 δ : N R 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 δ . Each bar ( b , d ) corresponds to a connected component in the sublevel sets δ 1 [ 0 , t ) , 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 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 N L , let L v denote the set of leaves of the subtree of T with root at the branch point v. Let μ : N R be the function defined by
μ ( v ) = max δ ( l ) | l L v : v N L , δ ( v ) : v L .
We order the children of any vertex of T by their μ -value: if v 1 , v 2 N are siblings, then v 1 is younger than v 2 if μ ( v 1 ) < μ ( 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 δ ( b ) , δ ( l ) . 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 μ is maximal among all leaves, which is recorded in the barcode as a bar 0 , δ ( l ) .
If T is a digital reconstruction of a neuron, and the function δ 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 exactly the same distance from the soma is almost zero, and TMD ( T ) always has a longest bar that contains all the others. This observation justifies our interest in the subset of strict barcodes.
The TMD gives rise to an equivalence relation on T : two geometric trees T and T are TMD-equivalent, denoted T tmd T , if TMD ( T ) bar TMD ( T ) . We provide below an in-depth analysis of the TMD-equivalence classes of geometric trees. Geometric trees can be combinatorially equivalent without being TMD-equivalent and vice versa, cf. Figure 5.

2.4. The TNS: From Barcodes to Trees

The topological neuron synthesis (TNS) algorithm [21] stochastically generates synthetic neurons, in particular for use in digital reconstructions of brain circuitry [23]. In this paper, we focus on the sub-process of the TNS that stochastically generates a geometric tree from a strict barcode, in such a way that, if a tree T is generated from a barcode B, then TMD ( T ) is “close to” to B, with respect to an appropriate metric on the set of barcodes, up to some stochastic noise, cf. Section 4. Henceforth, when we refer to the TNS, we mean this sub-process.
To grow geometric trees, the TNS algorithm first initiates growth, then loops through steps of elongation and branching/termination. Each branch of the tree is elongated as a directed random walk [24] with memory. At each step, a growing tip is assigned probabilities to bifurcate, to terminate, or to continue that depend on the path distance from the root and on a chosen bar of the selected barcode. Once a bar has been used, it is removed from the barcode. The growth of a tree terminates when no bars remain to be used. We now provide further details of the two steps in this process.

2.4.1. Bifurcation/Termination

The branching process in the TNS algorithm is based on the concept of a Galton–Watson tree [25], which is a finite rooted tree recursively generated as follows. At each step, a number of offspring is independently sampled from a distribution. Since a geometric tree consists only of bifurcations, terminations, and continuations, the accepted values for the number of offspring are: zero (termination), one (continuation), and two (bifurcation). The Galton–Watson algorithm generates only a combinatorial tree, with no embedding in space, so we modify the traditional process to introduce a dependency of the tree growth on the embedding, so that the bifurcation/termination probabilities depend on the path distance of the growing tip from the root.
The bifurcation/termination step of the growth process of a geometric tree with associated barcode B proceeds as follows. Each growing tip of the tree is assigned a bar ( b i , d i ) sampled from the barcode B and a bifurcation angle a i . The growing tip first checks the probability to bifurcate, then the probability to terminate. If the growing tip does not bifurcate or terminate, then the branch continues to elongate. The probability to bifurcate depends on b i : as the distance from the root to the growing tip approaches b i , the probability to bifurcate increases exponentially until it attains a maximum of 1 at b i . Similarly, the probability to terminate depends exponentially on d i .
The probabilities to bifurcate and terminate are sampled from an exponential distribution e λ x , whose free parameter λ should be wisely chosen. A very steep exponential distribution (high value of λ ) reduces the variance of the population of geometric trees synthesized based on the same barcode. On the other hand, a very low value of λ results in trees that are almost random, since the dependence on the input persistence barcode is decreased significantly. If we assume that growth takes place in discrete steps of size L, the value of the parameter λ should be of the order of the step size L, to ensure biologically appropriate variance [21]. Assuming L = 1 in some appropriate units, we usually select λ 1 , so that the bifurcation and termination points are stochastically chosen but still strongly correlated with the input persistence barcodes.
Contrary to other neuron synthesis algorithms [26] that sample the branching and termination probabilities from independent distributions, in the TNS, the correlation of these probabilities is captured in the structure of the barcode. When the growing tip bifurcates, the corresponding bar is removed from the input barcode to exclude re-sampling of the same conditional probability, thus recording the tree’s growth history, which is essential for reproducing the branching structure. In the event of a termination, the growing tip is deactivated, and the bar that corresponds to this termination point is removed from the reference barcode.
At a bifurcation, the directions of the two daughter branches created depend on the bifurcation angle a i . In this study, we focus primarily on the combinatorial type and the TMD type of the generated geometric tree, so we do not investigate the effect of bifurcation angles on the growth.

2.4.2. Elongation

We now describe how the synthesized trees are embedded in R 3 . A segment of a growing tree is the portion of the tree between a pair of consecutive vertices (parent and child). Each synthesized tree is grown segment by segment. The direction of a segment, i.e., the vector d from its starting point to its end point, is a weighted sum of three unit vectors: the cumulative memory m of the directions of previous segments within a branch, a target vector t , and a random vector r [26]. The memory term is a weighted sum of the previous directions of the branch, with the weights decreasing with distance from the tip. As long as the memory function decreases faster than linearly with the distance from the growing tip, the exact choice of function is not important [21]. The target vector is chosen at the beginning of each branch and depends on the bifurcation angles. The random component is a unit vector sampled uniformly from R 3 at each step. The direction of the segment
d = ρ r + τ t + μ m ,
then depends on three weight parameters ρ , τ , and μ , where ρ + τ + μ = 1 .
An increase of the randomness weight ρ results in a highly tortuous branch, approaching the limit of a simple random walk when ρ = 1 . If the targeting weight τ = 1 , the branch will be a straight line in the target direction. Different combinations of the three parameters ( τ , ρ , μ ) generate more or less meandering branches and thus reproduce a large diversity of geometric trees.

2.4.3. The Elder Rule and TNS

The TNS provides a sort of right inverse to the TMD . To recreate a tree that is close to TMD-equivalent to the original, the branch corresponding to a particular bar ( b i , d i ) in the barcode can be attached only to branches corresponding to bars ( b j , d j ) such that d i < d j and b i > b j . This rule ensures that the Elder rule (at a bifurcation, the longer component survives) holds in the TMD transformation. As a result, only a subset of trees with n branches can be generated by the TNS from a given strict barcode with n bars.

3. Tree-Realizations of Barcodes

In this section, we provide an in-depth analysis of the set of geometric trees that realize a specific strict barcode B, i.e., each of which has TMD equal to B.

3.1. Realizing Barcodes as Trees

A geometric tree T is a tree-realization of a barcode B if TMD ( T ) = B , i.e., T TMD 1 ( B ) . Examples of tree-realizations are provided in Figure 4B, while Figure 5 shows all the possible combinatorial types of tree-realizations of a strict barcode with n = 4 .
In Figure 4 and Figure 5, we encode the combinatorial structure of the tree, i.e., how the branches may be attached to each other, in an adjacency matrix in which the ( i , j ) coefficient is non-zero if the Elder Rule allows bar i to be connected to bar j. For example, in Figure 4A, bars 1–3 may all be connected to the black bar 0, thus the coefficients ( 0 , 1 ) , ( 0 , 2 ) , ( 0 , 3 ) are all non-zero in the corresponding adjacency matrix. Note that in each realization only a subset of these possible attachments is actually made (Figure 4B), since each branch can be attached to only one other branch.
The connectivity diagram (bottom of Figure 4A) provides another representation of the pairs of branches that may be connected, in agreement with the Elder Rule. The arrow on an edge in the diagram indicates the direction of the connection. In this example, there are arrows from 0 towards 1 , 2 , and 3, from 1 to 2 and 3, and from 2 to 3.
For any strict barcode B, let T ( B ) denote the set of combinatorial equivalence classes of tree-realizations of B, i.e.,
T ( B ) = TMD 1 ( B ) / comb .
We can characterize the equivalence relation on strict barcodes in terms of T ( B ) .
Lemma 1.
If B and B are two strict barcodes with the same number of bars, then
B bar B T ( B ) = T ( B ) .
Proof. 
The order of the deaths in a strict barcode B completely determines the set of combinatorial equivalence classes of its possible tree realizations.
Indeed, the two pairs of bars in Figure 6B lead to the same adjacency possibilities for their respective branches. Only move (A) in Figure 6, corresponding to switching the order of the deaths of the two bars, modifies the permutation equivalence class of the barcode, hence also the set of trees that return the given barcode.

3.2. The Combinatorics of Tree-Realization

Let B = { ( b i , d i ) } i = 0 , , n be a strict barcode. In this section, we analyze the tree-realization number of B,
TRN ( B ) = # T ( B ) ,
i.e., the number of combinatorial equivalence classes of tree-realizations of B. We provide a formula for TRN ( B ) in terms of the index of each bar ( b i , d i ) , i.e., the number of bars that include ( b i , d i ) strictly:
index i ( B ) = # { j b j < b i < d i < d j } = # { j < i d i < d j } .
A version of this formula was established by Curry in [22].
Lemma 2.
The tree-realization number of a strict barcode B = { ( b i , d i ) } i = 0 , , n is equal to the product of the indices of its bars, i.e.,
TRN ( B ) = 1 i n index i ( B ) .
Proof. 
Because of the Elder Rule applied in the TMD, one branch can be attached to another only if its corresponding bar is included in the other bar. This simple observation enables us to prove the lemma by a straightforward recursion on the number of bars. □
In particular, the maximum tree-realization number for a strict barcode with n + 1 bars is n ! , in the specific case where d n < < d 1 < d 0 . We call this case a strictly ordered barcode.
Note that the tree-realization number does not satisfy
TRN ( B ) = TRN ( B ) B B
in general, i.e., the tree-realization number is not a complete invariant of the barcode equivalence relation. For instance, barcodes ( 231 ) and ( 312 ) in Figure 7 both have TRN ( B ) = 2 but have different permutation types. The inverse clearly does hold, however:
TRN ( B ) TRN ( B ) B B ,
enabling us to detect non-equivalence of barcodes. For the pairs of barcodes studied in Section 4 and Section 5 of this paper, though, it is usually true that if they have same TRN, then they are equivalent, so that we can use the TRN to detect equivalence of barcodes in these special cases. In particular, if a new bar is added to a barcode or two deaths are transposed and no other changes take place, then the tree-realization number does change.
Lemma 2 enables us to quantify how adding a new bar changes tree-realization number.
Lemma 3.
Let B = { ( b i , d i ) } i = 0 , n and B = B { ( b n + 1 , d n + 1 ) } , where b n + 1 > b i for all 0 i n , be strict barcodes. If d i 1 > d i k 1 > d n + 1 > d i k > d i n , then
TRN ( B ) = TRN ( B ) · k .
Proof. 
The condition on d n + 1 implies that the new bar ( b n + 1 , d n + 1 ) is included in exactly k other bars, so its index is k. □
Example 1.
Let B be a barcode with four bars such that b 0 < b 1 < b 2 < b 3 and d 0 > d 2 > d 1 > d 3 , i.e., its equivalence class is ( 213 ) . It is easy to see that TRN ( B ) = 3 (see Figure 8). If we add a new bar ( b 4 , d 4 ) such that d 1 > d 4 > d 3 , the equivalence class of the new barcode B is ( 2143 ) , and bar ( b 4 , d 4 ) is included in ( b 0 , d 0 ) , ( b 2 , d 2 ) , and ( b 1 , d 1 ) , but not in ( b 3 , d 3 ) because d 4 > d 3 . Therefore, its index is 3, whence TRN ( B ) = 3 × 3 = 9 .
We can also apply Lemma 2 to determining how switching the order of two consecutive deaths in the barcodes affects the tree realization number.
Proposition 1.
Let B = { ( b i , d i ) } i = 0 , n be a strict barcode in the equivalence class ( i 1 i n ) . Let B = { ( b i , d i ) } i = 0 , n be a new barcode obtained by permuting the deaths d i k and d i k + 1 , i.e., b i = b i for all i and d i = d i for all i i k , i k + 1 , while d i k = d i k + 1 and d i k + 1 = d i k .
1.
If i k < i k + 1 , then index i k + 1 ( B ) = index i k + 1 ( B ) 1 , and
TRN ( B ) = TRN ( B ) ( index i k + 1 ( B ) 1 ) index i k + 1 ( B ) .
2.
If i k > i k + 1 , then index i k + 1 ( B ) = index i k + 1 ( B ) + 1 , and
TRN ( B ) = TRN ( B ) ( index i k + 1 ( B ) + 1 ) index i k + 1 ( B ) .
Proof. 
It is enough to prove (1), since (2) then follows by switching the roles of B and B .
If i k < i k + 1 , then b i k < b i k + 1 . Since B is in the equivalence class ( i 1 i n ) , d i k + 1 < d i k as well, whence ( b i k + 1 , d i k + 1 ) ( b i k , d i k ) . On the other hand, ( b i k + 1 , d i k + 1 ) ( b i k , d i k ) , but otherwise respects all of the same inclusion relations as ( b i k + 1 , d i k + 1 ) , so that
index i k + 1 ( B ) = index i k + 1 ( B ) 1 ,
as desired. Moreover, ( b i k , d i k ) ( b i k + 1 , d i k + 1 ) , so ( b i k , d i k ) respects exactly the same inclusion relations as ( b i k , d i k ) , i.e.,
index i k ( B ) = index i k ( B ) .
Because no other bars are affected when passing from B to B , we can conclude. □
Example 2.
In Figure 9, we show all the possible death-transpositions in a strict barcode with five bars. As an example, take B in the equivalence class ( 2134 ) , so the barcode satisfies d 2 > d 1 > d 3 > d 4 . The index of ( b 4 , d 4 ) is 4 because it is included in all the other bars. Permuting d 3 and d 4 leads to a barcode in the equivalence class ( 2143 ) . The index of the last bar is now 3 because it is no longer included in the third bar.
Recall the bijection σ : B n st S n from Section 2.2. Permuting the order of the deaths d i and d i + 1 corresponds to a transposition ( i , i + 1 ) in S n (and to move (A) in Figure 6). Studying the allowed moves and their effects on the barcode is equivalent to studying the symmetric group seen as generated by transpositions of type ( i , i + 1 ) , enabling us to create the following revealing visualization of the effect of switching the order of deaths or of adding a new bar by using Cayley graphs of S n .
We illustrate the results of Lemma 3 and Proposition 1 on the two Cayley graphs of S 3 and S 4 in Figure 7 and Figure 9. Figure 7 shows the Cayley graph of S 3 generated by the permutations ( 12 ) and ( 23 ) and the corresponding equivalence classes of barcodes. The vertices of the graph correspond to the permutations in the symmetric group and their corresponding barcode types, and the edges between them to the transpositions transforming one permutation into another. The number next to each bar is its index. The trees that return a given barcode are sketched next to each vertex of the Cayley graph of S 3 .
Figure 9 shows the Cayley graph of S 4 generated by the transpositions ( 12 ) , ( 23 ) , and ( 34 ) , illustrating the effect on tree-realization number both of switching the order of two deaths and, in comparison with the previous figure, of adding an extra bar.

4. Stability of the TNS

In this section, we investigate the effect of the composition of the TNS and TMD algorithms from a theoretical perspective. Given a strict barcode B = { ( b i , d i ) } i = 0 , , n , we apply the TNS to B, for a fixed choice of the parameter λ (cf. Section 2.4), obtaining a tree T B , and then compute the barcode of T B , TMD ( T B ) , which we denote by B = { ( b i , d i ) } i = 0 , , n . To quantify to what extent the TNS acts as an inverse to the TMD, we are interested in determining how similar B and B are.
Expressing the similarity between B and B in terms of the bottleneck distance enables us to establish one form of stability for the TNS in the first part of this section. We establish another type of stability for the TNS in the second part, when we show that the probability that the order of two specific bars will be altered upon applying TMD TNS decreases exponentially with the distance between the death times of the two bars. Together, these stability results imply that the TNS is an excellent approximation to a (right) inverse to the TMD.

4.1. Bottleneck Stability

Henceforth, we call the endpoints of the bars of the barcode B targets, as the TNS algorithm either creates a new branch or terminates a branch when the distance from the root approaches a birth or death point, respectively.
By definition of the TNS algorithm (cf. Section 2.4), when approaching a target, there is an exponential probability to bifurcate (create a new branch) or terminate, depending on λ . It follows that, for any bar ( b i , d i ) of a given barcode B, the distance between b i and b i (the bifurcation distance and the target bifurcation distance of the i th branch) and the distance between d i and d i (the termination distance and the target termination distance of the i th branch) should follow an exponential distribution of parameter λ ,
| b i b i | Exp ( λ ) and | d i d i | Exp ( λ ) .
The notion of similarity between barcodes that we consider here is the standard bottleneck distance. Given two strict barcodes B and B with n + 1 bars, the bottleneck distance between them is
d ( B , B ) = inf γ S n sup i | b i b γ ( i ) | + | d i d γ ( i ) | .
Lemma 4.
Let B be a strict barcode with n bars, and let B = TMD TNS ( B ) . If B B , then
P d ( B , B ) > ε 1 ( 1 exp ( λ ε ) ( λ ε + 1 ) ) n .
Proof. 
Considering the case where γ is the identity, we see that
d ( B , B ) sup i | b i b i | + | d i d i | .
If B B , the differences between the new and original values of the births and deaths all follow an exponential distribution,
| b i b i | Exp ( λ ) and | d i d i | Exp ( λ ) .
The cumulative probability distribution function of | b i b i | + | d i d i | is thus given by an Erlang ( 2 , λ ) distribution
P | b i b i | + | d i d i | ε = 1 ( 1 + λ ε ) exp ( λ ε ) .
Because we consider the supremum over i of the sum | b i b i | + | d i d i | , and all of the | b i b i | + | d i d i | are i.i.d, it follows from the theory of order statistics that
P d ( B , B ) ε P ( sup i | b i b i | + | d i d i | ε ) = ( 1 exp ( λ ε ) ( λ ε + 1 ) ) n .
Considering the probability of the complement leads to the result in Equation (1). □
Lemma 4 implies that the TNS is stable with respect to the bottleneck distance, in a manner dependent on the parameter λ . To illustrate this dependence, we plot the function of Equation (1) for different values of λ in Figure 10. The curve obtained for λ = 1 (blue in Figure 10) makes it clear that setting λ = 1 ensures that the TNS gives rise to a diverse family of new trees that are nonetheless topologically not significantly far from the original ones, which is the desired goal from a biological perspective. Making an appropriate choice of the parameter λ is thus essential.
If B B , the bound by γ = I in the formula for the bottleneck distance is computed between pairs of points that follow the same exponential law, as the order of bars is preserved. If B B , for example when a switch of bars occurs, then we cannot assume that the distances between matched pairs of points in the computed bottleneck distance follow the same law. Change of permutation type between B and B is more frequent for small λ (Figure 14). Therefore, the previous lemma is usually not applicable for small values of λ , for which it is any case not particularly useful, as shown in Figure 10. In Figure 11, we summarize graphically the discussion above. The transposition of bars is studied in detail in the next section.
We perform two experiments to illustrate our theoretical results computationally. First, we compute the bottleneck distance between input barcodes B and output barcodes B , for increasing values of lambda λ from 0.01 to 2 (see Figure 12A1-3). The computational results (average bottleneck distances in red, Figure 12A2) fit the curve of the expected mean of the probability density function (The PDF can be deduced from Equation (2) in the proof of Lemma 4 by taking the derivative of ( 1 exp ( λ ε ) ( λ ε + 1 ) ) n .) well (blue curve).
We also compute the cumulative density function for 0 ϵ 200 and 0 λ 2 , which we compare to the computational results (red points, Figure 12A3), showing that they match the theoretical prediction (blue colormap) very closely for a wide range of sufficiently large λ (zoom-in, Figure 12A3). However, for very small values of λ , the condition B B is not always satisfied, leading to the observation that, for λ < 0.2 , the computationally computed bottleneck distances are larger than the theoretically expected values.
Second, we compute the bottleneck distance between input and output barcodes for various fixed values of λ , where the input barcodes arise by gradually decreasing the death time of one bar of an initial barcode B and thus increasing the distance to the next death time in the sequence (see Figure 12B1-2). All other bars of the initial barcode B remain the same. We observe that the bottleneck distance depends only on the value of λ and not on the distance between the bars of the input barcode.

4.2. Transposition Stability

As the TNS algorithm is a stochastic process, the image of any strict barcode B = { ( b i , d i } under the composite TMD TNS essentially always differs at least slightly from B. Here, we determine the probability that the orders of the death times of two specific bars of B and TMD TNS ( B ) = B = { ( b i , d i ) } are different, so that B and TMD TNS ( B ) are not combinatorially equivalent, i.e., the associated permutations are different, as long as the birth times are not also transposed (Figure 13).
Lemma 5.
Let B be a strict barcode, and let ( b i , d i ) , ( b j , d j ) be bars of B such that d i < d j . Let ( b i , d i ) and ( b j , d j ) denote the corresponding bars in B = TMD TNS ( B ) . The probability that d j < d i is
P ( d j < d i ) = 1 2 exp ( λ ( d j d i ) ) .
The TNS thus exhibits a sort of “transposition stability”: the probability that the death times of two bars will be transposed decreases exponentially with the distance between those death times.
Proof. 
We compute P ( d j < d i ) = P ( d j < d i | d i < d j ) , the probability that d j < d i given that d i < d j . Observe first that
P ( d j < d i ) = P ( d j + ( d i d i ) < d i + ( d j d j ) ) = P ( d j + X i < d i + X j ) = P ( X j X i > d j d i ) .
Let Y = X j X i . As X j and X i both follow an exponential law, the density function of their difference, Y, is given by f Y ( t ) = λ 2 exp ( λ t ) when t 0 . Therefore,
P ( d j < d i ) = P ( X j X i > d j d i ) = d j d i f Y ( t ) d t = 1 2 exp ( λ ( d j d i ) ) .
Remark 1.
Since the TNS is based on a stochastic process, multiple transpositions can occur when generating a new tree from a barcode. This makes it challenging to determine the overall probability of changing equivalence classes when computing the composite TMD TNS . Note that the TNS might also affect the birth order, but we will not discuss this possible effect in this paper. For the following experiments, the selected examples do not experience birth-switches, as the cells from which we computed the barcodes were chosen with sufficient gaps between birth values to avoid such switches.
We perform the following computational experiment to evaluate the transposition stability results. We systematically vary the distance between two bars by changing the death time of a bar in the input barcode and compute the percentage of order changes that occur for different values of lambda (see Figure 14). We compare the theoretical results (solid lines) to the computational experiment (scatter points) for five different values of lambda. Note that, for this experiment, the birth times are chosen to be sufficiently distinct, and only the number of switches due to permutations that correspond to death changes are counted. The experimental results match the theoretical prediction with high accuracy, where we compute the error as the average distance of the computational points from the theoretical curve ( λ = 10 , e r r o r = 0 % , λ = 5 , e r r o r = 0.02 % , λ = 1 , e r r o r = 0.5 % , λ = 0.5 , e r r o r = 0.9 % , λ = 0.1 , e r r o r = 3 % , λ = 0.05 , e r r o r = 5 % ). Note that the error increases for smaller values of λ , due to the computational artifacts introduced when λ is small.

5. Computational Exploration of Tree-Realization

In this section, we present computational results that illustrate the complex relationship between the equivalence class of a barcode and its possible tree-realizations.
We first present four results concerning all geometric trees: a computation of the distribution of tree-realization numbers across the set of equivalence classes of strict barcodes for various numbers of bars, a computation of the empirical distribution of combinatorial types of geometric trees in a synthesized population as a function of the equivalence class of the input barcode, a measurement of the diversity of TMD-equivalence classes among the realizations of a fixed barcode, and simulations of the fluctuations in tree-realization number that can occur as two bars gradually switch the order of their deaths.
We conclude by reporting on an experiment that sheds light on the distinguishing characteristics of “biological” geometric trees, i.e., those that arise from digital reconstructions of neurons.

5.1. The Distribution of Tree-Realization Numbers

We illustrate here how the number of tree-realizations of strict barcodes with n + 1 bars depends on n. In Figure 15, we present the distribution of tree-realization numbers across equivalence classes of barcodes with n + 1 bars, for 1 n 10 . As mentioned in Section 3.2, the tree-realization number is maximal for a fixed number of bars if and only if the barcode is strictly ordered. We observe an exponential-like behavior in the distribution of tree-realizations with the increase of the number of bars. We expect to link this behavior with intrinsic properties in the space of barcodes in a future work.

5.2. Empirical Distributions of Combinatorial Types of Trees

In this section, we explore computationally the probability to generate different combinatorial tree types (see Figure 5B (A–F)) with the TNS. We observe that this probability depends on the choice of the parameter λ (cf. Section 2.4). When λ > 2 , the TNS is more likely to generate trees with all branches connected to the longest branch, due to the design of the algorithm. On the other hand, for smaller values of λ , the probability to generate different types of trees is approximately uniform.
Focusing on our preferred value of λ , we generated 1000 trees for λ = 1 and computed the percentage of each combinatorial tree type that is realized for each equivalence class of barcodes with four bars (Figure 16). There are six possible equivalence classes of strict barcodes with four bars and six combinatorial equivalence classes of geometric trees with four branches.

5.3. Diversity of Realized TMD-Equivalence Classes

We now explore the diversity of TMD-equivalence classes of geometric trees that can be synthesized from a fixed barcode, in the particular case of the TMD of a biologically meaningful tree. For a fixed geometric tree with eight branches arising from a digital reconstruction of a layer 4 pyramidal cell, we computed its TMD barcode, to which we applied the TNS with λ = 1 to generate a set of 100 geometric trees. We computed the barcode-type and the persistence diagrams of the synthesized trees (Figure 17).
In agreement with the results presented in Figure 12, the persistence diagrams of the synthesized trees (Figure 17B, in blue) are essentially indistinguishable from the persistence diagram of the original barcode (Figure 17B, in red). On the other hand, the TMD-equivalence class of a synthesized tree is not necessarily equal to that of the original tree (Figure 17A). Here, we represent the TMD-equivalence class of a tree in terms of the permutation σ B corresponding to the equivalence class of its TMD barcode B. In this graphical representation, we plot birth (or bifurcation) index k (on the x-axis) versus death (or termination) index σ B ( k ) (on the y-axis). A strictly ordered barcode would thus correspond to the set of points along the diagonal in this representation.

5.4. Statistics of Changing Classes

Motivated by the theoretical results on the probability to change classes in Section 4.2, we analyze here several simulations of gradual switching of death order of two bars and the resulting effect on tree realizations and their associated barcodes.
Let B be a strict barcode, and let ( b i , d i ) , ( b j , d j ) be bars of B such that d i < d j . By Lemma 5, for a fixed choice of the parameter λ (cf. Section 2.4), the probability that the order of these two bars is reversed in TMD TNS ( B ) depends exponentially on the distance between d i and d j :
P ( d j < d i ) = 1 2 exp ( λ ( d j d i ) ) .
Thus, when the distance between d i and d j decreases, the probability that the order of bars changes increases. When there is no k such that d i < d k < d j , Proposition 1 provides a formula for the tree-realization number of the new barcode obtained when such a switch happens, as long as the order of the birth times is not also reversed.
We start with a geometric tree T extracted from a digital reconstruction of a neuron and compute its associated barcode B = TMD ( T ) . We choose two bars ( b i , d i ) and ( b j , d j ) of B that are consecutive in the order of deaths and divide the interval ( d i , d j ) into 50 equally sized subintervals. For 0 k 50 , let B k be a barcode that is identical to B, except that its i th bar is b i , d i + k ( d j d i ) / 50 and its j th bar is b j , d j k ( d j d i ) / 50 . An interesting way to visualize this change is to think of B k as migrating along the edge between B and the barcode with d i and d j permuted in the corresponding Cayley graph as k increases. The middle point of the edge corresponds to the non-strict barcode for which the two deaths are equal.
Let B k = TMD TNS ( B k ) for all k. Because of the stochastic nature of the TNS algorithm, the permutation equivalence class of B k may be different from that of B k . Figure 18 provides an example of this construction, where the barcodes are represented as persistence diagrams for visualization purposes (cf. Section 2.2).
To test whether the barcode B k is equivalent to the original barcode B, we compute its tree-realization number: if TRN ( B k ) TRN ( B ) , then B and B k are not equivalent. Note that, for the specific process that gives rise to B k , it is likely that only the studied death-switch could lead to a difference between the tree-realization numbers of the input and output barcodes, unless two other deaths are too close to each other in the input barcode, as in the last row of Figure 19, which we explain further below. Therefore, the tree-realization number provides a very good indication of whether the switch of deaths took place, i.e., if B B k or not. Indeed, two barcodes that are the same except for two deaths that switched have different tree-realization numbers, cf. Proposition 1. Figure 19 shows several examples of the endpoint-switching process described above and the corresponding evolution of the tree-realization number as k increases. The corresponding permutation type and tree-realization number of each initial barcode, and the bars that are switched are listed in Table 2.
The top row of Figure 19 illustrates very well the exponential behavior of changing classes. When the distance between the death times of the two bars is very small (they are the closest when k = 25 ), the tree-realization number oscillates between its values for two different classes and otherwise stays constant.
The two middle rows come from the same biological tree and hence have the same starting barcode. The difference is that, in the second row, the death times of the two bars are already very close, leading to more frequent changes of equivalence class than in the third row.
The bottom row illustrates Remark 1 well. Since several bars are close to each other (represented here by several points in the persistence diagram that are close to each other), applying the TNS algorithm leads to frequent changes in equivalence classes, leading to the oscillatory behavior of the tree-realization number curve.

5.5. Tree-Realizations of Biological Barcodes

Since the original objective in developing the TMD was to classify digital reconstructions of neurons, it is natural to ask whether those barcodes that arise biologically exhibit any special characteristics compared to those arising from other sets of geometric trees. In Figure 20, we employ the graphical representation of permutations introduced in Section 5.3 to display as red dots all possible permutations corresponding to TMD-barcodes of biological trees with at most 30 branches arising from a population of digital reconstructions of neurons. Clearly, only a small fraction of the set of all possible permutations can be realized as the barcode-equivalence classes of geometric trees extracted from digital reconstructions of neurons, as every black dot in this plot can arise as a pair k , σ ( k ) for some permutation σ . In future work, we intend to study the biological relevance of this restriction.
To provide further insight into the subset of TMD-equivalence classes of biological geometric trees within the set of all possible TMD-equivalence classes, we computed the tree-realization number as a function of the number of bars, for a population of barcodes obtained by applying the TMD to geometric trees extracted from a population of digitally reconstructed neurons. We compared the values obtained to the maximum tree-realization number and to the tree-realization numbers of randomly chosen barcodes with the same number of bars (Figure 21). Interestingly, the barcodes that correspond to apical dendrites (relatively complex neural trees that perform significant processing tasks) exhibit a more narrow range of possible tree-realization numbers than random barcodes of the same size. On the other hand, barcodes of basal dendrites (less complex neuronal trees) exhibit tree-realization numbers similar to those of the randomly generated barcodes.

6. Discussion

In this paper, we presented and analyzed two algorithms that are relevant in topological data analysis: the TMD, which encodes the structure of a geometric tree in a barcode, and the TNS, which generates a geometric tree from a barcode. We proved that, for a good choice of parameter, the TNS is robust with respect to small perturbations of barcodes; an analogous stability result for the TMD was established in [13].
We observed that ordering the bars in the persistence barcode according to birth times results in the natural association of a permutation to the barcode, based on death times, giving rise to a meaningful equivalence relation on the set of barcodes. We also introduced a natural, combinatorial equivalence relation on geometric trees. For any barcode, we analyzed the set of combinatorial equivalence classes of those geometric trees whose TMD corresponds to that barcode, providing a simple, explicit formula for its cardinality in terms of the permutation associated with the barcode. Cayley graphs of symmetric groups provide a useful visualization of how this cardinality varies as bars in the barcode are transposed.
We illustrated our theoretical results computationally. In addition, we computed the probability for the TNS to generate different combinatorial tree types from a fixed barcode and found it to be a function of the parameter λ on which the TNS depends, a result which can be explained only by the stochastic nature of the TNS algorithm. The stochastic nature of the TNS algorithm also leads to variation in the equivalence classes of barcodes associated by the TMD to the trees generated from a fixed barcode by the TNS. In particular, when starting with the TMD of a “biological” tree (i.e., arising from a digital neuron reconstruction) including bars with similar birth or death times, we observed an oscillatory behavior between two (or more) different classes states, increasing the variance of the generated trees.
We also initiated an analysis of the distinctive features of biological trees compared to random trees. We discovered that the barcodes associated by the TMD to trees representing neuronal morphologies represent a small fraction of possible equivalence classes of barcodes. It follows that the set of combinatorial types of geometric trees that are biologically realized is also constrained, indicating a biological preference for specific tree structures. There is much still to discover about which geometric or combinatorial features distinguish biological trees among all geometric trees and why.
In future work, we intend to further investigate the effect of different types of noise on the TNS algorithm. For instance, we have considered only the effect of transposing two bars, but other types of changes are certainly also relevant, such as investigating the effects of switching both births and deaths, as mentioned in Remark 1. On a more neuroscientific note, we intend to continue exploring the distinguishing characteristics of biological trees, with the goal of explaining the structural and functional reasons for the observed geometric and combinatorial constraints.
On the mathematical side, we are currently analyzing the structure on the space of barcodes revealed by the symmetric groups and determining what information can be extracted from the induced stratification of this space. This structure on the space of barcodes should also provide significant insights into the still somewhat mysterious space of geometric trees, which is of considerable interest to a wide range of mathematicians.

Author Contributions

Conceptualization by L.K., experiments performed by L.K. and A.G. Formal analysis and theorem formulation by L.K., A.G., and K.H. Supervision by K.H. All authors have read and agreed to the published version of the manuscript.

Funding

This study was supported by funding to the Blue Brain Project, a research center of the École polytechnique fédérale de Lausanne (EPFL), from the Swiss government’s ETH Board of the Swiss Federal Institutes of Technology. A.G. and K.H. gratefully acknowledge the support of Swiss National Science Foundation, Grant No. CRSII5_177237.

Acknowledgments

The authors would like to thank Justin Curry, Jordan De Sha, and Brendan Mallery for fruitful discussions. We also thank LNMC lab for the neuronal reconstructions used for this analysis, as part of the BBP neuron morphologies dataset.

Conflicts of Interest

The authors declare no conflict of interest.

References

  1. Frosini, P.; Landi, C. Size Functions and Morphological Transformations. Acta Appl. Math. 1997, 49, 85–104. [Google Scholar] [CrossRef]
  2. Edelsbrunner, H.; Letscher, D.; Zomorodian, A. Topological Persistence and Simplification. Discret. Comput. Geom. 2002, 28, 511–533. [Google Scholar] [CrossRef] [Green Version]
  3. Robins, V. Computational Topology for Point Data: Betti Numbers of α-Shapes. In Morphology of Condensed Matter; Springer: Berlin/Heidelberg, Germany, 2002. [Google Scholar]
  4. Zomorodian, A.; Carlsson, G. Computing persistent homology. Discret. Comput. Geom. 2005, 33, 249–274. [Google Scholar] [CrossRef] [Green Version]
  5. Verri, A.; Uras, C.; Frosini, P.; Ferri, M. On the use of size functions for shape analysis. Biol. Cybern. 2004, 70, 99–107. [Google Scholar] [CrossRef]
  6. Carlsson, G. Topology and data. Bull. Am. Math. Soc. 2009, 46, 255–308. [Google Scholar] [CrossRef] [Green Version]
  7. Harrington, H.; Feliu, E.; Wiuf, C.; Stumpf, M.P. Cellular compartments cause multistability in biochemical reaction networks and allow cells to process more information. arXiv 2012, arXiv:1210.2993v1. [Google Scholar]
  8. Byrne, H.; Harrington, H.; Muschel, R.; Reinert, G.; Stolz, B.J.; Tillmann, U. Topological Methods for Characterising Spatial Networks: A Case Study in Tumour Vasculature. arXiv 2019, arXiv:1907.08711. [Google Scholar]
  9. Martino, A.; Rizzi, A.; Mascioli, F.M.F. Supervised Approaches for Protein Function Prediction by Topological Data Analysis. In Proceedings of the 2018 International Joint Conference on Neural Networks (IJCNN), Rio de Janeiro, Brazil, 8–13 July 2018; pp. 1–8. [Google Scholar]
  10. Gameiro, M.; Hiraoka, Y.; Izumi, S.; Kramár, M.; Mischaikow, K.; Nanda, V. A topological measurement of protein compressibility. Jpn. J. Ind. Appl. Math. 2015, 32, 1–17. [Google Scholar] [CrossRef]
  11. Lee, Y.; Barthel, S.; Dłotko, P.; Moosavi, S.M.; Hess, K.; Smit, B. High-Throughput Screening Approach for Nanoporous Materials Genome Using Topological Data Analysis: Application to Zeolites. J. Chem. Theory Comput. 2018, 14, 4427–4437. [Google Scholar] [CrossRef]
  12. Muszynski, G.; Kashinath, K.; Kurlin, V.; Wehner, M.F.; Prabhat, M. Topological Data Analysis and Machine Learning for Recognizing Atmospheric River Patterns in Large Climate Datasets. Geosci. Model Dev. 2019, 12, 613–628. [Google Scholar] [CrossRef] [Green Version]
  13. Kanari, L.; Dłotko, P.; Scolamiero, M.; Levi, R.; Shillcock, J.; Hess, K.; Markram, H. A Topological Representation of Branching Neuronal Morphologies. Neuroinformatics 2018, 16, 3–13. [Google Scholar] [CrossRef] [PubMed] [Green Version]
  14. Reimann, M.W.; Nolte, M.; Scolamiero, M.; Turner, K.; Perin, R.; Chindemi, G.; Dlotko, P.; Levi, R.; Hess, K.; Markram, H. Cliques of Neurons Bound into Cavities Provide a Missing Link between Structure and Function. Front. Comput. Neurosci. 2017, 11, 48. [Google Scholar] [CrossRef] [PubMed] [Green Version]
  15. Sizemore, A.; Giusti, C.; Kahn, A.E.; Vettel, J.; Betzel, R.; Bassett, D. Cliques and cavities in the human connectome. J. Comput. Neurosci. 2017, 44, 115–145. [Google Scholar] [CrossRef] [PubMed] [Green Version]
  16. Stolz, B.J.; Harrington, H.; Porter, M. Persistent homology of time-dependent functional networks constructed from coupled time series. Chaos 2017, 27, 047410. [Google Scholar] [CrossRef]
  17. Kanari, L.; Ramaswamy, S.; Shi, Y.; Morand, S.; Meystre, J.; Perin, R.; Abdellah, M.; Wang, Y.; Hess, K.; Markram, H. Objective Morphological Classification of Neocortical Pyramidal Cells. Cereb. Cortex 2019, 29, 1719–1735. [Google Scholar] [CrossRef]
  18. Oudot, S.; Solomon, E. Inverse Problems in Topological Persistence. arXiv 2018, arXiv:1810.10813. [Google Scholar]
  19. Curry, J.; Mukherjee, S.; Turner, K. How Many Directions Determine a Shape and other Sufficiency Results for Two Topological Transforms. arXiv 2018, arXiv:1805.09782. [Google Scholar]
  20. Belton, R.L.; Fasy, B.T.; Mertz, R.; Micka, S.; Millman, D.L.; Salinas, D.; Schenfisch, A.; Schupbach, J.; Williams, L. Reconstructing Embedded Graphs from Persistence Diagrams. arXiv 2020, arXiv:1912.08913. [Google Scholar] [CrossRef]
  21. Kanari, L.; Dictus, H.; Chalimourda, A.; Van Geit, W.; Coste, B.; Shillcock, J.; Hess, K.; Markram, H. Computational Synthesis of Cortical Dendritic Morphologies. Cell 2020. [Google Scholar] [CrossRef]
  22. Curry, J. The Fiber of the Persistence Map for Functions on the Interval. arXiv 2019, arXiv:1706.06059. [Google Scholar] [CrossRef] [Green Version]
  23. Markram, H.; Muller, E.; Ramaswamy, S.; Reimann, M.W.; Abdellah, M.; Sanchez, C.A.; Ailamaki, A.; Alonso-Nanclares, L.; Antille, N.; Arsever, S.; et al. Reconstruction and Simulation of Neocortical Microcircuitry. Cell 2015, 163, 456–492. [Google Scholar] [CrossRef] [PubMed]
  24. Aslangul, C.; Pottier, N.; Chvosta, P.; Saint-James, D. Directed random walk with spatially correlated random transfer rates. Phys. Rev. E 1993, 47 3, 1610–1617. [Google Scholar] [CrossRef]
  25. Galton, F.; Watson, H.W. On the Probability of the Extinction of Families. J. Anthropol. Inst. Great Br. Irel. 1875, 4, 138–144. [Google Scholar]
  26. Koene, R.; Tijms, B.; van Hees, P.; Postma, F.; Ridder, A.; Ramakers, G.; Pelt, J.; Ooyen, A.V. NETMORPH: A Framework for the Stochastic Generation of Large Scale Neuronal Networks with Realistic Neuron Morphologies. Neuroinformatics 2009, 7, 195–210. [Google Scholar] [CrossRef] [PubMed]
Figure 1. The two composites of TMD and TNS. (Left) An illustration of how a neuron (black) is modeled as a tree (dashed red lines). We describe this process and how to extract a barcode from a tree in Section 2.3. (Top) The composite TMD TNS applied to a barcode B. The new barcode B = TMD TNS ( B ) is indicated in dashed lines on top of the barcode B on the right. We show in Section 4 that the barcodes B and B will almost certainly be very similar and quantify this similarity. (Bottom) The composite TNS TMD applied to a tree T. The tree T that we start with is indicated in dashed red lines under the new tree T = TNS TMD ( T ) . The trees T and T can be quite different combinatorially, as seen on the right.
Figure 1. The two composites of TMD and TNS. (Left) An illustration of how a neuron (black) is modeled as a tree (dashed red lines). We describe this process and how to extract a barcode from a tree in Section 2.3. (Top) The composite TMD TNS applied to a barcode B. The new barcode B = TMD TNS ( B ) is indicated in dashed lines on top of the barcode B on the right. We show in Section 4 that the barcodes B and B will almost certainly be very similar and quantify this similarity. (Bottom) The composite TNS TMD applied to a tree T. The tree T that we start with is indicated in dashed red lines under the new tree T = TNS TMD ( T ) . The trees T and T can be quite different combinatorially, as seen on the right.
Algorithms 13 00335 g001
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 ) .
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 ) .
Algorithms 13 00335 g002
Figure 3. The algorithm to encode a tree structure as a persistence barcode. (A) neuronal tree; (B) persistence barcode generated with TMD. Each branch in the tree (A) corresponds to a bar in the barcode (B); the circled numbers encode the correspondence between branches and bars. Terminations are shown in blue, bifurcations in red, and branches in between in black.
Figure 3. The algorithm to encode a tree structure as a persistence barcode. (A) neuronal tree; (B) persistence barcode generated with TMD. Each branch in the tree (A) corresponds to a bar in the barcode (B); the circled numbers encode the correspondence between branches and bars. Terminations are shown in blue, bifurcations in red, and branches in between in black.
Algorithms 13 00335 g003
Figure 4. A strict barcode, whose bars are ordered according to birth times (greyscale), defines a unique ordering of death times. This ordering and the Elder Rule constrain the possible combinatorial types of trees that can be realized from this barcode. (A) the notation that will be used in this paper from a barcode that corresponds to an adjacency matrix of possible connectivities. Equivalently, the possible connectivities are presented in the connectivity diagram; (B) examples of possible tree realizations from branches that connect to the longest one (top) to random (bottom).
Figure 4. A strict barcode, whose bars are ordered according to birth times (greyscale), defines a unique ordering of death times. This ordering and the Elder Rule constrain the possible combinatorial types of trees that can be realized from this barcode. (A) the notation that will be used in this paper from a barcode that corresponds to an adjacency matrix of possible connectivities. Equivalently, the possible connectivities are presented in the connectivity diagram; (B) examples of possible tree realizations from branches that connect to the longest one (top) to random (bottom).
Algorithms 13 00335 g004
Figure 5. Tree-realizations of all possible strict barcodes B with four bars. Each row (left) represents a possible permutation of death times for the corresponding order of bars in B, i.e., a possible TMD-type. Each barcode can be realized by a subset of all the combinatorial tree types, each represented by a column, with a corresponding adjacency matrix.
Figure 5. Tree-realizations of all possible strict barcodes B with four bars. Each row (left) represents a possible permutation of death times for the corresponding order of bars in B, i.e., a possible TMD-type. Each barcode can be realized by a subset of all the combinatorial tree types, each represented by a column, with a corresponding adjacency matrix.
Algorithms 13 00335 g005
Figure 6. The two possible moves that respect the condition of a realizable barcode. Move ( A ) modifies the barcode’s ordering, whereas move ( B ) does not change the order of the deaths.
Figure 6. The two possible moves that respect the condition of a realizable barcode. Move ( A ) modifies the barcode’s ordering, whereas move ( B ) does not change the order of the deaths.
Algorithms 13 00335 g006
Figure 7. A representation of the space of barcodes with four bars up to permutation equivalence class as the Cayley graph of S 3 generated by the transpositions ( 12 ) and ( 23 ) , respectively. Each vertex is an element of the group. The edges represent the transposition to convert one end point into the other, colored by generator. The number to the right of each bar is its index. All trees T such that TMD ( T ) = B are indicated next to a barcode B with the corresponding tree type of Figure 5. The number of such trees can be computed using Lemma 2.
Figure 7. A representation of the space of barcodes with four bars up to permutation equivalence class as the Cayley graph of S 3 generated by the transpositions ( 12 ) and ( 23 ) , respectively. Each vertex is an element of the group. The edges represent the transposition to convert one end point into the other, colored by generator. The number to the right of each bar is its index. All trees T such that TMD ( T ) = B are indicated next to a barcode B with the corresponding tree type of Figure 5. The number of such trees can be computed using Lemma 2.
Algorithms 13 00335 g007
Figure 8. A barcode B in equivalence class ( 213 ) is shown in black. There are three possible combinatorial equivalence classes of trees whose TMD barcode is B, also represented in black. After adding the extra bar in red, we obtain a new barcode B , in the equivalence class ( 2143 ) . In a tree-realization of B , the branch corresponding to the red bar can be attached to any of the branches corresponding to the 0th, 1st, and 2nd bars, represented on the trees by the red branches. This leads to nine possible combinatorial equivalence classes of trees for the barcode ( 2134 ) .
Figure 8. A barcode B in equivalence class ( 213 ) is shown in black. There are three possible combinatorial equivalence classes of trees whose TMD barcode is B, also represented in black. After adding the extra bar in red, we obtain a new barcode B , in the equivalence class ( 2143 ) . In a tree-realization of B , the branch corresponding to the red bar can be attached to any of the branches corresponding to the 0th, 1st, and 2nd bars, represented on the trees by the red branches. This leads to nine possible combinatorial equivalence classes of trees for the barcode ( 2134 ) .
Algorithms 13 00335 g008
Figure 9. The Cayley graph representing S 4 generated by ( 12 ) , ( 23 ) , ( 34 ) . For the four outside elements, we provide the barcode associated with the permutation. The number next to each bar is its index.
Figure 9. The Cayley graph representing S 4 generated by ( 12 ) , ( 23 ) , ( 34 ) . For the four outside elements, we provide the barcode associated with the permutation. The number next to each bar is its index.
Algorithms 13 00335 g009
Figure 10. Upper bound on the probability that the bottleneck distance between B and TNS TMD ( B ) is larger than ε (Equation (1)) for various values of λ and for n = 10 .
Figure 10. Upper bound on the probability that the bottleneck distance between B and TNS TMD ( B ) is larger than ε (Equation (1)) for various values of λ and for n = 10 .
Algorithms 13 00335 g010
Figure 11. (A) The 1 -distance between the black bullet and the diamond follows an Erlang ( 2 , λ ) distribution. The interior of the green square defines a bound for the 1 -distance from the black bullet that depends on the value of the parameter λ . (B) If the endpoints of the bars of B are sufficiently far away from each other and B TMD TNS ( B ) , then, with high probability, taking γ = I will minimize the 1 -distance between pairs of endpoints of bars. (C) If the endpoints of B are instead close to each other, then it is more likely that B TMD TNS ( B ) , so that the optimal choice of γ (represented by red segments) is not the identity. The red distances do not necessarily follow exponential distributions, so the proof of Lemma 4 does not apply.
Figure 11. (A) The 1 -distance between the black bullet and the diamond follows an Erlang ( 2 , λ ) distribution. The interior of the green square defines a bound for the 1 -distance from the black bullet that depends on the value of the parameter λ . (B) If the endpoints of the bars of B are sufficiently far away from each other and B TMD TNS ( B ) , then, with high probability, taking γ = I will minimize the 1 -distance between pairs of endpoints of bars. (C) If the endpoints of B are instead close to each other, then it is more likely that B TMD TNS ( B ) , so that the optimal choice of γ (represented by red segments) is not the identity. The red distances do not necessarily follow exponential distributions, so the proof of Lemma 4 does not apply.
Algorithms 13 00335 g011
Figure 12. (A1A3) Bottleneck distance as a function of λ . We compute the bottleneck distance between an input barcode B and an output barcode B for λ = 0.01 2 . (A1) From barcode B (in black), a tree (in red) is generated using the TNS which results in a new barcode B = TMD TNS ( B ) (in red). (A2) The average bottleneck distance (red points) is compared to the expected mean of the probability distribution function found in Lemma 4 (blue curve). (A3) The bottleneck distances (red) are compared to the cumulative distribution probability for 0 < ϵ < 200 and 0 < λ < 2 (blue). (B1B2) bottleneck distance between B and B as a function of distances between bars in B. (B1). We consider barcodes of the same permutation type for different distances between two bars ( b i , d i ) and ( b j , d j ) of the initial barcode B that are consecutive in the order of deaths. (B2) For each input barcode with increasing d i , the distance between death times presented in x-axis, 100 synthesized barcodes are generated and the bottleneck distance between the input and output barcodes is computed (y-axis), which depends only on the value of λ and not on the distance between the bars.
Figure 12. (A1A3) Bottleneck distance as a function of λ . We compute the bottleneck distance between an input barcode B and an output barcode B for λ = 0.01 2 . (A1) From barcode B (in black), a tree (in red) is generated using the TNS which results in a new barcode B = TMD TNS ( B ) (in red). (A2) The average bottleneck distance (red points) is compared to the expected mean of the probability distribution function found in Lemma 4 (blue curve). (A3) The bottleneck distances (red) are compared to the cumulative distribution probability for 0 < ϵ < 200 and 0 < λ < 2 (blue). (B1B2) bottleneck distance between B and B as a function of distances between bars in B. (B1). We consider barcodes of the same permutation type for different distances between two bars ( b i , d i ) and ( b j , d j ) of the initial barcode B that are consecutive in the order of deaths. (B2) For each input barcode with increasing d i , the distance between death times presented in x-axis, 100 synthesized barcodes are generated and the bottleneck distance between the input and output barcodes is computed (y-axis), which depends only on the value of λ and not on the distance between the bars.
Algorithms 13 00335 g012
Figure 13. We are interested in the case where d j < d i when we start from d i < d j . The distances | d i d i | and | d j d j | both follow an exponential law of parameter λ . The probability to terminate increases exponentially when approaching d i and d j , as represented by the blue arrows.
Figure 13. We are interested in the case where d j < d i when we start from d i < d j . The distances | d i d i | and | d j d j | both follow an exponential law of parameter λ . The probability to terminate increases exponentially when approaching d i and d j , as represented by the blue arrows.
Algorithms 13 00335 g013
Figure 14. (A) Example of two bars changing order, which results in switching of classes. We show here a tree, its barcode, and the corresponding persistence diagram when two consecutive deaths switch their order. The impact of the change is illustrated by the red arrows; (B) percentage of order changes per 100 repetitions for varied distance between death times of two consecutive bars of the input barcode. Comparison of theoretical results (solid lines) to simulations (scatter plot) for different values of lambda.
Figure 14. (A) Example of two bars changing order, which results in switching of classes. We show here a tree, its barcode, and the corresponding persistence diagram when two consecutive deaths switch their order. The impact of the change is illustrated by the red arrows; (B) percentage of order changes per 100 repetitions for varied distance between death times of two consecutive bars of the input barcode. Comparison of theoretical results (solid lines) to simulations (scatter plot) for different values of lambda.
Algorithms 13 00335 g014
Figure 15. Histogram of tree-realization numbers for equivalence classes of barcodes with n + 1 bars ( 1 n 10 ). The maximal tree-realization number for a fixed number of bars can be achieved with exactly one equivalence class that of the strictly ordered barcode.
Figure 15. Histogram of tree-realization numbers for equivalence classes of barcodes with n + 1 bars ( 1 n 10 ). The maximal tree-realization number for a fixed number of bars can be achieved with exactly one equivalence class that of the strictly ordered barcode.
Algorithms 13 00335 g015
Figure 16. Empirical distribution (percentage of 1000 trees) of synthesized geometric trees with four branches by combinatorial tree type (AF) for a given input barcode equivalence class (rows), when λ = 1 . We observe that the distribution is approximately uniform.
Figure 16. Empirical distribution (percentage of 1000 trees) of synthesized geometric trees with four branches by combinatorial tree type (AF) for a given input barcode equivalence class (rows), when λ = 1 . We observe that the distribution is approximately uniform.
Algorithms 13 00335 g016
Figure 17. Barcode-equivalence class, represented by the corresponding permutation, (A) and persistence diagram (B) of 100 synthesized cells based on a geometric tree with eight branches, extracted from a layer 4 pyramidal cell. The barcode-equivalence classes of the synthesized trees (represented by blue dots) can differ from that of the original tree due to the stochastic nature of synthesis algorithm. The persistence diagrams of the synthesized trees ((B), blue) are essentially indistinguishable from those of the original tree ((B), red).
Figure 17. Barcode-equivalence class, represented by the corresponding permutation, (A) and persistence diagram (B) of 100 synthesized cells based on a geometric tree with eight branches, extracted from a layer 4 pyramidal cell. The barcode-equivalence classes of the synthesized trees (represented by blue dots) can differ from that of the original tree due to the stochastic nature of synthesis algorithm. The persistence diagrams of the synthesized trees ((B), blue) are essentially indistinguishable from those of the original tree ((B), red).
Algorithms 13 00335 g017
Figure 18. We begin with a barcode with eight bars. The death times d i 4 and d i 5 (i.e., the 4th and 5th largest death times) are slowly switching as k increases, represented by red-shifting of the color of the points in the persistence diagram. When k = 0 (in red), we have the original barcode B, and when k = 50 (in blue) we obtain a barcode identical to the original, except that ( b i 4 , d i 4 ) is replaced by ( b i 4 , d i 5 ) and ( b i 5 , d i 5 ) by ( b i 5 , d i 4 ) .
Figure 18. We begin with a barcode with eight bars. The death times d i 4 and d i 5 (i.e., the 4th and 5th largest death times) are slowly switching as k increases, represented by red-shifting of the color of the points in the persistence diagram. When k = 0 (in red), we have the original barcode B, and when k = 50 (in blue) we obtain a barcode identical to the original, except that ( b i 4 , d i 4 ) is replaced by ( b i 4 , d i 5 ) and ( b i 5 , d i 5 ) by ( b i 5 , d i 4 ) .
Algorithms 13 00335 g018
Figure 19. On the left, evolution of PD ( B k ) as k increases (represented by red-shifting of the point color, from red k = 0 to blue k = 50 ), for various pairs of bars. When not clear, we circle in orange the two points that switch. On the right, the corresponding evolution of the tree realization number TRN ( B k ) as k increases. For instance, as indicated in Table 2, the tree-realization number of B 1 is 810 and that of B ^ 1 = B 50 1 is 540. The barcodes B k exhibit the behavior described in Lemma 5, except for the last row, in which death times that are too close to each other (circled in purple and green) interfere with the process. Without this interference, the tree-realization numbers should oscillate between 20 and 40. When k gets close to 50 (blue), the death time d i 1 (largest death time) starts interfering with the third one d i 3 (circled in purple) in the tree synthesis process.
Figure 19. On the left, evolution of PD ( B k ) as k increases (represented by red-shifting of the point color, from red k = 0 to blue k = 50 ), for various pairs of bars. When not clear, we circle in orange the two points that switch. On the right, the corresponding evolution of the tree realization number TRN ( B k ) as k increases. For instance, as indicated in Table 2, the tree-realization number of B 1 is 810 and that of B ^ 1 = B 50 1 is 540. The barcodes B k exhibit the behavior described in Lemma 5, except for the last row, in which death times that are too close to each other (circled in purple and green) interfere with the process. Without this interference, the tree-realization numbers should oscillate between 20 and 40. When k gets close to 50 (blue), the death time d i 1 (largest death time) starts interfering with the third one d i 3 (circled in purple) in the tree synthesis process.
Algorithms 13 00335 g019
Figure 20. (A) TMD-equivalence classes of a population of biological geometric trees with at most 30 bars (red dots), represented by their associated permutations; (B) examples of TMD-equivalence classes of individual biological geometric trees with eight branches, extracted from layer 4 pyramidal cells (red dots).
Figure 20. (A) TMD-equivalence classes of a population of biological geometric trees with at most 30 bars (red dots), represented by their associated permutations; (B) examples of TMD-equivalence classes of individual biological geometric trees with eight branches, extracted from layer 4 pyramidal cells (red dots).
Algorithms 13 00335 g020
Figure 21. The log of the tree-realization number for barcodes with varying numbers of bars. (A) the log of tree-realization number for barcodes of basal dendrites (in blue) in comparison with random barcodes (in yellow) and the maximum tree-realization number ( n ! for n + 1 bars) (in red); (B) the log of the tree-realization number for barcodes of apical dendrites (in blue) in comparison with random barcodes (in yellow) and the maximum maximum tree-realization number (in red).
Figure 21. The log of the tree-realization number for barcodes with varying numbers of bars. (A) the log of tree-realization number for barcodes of basal dendrites (in blue) in comparison with random barcodes (in yellow) and the maximum tree-realization number ( n ! for n + 1 bars) (in red); (B) the log of the tree-realization number for barcodes of apical dendrites (in blue) in comparison with random barcodes (in yellow) and the maximum maximum tree-realization number (in red).
Algorithms 13 00335 g021
Table 1. Summary and terminology of the TMD and TNS algorithms. The TMD computes the barcode of a tree from the tips of branches towards the root, whereas the TNS grows the tree in the opposite direction, from the root to the leaves.
Table 1. Summary and terminology of the TMD and TNS algorithms. The TMD computes the barcode of a tree from the tips of branches towards the root, whereas the TNS grows the tree in the opposite direction, from the root to the leaves.
TMDTNS
GoalCompute the barcode of a tree based on a distance functionGrow a new tree from a barcode
DirectionalityFrom leaves to rootFrom root to leaves
Domains { geometric trees } { barcodes } { barcodes } { geometric trees }
Table 2. For each example displayed in Figure 19, we list the permutation type and the tree-realization number of the original barcode B and of B ^ = B 50 , and the indices of the bars that are switched. The superscript i in B i indicates the corresponding row of Figure 19. For example, the largest death time of barcode B 1 is the second bar (in order of birth times), and its shortest death is the third one. When we switch the 4th and 5th (from largest to smallest) death times in B 1 and B ^ 1 , the TRN changes from 810 to 540.
Table 2. For each example displayed in Figure 19, we list the permutation type and the tree-realization number of the original barcode B and of B ^ = B 50 , and the indices of the bars that are switched. The superscript i in B i indicates the corresponding row of Figure 19. For example, the largest death time of barcode B 1 is the second bar (in order of birth times), and its shortest death is the third one. When we switch the 4th and 5th (from largest to smallest) death times in B 1 and B ^ 1 , the TRN changes from 810 to 540.
PermutationTRNBars That Switch
B 1 ( 2 , 6 , 8 , 1 , 5 , 7 , 4 , 3 ) 8104 and 5
B ^ 1 ( 2 , 6 , 8 , 5 , 1 , 7 , 4 , 3 ) 5404 and 5
B 2 ( 5 , 7 , 6 , 4 , 2 , 1 , 3 ) 122 and 3
B ^ 2 ( 5 , 6 , 7 , 4 , 2 , 1 , 3 ) 182 and 3
B 3 ( 5 , 7 , 6 , 4 , 2 , 1 , 3 ) 123 and 4
B ^ 3 ( 5 , 7 , 4 , 6 , 2 , 1 , 3 ) 183 and 4
B 4 ( 8 , 6 , 7 , 4 , 3 , 1 , 2 , 5 ) 201 and 2
B ^ 4 ( 6 , 8 , 7 , 4 , 3 , 1 , 2 , 5 ) 401 and 2
Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Share and Cite

MDPI and ACS Style

Kanari, L.; Garin, A.; Hess, K. From Trees to Barcodes and Back Again: Theoretical and Statistical Perspectives. Algorithms 2020, 13, 335. https://0-doi-org.brum.beds.ac.uk/10.3390/a13120335

AMA Style

Kanari L, Garin A, Hess K. From Trees to Barcodes and Back Again: Theoretical and Statistical Perspectives. Algorithms. 2020; 13(12):335. https://0-doi-org.brum.beds.ac.uk/10.3390/a13120335

Chicago/Turabian Style

Kanari, Lida, Adélie Garin, and Kathryn Hess. 2020. "From Trees to Barcodes and Back Again: Theoretical and Statistical Perspectives" Algorithms 13, no. 12: 335. https://0-doi-org.brum.beds.ac.uk/10.3390/a13120335

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Metrics

Back to TopTop