BACKGROUND
neuronal morphology has been an important research topic due to its relevance to neuron growth, electrophysiology, classification, connectivity, and pathology.
in recent years the availability of morphological data has dramatically increased across a broad set of species, cell types, and conditions thanks in part to search and curation efforts of neuromorpho.org  <cit> .
meanwhile, new staining, imaging, and reconstruction technologies are producing orders of magnitude more data from animal models in projects such as flycircuit  <cit>  and flylight  <cit> .
ongoing advancements are continuously improving automated reconstruction  <cit>  and groundbreaking large scale endeavors such as the brain initiative are expected to expand the amount of data from mammalian organisms by additional fold factors.
importantly, these large datasets provide opportunity to validate universal morphological characteristics  <cit>  as well as to discover or test features and relationships of specific neuron types  <cit> .
drawing inspiration from the field of genomics, where the human genome project ushered in an analogous flood of data, a variety of new methods are being developed to enable search and analysis of the growing pool of morphological data.
historically, most metrics devised for morphological analysis have focused at the whole neuron level or averaged across branches, with some derived methods quantifying a feature as a function of distance from the soma .
pairwise comparisons have greater potential to detect fine structural distinctions, making them appropriate for search, curation, classification, and exploration of prototypical features.
recently several studies have used pairwise comparisons in morphological analysis.
pairwise sequence alignment of neurite path directional vectors helped determine the unique neuroblast lineage of larval drosophila neurons  <cit> .
the nblast algorithm leveraged a form of vector comparison, with nearest edges in two neuron images aligned and measured by their tangent vectors and spatial distance  <cit> .
thus, anatomical position and overall shape were applied for search, clustering, and classification to a database of over  <dig>  drosophila neurons.
the path2path algorithm compares neurons by assigning every path, from root to tip, of one neuron to the other.
the distance is given by the deformation of the paths, modulated by the difference in topological hierarchy of points along the paths  <cit> .
an extension of the elastic shape analysis framework captures the difference between trees based on path shape and topology, as well as bifurcation locations and angles  <cit> .
this method can also generate a representative “mean shape”, though the examples primarily represent common path features.
blastneuron, the most recent entry into the field, focuses on aligning branches both by topology and path shape via dynamic programming after first searching for similar neurons on the basis of morphometrics  <cit> .
in addition to providing an efficient approach for search in large databases, the alignment component could prove useful in detecting and pinpointing differences between related neurons and between reconstructions of the same neuron produced by multiple algorithms, enabling error correction and even synthesis of those algorithms.
the tree edit distance  compares the topology of two trees by determining the minimum sequence of edit operations required to transform one tree into another  <cit> .
specifically, each branch of two trees is aligned to a branch in the other tree or labeled as an insertion.
branch features such as length, volume, surface, and bifurcation angle can be represented; in this case an edit cost based on their differences is applied for each branch assignment.
the ted has been used on tree structures in multiple fields  <cit>  and constitutes the most related algorithm to what we present here.
we present an original strategy to evaluate alignment of topology distinctly from other branch features across a broad range of neuronal classes.
our method exploits the novel encoding of neuron trees as sequences of characters representing bifurcations presented in the preceding companion paper  <cit> .
we align the resulting strings with a custom-developed python package introduced here: pattern analysis via sequence-based tree alignment .
we used model-based cluster analysis on alignment scores to group similar neurites.
furthermore, we generated a consensus representation of clustered neurites by multiple sequence alignment revealing the conserved structural features of the corresponding trees.
sufficiently large neuron classes, well-defined by available metadata, were compared to the clusters to determine whether those classes are topologically distinct and, if so, what their defining global features are.
each arbor type of axons, dendrites, and pyramidal cell apical dendrites showed clear topology alignment clusters with distinctly conserved features.
moreover, we show that multiple alignment consensuses and motif analysis provide complementary levels of analysis of neurite topology.
as an immediate application, the pasta tool also enabled detection of previously unidentified duplicate reconstructions in the neuromorpho.org database; this important curation step will be incorporated in the regular data processing pipeline of this repository.
at the same time, the approach is extensible to more complex representations as required by the research goal.
methods
sequences are generated from neuronal trees as presented in the companion paper  <cit> : each branch is encoded as an a, c, or t depending on whether its child branches both bifurcate, bifurcate and terminate, or both terminate.
a depth-first traversal keeps child branches relatively near to parent branches in the sequence representation, and traversing the smaller subtree  before the larger  further preserves that proximity.
this choice also allows for a more intuitive description of changes to a tree structure .figure  <dig> pairwise global sequence alignment.
a. changes in tree structure are reflected in sequence representation.
when a side-branch is lost from a non-t node or a t-node with a c parent, a c node is removed from the sequence.
when a branch is lost from a t node with an a parent, the t is removed and the parent a becomes a c. b. two tree-derived sequences are aligned by matching characters and placing gaps when an alignment cannot be made.
c nodes or entire subtrees are gapped, from an a to its associated t .
the a at the front of a gap region can be matched to a c .
matches  count as  <dig> point, gaps  count as - <dig> point, and openings of a gap region count as - <dig> points.
alignment scores are normalized and converted into distance values.
c. sample apical dendrite morphologies of hippocampal ca <dig> and ca <dig> pyramidal cells   <cit>  and their topology dendrograms illustrate alignments between neurites of the same sub-region along with normalized distances for all  <dig> pairs.
raw alignment scores are also provided for within-class alignments.
inset: within- and between-group distributions of normalized distances  indicate that the pyramidal apical dendrites are topologically more similar to apical dendrites of their own group than to those in the other group.
custom sequence alignment algorithms were developed for tree-derived sequences given their particular structural features.
a global alignment algorithm was developed with specialized character types and alignment rules associated with bifurcation types.
the scores produced by this method were normalized by size and a random-tree baseline prior to analysis.
a multiple sequence alignment algorithm was also custom-adapted for tree-sequences from the genomics global and multiple alignment techniques.
other well-established data manipulation and analysis methods utilized in this work are briefly described as well, such as the creation of a metric space from alignments for further analysis including classification and model-based clustering.
clusters are then statistically analyzed for associations with known cell groups.
this methods section also describes the  dataset used in this study and related selection criteria.
all code developed for this study , including tree and sequence generation , sequence alignment , and analysis , is available open source at http://krasnow <dig> gmu.edu/cn3/neuritesequence/.
global tree-sequence alignment
powerful bioinformatics approaches exist for comparing gene sequences to each other to determine similarity and derive evolutionary relationships.
a gene may mutate by conversion of one base pair to another , the introduction of a new base , or the elimination of a base .
analogous operations allow the comparison of neuronal trees: the modification of branch properties, outgrowth of new branches, and branch retraction.
while neuronal trees do not explicitly share an ancestry or phylogenetic relationship typical of nucleotide sequences, they do share growth programs based on neuron type and associated genetic expression.
from a functional perspective, neuronal branches have properties that impact charge transfer, signal integration, and space occupancy.
the assembly plan of these features may indicate growth rules and functional attributes of the neuronal arbor as a whole.
given the described encoding scheme  <cit> , the growth of a single neurite branch results in one of two possible sequence edits, with branch retraction expectedly producing the opposite edit in either case.
growth prior to a bifurcation, or on the child branches of a t bifurcation, yields the insertion of a c .
growth on the terminal branch of a c bifurcation, however, will turn the c into an a bifurcation and insert a t .
conversely, the retraction of a t’s terminal branch deletes the t and turns the parent a into a c. if the t’s parent is a c, then the retraction effectively deletes the c .
a sequence traversed by the smaller subtree first ensures that the t insertion/deletion occurs adjacent to the a/c conversion.
the global alignment of topological sequences is modified from the needleman-wunsch algorithm  <cit>  to account for the branching structure of binary trees, with alignment rules associated with bifurcation types .
the algorithm involves a matrix created from the character positions of the two sequences being aligned running along either axis.
scores are calculated from the beginning of both sequences  to the end of both sequences  using previously calculated position alignments.
the best score from the three possible steps to a given position is assigned to each position in the matrix .
those steps include a match between the characters , a gap over the character of the first sequence , or a gap over the character of the second sequence .
the alignment score is given in the final position and a back-trace of the optimal route from the final position to the start position produces the alignment .
the tree-based sequence modifications correspond to the a, c, and t bifurcation node types, allowing for a representation that includes branch properties in addition to local topology.
it also assumes that each sequence is a single complete tree.
limitations are placed both on matching and gapping based on node type in order to ensure consistent alignment with a valid tree structure .
only pairs of characters of the same type are directly matched in the dynamic programming process.
a-type characters cannot be explicitly gapped.
although this can result in inaccessible positions during back-trace, a valid back-trace will always exist as long as each sequence is a complete tree.
c-type characters can be gapped normally.
t-type characters can be gapped, but the gap must extend up to the associated a node.
in terms of tree structure, the t node would be the last traversed node on the a node’s smaller subtree .
this within-sequence a-t relationship is defined in a recursive manner such that a t node’s associated a node is the nearest prior a node that does not have its own nearer subsequent t node.
while an entire subtree can be eliminated by gapping all characters from a to t, it is also possible for all but a single branch to be eliminated, leaving a single c node .
thus, when gapping a t node and its associated subtree, if the character in the opposing sequence position is a c, the gap region can end such that the a and c are matched.
the final t node of any sequence will have no matching a and cannot be gapped.
this would effectively lead all tree-sequences to align on the final t node making certain alignments impossible, such as a smaller tree aligning to an inner subtree of a larger tree.
two final modifications  fix this problem.
first, a nodes can be gapped prior to any matches.
second, the final t node of either sequence can gap back to another t node that has a match.
alignment scores are given by the number of matching positions minus the number of gaps .
an additional penalty of − <dig> is applied for each region of consecutive gaps.
this cost helps distinguish more closely related sequences and reduces the otherwise high probability of a perfect score for a pair of sequences of very different lengths.
perfect scores are problematic as they produce distance values of  <dig>  making alignment-space embedding impossible.
alternative gap opening costs were tried with no meaningful impact on the results reported here; however, tuning this parameter might help optimize future analyses depending on the specific questions of interest.
non-unitary gap costs have no impact  due to all matches adding the same amount to the score.
in order to focus on topological structure differences and not tree size differences, we normalized scores by sequence length.
specifically, a per-character score is computed and normalized against a length-pair matched random tree alignment baseline prior to analysis .
the normalized alignment score of a pair of trees is then converted to distance by subtracting it from  <dig>  the maximum possible score .
spatial embedding and classification
in order to investigate the pairwise relationships among neuronal tree sequences, neurites were embedded in a multidimensional space consistent with alignment distances using multidimensional scaling   <cit> .
while edit distances would allow for standard mds, the triangle inequality does not hold for tree alignment scores  <cit>  or our normalized distances, thus a non-metric version was employed  <cit> .
instead of producing a space that preserves the original distance values in the embedded space, non-metric mds seeks to preserve the relative proximity of the data elements.
in other words, neurites that are closer to each other than to a third item in the space have that same relationship in the original data.
the embedded data were subjected to cluster analysis to determine whether different neuron classes can be distinguished in terms of their topological sequences.
a wide variety of clustering methods exist, including agglomerative clustering, k-means clustering, and model-based clustering.
agglomerative clustering, including ward’s method  <cit> , can be run directly with distance values, obviating the need for mds, but top level clusters are less stable than in other methods and visualization is limited.
k-means assumes that the clusters are spherical and approximately of the same size  <cit> , but neither of those assumptions is sound with regards to the diverse population of neurite shapes.
model-based clustering was chosen due to its ability to test a variety of potentially optimal model types based upon the structure of the dataset  <cit> .
we used this approach to fit multivariate gaussians with parameters for size, shape, and correlation between dimensions while varying the number of clusters.
the simplest model with the greatest likelihood was selected using the bayesian information criterion.
associations between clusters and known neuron classes were quantified by the relative representation of a given metadata group within a cluster and vice versa using the bonferroni-corrected χ <dig> test .
to determine whether the alignment space captured the same or additional information relative to that of standard topological metrics, we compared the corresponding abilities to correctly identify known neuron types using unsupervised and supervised classification.
model-based clustering is unsupervised and was restricted to two clusters for the purposes of classification.
linear discriminant analysis  is a supervised approach that produces a trained classifier based on a subset of the data  <cit> .
by applying each method with different numbers of variables, an optimal classifier can be produced with the most informative variables identified.
classification accuracy was computed as the proportion of neurites in the appropriate class .
clustering performance was further measured by the adjusted rand index   <cit> .
an ari score of  <dig> indicates perfect cluster partitions along known classification, while a score of  <dig> indicates random partitioning of the neurites.
the metrics tested were number of bifurcations, maximum branch order, average partition asymmetry, and caulescence   <cit> .
multiple sequence alignment
the multiple sequence alignment  process involves several steps: the creation of a composite allowing for registration of the multiple alignment, multiple alignment of all sequences to the composite, generation of a position-specific scoring matrix  based on the prior msa, iteration until the msa is stable, and finally thresholding to extract a consensus sequence .
the composite is initially formed by aligning one sequence to another and then creating a sequence out of the alignment.
positions in which a gap exists are filled with the character on the non-gapped side of the alignment, and matches of a and c nodes take the a type.
this process is repeated with the growing composite now being aligned to each sequence in the set one at a time .
the multiple alignment is formed by aligning every sequence to the complete composite in the same manner as was used in the pairwise global sequence alignment.
this process identifies the sequence co-alignment positions without requiring an explicit score, thus no penalty is needed for initiating a gap region.
since the initial multiple alignment could be suboptimal, a pssm is generated with the positions defined by the composite and the scores defined by the number of sequences aligned at each position .
the multiple alignment is run again using the pssm, the process iterating until stability is reached or the thresholded consensus fails to increase in size or average conservation.
final consensuses can be determined for any given minimum conservation threshold.
higher thresholds produce shorter consensuses with higher average conservation and vice versa.
a threshold of 50% was used for all msa in this paper.
in msa columns containing both a and c nodes, the consensus value is an a if at least 50% of the sequences contain an a, and a c if at least 50% of the sequences contain either.
the a node’s associated t will have the same count, and thus will be contained in the consensus if and only if the a is.
this ensures that the consensus represents a single complete tree.
neuromorpho.org dataset
the dataset used in this research is the same as in the companion motif analysis  <cit> , drawing from neuromorpho.org  <cit>  version  <dig> .
briefly, it was composed of all unique neurons of the control, non-cultured condition, except for pyramidal neurons without distinct apical/basal trees.
axons, dendrites , and pyramidal apical dendrites were treated separately, with dendrites having any terminal branches smaller than  <dig> microns removed to avoid confusing likely spines for dendrites.
neurites with fewer than  <dig> bifurcations were eliminated to ensure sufficient complexity and reduce the probability of unrelated neurites achieving high similarity by chance.
a total of  <dig>  neurites were analyzed, including  <dig>  axons,  <dig>  dendrites, and  <dig> pyramidal apical dendrites.
RESULTS
using the separated arbors of neurons from the neuromorpho.org database, each neurite was encoded as a sequence  <cit> , aligned with every other sequence in the dataset, and the scores normalized and converted into distances .
inspection of normalized distances from hippocampal ca <dig> and ca <dig> apical dendrites, two groups known to have distinct topologies, showed greater distances between sequences from different groups than from within the same group .
this verifies that the tree-sensitive alignment of neurite sequences can distinguish different neurite classes.
while the distributions of within- and between-class distances overlap considerably, they are clearly more distinct than those generated using average partition asymmetry , which has previously been shown to distinguish ca <dig> and ca <dig> pyramidal apical dendrites  <cit> .
we next undertook an unsupervised cluster analysis to identify groups of neurites for inspection of topological features.
topology alignment space
an abstract sequence alignment space of neural trees was generated for the purposes of analyzing topological relationships between neurite types.
the calculated distances were used to embed neurites into a feature space, hereon referred to as alignment space, using non-metric multidimensional scaling .
eight dimensions were sufficient for the entire dataset, with the first four showing clear structure in terms of density distribution .
the spaces produced for each data subset are highly similar in the dominant first few dimensions which capture most of the original distance relationships.
while the space is an abstraction, roughly speaking the top dimensions are mainly a function of the number of bifurcations and asymmetry.
the first effect may initially seem counterintuitive since the number of bifurcations  was explicitly controlled for; however, it is in fact consistent with the observation that dendritic branch type composition depends on tree size .
at any rate, the correspondence between alignment dimensions and topological features is far from exact.
within a restricted region of the alignment space, moving in a set direction will result in trees with increasing or decreasing richness in some structural elements; over broader spans of the abstract space, however, the directional gradient of different elements will typically vary.figure  <dig> alignment space and clustering.
a. the log density plot of all neurite-derived sequences on the first two dimensions of alignment space suggests differentiable groups.
b. clustering of the alignment space reveals four clusters associated with dendrites , two associated with axons , and one associated with apical dendrites ; most neurites grouped with the cluster associated to their arbor types, but some classified with another cluster .
ellipses reflect the covariance matrices of the cluster models.
c. sub-clustering of apical dendrites yields additional spherical clusters that associate with neocortex , hippocampal ca <dig> , and hippocampal ca <dig> .
apical dendrites improperly classified have lower color intensity.
d. unsupervised model-based clustering of the alignment space classifies ca <dig> and ca <dig> apical dendrites with an adjusted rand index of  <dig> .
a trained linear discriminant analysis achieves 94% accuracy.
the density distribution of the alignment space suggests groupings of neurites that are more related to each other than they are to other groups of neurites.
model-based clustering methods were applied to choose the best model and the optimal number of clusters, and then to detect the clusters.
clusters take the form of multivariate gaussians with defined size, shape, and orientation, where parameters may be the same for all clusters or unique for each.
analyzing all neurites in the dataset yielded seven clusters with all parameters specified and distinct.
of those, four were solely associated with dendrites, one with axons, one with pyramidal apical dendrites, and one principally with axons but also significantly with apical dendrites .
this is consistent with the greater number and diversity of dendrites in the neuromorpho.org dataset.
accuracy  was 80% for dendrites, 65% for axons, and 54% for apical dendrites due to the significant overlap with one of the axon clusters.
each arbor type was also analyzed separately to identify potential sub-clusters and related associations with known metadata.
in the case of apical dendrites, the resulting three sub-clusters clearly associated with brain regions, specifically neocortex, hippocampal ca <dig>  and hippocampal ca <dig> .
this result highlights the importance of clustering subsets, particularly when there is a bias in proportions of available data.
in some cases differences may exist but be too small relative to topological variability or have too small of a sample size to detect.
classification and comparison to morphometrics
in order to determine how well, relative to morphometrics, alignment space can distinguish neurites of different types, we used both model-based clustering and linear discriminant analysis  to classify neurites.
in the case of ca <dig> and ca <dig> hippocampal apical dendrites , the optimal set of alignment space dimensions performed  better than the optimal principal components of topological metrics  using both methods.
the clustering approach produced an accuracy of 92%  using alignment space compared to 91%  using the principal components of the topological metrics.
alignment space performed even better using lda, producing an accuracy of 94% compared to 89% with topological metrics.
in the case of drosophila olfactory axons and mouse cortical pyramidal axons, alignment space  also produced better classification scores than topological morphometrics  using both methods.
of nine other neuronal class pairs that were at least minimally separated, the alignment space performed as well as  or better than topological metrics in  <dig> out of  <dig> cases.
these results show that, while topological metrics generally provide a robust characterization of neuronal classes, the additional detail captured by the sequence representation and alignment is sufficient to improve classification for some known classes.
for the explicit purposes of classification, supplementary  morphometrics are certainly called for; however, expanded sequence representation and pairwise alignment incorporating non-topological branch features have the potential to be more effective than those features summed or averaged across the neuron.
dendrite and axon clusters
we next looked at how dendrites sub-clustered by topological alignment.
dendrites, which make up the largest arbor type subset of the data , fell into  <dig> clusters with gaussians of varying cluster size, shape, and orientation .
four alignment dimensions were required to distinguish those clusters.
upon considering dendrite classes with sufficient specificity and size, seven classes showed highly significant association with one or more clusters .
the  <dig> dendrite clusters clearly separated cortical neurons from sensory neurons of several different species.
the only class that reciprocally associated with only one cluster  consisted of primate neocortical  pyramidal basal dendrites .
rodent neocortical pyramidal basal dendrites alone associated with cluster  <dig> and jointly with rodent neocortical interneuron dendrites in cluster  <dig>  clusters 4– <dig> associated with sensory and motor neurons.
motoneurons, primarily from cat, rat, and mouse, as well as rodent retinal ganglion cells, associated with cluster  <dig>  the rodent retinal ganglion cells associated most significantly with cluster  <dig> along with adult fly tangential cells  and larval fly sensory cells.
the latter two groups also associated with cluster  <dig>  thus, the three types of sensory neurons co-clustered, suggesting that topological features are shared by neurons which respond directly to the external environment.
tree size clearly distinguishes some of the clusters exemplified in some sample dendrites from each group, but differences in the number and distribution of major branches are also evident .figure  <dig> dendrite clusters.
a. clusters of  dendrites are shown in two perspectives of alignment space.
each perspective highlights dendrites in three of the six clusters, with dendrites in the other three shown in gray.
b. the association matrix of the clusters and seven groups defined by metadata combination of species, region, cell type, and age range.
the number of dendrites in each group and cluster are shown in parentheses.
values reflect the natural log of the contingency matrix p-values, with absolute values above  <dig> being significant .
dark gray cells represent cases in which significantly fewer dendrites satisfy the cluster/group association than expected given the marginals.
positive values in colored cells represent cases in which more dendrites fall into the cell than expected.
darker colors signify that an example morphology and dendrogram is provided in c   <cit> .
axons, though with far fewer total reconstructions  and representing fewer metadata groups, tend to be larger and so have the potential to separate more clearly.
perhaps due to their relatively limited diversity, axons exhibited structure in just two dimensions and fell into  <dig> clusters .
nevertheless, the clusters  had strong associations with metadata groups, specifically separating insects from mammals, pyramidal cells from different rodent species, and distinct interneuron types .
the fly olfactory neuron axons most clearly associated with cluster  <dig> and are substantially dissociated from clusters  <dig> and  <dig>  rat neocortical pyramidal axons associated with cluster  <dig>  while mouse neocortical pyramidal axons associated with cluster  <dig>  this result should be interpreted with caution since the larger axons of rat neurons may be more prone to slicing artifacts.
since the specific histological and imaging procedures can also affect the reconstructions, it is important to note that the mouse pyramidal axons primarily come from a single archive while the rat data have substantial contributions  from four different laboratories.
rodent  neocortical dendritic targeting interneurons  also associated with cluster  <dig>  though not as strongly.
rodent neocortical perisomatic targeting interneurons  associated with cluster  <dig>  representative morphologies and dendrograms  suggest features which are shared within or even define each cluster.
derivation of consensus representations and the qualitative and quantitative description of those features follow.figure  <dig> axon clusters.
a. axons fall into four spherical clusters of varying sizes.
colored dots correspond to axons classified with the cluster associated with the matching metadata group.
diamonds represent rodent cortical dendritic-targeting interneurons.
circles are defined by the covariance matrix of their cluster model with a radius of one standard deviation.
b. association matrix for axon metadata groups and clusters.
colored and dark gray cells show significantly positive and negative associations, respectively, with the number of axons in each group and cluster in parentheses.
c. representative morphologies and dendrograms are shown for each significantly positive association   <cit> .
multiple sequence alignment and consensuses
multiple sequence alignment  provides the means for extracting common structural features of a group of neurite sequences and measuring their level of conservation.
msa can be visualized as vertical densities illustrating how represented various positions are .
a consensus structure can be defined by setting a threshold for the proportion of member sequences aligned at each position.
a low threshold will result in a relatively larger consensus with lower average conservation  across member sequences.
this choice tends to reveal common local patterns, though in the extreme, motif analysis  <cit>  could be more effective for that purpose.
higher thresholds, in contrast, reveal the common global pattern by producing narrower consensuses with higher average conservation.
a 50% threshold was found to yield consistently clear results across clusters.
in general, the relative consensus length  and average conservation together provide a measure of how inter-related the sequences in a set are in terms of shared topological features.
for a measure of global representativeness that accounts for the sequence length variability, we also employed the normalized pairwise alignment score.figure  <dig> multiple sequence alignment and consensuses.
a. sequences of axonal cluster  <dig>  are aligned .
a section of the alignment is magnified along with the composite and consensus .
a single neurite in the cluster and its sequence in the msa is highlighted .
b, d. consensuses of axon clusters  <dig>  and  <dig> in sequence and dendrogram form, with relative length and average conservation statistics.
dendrogram branch width indicates conservation of the parent bifurcation .
branch length indicates variability preceding a bifurcation, calculated as the average proportion of a sequence falling between conserved bifurcations.
c, e. example morphologies and dendrograms of cluster  <dig>  and  <dig>  .
colored segments indicate an alignment with the consensus at the bifurcation.
black and gray segments indicate consensus bifurcations not found in the neurite and vice versa.
we take for comparison axon clusters  <dig> and  <dig>  which are next to each other in alignment space but display considerably different consensus features.
in order to focus on the most representative trees of each cluster, we only considered those sequences within one standard deviation of their cluster centers.
furthermore, to avoid any potential effect of number of sequences on the msa, the  <dig> sequences  closest to their respective cluster centers were used for msa and subsequent analysis.
the consensus of cluster  <dig> has an absolute length of  <dig>  a relative length of  <dig> %, and an average conservation of  <dig> % .
the consensus of cluster  <dig> has a substantially longer absolute length of  <dig> but a smaller relative length of  <dig> % due to the larger median sequence length relative to cluster  <dig> .
the cluster  <dig> consensus also has a higher average conservation of  <dig> %, meaning that while cluster  <dig> has a higher proportion of well-aligned branches, the well-aligned branches of cluster  <dig> are more densely represented in the cluster sequences.
these properties are in part explained by the different variability of sequence length between the two clusters.
if the higher variability of a cluster is due in part to a larger number of relatively short sequences, fewer bifurcations overall could align in the consensus.
longer sequences may be more likely to contribute to the consensus but will also align in many positions that do not pass the consensus threshold.
cluster  <dig> sequences have an average length of  <dig> , median of  <dig> , and standard deviation of  <dig> ; in contrast, cluster  <dig> sequences have an average length of  <dig>  a median of  <dig>  and a standard deviation of  <dig> .
the impact of this variability is seen in the branch lengths of the consensus dendrogram .
however, alignment scores normalized to z-scores , show the same relationship with cluster  <dig> having a score of  <dig>  ±  <dig>  compared to the cluster  <dig> average of  <dig>  ±  <dig>  .
this is consistent with the larger gaussian model which was fit to cluster  <dig>  indicating the looser relationship between its sequences.
the consensus dendrogram of cluster  <dig> shows where a substantial portion of the variability falls.
the root branch is particularly long, meaning that a relatively large proportion of parts of member sequences exist prior to that bifurcation.
sample axons from the cluster illustrate the alignment of the axons and consensus in full context .
consensus structural details also differ substantially between clusters  <dig> and  <dig>  consensus  <dig> has greater symmetry : in fact, consensus  <dig> has a maximum branch order of  <dig> compared to  <dig> for cluster  <dig>  even though cluster  <dig> has  <dig> more bifurcations.
the axons of cluster  <dig> show a greater average asymmetry of  <dig>  compared to cluster  <dig> axons asymmetry of  <dig>  .
other structural differences could relate to differential spatial targeting of these classes.
although the arbors from the two clusters showed similar spatial arrangements , their total neurite length differed significantly.
cluster  <dig> had a median length of  <dig>  μm  and cluster  <dig> a median of  <dig>  μm .
although many of the larger neurons in the clusters were not from the associated cell classes, the trend was consistent.
pyramidal axons, with a median length of  <dig>  μm, were shorter than dendritic targeting interneurons, with a median length of  <dig>  μm .
perisomatic targeting interneurons, with a median of  <dig>  μm were yet longer .
the greater length in spite of similar spatial arrangement suggests a greater density or some alternative heterogeneous distribution of branches for cluster  <dig> axons.
consensuses and motifs
we next considered whether the consensus is representative of local motifs patterns  <cit> , and whether motifs capture the global features of the consensus.
trimer-constrained surrogate sets were generated for each axon cluster consensus and for each individual axon sequence in order to produce motif profiles for comparison with the motif profiles of each cluster’s sequences.
briefly, random trees were generated with just size, size and node-type proportions, and size and dimer proportions equivalent to each consensus.
for a given consensus or axon sequence, node-type, dimer, and trimer proportions were then normalized to the respective proportions in the surrogate sets by determining the percentile rank of a given consensus k-mer proportion within the surrogate set’s k-mer proportion distribution .
the correlation between the motif patterns in the neurite sequences and their corresponding consensuses was small across the  <dig> axonal clusters , with the consensus values varying substantially more than the cluster averages .
moreover, while clusters  <dig> and  <dig> had very similar motif profiles, with only minor differences in dimers at, cc, ac, and ct, their consensuses differed dramatically .
for further comparison, cluster 3’s values are very different from clusters  <dig> and  <dig>  falling much closer to baseline, while the global consensus appears intermediate between those of clusters  <dig> and  <dig>  thus, while differences in global structure can in principle influence motif patterns, local structural features appear to be largely independent.figure  <dig> global consensus and local motifs.
a. plot of the k-mer percentile ranks , for each dimer and trimer of every cluster, with the cluster’s consensus values on the y-axis and the cluster’s average sequence values on the x-axis.
the small correlation indicates that consensuses only capture a small proportion  of the local motif information about the cluster’s members.
b. dimer profile  and consensus dendrograms  for clusters  <dig>   <dig>  and  <dig>  the dimer profile is similar between clusters  <dig> and  <dig>  while the consensuses differ dramatically.
c. consensus dendrograms of cluster  <dig> neurite sequences, trimer-constrained surrogates of the sequences, and length-constrained surrogates of the sequences.
average normalized alignment scores are provided given a set of sequences aligned to a single consensus.
dendrogram branch widths show parent bifurcation’s conservation.
motifs were similarly insufficient to consistently capture global features.
trimer-constrained surrogates of each cluster were aligned and consensuses generated.
some trimer-constrained surrogate consensuses were comparable to their real neurite consensus counterparts.
for instance, global alignment scores of cluster  <dig> neurite sequences aligned to the neurite consensus were not significantly different than the scores when aligned to the surrogate consensus.
however, in other cases, most notably cluster  <dig>  the trimer-constrained surrogates produced a far less representative consensus .
for comparison, length-constrained surrogates always failed to produce representative consensuses with alignment scores systematically below those achieved with trimer-constrained surrogate consensuses.
this means that generally motifs and consensuses have only limited impact on each other and they provide complementary information relating to local and global patterns, respectively.
discussion
the following discussion focuses specifically on sequence alignment.
more generally relevant issues of topological encoding are discussed in the companion article  <cit> .
biological interpretations and current limits of experimental data
axons are of particular interest due to their role in connecting neurons to enable network function.
given the diversity of cortical inhibitory interneurons in terms of axonal morphology  <cit> , it is not surprising that these cells would fall into different topological clusters.
perisomatic-targeting interneurons are responsible for generating synchronous network rhythms  <cit>  by densely synapsing on a large number of principal neurons.
the relative symmetry of perisomatic-targeting interneurons might then reflect a combination of dense synaptic fields along with growth mechanisms to ensure minimal path distance   <cit> .
shorter paths to targets would serve to optimize synchrony of the gabaergic signals from the interneuron.
it is interesting that a complementary subset of  interneurons would instead associate with neocortical pyramidal cells based on the topological sequences of the respective axonal arbors.
this does not mean that the two axonal classes have the same distribution of topological features, as they do not share the cluster space equally; however their co-clustering does suggest a substantial overlap in those features.
the relatively asymmetric branching of dendritic-targeting interneurons and mouse pyramidal cells suggests two possible non-exclusive explanations.
the first is that the two classes are similar in their spatial targeting, and distinct from that of perisomatic-targeting interneurons.
an alternative is that both classes are not as highly constrained in the timing of their efferent signals and thus wiring minimization is preferred over path minimization and its limiting effect on signal delay.
the spatial targeting explanation is consistent with the roles of pyramidal cells and dendritic targeting interneurons in network computation requiring a diverse synaptic distribution to generate more powerful networks  <cit> .
specifically, sparser postsynaptic targeting would yield greater differences between the connectivity profiles of principal neurons and thus increase network complexity, which may aid in computational functions such as pattern separation  <cit> .
the differentiation between mouse and rat pyramidal cell axons is not as clear from a biological perspective.
it is important to recognize, however, that most morphological data are derived from in vitro slice preparations, most often preventing the full reconstruct of axonal trees.
relative to dendrites, axons typically involve more expansive arbors and span well beyond the region explored in a given experiment.
given the size difference between mouse and rat brains, the impact of slicing on the reconstruction would be larger for rat axons.
to test this hypothesis, we compared artificially clipped mouse pyramidal axons to their rat counterparts.
our analysis suggests that morphological incompleteness due to sectioning artifacts is not the source of the difference between mouse and rat.
three pyramidal cell axons of various sizes , were selected among the few instances of in vivo  reconstructions, one from rat hippocampus and two from cat neocortex.
to simulate the effect of tissue slicing, these arbors were modified by eliminating all branches and sub-trees beyond a given distance in the z-dimension from the soma.
cutting at several distances showed a decrease in normalized alignment score, but even with a quarter of the z-range and less than 50% of the original sequence length, the scores always remained significantly greater  than length-matched random sequences.
other similarly severe cuts maintained much higher normalized scores.
this suggests that sequence analysis is relatively robust to reconstruction artifacts of this kind.
thus, brain size is not likely to explain the differences between rat and mouse axonal trees.
other experimental protocol details, or an unknown biased sampling of neocortical pyramidal neurons, may yet be responsible; however, it is also possible that mouse and rat pyramidal cell axons indeed slightly differ in their branching topology.
sequence alignment and expanded representations
the global sequence alignment modifications were necessary to ensure proper accounting of tree topology.
attempts to use standard global alignment  and a simpler clustering method revealed no meaningful differences among known neuron types.
this is because very different trees could have similar sequences if the structural attributes of bifurcations are disregarded.
for instance, three subsequences with distinct patterns, α, β, and γ, could be arranged in sequence as αβγ and matched to another sequence α’β’γ’ where α’ is a close match to α, β’ to β, and γ’ to γ. these two trees, however, could be arranged in very different ways: α as the parent of subtrees β and γ, and α’ as the parent of β’ and β’ as the parent of γ’.
thus, αβγ and α’β’γ’ would match well despite substantially different tree structures.
in contrast, the modified global alignment algorithm implemented in pasta distinguishes the two cases.
expanded representations including branch-level morphological features could enhance alignment sensitivity, decreasing the likelihood of spurious alignment for shorter sequences.
for instance, several characters could be used for each topological node type to encode the bifurcation angles  relative to the population distribution.
the increased sequence complexity would alleviate the need for a gap opening cost, allowing a greater range for parameter tuning.
additionally, such encodings would enable analyses for relating local topological patterns with other morphological features.
subtree size and tortuosity are similarly reliable branch metrics which could be encoded; distance from soma and maximum distance to termination are also suitable candidates.
diameter and associated metrics , while possible in principle, are more susceptible to experimental protocols  <cit> .
combining several morphological attributes in the encoding would multiply the number of characters required, but feature vectors could be used rather than characters, increasing sensitivity at the expense of speed.
alternatively, the number of features and their discretization could be judiciously selected based on the specific research questions.
leveraging pairwise tree alignment, cluster analysis, and multiple sequence alignment, an expanded encoding could help discover novel relationships between morphological features, including their relative conservation and specificity across neuronal classes.
for instance, the different tortuosity among interneuron classes  <cit>  could reveal regional differences within the arbor, which would suggest axonal domains with specific targeting features.
the level of conservation would provide an indication of the feature’s functional importance as well as provide a constraint for modeling growth mechanisms.
since morphology ultimately depends on ultrastructural features to produce function, lower-scale branch properties such as spines or bouton densities and even local molecular expression could create powerful analyses.
this would require a richer data type and new experimental processes, but with recent technologies the prospect is real  <cit> .
combining biophysical data with pairwise alignment would enable exploration and detection of morphological-physiological relationships, such as spike failures near regions of high bifurcation density, or receptors of neurotrophic factors in sequences with many c nodes.
spatial information, such as the cortical layer or brain region in which a branch is located, could also be encoded, allowing for explicit alignment by anatomical domain.
while we found no association between axonal consensuses and spatial location relative to the soma , such associations may be anticipated with apical dendrites and more complete axonal reconstructions spanning multiple brain regions, and spatial encoding would facilitate such discoveries.
the code available at http://krasnow <dig> gmu.edu/cn3/neuritesequence/ includes sample expanded branch feature encoding to enable future exploration by the research community.
an extended encoding could also improve classification.
while we showed that the alignment space is at least as informative as standard topological metrics, whole-neurite metrics  and branch level features such as length and tortuosity are also useful for classification.
for a discussion of which morphometrics are effective for neuronal classification, see  <cit> .
a feature matrix composed of alignment space dimensions and morphometrics would allow for classification on both.
in cases in which classes are similar in terms of average branch level metric but different in their relation to topology, the extended encoding has the potential to be more powerful than simply adding branch level metric distributions to the feature matrix.
an optimized multi-stage classification which aligns only neurites similar by standard morphometrics could deliver an improved classifier with only a modest increase in alignment computation.
optimizing algorithms and analysis
the sequence approach depends critically on the constraint that small-side subtrees necessarily be matched to other smaller-side subtrees.
this condition produces near-optimal results  with moderately to highly asymmetric trees, which have low probabilities of improved tree-alignment from a larger-side subtree aligned to a smaller-side subtree.
the scores are near optimal even in the case of trees with greater symmetry, so long as the subtrees are topologically similar.
this assumption is generally true of neurites, which explains its effectiveness in this study.
however, it is possible to conceive a “worst-case scenario” of a root bifurcating into two large subtrees with exactly the same number of branches, but one fully symmetric and one fully asymmetric.
aligning the corresponding sequence with an almost identical arbor in which a single branch is added to the symmetric side  would yield a dismally low score despite the great structural similarity between the two trees.
to gauge the risk incidence of this effect in neurites, we assessed the asymmetry characteristics of bifurcations with similar subtree sizes, specifically, those with a difference of no more than  <dig> bifurcations.
of the 5% of axon, 26% of apical dendrite, and 36% of dendrite bifurcations satisfying the condition, the median difference in asymmetry was  <dig> , with 75% having a difference less than  <dig>  , though the differences were much smaller for the 5% of subtrees with more than  <dig> bifurcations.
this survey suggests that only dendrites might be susceptible to this problem, though with reasonably small impacts for each instance.
thus, based on currently available data, the relatively simple topological encoding results in practically robust sequence alignments however, the possibility that future larger dataset of complete axonal reconstructions will require a more optimal alignment method cannot be ruled out.
in the big-data prospect of orders-of-magnitude increase in neurite dataset size, heuristics will become important for efficient processing.
given that mds does not require distances for every neurite pair, not all pairwise combinations are necessary for producing an alignment space.
moreover, for search or analysis, topological metrics can be used to limit the number of neurite alignments by filtering out those that would likely score poorly, as achieved by blastneuron with a broader range of morphometrics  <cit> .
the pasta algorithm itself can be sped up by ignoring the possibilities least likely to contribute to an optimal alignment .
other heuristic approaches could be applied that involve candidate seed locations of short matching strings from which the alignment is extended in either direction  <cit> .
the most efficient modern algorithms index seeds in advance  <cit> .
a larger dataset of more complete axons, widely expected from ongoing and discussed connectomic projects, would require appropriate heuristics and efficient implementation in a compiled language, such as c or c++.
in cases where sensitivity is more important than speed, sequences of branch feature vectors could take the place of discrete characters.
the diversity of available gene sequence alignment tools highlights the utility of specific parameters and alternative algorithms for different experimental questions or computational requirements  <cit> .
methods of neurite pairwise alignment of one sort or another, including variations on our method, will likely grow in a similar manner to fill various niches, whether in terms of sensitivity or efficiency.
CONCLUSIONS
the newly developed method for aligning binary tree sequences enabled the comparison of large numbers of neurites and revealed their shared topological features.
sequence alignment similarity with a purely topological encoding was sufficient to distinguish different arbor types  as well as certain neuron types, brain regions, and species.
moreover, the sequence representations could differentiate cell classes better than  traditional morphometrics and are consistently as informative as traditional topological metrics.
cluster analysis produced groupings highly associated with known metadata differences, and multiple sequence alignment generated a consensus representation of each cluster that revealed the common topological features.
comparative analysis between consensus and motif profile demonstrated that these analyses captured complementary topological characteristics, with consensuses reliably extracting global features and motifs effectively quantifying local features.
additional file
additional file 1:
this file provides additional methodological information regarding  alignment score baselines and distance normalization,  non-metric multidimensional scaling,  model-based clustering,  cluster-metadata associations, and  classification.
it additionally includes four supplementary figures referenced in the main text.
competing interests
the authors declare that they have no competing interests.
authors’ contributions
tag and gaa developed the methods and designed the research.
tag implemented the methods, carried out the analyses, and drafted the manuscript.
ph contributed to the design and implementation of the sequence alignment algorithms and provided input on the manuscript.
gaa guided the study and edited the manuscript.
all authors read and approved the final manuscript.

 neuronal morphology has been an important research topic due to its relevance to neuron growth, electrophysiology, classification, connectivity, and pathology. in recent years the availability of morphological data has dramatically increased across a broad set of species, cell types, and conditions thanks in part to search and curation efforts of neuromorpho.org. meanwhile, new staining, imaging, and reconstruction technologies are producing orders of magnitude more data from animal models in projects such as flycircuit and flylight. ongoing advancements are continuously improving automated reconstruction and groundbreaking large scale endeavors such as the brain initiative are expected to expand the amount of data from mammalian organisms by additional fold factors. importantly, these large datasets provide opportunity to validate universal morphological characteristics as well as to discover or test features and relationships of specific neuron types. drawing inspiration from the field of genomics, where the human genome project ushered in an analogous flood of data, a variety of new methods are being developed to enable search and analysis of the growing pool of morphological data. historically, most metrics devised for morphological analysis have focused at the whole neuron level or averaged across branches, with some derived methods quantifying a feature as a function of distance from the soma. pairwise comparisons have greater potential to detect fine structural distinctions, making them appropriate for search, curation, classification, and exploration of prototypical features. recently several studies have used pairwise comparisons in morphological analysis. pairwise sequence alignment of neurite path directional vectors helped determine the unique neuroblast lineage of larval drosophila neurons. the nblast algorithm leveraged a form of vector comparison, with nearest edges in two neuron images aligned and measured by their tangent vectors and spatial distance. thus, anatomical position and overall shape were applied for search, clustering, and classification to a database of over drosophila neurons. the path2path algorithm compares neurons by assigning every path, from root to tip, of one neuron to the other. the distance is given by the deformation of the paths, modulated by the difference in topological hierarchy of points along the paths. an extension of the elastic shape analysis framework captures the difference between trees based on path shape and topology, as well as bifurcation locations and angles. this method can also generate a representative “mean shape”, though the examples primarily represent common path features. blastneuron, the most recent entry into the field, focuses on aligning branches both by topology and path shape via dynamic programming after first searching for similar neurons on the basis of morphometrics. in addition to providing an efficient approach for search in large databases, the alignment component could prove useful in detecting and pinpointing differences between related neurons and between reconstructions of the same neuron produced by multiple algorithms, enabling error correction and even synthesis of those algorithms. the tree edit distance compares the topology of two trees by determining the minimum sequence of edit operations required to transform one tree into another. specifically, each branch of two trees is aligned to a branch in the other tree or labeled as an insertion. branch features such as length, volume, surface, and bifurcation angle can be represented; in this case an edit cost based on their differences is applied for each branch assignment. the ted has been used on tree structures in multiple fields and constitutes the most related algorithm to what we present here. we present an original strategy to evaluate alignment of topology distinctly from other branch features across a broad range of neuronal classes. our method exploits the novel encoding of neuron trees as sequences of characters representing bifurcations presented in the preceding companion paper. we align the resulting strings with a custom-developed python package introduced here: pattern analysis via sequence-based tree alignment. we used model-based cluster analysis on alignment scores to group similar neurites. furthermore, we generated a consensus representation of clustered neurites by multiple sequence alignment revealing the conserved structural features of the corresponding trees. sufficiently large neuron classes, well-defined by available metadata, were compared to the clusters to determine whether those classes are topologically distinct and, if so, what their defining global features are. each arbor type of axons, dendrites, and pyramidal cell apical dendrites showed clear topology alignment clusters with distinctly conserved features. moreover, we show that multiple alignment consensuses and motif analysis provide complementary levels of analysis of neurite topology. as an immediate application, the pasta tool also enabled detection of previously unidentified duplicate reconstructions in the neuromorpho.org database; this important curation step will be incorporated in the regular data processing pipeline of this repository. at the same time, the approach is extensible to more complex representations as required by the research goal. methods sequences are generated from neuronal trees as presented in the companion paper: each branch is encoded as an a, c, or t depending on whether its child branches both bifurcate, bifurcate and terminate, or both terminate. a depth-first traversal keeps child branches relatively near to parent branches in the sequence representation, and traversing the smaller subtree before the larger further preserves that proximity. this choice also allows for a more intuitive description of changes to a tree structure.figure pairwise global sequence alignment. a. changes in tree structure are reflected in sequence representation. when a side-branch is lost from a non-t node or a t-node with a c parent, a c node is removed from the sequence. when a branch is lost from a t node with an a parent, the t is removed and the parent a becomes a c. b. two tree-derived sequences are aligned by matching characters and placing gaps when an alignment cannot be made. c nodes or entire subtrees are gapped, from an a to its associated t. the a at the front of a gap region can be matched to a c. matches count as point, gaps count as - point, and openings of a gap region count as - points. alignment scores are normalized and converted into distance values. c. sample apical dendrite morphologies of hippocampal ca and ca pyramidal cells and their topology dendrograms illustrate alignments between neurites of the same sub-region along with normalized distances for all pairs. raw alignment scores are also provided for within-class alignments. inset: within- and between-group distributions of normalized distances indicate that the pyramidal apical dendrites are topologically more similar to apical dendrites of their own group than to those in the other group. custom sequence alignment algorithms were developed for tree-derived sequences given their particular structural features. a global alignment algorithm was developed with specialized character types and alignment rules associated with bifurcation types. the scores produced by this method were normalized by size and a random-tree baseline prior to analysis. a multiple sequence alignment algorithm was also custom-adapted for tree-sequences from the genomics global and multiple alignment techniques. other well-established data manipulation and analysis methods utilized in this work are briefly described as well, such as the creation of a metric space from alignments for further analysis including classification and model-based clustering. clusters are then statistically analyzed for associations with known cell groups. this methods section also describes the dataset used in this study and related selection criteria. all code developed for this study, including tree and sequence generation, sequence alignment, and analysis, is available open source at http://krasnow gmu.edu/cn3/neuritesequence/. global tree-sequence alignment powerful bioinformatics approaches exist for comparing gene sequences to each other to determine similarity and derive evolutionary relationships. a gene may mutate by conversion of one base pair to another, the introduction of a new base, or the elimination of a base. analogous operations allow the comparison of neuronal trees: the modification of branch properties, outgrowth of new branches, and branch retraction. while neuronal trees do not explicitly share an ancestry or phylogenetic relationship typical of nucleotide sequences, they do share growth programs based on neuron type and associated genetic expression. from a functional perspective, neuronal branches have properties that impact charge transfer, signal integration, and space occupancy. the assembly plan of these features may indicate growth rules and functional attributes of the neuronal arbor as a whole. given the described encoding scheme, the growth of a single neurite branch results in one of two possible sequence edits, with branch retraction expectedly producing the opposite edit in either case. growth prior to a bifurcation, or on the child branches of a t bifurcation, yields the insertion of a c. growth on the terminal branch of a c bifurcation, however, will turn the c into an a bifurcation and insert a t. conversely, the retraction of a t’s terminal branch deletes the t and turns the parent a into a c. if the t’s parent is a c, then the retraction effectively deletes the c. a sequence traversed by the smaller subtree first ensures that the t insertion/deletion occurs adjacent to the a/c conversion. the global alignment of topological sequences is modified from the needleman-wunsch algorithm to account for the branching structure of binary trees, with alignment rules associated with bifurcation types. the algorithm involves a matrix created from the character positions of the two sequences being aligned running along either axis. scores are calculated from the beginning of both sequences to the end of both sequences using previously calculated position alignments. the best score from the three possible steps to a given position is assigned to each position in the matrix. those steps include a match between the characters, a gap over the character of the first sequence, or a gap over the character of the second sequence. the alignment score is given in the final position and a back-trace of the optimal route from the final position to the start position produces the alignment. the tree-based sequence modifications correspond to the a, c, and t bifurcation node types, allowing for a representation that includes branch properties in addition to local topology. it also assumes that each sequence is a single complete tree. limitations are placed both on matching and gapping based on node type in order to ensure consistent alignment with a valid tree structure. only pairs of characters of the same type are directly matched in the dynamic programming process. a-type characters cannot be explicitly gapped. although this can result in inaccessible positions during back-trace, a valid back-trace will always exist as long as each sequence is a complete tree. c-type characters can be gapped normally. t-type characters can be gapped, but the gap must extend up to the associated a node. in terms of tree structure, the t node would be the last traversed node on the a node’s smaller subtree. this within-sequence a-t relationship is defined in a recursive manner such that a t node’s associated a node is the nearest prior a node that does not have its own nearer subsequent t node. while an entire subtree can be eliminated by gapping all characters from a to t, it is also possible for all but a single branch to be eliminated, leaving a single c node. thus, when gapping a t node and its associated subtree, if the character in the opposing sequence position is a c, the gap region can end such that the a and c are matched. the final t node of any sequence will have no matching a and cannot be gapped. this would effectively lead all tree-sequences to align on the final t node making certain alignments impossible, such as a smaller tree aligning to an inner subtree of a larger tree. two final modifications fix this problem. first, a nodes can be gapped prior to any matches. second, the final t node of either sequence can gap back to another t node that has a match. alignment scores are given by the number of matching positions minus the number of gaps. an additional penalty of − is applied for each region of consecutive gaps. this cost helps distinguish more closely related sequences and reduces the otherwise high probability of a perfect score for a pair of sequences of very different lengths. perfect scores are problematic as they produce distance values of making alignment-space embedding impossible. alternative gap opening costs were tried with no meaningful impact on the results reported here; however, tuning this parameter might help optimize future analyses depending on the specific questions of interest. non-unitary gap costs have no impact due to all matches adding the same amount to the score. in order to focus on topological structure differences and not tree size differences, we normalized scores by sequence length. specifically, a per-character score is computed and normalized against a length-pair matched random tree alignment baseline prior to analysis. the normalized alignment score of a pair of trees is then converted to distance by subtracting it from the maximum possible score. spatial embedding and classification in order to investigate the pairwise relationships among neuronal tree sequences, neurites were embedded in a multidimensional space consistent with alignment distances using multidimensional scaling. while edit distances would allow for standard mds, the triangle inequality does not hold for tree alignment scores or our normalized distances, thus a non-metric version was employed. instead of producing a space that preserves the original distance values in the embedded space, non-metric mds seeks to preserve the relative proximity of the data elements. in other words, neurites that are closer to each other than to a third item in the space have that same relationship in the original data. the embedded data were subjected to cluster analysis to determine whether different neuron classes can be distinguished in terms of their topological sequences. a wide variety of clustering methods exist, including agglomerative clustering, k-means clustering, and model-based clustering. agglomerative clustering, including ward’s method, can be run directly with distance values, obviating the need for mds, but top level clusters are less stable than in other methods and visualization is limited. k-means assumes that the clusters are spherical and approximately of the same size, but neither of those assumptions is sound with regards to the diverse population of neurite shapes. model-based clustering was chosen due to its ability to test a variety of potentially optimal model types based upon the structure of the dataset. we used this approach to fit multivariate gaussians with parameters for size, shape, and correlation between dimensions while varying the number of clusters. the simplest model with the greatest likelihood was selected using the bayesian information criterion. associations between clusters and known neuron classes were quantified by the relative representation of a given metadata group within a cluster and vice versa using the bonferroni-corrected χ test. to determine whether the alignment space captured the same or additional information relative to that of standard topological metrics, we compared the corresponding abilities to correctly identify known neuron types using unsupervised and supervised classification. model-based clustering is unsupervised and was restricted to two clusters for the purposes of classification. linear discriminant analysis is a supervised approach that produces a trained classifier based on a subset of the data. by applying each method with different numbers of variables, an optimal classifier can be produced with the most informative variables identified. classification accuracy was computed as the proportion of neurites in the appropriate class. clustering performance was further measured by the adjusted rand index. an ari score of indicates perfect cluster partitions along known classification, while a score of indicates random partitioning of the neurites. the metrics tested were number of bifurcations, maximum branch order, average partition asymmetry, and caulescence. multiple sequence alignment the multiple sequence alignment process involves several steps: the creation of a composite allowing for registration of the multiple alignment, multiple alignment of all sequences to the composite, generation of a position-specific scoring matrix based on the prior msa, iteration until the msa is stable, and finally thresholding to extract a consensus sequence. the composite is initially formed by aligning one sequence to another and then creating a sequence out of the alignment. positions in which a gap exists are filled with the character on the non-gapped side of the alignment, and matches of a and c nodes take the a type. this process is repeated with the growing composite now being aligned to each sequence in the set one at a time. the multiple alignment is formed by aligning every sequence to the complete composite in the same manner as was used in the pairwise global sequence alignment. this process identifies the sequence co-alignment positions without requiring an explicit score, thus no penalty is needed for initiating a gap region. since the initial multiple alignment could be suboptimal, a pssm is generated with the positions defined by the composite and the scores defined by the number of sequences aligned at each position. the multiple alignment is run again using the pssm, the process iterating until stability is reached or the thresholded consensus fails to increase in size or average conservation. final consensuses can be determined for any given minimum conservation threshold. higher thresholds produce shorter consensuses with higher average conservation and vice versa. a threshold of 50% was used for all msa in this paper. in msa columns containing both a and c nodes, the consensus value is an a if at least 50% of the sequences contain an a, and a c if at least 50% of the sequences contain either. the a node’s associated t will have the same count, and thus will be contained in the consensus if and only if the a is. this ensures that the consensus represents a single complete tree. neuromorpho.org dataset the dataset used in this research is the same as in the companion motif analysis, drawing from neuromorpho.org version. briefly, it was composed of all unique neurons of the control, non-cultured condition, except for pyramidal neurons without distinct apical/basal trees. axons, dendrites, and pyramidal apical dendrites were treated separately, with dendrites having any terminal branches smaller than microns removed to avoid confusing likely spines for dendrites. neurites with fewer than bifurcations were eliminated to ensure sufficient complexity and reduce the probability of unrelated neurites achieving high similarity by chance. a total of neurites were analyzed, including axons, dendrites, and pyramidal apical dendrites.  using the separated arbors of neurons from the neuromorpho.org database, each neurite was encoded as a sequence, aligned with every other sequence in the dataset, and the scores normalized and converted into distances. inspection of normalized distances from hippocampal ca and ca apical dendrites, two groups known to have distinct topologies, showed greater distances between sequences from different groups than from within the same group. this verifies that the tree-sensitive alignment of neurite sequences can distinguish different neurite classes. while the distributions of within- and between-class distances overlap considerably, they are clearly more distinct than those generated using average partition asymmetry, which has previously been shown to distinguish ca and ca pyramidal apical dendrites. we next undertook an unsupervised cluster analysis to identify groups of neurites for inspection of topological features. topology alignment space an abstract sequence alignment space of neural trees was generated for the purposes of analyzing topological relationships between neurite types. the calculated distances were used to embed neurites into a feature space, hereon referred to as alignment space, using non-metric multidimensional scaling. eight dimensions were sufficient for the entire dataset, with the first four showing clear structure in terms of density distribution. the spaces produced for each data subset are highly similar in the dominant first few dimensions which capture most of the original distance relationships. while the space is an abstraction, roughly speaking the top dimensions are mainly a function of the number of bifurcations and asymmetry. the first effect may initially seem counterintuitive since the number of bifurcations was explicitly controlled for; however, it is in fact consistent with the observation that dendritic branch type composition depends on tree size. at any rate, the correspondence between alignment dimensions and topological features is far from exact. within a restricted region of the alignment space, moving in a set direction will result in trees with increasing or decreasing richness in some structural elements; over broader spans of the abstract space, however, the directional gradient of different elements will typically vary.figure alignment space and clustering. a. the log density plot of all neurite-derived sequences on the first two dimensions of alignment space suggests differentiable groups. b. clustering of the alignment space reveals four clusters associated with dendrites, two associated with axons, and one associated with apical dendrites; most neurites grouped with the cluster associated to their arbor types, but some classified with another cluster. ellipses reflect the covariance matrices of the cluster models. c. sub-clustering of apical dendrites yields additional spherical clusters that associate with neocortex, hippocampal ca, and hippocampal ca. apical dendrites improperly classified have lower color intensity. d. unsupervised model-based clustering of the alignment space classifies ca and ca apical dendrites with an adjusted rand index of. a trained linear discriminant analysis achieves 94% accuracy. the density distribution of the alignment space suggests groupings of neurites that are more related to each other than they are to other groups of neurites. model-based clustering methods were applied to choose the best model and the optimal number of clusters, and then to detect the clusters. clusters take the form of multivariate gaussians with defined size, shape, and orientation, where parameters may be the same for all clusters or unique for each. analyzing all neurites in the dataset yielded seven clusters with all parameters specified and distinct. of those, four were solely associated with dendrites, one with axons, one with pyramidal apical dendrites, and one principally with axons but also significantly with apical dendrites. this is consistent with the greater number and diversity of dendrites in the neuromorpho.org dataset. accuracy was 80% for dendrites, 65% for axons, and 54% for apical dendrites due to the significant overlap with one of the axon clusters. each arbor type was also analyzed separately to identify potential sub-clusters and related associations with known metadata. in the case of apical dendrites, the resulting three sub-clusters clearly associated with brain regions, specifically neocortex, hippocampal ca and hippocampal ca. this result highlights the importance of clustering subsets, particularly when there is a bias in proportions of available data. in some cases differences may exist but be too small relative to topological variability or have too small of a sample size to detect. classification and comparison to morphometrics in order to determine how well, relative to morphometrics, alignment space can distinguish neurites of different types, we used both model-based clustering and linear discriminant analysis to classify neurites. in the case of ca and ca hippocampal apical dendrites, the optimal set of alignment space dimensions performed better than the optimal principal components of topological metrics using both methods. the clustering approach produced an accuracy of 92% using alignment space compared to 91% using the principal components of the topological metrics. alignment space performed even better using lda, producing an accuracy of 94% compared to 89% with topological metrics. in the case of drosophila olfactory axons and mouse cortical pyramidal axons, alignment space also produced better classification scores than topological morphometrics using both methods. of nine other neuronal class pairs that were at least minimally separated, the alignment space performed as well as or better than topological metrics in out of cases. these results show that, while topological metrics generally provide a robust characterization of neuronal classes, the additional detail captured by the sequence representation and alignment is sufficient to improve classification for some known classes. for the explicit purposes of classification, supplementary morphometrics are certainly called for; however, expanded sequence representation and pairwise alignment incorporating non-topological branch features have the potential to be more effective than those features summed or averaged across the neuron. dendrite and axon clusters we next looked at how dendrites sub-clustered by topological alignment. dendrites, which make up the largest arbor type subset of the data, fell into clusters with gaussians of varying cluster size, shape, and orientation. four alignment dimensions were required to distinguish those clusters. upon considering dendrite classes with sufficient specificity and size, seven classes showed highly significant association with one or more clusters. the dendrite clusters clearly separated cortical neurons from sensory neurons of several different species. the only class that reciprocally associated with only one cluster consisted of primate neocortical pyramidal basal dendrites. rodent neocortical pyramidal basal dendrites alone associated with cluster and jointly with rodent neocortical interneuron dendrites in cluster clusters 4– associated with sensory and motor neurons. motoneurons, primarily from cat, rat, and mouse, as well as rodent retinal ganglion cells, associated with cluster the rodent retinal ganglion cells associated most significantly with cluster along with adult fly tangential cells and larval fly sensory cells. the latter two groups also associated with cluster thus, the three types of sensory neurons co-clustered, suggesting that topological features are shared by neurons which respond directly to the external environment. tree size clearly distinguishes some of the clusters exemplified in some sample dendrites from each group, but differences in the number and distribution of major branches are also evident.figure dendrite clusters. a. clusters of dendrites are shown in two perspectives of alignment space. each perspective highlights dendrites in three of the six clusters, with dendrites in the other three shown in gray. b. the association matrix of the clusters and seven groups defined by metadata combination of species, region, cell type, and age range. the number of dendrites in each group and cluster are shown in parentheses. values reflect the natural log of the contingency matrix p-values, with absolute values above being significant. dark gray cells represent cases in which significantly fewer dendrites satisfy the cluster/group association than expected given the marginals. positive values in colored cells represent cases in which more dendrites fall into the cell than expected. darker colors signify that an example morphology and dendrogram is provided in c. axons, though with far fewer total reconstructions and representing fewer metadata groups, tend to be larger and so have the potential to separate more clearly. perhaps due to their relatively limited diversity, axons exhibited structure in just two dimensions and fell into clusters. nevertheless, the clusters had strong associations with metadata groups, specifically separating insects from mammals, pyramidal cells from different rodent species, and distinct interneuron types. the fly olfactory neuron axons most clearly associated with cluster and are substantially dissociated from clusters and rat neocortical pyramidal axons associated with cluster while mouse neocortical pyramidal axons associated with cluster this result should be interpreted with caution since the larger axons of rat neurons may be more prone to slicing artifacts. since the specific histological and imaging procedures can also affect the reconstructions, it is important to note that the mouse pyramidal axons primarily come from a single archive while the rat data have substantial contributions from four different laboratories. rodent neocortical dendritic targeting interneurons also associated with cluster though not as strongly. rodent neocortical perisomatic targeting interneurons associated with cluster representative morphologies and dendrograms suggest features which are shared within or even define each cluster. derivation of consensus representations and the qualitative and quantitative description of those features follow.figure axon clusters. a. axons fall into four spherical clusters of varying sizes. colored dots correspond to axons classified with the cluster associated with the matching metadata group. diamonds represent rodent cortical dendritic-targeting interneurons. circles are defined by the covariance matrix of their cluster model with a radius of one standard deviation. b. association matrix for axon metadata groups and clusters. colored and dark gray cells show significantly positive and negative associations, respectively, with the number of axons in each group and cluster in parentheses. c. representative morphologies and dendrograms are shown for each significantly positive association. multiple sequence alignment and consensuses multiple sequence alignment provides the means for extracting common structural features of a group of neurite sequences and measuring their level of conservation. msa can be visualized as vertical densities illustrating how represented various positions are. a consensus structure can be defined by setting a threshold for the proportion of member sequences aligned at each position. a low threshold will result in a relatively larger consensus with lower average conservation across member sequences. this choice tends to reveal common local patterns, though in the extreme, motif analysis could be more effective for that purpose. higher thresholds, in contrast, reveal the common global pattern by producing narrower consensuses with higher average conservation. a 50% threshold was found to yield consistently clear results across clusters. in general, the relative consensus length and average conservation together provide a measure of how inter-related the sequences in a set are in terms of shared topological features. for a measure of global representativeness that accounts for the sequence length variability, we also employed the normalized pairwise alignment score.figure multiple sequence alignment and consensuses. a. sequences of axonal cluster are aligned. a section of the alignment is magnified along with the composite and consensus. a single neurite in the cluster and its sequence in the msa is highlighted. b, d. consensuses of axon clusters and in sequence and dendrogram form, with relative length and average conservation statistics. dendrogram branch width indicates conservation of the parent bifurcation. branch length indicates variability preceding a bifurcation, calculated as the average proportion of a sequence falling between conserved bifurcations. c, e. example morphologies and dendrograms of cluster and. colored segments indicate an alignment with the consensus at the bifurcation. black and gray segments indicate consensus bifurcations not found in the neurite and vice versa. we take for comparison axon clusters and which are next to each other in alignment space but display considerably different consensus features. in order to focus on the most representative trees of each cluster, we only considered those sequences within one standard deviation of their cluster centers. furthermore, to avoid any potential effect of number of sequences on the msa, the sequences closest to their respective cluster centers were used for msa and subsequent analysis. the consensus of cluster has an absolute length of a relative length of %, and an average conservation of %. the consensus of cluster has a substantially longer absolute length of but a smaller relative length of % due to the larger median sequence length relative to cluster. the cluster consensus also has a higher average conservation of %, meaning that while cluster has a higher proportion of well-aligned branches, the well-aligned branches of cluster are more densely represented in the cluster sequences. these properties are in part explained by the different variability of sequence length between the two clusters. if the higher variability of a cluster is due in part to a larger number of relatively short sequences, fewer bifurcations overall could align in the consensus. longer sequences may be more likely to contribute to the consensus but will also align in many positions that do not pass the consensus threshold. cluster sequences have an average length of, median of, and standard deviation of; in contrast, cluster sequences have an average length of a median of and a standard deviation of. the impact of this variability is seen in the branch lengths of the consensus dendrogram. however, alignment scores normalized to z-scores, show the same relationship with cluster having a score of  ±  compared to the cluster average of  ± . this is consistent with the larger gaussian model which was fit to cluster indicating the looser relationship between its sequences. the consensus dendrogram of cluster shows where a substantial portion of the variability falls. the root branch is particularly long, meaning that a relatively large proportion of parts of member sequences exist prior to that bifurcation. sample axons from the cluster illustrate the alignment of the axons and consensus in full context. consensus structural details also differ substantially between clusters and consensus has greater symmetry: in fact, consensus has a maximum branch order of compared to for cluster even though cluster has more bifurcations. the axons of cluster show a greater average asymmetry of compared to cluster axons asymmetry of. other structural differences could relate to differential spatial targeting of these classes. although the arbors from the two clusters showed similar spatial arrangements, their total neurite length differed significantly. cluster had a median length of  μm and cluster a median of  μm. although many of the larger neurons in the clusters were not from the associated cell classes, the trend was consistent. pyramidal axons, with a median length of  μm, were shorter than dendritic targeting interneurons, with a median length of  μm. perisomatic targeting interneurons, with a median of  μm were yet longer. the greater length in spite of similar spatial arrangement suggests a greater density or some alternative heterogeneous distribution of branches for cluster axons. consensuses and motifs we next considered whether the consensus is representative of local motifs patterns, and whether motifs capture the global features of the consensus. trimer-constrained surrogate sets were generated for each axon cluster consensus and for each individual axon sequence in order to produce motif profiles for comparison with the motif profiles of each cluster’s sequences. briefly, random trees were generated with just size, size and node-type proportions, and size and dimer proportions equivalent to each consensus. for a given consensus or axon sequence, node-type, dimer, and trimer proportions were then normalized to the respective proportions in the surrogate sets by determining the percentile rank of a given consensus k-mer proportion within the surrogate set’s k-mer proportion distribution. the correlation between the motif patterns in the neurite sequences and their corresponding consensuses was small across the axonal clusters, with the consensus values varying substantially more than the cluster averages. moreover, while clusters and had very similar motif profiles, with only minor differences in dimers at, cc, ac, and ct, their consensuses differed dramatically. for further comparison, cluster 3’s values are very different from clusters and falling much closer to baseline, while the global consensus appears intermediate between those of clusters and thus, while differences in global structure can in principle influence motif patterns, local structural features appear to be largely independent.figure global consensus and local motifs. a. plot of the k-mer percentile ranks, for each dimer and trimer of every cluster, with the cluster’s consensus values on the y-axis and the cluster’s average sequence values on the x-axis. the small correlation indicates that consensuses only capture a small proportion of the local motif information about the cluster’s members. b. dimer profile and consensus dendrograms for clusters and the dimer profile is similar between clusters and while the consensuses differ dramatically. c. consensus dendrograms of cluster neurite sequences, trimer-constrained surrogates of the sequences, and length-constrained surrogates of the sequences. average normalized alignment scores are provided given a set of sequences aligned to a single consensus. dendrogram branch widths show parent bifurcation’s conservation. motifs were similarly insufficient to consistently capture global features. trimer-constrained surrogates of each cluster were aligned and consensuses generated. some trimer-constrained surrogate consensuses were comparable to their real neurite consensus counterparts. for instance, global alignment scores of cluster neurite sequences aligned to the neurite consensus were not significantly different than the scores when aligned to the surrogate consensus. however, in other cases, most notably cluster the trimer-constrained surrogates produced a far less representative consensus. for comparison, length-constrained surrogates always failed to produce representative consensuses with alignment scores systematically below those achieved with trimer-constrained surrogate consensuses. this means that generally motifs and consensuses have only limited impact on each other and they provide complementary information relating to local and global patterns, respectively. discussion the following discussion focuses specifically on sequence alignment. more generally relevant issues of topological encoding are discussed in the companion article. biological interpretations and current limits of experimental data axons are of particular interest due to their role in connecting neurons to enable network function. given the diversity of cortical inhibitory interneurons in terms of axonal morphology, it is not surprising that these cells would fall into different topological clusters. perisomatic-targeting interneurons are responsible for generating synchronous network rhythms by densely synapsing on a large number of principal neurons. the relative symmetry of perisomatic-targeting interneurons might then reflect a combination of dense synaptic fields along with growth mechanisms to ensure minimal path distance. shorter paths to targets would serve to optimize synchrony of the gabaergic signals from the interneuron. it is interesting that a complementary subset of interneurons would instead associate with neocortical pyramidal cells based on the topological sequences of the respective axonal arbors. this does not mean that the two axonal classes have the same distribution of topological features, as they do not share the cluster space equally; however their co-clustering does suggest a substantial overlap in those features. the relatively asymmetric branching of dendritic-targeting interneurons and mouse pyramidal cells suggests two possible non-exclusive explanations. the first is that the two classes are similar in their spatial targeting, and distinct from that of perisomatic-targeting interneurons. an alternative is that both classes are not as highly constrained in the timing of their efferent signals and thus wiring minimization is preferred over path minimization and its limiting effect on signal delay. the spatial targeting explanation is consistent with the roles of pyramidal cells and dendritic targeting interneurons in network computation requiring a diverse synaptic distribution to generate more powerful networks. specifically, sparser postsynaptic targeting would yield greater differences between the connectivity profiles of principal neurons and thus increase network complexity, which may aid in computational functions such as pattern separation. the differentiation between mouse and rat pyramidal cell axons is not as clear from a biological perspective. it is important to recognize, however, that most morphological data are derived from in vitro slice preparations, most often preventing the full reconstruct of axonal trees. relative to dendrites, axons typically involve more expansive arbors and span well beyond the region explored in a given experiment. given the size difference between mouse and rat brains, the impact of slicing on the reconstruction would be larger for rat axons. to test this hypothesis, we compared artificially clipped mouse pyramidal axons to their rat counterparts. our analysis suggests that morphological incompleteness due to sectioning artifacts is not the source of the difference between mouse and rat. three pyramidal cell axons of various sizes, were selected among the few instances of in vivo reconstructions, one from rat hippocampus and two from cat neocortex. to simulate the effect of tissue slicing, these arbors were modified by eliminating all branches and sub-trees beyond a given distance in the z-dimension from the soma. cutting at several distances showed a decrease in normalized alignment score, but even with a quarter of the z-range and less than 50% of the original sequence length, the scores always remained significantly greater than length-matched random sequences. other similarly severe cuts maintained much higher normalized scores. this suggests that sequence analysis is relatively robust to reconstruction artifacts of this kind. thus, brain size is not likely to explain the differences between rat and mouse axonal trees. other experimental protocol details, or an unknown biased sampling of neocortical pyramidal neurons, may yet be responsible; however, it is also possible that mouse and rat pyramidal cell axons indeed slightly differ in their branching topology. sequence alignment and expanded representations the global sequence alignment modifications were necessary to ensure proper accounting of tree topology. attempts to use standard global alignment and a simpler clustering method revealed no meaningful differences among known neuron types. this is because very different trees could have similar sequences if the structural attributes of bifurcations are disregarded. for instance, three subsequences with distinct patterns, α, β, and γ, could be arranged in sequence as αβγ and matched to another sequence α’β’γ’ where α’ is a close match to α, β’ to β, and γ’ to γ. these two trees, however, could be arranged in very different ways: α as the parent of subtrees β and γ, and α’ as the parent of β’ and β’ as the parent of γ’. thus, αβγ and α’β’γ’ would match well despite substantially different tree structures. in contrast, the modified global alignment algorithm implemented in pasta distinguishes the two cases. expanded representations including branch-level morphological features could enhance alignment sensitivity, decreasing the likelihood of spurious alignment for shorter sequences. for instance, several characters could be used for each topological node type to encode the bifurcation angles relative to the population distribution. the increased sequence complexity would alleviate the need for a gap opening cost, allowing a greater range for parameter tuning. additionally, such encodings would enable analyses for relating local topological patterns with other morphological features. subtree size and tortuosity are similarly reliable branch metrics which could be encoded; distance from soma and maximum distance to termination are also suitable candidates. diameter and associated metrics, while possible in principle, are more susceptible to experimental protocols. combining several morphological attributes in the encoding would multiply the number of characters required, but feature vectors could be used rather than characters, increasing sensitivity at the expense of speed. alternatively, the number of features and their discretization could be judiciously selected based on the specific research questions. leveraging pairwise tree alignment, cluster analysis, and multiple sequence alignment, an expanded encoding could help discover novel relationships between morphological features, including their relative conservation and specificity across neuronal classes. for instance, the different tortuosity among interneuron classes could reveal regional differences within the arbor, which would suggest axonal domains with specific targeting features. the level of conservation would provide an indication of the feature’s functional importance as well as provide a constraint for modeling growth mechanisms. since morphology ultimately depends on ultrastructural features to produce function, lower-scale branch properties such as spines or bouton densities and even local molecular expression could create powerful analyses. this would require a richer data type and new experimental processes, but with recent technologies the prospect is real. combining biophysical data with pairwise alignment would enable exploration and detection of morphological-physiological relationships, such as spike failures near regions of high bifurcation density, or receptors of neurotrophic factors in sequences with many c nodes. spatial information, such as the cortical layer or brain region in which a branch is located, could also be encoded, allowing for explicit alignment by anatomical domain. while we found no association between axonal consensuses and spatial location relative to the soma, such associations may be anticipated with apical dendrites and more complete axonal reconstructions spanning multiple brain regions, and spatial encoding would facilitate such discoveries. the code available at http://krasnow gmu.edu/cn3/neuritesequence/ includes sample expanded branch feature encoding to enable future exploration by the research community. an extended encoding could also improve classification. while we showed that the alignment space is at least as informative as standard topological metrics, whole-neurite metrics and branch level features such as length and tortuosity are also useful for classification. for a discussion of which morphometrics are effective for neuronal classification, see. a feature matrix composed of alignment space dimensions and morphometrics would allow for classification on both. in cases in which classes are similar in terms of average branch level metric but different in their relation to topology, the extended encoding has the potential to be more powerful than simply adding branch level metric distributions to the feature matrix. an optimized multi-stage classification which aligns only neurites similar by standard morphometrics could deliver an improved classifier with only a modest increase in alignment computation. optimizing algorithms and analysis the sequence approach depends critically on the constraint that small-side subtrees necessarily be matched to other smaller-side subtrees. this condition produces near-optimal results with moderately to highly asymmetric trees, which have low probabilities of improved tree-alignment from a larger-side subtree aligned to a smaller-side subtree. the scores are near optimal even in the case of trees with greater symmetry, so long as the subtrees are topologically similar. this assumption is generally true of neurites, which explains its effectiveness in this study. however, it is possible to conceive a “worst-case scenario” of a root bifurcating into two large subtrees with exactly the same number of branches, but one fully symmetric and one fully asymmetric. aligning the corresponding sequence with an almost identical arbor in which a single branch is added to the symmetric side would yield a dismally low score despite the great structural similarity between the two trees. to gauge the risk incidence of this effect in neurites, we assessed the asymmetry characteristics of bifurcations with similar subtree sizes, specifically, those with a difference of no more than bifurcations. of the 5% of axon, 26% of apical dendrite, and 36% of dendrite bifurcations satisfying the condition, the median difference in asymmetry was, with 75% having a difference less than, though the differences were much smaller for the 5% of subtrees with more than bifurcations. this survey suggests that only dendrites might be susceptible to this problem, though with reasonably small impacts for each instance. thus, based on currently available data, the relatively simple topological encoding results in practically robust sequence alignments however, the possibility that future larger dataset of complete axonal reconstructions will require a more optimal alignment method cannot be ruled out. in the big-data prospect of orders-of-magnitude increase in neurite dataset size, heuristics will become important for efficient processing. given that mds does not require distances for every neurite pair, not all pairwise combinations are necessary for producing an alignment space. moreover, for search or analysis, topological metrics can be used to limit the number of neurite alignments by filtering out those that would likely score poorly, as achieved by blastneuron with a broader range of morphometrics. the pasta algorithm itself can be sped up by ignoring the possibilities least likely to contribute to an optimal alignment. other heuristic approaches could be applied that involve candidate seed locations of short matching strings from which the alignment is extended in either direction. the most efficient modern algorithms index seeds in advance. a larger dataset of more complete axons, widely expected from ongoing and discussed connectomic projects, would require appropriate heuristics and efficient implementation in a compiled language, such as c or c++. in cases where sensitivity is more important than speed, sequences of branch feature vectors could take the place of discrete characters. the diversity of available gene sequence alignment tools highlights the utility of specific parameters and alternative algorithms for different experimental questions or computational requirements. methods of neurite pairwise alignment of one sort or another, including variations on our method, will likely grow in a similar manner to fill various niches, whether in terms of sensitivity or efficiency.  the newly developed method for aligning binary tree sequences enabled the comparison of large numbers of neurites and revealed their shared topological features. sequence alignment similarity with a purely topological encoding was sufficient to distinguish different arbor types as well as certain neuron types, brain regions, and species. moreover, the sequence representations could differentiate cell classes better than traditional morphometrics and are consistently as informative as traditional topological metrics. cluster analysis produced groupings highly associated with known metadata differences, and multiple sequence alignment generated a consensus representation of each cluster that revealed the common topological features. comparative analysis between consensus and motif profile demonstrated that these analyses captured complementary topological characteristics, with consensuses reliably extracting global features and motifs effectively quantifying local features. additional file additional file 1: this file provides additional methodological information regarding alignment score baselines and distance normalization, non-metric multidimensional scaling, model-based clustering, cluster-metadata associations, and classification. it additionally includes four supplementary figures referenced in the main text. competing interests the authors declare that they have no competing interests. authors’ contributions tag and gaa developed the methods and designed the research. tag implemented the methods, carried out the analyses, and drafted the manuscript. ph contributed to the design and implementation of the sequence alignment algorithms and provided input on the manuscript. gaa guided the study and edited the manuscript. all authors read and approved the final manuscript. 
