Definitions

BCT formalism

With the BCT form, the topology of a tree can be written as a simple string. The BCT form can be obtained by a simple algorithm

adapted from
PLoS supp. material by Hermann Cuntz

← using_graph_theory
→ sorted_and_equivalent_tree

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 (B₁). Open new branch (B₂). Terminate last branch which is still open (T₂). Terminate previous branch (T₁). Open new branch (B₃). Terminate last opened branch (T₃). Terminate full tree (T₀).”

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 (see "sort_tree").

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 (see "BCT_tree") 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
End

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 C_x:

Note that one rough way to obtain all possible BCT strings with N nodes is by setting all numbers from 0 to 3^N-1 into base 3 and verifying whether they are BCT.