PLoS supp. material by Hermann Cuntz
None of the common formats for dendritic trees represent one and
the same tree in a unique way. This becomes very clear for the graph
representation where all permutations of labels (indices)
i → j result in the same tree:
dA(i,i) → dA(j,j)
Again, the same is true for the .swc format.
A more constrained representation is given by the BCT formalism
(which was developed as far as we know by Rocky Nevin
and implemented in the compartmental modelling software
NeMoSys, Eeckman FH, Theunissen FE and Miller JP, 1994,
Nemosys: a system for realistic single neuron modeling.
In Neural Network Simulation Environments,
ed. Skrzypek J, pp. 114-135. Boston, Dordrecht,
London: Kluwer Academic Publishers).
There, the node labels are sorted hierarchically
so that the nodes of a sub-tree remain in sequence
and within each sub-tree parent nodes always precede
their respective daughter nodes. This was done in our example:
the resulting BCT string can then be read out by summing
over the columns of dA.
Nodes where this sum is 0 (no daughter nodes) are termed “T” for terminal.
Nodes where the sum is 1 are termed “C” for continuation.
Nodes where the sum is 2 are termed “B” for branch.
The resulting string reads “CBBTTBTT”:
“Define a root and start a branch. Continue to next node (C).
Open new branch (B1). Open new branch (B2).
Terminate last branch which is still open (T2).
Terminate previous branch (T1).
Open new branch (B3). Terminate last opened branch (T3).
Terminate full tree (T0).”
The adjacency matrix is fully described by the BCT string
and additionally the labelling of the nodes is now more restricted.
But at each branch point permuting the sub-trees would still result
in the exact same underlying tree.
A simple way to arrange the node labels to conform to BCT is to insert
each node one by one directly behind its parent node and to re-label
the nodes after the whole process
An important note here: If the nodes are pre-sorted beforehand
(for example lexicographically or by level order and topological path length,
see section “sorting a tree”)
a perfectly unique representation of the topology can be obtained.
Note also: In BCT form, all entries in dA are strictly below the diagonal.
In order to find the directed adjacency matrix from a BCT string
by maintaining the order of elements (metrics can then be directly transferred)
the following algorithmic procedure can be applied:
% basic algorithm:
Set dA to square matrix of zeros
Use a stack
For i = 1:N
if index exists then dA(i,index) = 1
index = i
If BCT(i) == ‘0|T’ then index = POP stack
If BCT(i) == ‘2|B’ then PUSH i to stack
If an adjacency matrix represents a correct BCT order,
a pointer starting with one at the root diminishing by one for each terminal
and increasing by one for each branching point should become zero exactly
at the end of the string (position N, number of nodes).
This can be represented by the cumulative sum Cx:
Note that one rough way to obtain all possible BCT strings
with N nodes is by setting all numbers from 0 to 3N-1
into base 3 and verifying whether they are BCT.
This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 License