the space generated from pairwise similarities is capable of classifying neuronal arbor types as well as, or better than, traditional topological metrics. unsupervised cluster analysis produces groups that significantly correspond with known cell classes for axons, dendrites, and pyramidal apical dendrites. moreover, comparison of multiple alignment with motif analysis shows that the two techniques provide complementary information respectively revealing global and local features. we implemented a modified global alignment algorithm representing axonal and dendritic bifurcations as strings of characters. interestingly, the axons of dendritic-targeting interneurons in the rodent cortex associates with pyramidal axons but apart from the axons of perisomatic-targeting interneurons. furthermore, the distinguishing consensus topology generated by multiple sequence alignment of a group of neurons reveals their shared branching blueprint. global pairwise and multiple sequence alignment of neurite topologies enables detailed comparison of neurites and identification of conserved topological features in alignment-defined clusters. sequence alignmentneuronal morphologymultiple sequence alignmenttree topologyissue-copyright-statement© the author 2015
 the increasing abundance of neuromorphological data provides both the opportunity and the challenge to compare massive numbers of neurons from a wide diversity of sources efficiently and effectively. we implemented a modified global alignment algorithm representing axonal and dendritic bifurcations as strings of characters. sequence alignment quantifies neuronal similarity by identifying branch-level correspondences between trees.  the space generated from pairwise similarities is capable of classifying neuronal arbor types as well as, or better than, traditional topological metrics. unsupervised cluster analysis produces groups that significantly correspond with known cell classes for axons, dendrites, and pyramidal apical dendrites. furthermore, the distinguishing consensus topology generated by multiple sequence alignment of a group of neurons reveals their shared branching blueprint. interestingly, the axons of dendritic-targeting interneurons in the rodent cortex associates with pyramidal axons but apart from the axons of perisomatic-targeting interneurons.  global pairwise and multiple sequence alignment of neurite topologies enables detailed comparison of neurites and identification of conserved topological features in alignment-defined clusters. the methods presented also provide a framework for incorporation of additional branch-level morphological features. moreover, comparison of multiple alignment with motif analysis shows that the two techniques provide complementary information respectively revealing global and local features. electronic supplementary material the online version of this article contains supplementary material, which is available to authorized users. keywords sequence alignmentneuronal morphologymultiple sequence alignmenttree topologyissue-copyright-statement© the author 2015 