Fabio Pardi
email: pardi@lirmm.fr

Olivier Gascuel
email: gascuel@lirmm.fr

Distance--based methods in phylogenetics

Keywords: Additive distance, branch lengths, computational complexity, consistency, distance matrix, evolutionary distance, least squares, minimum evolution, neighbor joining, phylogenetic tree

Additive distances: a collection of pairwise distances 𝛿 !" is additive if there exists a phylogenetic tree whose branch lengths determine distances between leaves coinciding with the 𝛿 !" .

Branch lengths: the branches in a phylogenetic tree usually have lengths representing the amount of evolutionary change that has occurred between the taxa at their endpoints. When the tree represents the evolution of a set of biological sequences, branch lengths are usually measured in terms of expected number of substitutions per site.

Computational complexity: a measure of how a resource (typically time or memory) employed by an algorithm scales with the input data. An algorithm has complexity 𝑂(𝑓 𝑛 ) if the resources grow at most proportionally to 𝑓 𝑛 , a function of the input size n.

Distance matrix: a square matrix, i.e., a table with an equal number of rows and columns corresponding to a set of taxa, where the entry in column i and row j, denoted 𝛿 !" represents an estimate of the evolutionary distance between the i--th and the j--th taxon. The matrix is symmetric (i.e., 𝛿 !" = 𝛿 !" ) and the elements on its diagonal are zero (𝛿 !! = 0).

Evolutionary distance: a measure of the amount of change or divergence that has occurred between two taxa. When taxa are represented by biological sequences, `change' is usually taken as the occurrence of substitutions along the evolutionary path connecting the sequences.

Least squares (LS): a general principle from regression analysis to adjust the parameters of a model function to best fit some observed data. In distance--based reconstruction, it is used to fit the branch lengths of a phylogeny to a set of distance estimates. Least squares methods aim to minimize a quadratic function of the differences between the distance estimates and the additive distances determined by the branch lengths. For ordinary least squares (OLS) the goal is to minimize the sum of the squared differences, while for weighted least squares (WLS) this sum is weighted by terms reflecting the variances of the distance estimates.

Minimum evolution (ME): a general distance--based principle, analogous to parsimony, to measure the plausibility of a phylogenetic tree whose branch lengths have been fitted to the data, typically by least squares (see above). If we define the length of a tree as the sum of its branch lengths, then shorter trees are deemed to be more plausible than longer ones.

Molecular clock: the assumption of a constant substitution rate across a phylogeny, implying that branch lengths are directly proportional to time.

Molecular phylogenetics: the study and reconstruction of phylogenies representing the evolution of molecular sequences, such as those of DNA or proteins.

)) or into ((A,D),(B,C)).

Sequence profile: a table describing the general form of a collection of aligned sequences. For each site, the profile specifies the frequency of each possible character (including gaps) at that position.

Statistical consistency: in statistics, a method of estimation is statistically consistent if it is guaranteed to converge, with probability 1, towards the correct value of the parameter, as the size of the input sample tends to infinity. In molecular phylogenetics, the central parameter is often taken to be the topology τ of the correct phylogenetic tree, so a method is said to be statistically consistent if the probability of reconstructing a tree of topology τ converges to 1 as the input sequence alignment becomes longer and longer.

Substitution model: a probabilistic model describing the occurrence of substitutions in a DNA or protein sequence. Substitutions models are used to estimate the evolutionary distances between pairs of molecular sequences.

Subtree pruning and regrafting (SPR): a rearrangement of a tree topology, which removes a subtree (a clade) and reinserts it elsewhere in the tree topology.

Tree topology: the discrete, structural information contained in a phylogenetic tree, besides branch length information.

Ultrametric distances: the pairwise distances 𝛿 !" are ultrametric if they are additive with respect to a tree whose leaves are all at the same distance from the root. In molecular phylogenetics, distances are approximately ultrametric only when the molecular clock assumption holds.

Introduction

Distance--based phylogenetic reconstruction rests on two steps. First, for each pair of taxa estimate the amount of change that has occurred along the evolutionary path connecting them. Such measure of change is called an evolutionary distance, and in the case of biological (DNA or protein) sequences, it is proportional to the number of substitutions that have taken place in the two lineages since the last common ancestor of the two sequences. Tree inference is then based on these estimates -the goal being to find the tree that best accounts for the estimated distances.

Using pairwise distances or similarities between taxa is arguably the oldest approach to investigate systematic relationships by means of a computer [START_REF] Sokal | The application of computers to taxonomy[END_REF][START_REF] Sokal | A statistical method for evaluating systematic relationships[END_REF]. Early work saw a very clear distinction between, on the one hand, hierarchical clustering techniques for taxonomic classification [START_REF] Sokal | The application of computers to taxonomy[END_REF], and, on the other hand, optimization--based methods directly aimed at phylogenetic reconstruction [START_REF] Cavalli--Sforza | Phylogenetic analysis. Models and estimation procedures[END_REF][START_REF] Fitch | Construction of phylogenetic trees[END_REF]. These two lines of work eventually converged in the 1980s, leading to the hugely popular neighbor joining (NJ) method [START_REF] Saitou | The neighbor--joining method: a new method for reconstructing phylogenetic trees[END_REF]) -which combined algorithmic ideas from classification (e.g., UPGMA, [START_REF] Sokal | A statistical method for evaluating systematic relationships[END_REF]ADDTREE, Sattath & Tversky 1977) to optimization principles from phylogenetics (e.g. ME, [START_REF] Kidd | Phylogenetic analysis: concepts and methods[END_REF]OLS, Cavalli--Sforza & Edwards 1967; see below). From NJ onwards, phylogenetics has witnessed a renaissance of distance--based methods, often related to, or inspired by NJ (e.g., FastME, Desper & Gascuel 2002;FastNJ, Elias & Lagergren 2009;FastTree, Price et al. 2009).

These methods are still widely used for their computational efficiency, an advantage that makes them particularly suited for the reconstruction of very large phylogenies, or large collections of phylogenies (e.g., for bootstrapping), or to provide a basis for progressive multiple sequence alignments [START_REF] Larkin | Clustal W and Clustal X version 2.0[END_REF], or even to construct initial trees for more sophisticated inference approaches such as those based on maximum likelihood [START_REF] Guindon | A simple, fast, and accurate algorithm to estimate large phylogenies by maximum likelihood[END_REF].

More generally, using estimated distances between biological sequences is an obvious answer to cope with the massive data sets generated by the modern, ever faster and cheaper sequencing techniques -as testified by the ongoing success of NJ, which to date remains the most cited algorithm in phylogenetics.

In this entry, we outline the main ideas that underlie the methodology for distance--based phylogenetics. We start by explaining the importance of estimating distances that reflect the number of changes that have actually occurred between two taxa, rather than the (smaller) number of differences between them. After describing concisely the task of estimating evolutionary distances, the main focus here is on the methods for tree inference proper, that is, to reconstruct a tree that fits well the estimated distances.

Preliminaries

A phylogenetic tree T over a set of taxa X has two components. First, a tree topology τ, i.e. an unrooted tree with no degree--2 nodes, whose leaves are labeled by (and represent) the taxa in X, and whose internal nodes represent putative ancestors of these taxa. The second component consists of positive branch lengths 𝑏(𝑒) for every branch e in τ, which represent a measure of evolutionary change occurred along e.

Every phylogenetic tree T determines a collection of tree distances 𝑑 !"

! between the taxa 𝑖, 𝑗 ∈ 𝑋 = 1,2, … , 𝑛 labeling its leaves. They are defined by:

𝑑 !" ! = 𝑏(𝑒) !∈! !"
, where 𝜏 !" denotes the set of branches between i and j in 𝜏. In other words, the tree distance 𝑑 !" !

is the length of the path connecting i and j in T.

Now suppose that, for each pair of taxa 𝑖, 𝑗 ∈ 𝑋 = {1,2, … , 𝑛}, an estimate 𝛿 !" of their evolutionary distance is obtained. We say that the 𝛿 !" are additive, if 𝛿 !" = 𝑑 !" ! for all 𝑖, 𝑗 ∈ 𝑋 , for some phylogenetic tree T over X. Importantly, when such a tree exists, it is unique [START_REF] Zaretskii | Constructing a tree on the basis of a set of distances between the hanging vertices[END_REF][START_REF] Simões Pereira | A note on tree realizability of a distance matrix[END_REF][START_REF] Buneman | The recovery of trees from measures of dissimilarity[END_REF]. Moreover, as we shall see in the following, it is algorithmically easy to reconstruct tree T from its tree distances 𝑑 !" ! . These observations provide the fundamental idea underlying distance--based methods: if we manage to obtain precise estimates of the distances 𝑑 !" ! for the phylogenetic tree we seek, then reconstructing this tree is easy.

The word additive comes from the fact that if we could observe a taxon i as it evolves into k at an intermediate stage, and then eventually into j, then the true evolutionary distances between 𝑖, 𝑗, 𝑘 must satisfy

𝑑 !" = 𝑑 !" + 𝑑 !" . (1)
Figure 1: Uncorrected distances are not additive. We assume that i, k and j are realizations of the same sequence at three successive times. If distances were defined as the number of differences, we would have 𝑑 !" = 4 < 𝑑 !" + 𝑑 !" = 7, contradicting equation ( 1), and showing that the distances would not be additive. Note that both 𝑑 !" and 𝑑 !" + 𝑑 !" potentially underestimate the number of substitutions occurred between i and j.

Distance estimation

The first, fundamental component of a distance--based method is the definition of `evolutionary distance'. It is important to understand that not any measure of distance can be adopted for phylogenetic reconstruction: the key requirement is that the parameters that we set out to estimate must be additive in the sense specified above. This ensures that, as the data become more and more abundant and the distance estimates more and more accurate, these estimates will determine the correct phylogenetic tree [START_REF] Atteson | The performance of neighbor--joining methods of phylogenetic reconstruction[END_REF].

As a consequence, in molecular phylogenetics, where the data are collections of DNA or protein sequences, simply counting the number of differences between each pair of sequences is not acceptable, because of the possibility of multiple substitutions at the same site (see Fig. 1). The number of differences, or mismatches, between sequences is sometimes referred to as their `uncorrected distance'.

A much better approach is to define the distances as (proportional to) the number of substitutions that have occurred between the two sequences, which clearly leads to an additive measure. As this number is unobservable, the general approach is to estimate it using nucleotide or amino acid substitution models. Note that uncorrected distances do not account for unobserved changes -such as multiple substitutions at the same site -and therefore underestimate this number (see again Fig. 1). We will now describe, in very general terms, the maximum likelihood (ML) approach to solve this estimation problem. The interested reader is referred to more advanced textbooks (e.g. [START_REF] Felsenstein | Inferring phylogenies[END_REF][START_REF] Yang | Computational molecular evolution[END_REF]) for a detailed treatment of distance estimation.

Substitution models allow us to calculate a substitution probability matrix 𝑃 𝑑 = (𝑝 !" 𝑑 ), where x and y denote nucleotides, amino acids or other biological characters, and 𝑝 !" 𝑑 denotes the probability that an x becomes a y after evolving along a branch of length d. Note that d is not expressed in units of time. Instead, the rate of substitution models is usually scaled so that d equals the expected number of substitutions per site along a branch of that length. Also recall that 𝜋 ! denotes the stationary probability of x. It can be defined as 𝜋 ! = lim !→! 𝑝 !" 𝑑 , and is sometimes estimated using the frequency of x in the sequences being analyzed.

The evolutionary distance between two sequences x and y is estimated on the basis of a pairwise alignment of these two sequences. Denote by 𝑥 ! and 𝑦 ! the i--th aligned character of x and y, respectively. Assuming that the substitution model is time--reversible, the likelihood is given by:

𝐿 𝑑 = 𝜋 ! ! ! !!! 𝑝 ! ! ! ! 𝑑 ,
where the product is over the m aligned sites. Then, the ML estimate of the distance between x and y is the value of d that maximizes 𝐿 𝑑 above, and can be obtained numerically or analytically, depending on the model.

For illustration, we consider the simplest model of nucleotide substitution, the JC model [START_REF] Jukes | Evolution of protein molecules[END_REF]. For this model, we have, 𝜋 ! = 𝜋 ! = 𝜋 ! = 𝜋 ! = 1 4 and, assuming 𝑥 ≠ 𝑦,

𝑝 !! 𝑑 = 1 4 1 + 3𝑒 ! ! ! ! , 𝑝 !" 𝑑 = 1 4 1 -𝑒 ! ! ! ! .
The likelihood is then given by:

𝐿 𝑑 = 1 4 !! 1 -𝑒 ! ! ! ! ! ! 1 + 3𝑒 ! ! ! ! !!! ! ,
where 𝑚 ! is the number of mismatches. It is then easy to calculate that 𝐿 𝛿 is maximized for

𝛿 = - 3 4 ln 1 - 4 3 𝑚 ! 𝑚 .
That is, the distance estimate 𝛿 between the two sequences is a simple, strictly increasing function of the proportion of mismatches 𝑚 ! /𝑚 -the uncorrected distance we mentioned above. Note that 𝛿 ≥ 𝑚 ! /𝑚, corresponding to the fact that there are more substitutions than observed differences.

Other models cause the ML estimates of the distances to be functions of multiple features of the pairwise alignment, so strictly speaking it is not always accurate to describe distance estimates as transformations of the uncorrected distances. As ML distance estimation is the same as ML phylogenetic reconstruction of a 2--taxon tree, the numerical techniques for distance estimation are largely the same as those employed for ML branch length optimization [START_REF] Yang | Computational molecular evolution[END_REF].

Tree reconstruction

We organize our brief survey of tree reconstruction methods around three well--defined components. Any choice with respect to them defines a possible distance--based method.

C1 Branch length estimation: a method to assign lengths to the branches of any fixed tree topology, so that the resulting tree distances are as close as possible to the estimated distances 𝛿 !" . This is usually achieved using least squares techniques from regression analysis [START_REF] Cavalli--Sforza | Phylogenetic analysis. Models and estimation procedures[END_REF][START_REF] Fitch | Construction of phylogenetic trees[END_REF].

C2 What to optimize: a criterion assigning a score to all the trees of different topologies that can be obtained with component C1, reflecting the biological plausibility of a phylogenetic reconstruction given the estimated distances. An obvious choice for this is the least squares criterion used to assign branch lengths, but as we describe below a lot of recent methodology is based on a different criterion, minimum evolution [START_REF] Kidd | Phylogenetic analysis: concepts and methods[END_REF]. Some methods (e.g. ADDTREE; [START_REF] Sattath | Additive similarity trees[END_REF] directly optimize topological criteria, and thus bypass C1.

C3 How to optimize: an algorithm to seek the optimal tree with respect to the criterion in C2.

Since this is a computationally hard optimization problem, algorithms are usually heuristic, and based on simple but effective ideas such as stepwise addition, iterative agglomeration, or hill climbing [START_REF] Swofford | Phylogeny reconstruction[END_REF][START_REF] Felsenstein | Inferring phylogenies[END_REF]).

In the following, we start by surveying the methodology for C1 (Sec. 4.1). Then we describe one of the most popular criteria for C2, minimum evolution (Sec. 4.2), which is at the foundation of what is still the best known distance--based method, neighbor joining. We illustrate this algorithm along with other approaches that are based on the same ideas (Sec. 4.3). Finally, we briefly describe a few promising approaches which, strictly speaking, are not distance--based methods, but which share with them several ideas and the same emphasis on computational efficiency (Sec. 4.4).

Least squares branch length estimation

Given the estimated distances 𝛿 !" for all 𝑖, 𝑗 ∈ 𝑋 , the goal of least squares phylogenetic reconstruction [START_REF] Cavalli--Sforza | Phylogenetic analysis. Models and estimation procedures[END_REF][START_REF] Fitch | Construction of phylogenetic trees[END_REF] is to find a phylogenetic tree T that minimizes the gap between the estimates 𝛿 !" and the tree distances 𝑑 !" ! , measured in terms of a quadratic function 𝑄 𝑇 of the residuals 𝛿 !" -𝑑 !" ! . Different, statistically motivated choices for 𝑄 𝑇 are possible, and are detailed below. While many versions of this problem have been proven computationally hard [START_REF] Day | Computational complexity of inferring phylogenies from dissimilarity matrices[END_REF]), here we focus on the simpler problem of assigning branch lengths to a tree of fixed topology 𝜏. As we show below, exact, analytic, and polynomially--computable solutions are available for this task.

The method of least squares was first introduced in phylogenetics in the mid 1960s. The proposed objective function was [START_REF] Fitch | Construction of phylogenetic trees[END_REF]. The former is often referred to as ordinary least squares (OLS), and both approaches are particular cases of weighted least squares (WLS), where various choices are possible for 𝑤 !" . From a statistical standpoint, the weight 𝑤 !" represents the degree of confidence that we can attach to the distance estimate 𝛿 !" : ideally 𝑤 !" should be inversely proportional to the variance of 𝛿 !" , but in practice setting the weights is a delicate art, because the variances are difficult to evaluate.

𝑄 𝑇 = 𝑤 !" 𝛿 !" -𝑑 !" ! ! , !!! with 𝑤 !" = 1 (Cavalli--Sforza & Edwards 1967) and 𝑤 !" = 1 𝛿 !" ! (
One particular choice on which we will come back a few times in the following is that of balanced weights -with 𝑤 !" proportional to 2 !|! !" | (|𝜏 !" | denotes the number of edges on the path between i and j in 𝜏) -which assigns less confidence to the distances between topologically distant taxa.

WLS approaches ignore the correlations between the distance estimates 𝛿 !" , 𝛿 !" for different pairs of taxa, which may be significant when the paths 𝜏 !" and 𝜏 !" share many branches. In order to take these correlations into account, generalized least squares (GLS) [START_REF] Chakraborty | Estimation of time of divergence from phylogenetic studies[END_REF][START_REF] Bulmer | Use of the method of generalized least squares in reconstructing phylogenies from sequence data[END_REF] minimizes

𝑄 𝑇 = 𝑤 !",!" 𝛿 !" -𝑑 !" ! 𝛿 !" -𝑑 !" ! !!! !!! ,
where the 𝑤 !",!" should be set as the entries of the inverse of the variance--covariance matrix for the distance estimates 𝛿 !" . Just as OLS is a particular case of WLS, WLS is a particular case of GLS, obtained by setting 𝑤 !",!" = 0 whenever 𝑖, 𝑗 ≠ {𝑘, 𝑙} . In practice GLS is rarely used for phylogenetic inference, because of the difficulty of evaluating the covariances, and because of its higher computational costs relative to those of OLS and WLS.

The branch lengths that are optimal with respect to the 𝑄(𝑇) criteria above can be simply expressed in matrix notation. To this end, let 𝜹 = (𝛿 !" ) denote the distance estimates and 𝒅 𝑻 = (𝑑 !" ! ) the tree distances for a tree T, in vector form. Moreover, we represent any topology τ with a binary matrix 𝐴 ! = (𝑎 !",! ) -whose rows correspond to pairs of taxa 𝑗 and whose columns correspond to branches of τ - defined by setting 𝑎 !",! = 1 if e is on the path between i and j in τ, and 0 otherwise. Given these notations, we can write

𝒅 𝑻 = 𝐴 ! 𝒃,
where 𝒃 = (𝑏 𝑒 ) denotes the branch lengths of T in vector form. See Fig. 2 for an example illustrating these notations.

Figure 2: The usefulness of the topological matrix. The tree distances for the 5--taxon tree on the left are expressed here as 𝐴 ! 𝒃 = 𝒅 𝑻 .

The objective functions of OLS, WLS and GLS can then be written concisely in matrix form:

𝑄 𝑇 = 𝜹 -𝐴 ! 𝒃 ! 𝑊 𝜹 -𝐴 ! 𝒃 ,
where 𝑊 = (𝑤 !",!" ) contains the GLS weights and the superscript t denotes the matrix transpose.

When W is diagonal, or the identity matrix, WLS and OLS are obtained, respectively. The branch lengths for τ that minimize 𝑄(𝑇) can then be expressed as:

𝒃 = 𝐴 ! ! 𝑊𝐴 ! !! 𝐴 ! ! 𝑊𝜹. (2)
The matrix calculations in equation ( 2) are computationally expensive, but a number of properties of the matrices involved can be exploited to speed up the solution (Gascuel 1997a[START_REF] Bryant | Rapid evaluation of least--squares and minimum--evolution criteria on phylogenetic trees[END_REF]. For WLS, computational complexity is dominated by the matrix inversion - or equivalently by linear system resolution - which standard algorithms achieve in 𝑂(𝑛 ! ) time, where we recall that 𝑛 = |𝑋| denotes the number of taxa. For OLS, the complexity can be further to 𝑂(𝑛 ! ). In fact, the OLS branch lengths can be expressed with simple combinatorial formulae [START_REF] Vach | Least squares approximation of additive trees[END_REF][START_REF] Rzhetsky | Theoretical foundation of the minimum--evolution method of phylogenetic inference[END_REF]). More recently it was discovered that similar formulae exist for WLS with balanced weights [START_REF] Desper | Theoretical foundation of the balanced minimum evolution method of phylogenetic inference and its relationship to weighted least--squares tree fitting[END_REF], and in fact for a whole new class of special cases of WLS, those with multiplicative weights [START_REF] Mihaescu | Combinatorics of least--squares trees[END_REF].

We conclude by remarking that none of the approaches described above guarantees that the assigned branch lengths are all positive. Least squares branch length estimates are sometimes negative, which does not correspond to any biological reality. Constraining branch lengths to be non--negative leads to non--negative least--squares (NNLS) regression [START_REF] Lawson | Solving least squares problems[END_REF], an approach that however further increases computational costs.

Optimization criteria: minimum evolution

Once a way to assign branch lengths to any fixed topology has been determined, the next question (C2) is how to measure the plausibility of the trees we obtain. One possibility is to adopt the same least squares criterion 𝑄(𝑇) used for branch lengths, implying that a tree topology is considered plausible if its tree distances can be fitted very closely to the estimated distances. This approach is known to perform best when negative branch lengths are disallowed [START_REF] Kuhner | A simulation comparison of phylogeny algorithms under equal and unequal evolutionary rates[END_REF]), a constraint that can be imposed in popular programs such as FITCH [START_REF] Felsenstein | An alternating least squares approach to inferring phylogenies from pairwise distances[END_REF]) and PAUP* [START_REF] Swofford | PAUP*. Phylogenetic Analysis Using Parsimony (* and Other Methods)[END_REF].

A different approach - minimum evolution (ME) - scores a tree using the sum 𝐿(𝑇) of the fitted branch lengths: the shorter the tree, the better. The intuition underlying ME is the same as that of maximum parsimony for character--based tree reconstruction: similarly to the general principle that simple explanations are preferable to complex ones, in phylogenetics shorter trees are often considered more plausible than longer ones.

ME can deal with negative branch lengths in a variety of ways: they can be simply excluded from the sum in 𝐿(𝑇) [START_REF] Swofford | Phylogeny reconstruction[END_REF]), or 𝐿(𝑇) can be defined as the sum of the absolute values of the branch lengths [START_REF] Kidd | Phylogenetic analysis: concepts and methods[END_REF]. To date, the most common approach is to define 𝐿(𝑇) as the sum of all branch lengths, irrespective of their sign [START_REF] Saitou | Relative efficiencies of the Fitch--Margoliash, maximum-parsimony, maximum--likelihood, minimum--evolution, and neighbor--joining methods of phylogenetic tree construction in obtaining the correct tree[END_REF][START_REF] Rzhetsky | Theoretical foundation of the minimum--evolution method of phylogenetic inference[END_REF], which would seem to favor negative branch lengths, but in practice works quite well.

The first theoretical foundation of ME was provided by Rzhetsky and Nei, who showed that, if the distance estimates are unbiased, and branch lengths are assigned with OLS, then the mathematical expectation of 𝐿(𝑇) is minimized for the correct tree topology [START_REF] Rzhetsky | Theoretical foundation of the minimum--evolution method of phylogenetic inference[END_REF]. This means that, when the distance estimates equal the tree distances for a tree T -that is when 𝜹 = 𝒅 𝑻 -then the optimal tree with respect to OLS+ME is T itself. Note that in the following we will use the short form `C1+C2' to denote the optimization principle based on a particular choice for components C1 and C2 (see above).

If we assume that 𝜹 converges to 𝒅 𝑻 as more and more data are available, the result above implies that OLS+ME is statistically consistent -meaning that the probability of reconstructing T (within any given approximation) converges to 1 -which is an essential property of any phylogenetic inference method. Unfortunately ME does not always have this property [START_REF] Gascuel | Strengths and limitations of the minimum evolution principle[END_REF]) -an observation that casts serious doubts on the general applicability of the ME principle in phylogenetics. To date, statistical consistency has been proven to hold for all instances of WLS+ME with multiplicative weights [START_REF] Pardi | Combinatorics of distance--based tree inference[END_REF].

One special case of this is WLS+ME with balanced weights, which is also known as BME [START_REF] Pauplin | Direct calculation of a tree length using a distance matrix[END_REF][START_REF] Desper | Fast and accurate phylogeny reconstruction algorithms based on the minimum--evolution principle[END_REF][START_REF] Felsenstein | Inferring phylogenies[END_REF]. This optimization principle has several interesting mathematical features [START_REF] Semple | Cyclic permutations and evolutionary trees[END_REF], including the fact that for fully resolved trees its objective function can be expressed very concisely -and elegantly -as a function of the estimated distances:

𝐿 𝑇 = 2 !!|! !" | !!! 𝛿 !" (3)
BME is of key importance to interpret some of the most central methods in distance--based phylogenetics, including neighbor joining, as we explain below.

NJ and related algorithms

Neighbor joining (NJ) is an agglomerative clustering algorithm, that is, it constructs a tree in a bottom--up fashion by alternating the following two steps until the tree is complete:

Selection step: based on the distances between taxa, choose two `active' taxa i and j to agglomerate. That is, connect them to a new taxon (𝑖𝑗) representing their direct common ancestor. (Initially all taxa are `active'.)

Reduction step: remove i and j from the list of active taxa, and define new distances between the new active taxon (𝑖𝑗) and all remaining active taxa.

The two steps above are common to all agglomerative algorithms. For NJ, there are a number of equivalent [START_REF] Gascuel | A note on Sattath and Tversky's, Saitou and Nei's, and Studier and Keppler's algorithms for inferring phylogenies from evolutionary distances[END_REF] ways to specify the two steps above [START_REF] Saitou | The neighbor--joining method: a new method for reconstructing phylogenetic trees[END_REF][START_REF] Studier | A note on the neighbor--joining algorithm of Saitou and Nei[END_REF]). Here we describe the most efficient computationally [START_REF] Studier | A note on the neighbor--joining algorithm of Saitou and Nei[END_REF].

In the selection step, NJ agglomerates the taxa i and j that minimize

𝑞 !" = 𝑟 -2 𝛿 !" - 𝛿 !" ! !!! - 𝛿 !" ! !!! , (4)
where the sums run on the set of remaining active taxa, and r is their number. As for the reduction step, the new distance between (𝑖𝑗) and any other taxon k is defined by

𝛿 (!")! = ! ! 𝛿 !" + 𝛿 !" -𝛿 !"
. A third step, defining branch lengths for the reconstructed tree, is also usually described for NJ, but here we omit it for simplicity.

Different choices for the two steps above lead to other well--known agglomerative algorithms: single--linkage clustering (Sneath 1957), average--linkage clustering, also known as UPGMA [START_REF] Sokal | A statistical method for evaluating systematic relationships[END_REF], WPGMA [START_REF] Sokal | The application of computers to taxonomy[END_REF], ADDTREE [START_REF] Sattath | Additive similarity trees[END_REF], UNJ (Gascuel 1997a), and BIONJ [START_REF] Gascuel | BIONJ: an improved version of the NJ algorithm based on a simple model of sequence data[END_REF]. The last method is a special case of the MVR approach (Gascuel 2000a), which adapts the reduction step above so as to account for the variances and covariances of the distance estimates 𝛿 !" . It is similar in spirit to another agglomerative algorithm, Weighbor [START_REF] Bruno | Weighted neighbor joining: a likelihood--based approach to distance--based phylogeny reconstruction[END_REF], which also modifies the selection criterion, and uses a different formula [START_REF] Bulmer | Use of the method of generalized least squares in reconstructing phylogenies from sequence data[END_REF] to evaluate the variances of the distances.

Of the algorithms above, the fastest are single--linkage clustering, UPGMA and WPGMA, as they manage to construct a tree in 𝑂(𝑛 ! ) time [START_REF] Sibson | SLINK: an optimally efficient algorithm for the single--link cluster method[END_REF][START_REF] Murtagh | Complexities of hierarchic clustering algorithms: State of the art[END_REF][START_REF] Gronau | Optimal implementations of UPGMA and other common clustering algorithms[END_REF]. However they are only accurate when the distances are approximately ultrametric (see Glossary), and thus they are little used for phylogenetic inference, where the molecular clock is the exception rather than the rule. Apart from ADDTREE and MVR, which have a time complexity of 𝑂(𝑛 ! ), all other agglomerative algorithms mentioned above reconstruct a tree in 𝑂(𝑛 ! ) time. This includes NJ, where each of the 𝑛 -3 selection steps is carried out in 𝑂 𝑟 ! = 𝑂 𝑛 ! time via precalculation of the sums 𝛿 !" ! !!! [START_REF] Studier | A note on the neighbor--joining algorithm of Saitou and Nei[END_REF]. One of the reasons for the continued success of NJ is the fact that it has long been considered to achieve a very good tradeoff between reconstruction accuracy and running times.

Recently, a lot of work has gone into crafting computationally efficient implementations of NJ, both in terms of running time and memory usage. These include QuickTree [START_REF] Howe | QuickTree: building huge Neighbour--Joining trees of protein sequences[END_REF], QuickJoin [START_REF] Mailund | QuickJoin -fast neighbour joining tree reconstruction[END_REF], the bucket--based method of [START_REF] Zaslavsky | Accelerating the neighbor--joining algorithm using the adaptive bucket data structure[END_REF], NINJA [START_REF] Wheeler | Large--scale neighbor--joining with NINJA[END_REF], RapidNJ and ERapidNJ [START_REF] Simonsen | Inference of large phylogenies using neighbour--joining[END_REF]. A general idea is to speed up the selection of the pair of taxa that minimizes 𝑞 !" in equation ( 4), by limiting the search to a subset of pairs guaranteed to contain the best pair. Moreover, external (disk) memory is used to cope with large data sets (standard implementations can only deal with a few thousand taxa because of internal memory limitations). Although the worst--case time complexity remains 𝑂 𝑛 ! , these approaches permit a dramatic improvement in efficiency, allowing the reconstruction of trees with more than 50,000 taxa in a few hours on a normal PC [START_REF] Wheeler | Large--scale neighbor--joining with NINJA[END_REF][START_REF] Simonsen | Inference of large phylogenies using neighbour--joining[END_REF].

Even faster NJ--like algorithms can be obtained by employing heuristics -instead of exact algorithms - to select the pair of taxa to join on the basis of 𝑞 !" . These include FastNJ [START_REF] Elias | Fast neighbor joining[END_REF] and RelaxedNJ [START_REF] Evans | Relaxed neighbor joining: a fast distance--based phylogenetic tree construction method[END_REF], which is implemented in Clearcut [START_REF] Sheneman | Clearcut: a fast implementation of relaxed neighbor joining[END_REF]). In the case of FastNJ, the taxa to join are selected among a list of 𝑂 𝑛 pairs, implying a running time of 𝑂 𝑛 ! . For both methods, some loss of accuracy is to be expected, as in general these approaches do not reconstruct the same tree as NJ. Despite this, like NJ, these methods are statistically consistent, as they are guaranteed to reconstruct a tree T when the input distances are additive with respect to T, or nearly additive [START_REF] Atteson | The performance of neighbor--joining methods of phylogenetic reconstruction[END_REF][START_REF] Elias | Fast neighbor joining[END_REF].

A question that puzzled phylogeneticists for some time is whether NJ is related to any of the optimization criteria we discussed above. It was often suggested that "NJ has some relation to ordinary least squares and some to minimum evolution, without being definable as an approximate algorithm for either" [START_REF] Felsenstein | Inferring phylogenies[END_REF]). These connections come from the fact that the original selection criterion 𝑞 !" can be obtained as a sum of OLS estimates for a certain subset of branch lengths [START_REF] Saitou | The neighbor--joining method: a new method for reconstructing phylogenetic trees[END_REF][START_REF] Gascuel | A note on Sattath and Tversky's, Saitou and Nei's, and Studier and Keppler's algorithms for inferring phylogenies from evolutionary distances[END_REF]). However, if the good performance of NJ were due to its relation to OLS+ME, then we would expect that better (shorter) trees with respect to this criterion would also be phylogenetically more accurate than NJ trees, something that is actually contradicted by experience [START_REF] Saitou | Relative efficiencies of the Fitch--Margoliash, maximum-parsimony, maximum--likelihood, minimum--evolution, and neighbor--joining methods of phylogenetic tree construction in obtaining the correct tree[END_REF][START_REF] Kumar | A stepwise algorithm for finding minimum evolution trees[END_REF][START_REF] Gascuel | On the optimization principle in phylogenetic analysis and the minimum-evolution criterion[END_REF][START_REF] Desper | Fast and accurate phylogeny reconstruction algorithms based on the minimum--evolution principle[END_REF].

More recently, it was shown that the real optimization criterion behind NJ is BME [START_REF] Desper | The minimum evolution distance--based approach to phylogenetic inference[END_REF][START_REF] Gascuel | Neighbor--joining revealed[END_REF]. To briefly illustrate this, we note that the formula 𝐿 𝑇 in equation (3) (which only applies to bifurcating trees) can be generalized to unresolved trees by replacing 2 !!|! !" | by a factor 𝑝(𝑖 → 𝑗) expressing the probability of ending up in j when following a suitably defined random walk starting at i. The resulting generalized BME formula can then be seen as the guiding principle behind the selection step in NJ: at each of these steps, the agglomeration performed by NJ is the one that results in the tree with the smallest BME length.

Motivated by the observation that NJ can be seen as a greedy algorithm for BME, other methods guided by BME have been proposed [START_REF] Desper | Fast and accurate phylogeny reconstruction algorithms based on the minimum--evolution principle[END_REF][START_REF] Catanzaro | The balanced minimum evolution problem[END_REF]. These methods differ from NJ in their choice for component C3, that is, the algorithm to seek the BME-optimal tree. FastME [START_REF] Desper | Fast and accurate phylogeny reconstruction algorithms based on the minimum--evolution principle[END_REF][START_REF] Lefort | FastME 2.0: a comprehensive, accurate, and fast distance--based phylogeny inference program[END_REF] implements heuristics including stepwise addition to construct an initial tree, and common tree topology rearrangements (NNI, SPR) to perform a local search in tree space. Although the running time of FastME is comparable to that of NJ, its reconstruction accuracy is superior [START_REF] Desper | Fast and accurate phylogeny reconstruction algorithms based on the minimum--evolution principle[END_REF][START_REF] Felsenstein | Inferring phylogenies[END_REF][START_REF] Vinh | Shortest triplet clustering: reconstructing large phylogenies using representative sets[END_REF], thus confirming the suitability of BME as an optimization principle in distance--based phylogenetics.

Beyond distances

An important computational bottleneck of all the methods we presented so far is that they require the initial estimation and storage of distances for all pairs of taxa, which takes 𝑂 ℓ𝓁𝑛 ! time -assuming that distances are estimated from sequences of length ℓ𝓁 -and 𝑂 𝑛 ! memory. It is intuitive, however, that not all distances are necessary to reconstruct a phylogeny, meaning that these bounds can be improved. Some distances - those with large variances - may even be misleading for tree inference. Moreover, for large datasets with hundreds of thousands taxa, reducing memory usage may be a necessity: just storing the entire distance matrix for 100K taxa typically requires 20 GB of memory, which may be problematic for many users.

In the last few years a number of approaches have been proposed to bypass the bottleneck above. The most widely used is FastTree [START_REF] Price | FastTree: Computing large minimum evolution trees with profiles instead of a distance matrix[END_REF], whose strategy to construct an initial tree is inspired by NJ, but with two fundamental differences -one aimed at improving reconstruction accuracy, and the other for computational efficiency. We now briefly describe the main distinctive points of FastTree, as they underlie its good performance and thus its popularity.

The first difference with NJ and other classical distance--based methods is that FastTree stores sequence profiles for the active taxa (see Glossary) -instead of a distance matrix -and only computes the distance between two profiles if the corresponding pair is a candidate for joining. After each agglomeration, the sequence profile for the new node joining i and j is computed as the arithmetic average of the profiles for i and j. The pair of taxa to join is selected on the basis of a distance--based criterion formally similar to (4), but where distances are uncorrected and defined on the basis of the profiles stored for the active taxa. The second difference consists of maintaining a list of 𝑂( 𝑛) `top--hits' for each taxon (i.e. putative closest neighbours), which is combined to the strategies of FastNJ [START_REF] Elias | Fast neighbor joining[END_REF] and RelaxedNJ (Evans et al. 2006) to reduce the pairs of taxa to consider for agglomeration: at the end of its execution FastTree will only have considered 𝑂 𝑛 !.! log 𝑛 pairs -as opposed to 𝑂 𝑛 ! for NJ, and 𝑂 𝑛 ! for FastNJ. The NJ--like reconstruction of an initial tree -with a claimed complexity of 𝑂 ℓ𝓁𝑛 !.! log 𝑛 time and 𝑂 ℓ𝓁𝑛 + 𝑛 !.! memory -is then followed by a local search based on common tree topology rearrangements (NNI, SPR), using techniques similar to those implemented in FastME [START_REF] Desper | Fast and accurate phylogeny reconstruction algorithms based on the minimum--evolution principle[END_REF].

FastTree is faster and more memory--efficient than the distance--based methods discussed so far, and it can easily cope with data sets with hundreds of thousands of sequences. Given the central role of sequence profiles, it can be argued that FastTree is not a distance--based method. It shares ideas with with character--based methods such as parsimony, benefitting in particular from information about ancestral sequences -something that is not available to purely distance--based methodology.

Other methods that arguably lie beyond the frontier of distance methods -but which share with them several ideas and the same emphasis on computational efficiency -have recently been proposed by Brown, Truszkowski andcollaborators (Truszkowski et al. 2012, Brown andTruszkowski 2012). Particularly promising as a basis for future methodology is LSHTree [START_REF] Brown | Fast phylogenetic tree reconstruction using locality-sensitive hashing[END_REF], which like NJ proceeds in a bottom--up fashion by joining subtrees -although not necessarily at their roots. To do so, it uses `locality--sensitive hashing' exploiting ancestral sequence reconstructions, to rapidly find candidate pairs of close sequences to join. Just as FastTree, the running time of LSHTree is sub--quadratic.

Conclusion

Despite the simplicity of their approach, and the loss of information that is necessarily entailed by summarizing sequence data into a numerical matrix, distance--based methods are not just computationally efficient, but also remarkably accurate. The reconstruction accuracy of distance--based methods has been the subject of many simulation studies in the past (e.g., [START_REF] Saitou | Relative efficiencies of the Fitch--Margoliash, maximum-parsimony, maximum--likelihood, minimum--evolution, and neighbor--joining methods of phylogenetic tree construction in obtaining the correct tree[END_REF][START_REF] Kuhner | A simulation comparison of phylogeny algorithms under equal and unequal evolutionary rates[END_REF][START_REF] Kumar | A stepwise algorithm for finding minimum evolution trees[END_REF][START_REF] Gascuel | On the optimization principle in phylogenetic analysis and the minimum-evolution criterion[END_REF][START_REF] Nakhleh | The accuracy of fast phylogenetic methods for large datasets[END_REF][START_REF] Desper | Theoretical foundation of the balanced minimum evolution method of phylogenetic inference and its relationship to weighted least--squares tree fitting[END_REF]). The general idea of these studies is to generate sequences using standard substitution models and known model trees, and then compare the trees reconstructed by a number of competing methods to the model trees employed to generate the sequences. From these works it transpires that although not comparable to that of likelihood--based methods, the reconstruction accuracy of distance--based methods is competitive with that of maximum parsimony (MP), with MP superior for trees with short branches, and inferior when the effect of multiple substitutions at the same site becomes important. The reason for this is largely intuitive: while distance--based methods naturally account (or `correct') for multiple substitutions in the way they estimate distances, MP does not even model branch lengths, leading to serious problems such as statistical inconsistency in extreme cases [START_REF] Felsenstein | Cases in which parsimony or compatibility methods will be positively misleading[END_REF]. Another important conclusion that empirical studies have helped to reach is the importance of improving the tree reconstructed initially, via topological rearrangements such as NNI and SPR (e.g., [START_REF] Vinh | Shortest triplet clustering: reconstructing large phylogenies using representative sets[END_REF]. This is why most modern tree reconstruction methods include this important step, as we have seen for FastME [START_REF] Desper | Fast and accurate phylogeny reconstruction algorithms based on the minimum--evolution principle[END_REF] and FastTree [START_REF] Price | FastTree: Computing large minimum evolution trees with profiles instead of a distance matrix[END_REF]) in a distance--based context.

Another important advantage of distance--based methods is their versatility: they can be employed not just with sequence data, but in every context where pairwise comparisons are possible. For example, they have been used to infer phylogenies from morphological characters [START_REF] Sokal | A statistical method for evaluating systematic relationships[END_REF], immunological data [START_REF] Sarich | Immunological Time Scale for Hominid Evolution[END_REF], gene frequencies (Cavalli--Sforza & Edwards 1967), DNA--DNA hybridization data [START_REF] Sibley | The phylogeny of the hominoid primates, as indicated by DNA--DNA hybridization[END_REF], and more recently from gene content [START_REF] Snel | Genome phylogeny based on gene content[END_REF] or gene order [START_REF] Wang | Distance--based genome rearrangement phylogeny[END_REF]) within genomes. Another area where distance methods may prove useful is phylogenomics, where large collections of genomic alignments may be summarized into multiple distance matrices. Their combined analysis may provide an efficient alternative to traditional supertree and supermatrix approaches [START_REF] Lapointe | The average consensus procedure: combination of weighted trees containing identical or overlapping sets of taxa[END_REF][START_REF] Criscuolo | SDM: a fast distance--based approach for (super) tree building in phylogenomics[END_REF][START_REF] Binet | Fast and accurate branch length estimation for phylogenomic trees[END_REF]. See also: Parsimony (205), Maximum likelihood (207), Models and Model Selection (209).


Thomas Guiho

David Andreu

Victor Manuel López-Alvarez

Paul Cvancara

Arthur Hiairrassary

Loïc Wauters

Giuseppe Granata

Winnie Jensen

Jean-Louis Divoux

Silvestro Micera

Advanced 56 channels stimulation system to drive intrafascicular electrodes

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

I. INTRODUCTION

ITHIN the project EPIONE, our aim was to develop a prototype system to apply multi-channel microstimulation to the nerve stump of an amputee volunteer to manipulate his phantom limb sensations, and explore the possibility of using the method as a treatment for PLP.

The key technological challenges in this project involved the development of a portable multi-channel stimulator, a multi-channel peripheral nerve interface (i.e. the TIME-4H electrode) to be interfaced either with a psychophysical testing platform to evaluate the sensations generated or a handprosthesis to feedback sensations. The technological developments was guided, validated and evaluated through simulation studies and animal experiments. The application protocol on the SPI link for real time control allows to control simultaneously up to 8 active contacts playing independently with intensity and pulsewidth.

III. RESULTS

The whole system was first successfully tested on animals with implanted TIME-4H electrodes. On rats at UAB, sciatic nerve was implanted and EMG of 3-targeted muscles were recorded -i.e. tibialis anterior (TA), gastrocnemius (GM) and plantar interossei (PL) -and showed that the stimulation is accurately delivered to the different fascicules through selective recruitments. STIMEP performance was especially tested in studies designed to assess impact of pulse widths and intensities variations on recruitment (Fig. 2). Pigs experiments at AAU showed that the whole software and hardware was completely safe and that on a bigger nerve closed to the size of the targeted human ones, the same level of selectivity was achievable. These experiments validated all software routines used in human clinical trials. Both experiments will be shortly presented together with unpublished first human data.

IV. CONCLUSION

As far as we know, this is the first system allowed for invasive human's trial able to drive simultaneously 4 multicontact intrafascicular electrodes. The system enables real-time control of intensity, pulse-width and frequency of the stimulation to elicit very accurate sensation feedback. It also embeds impedance checking while being small enough to be further integrated in a future implantable pulse generator. The system is currently successfully used in a first human trial. Besides, the technology allows very advanced stimulation paradigms that may be explored in the future.

  II. MATERIALSElectrical stimulation of nerves is provided to the implanted transverse intrafascicular multichannel electrodes (TIME-4H) by the dedicated STIMEP neurostimulator able to address up to 56 different stimulation contacts and 8 ground electrodes. For therapy, STIMEP is remotely controlled in two different modes: i) Direct therapy parameterized by the Psychophysical Testing Platform (HMI software on PC) through insulated USB link.

  This work is conducted by the EU project 'EPIONE' under the FP7 Health program (HEALTH-F2-2013-602547), www.project-epione.eu. 1 Univ. of Montpellier, France 2 Axonic, MXM group, Sophia Antipolis, France 3 Univ. Autonoma of Barcelona, Spain 4 Univ. of Freiburg, Germany 5 EFPL, Lausanne, Switzerland 6 Univ. of Aalborg, Denmark 7 Universita' Cattolica del Sacro Cuore, Roma, Italy ii) Stimulation of sensory feedback in grasping tasks through insulated SPI controlled in real time by pressure and position sensors placed on a hand-prosthesis worn by the patient. This induces a bidirectional relationship between the patient and the hand-prosthesis. The main features of STIMEP are reported in table 1 and the architecture is schematically represented on Fig. 1. It consists of: i) a controller (SOC device) exchanging data with PC or the hand prosthesis, ii) 4 insulated stimulation units able to drive 4 TIME-4H simultaneously and independently. Each stimulation units is composed of CAFE24: proprietary analog ASIC stimulation front-end and a proprietary digital architecture based on an FPGA embedding communication functions, control of stimulation profiles and safety monitoring by means of reference models. A SOC-based controller drives and coordinates the 4 stimulation module activities each connected to a TIME-4H electrode. To comply with human trials, a full set of documentation, as per ISO 13485,conception, IEC 62304 for software part and 93/42/EEC directive (definitions, designs, protocols, justifications, flow charts, etc.), together with various regulatory files, including risk analysis, have been provided and are available for national authorities.

Figure 1

 1 Figure 1 STIMEP global architecture with partners' contribution. Achievements: -Specification of the XML-based application protocol on the USB/SPI link, implementation on the embedded processor of the XML parser. -Development of the 5 embedded Epione procedures configured by the Psychoplatform (impedance fast check, threshold search, therapy, sensation characterization)

Fig. 2 .

 2 Fig. 2. Recruitment curves for several PW (20 to 400µs) and I (20 to 300µA with à 20µA step) for PL muscle. It should be noted that 2 different index are used both for 50 and 100µs. This is due to additional point linked to a stimulation pitch decrease between 2 I. x-axis presents stimulation intensities while y-axis is expressed in Volt-RMS and presents average values over 5 repetitions.

Advanced 56 channels stimulation system to drive intrafascicular electrodes

  . Guiho 1 , D. Andreu 1 , V. M. López-Alvarez 3 , P. Cvancara 4 , A. Hiairrassary, G. Granata 7 , L. Wauters 2 , W. Jensen 6 , J.L. Divoux 2 , S. Micera 5 , T. Stieglitz 4 , X. Navarro 3 and D. Guiraud1

	-Development of the SYNERGY Neurostimulation
	software (accurate impedance check, system check, logged
	data upload).
	-All the procedures were formally modeled (Petri nets),
	analyzed and tested once implemented on µCOS certified
	real-time Operating System using C language.
	-Smart synchro out configuration for system checking,
	SEP and other measurements.
	-Safety procedures were designed, implemented and
	tested (USB communication watchdog, CRC, XML parser
	with frame decoding and checking), locked (forbidden)
	outputs management, charge injection limits (both to avoid
	patient pain and electrode corrosion).
	-Log of relevant information both at user level (the
	psychoplatform or SYNERGY Neurostimulation software)
	and at technical level.
	-Complex algorithms, for Handprosthesis control only,
	of frequency, Intensity and pulse width modulation (real
	time control of stimulation parameters linked to sensory
	feedback).
	W

T

ACKNOWLEDGMENT

The EPIONE consortium includes the following partners; 1) W. Jensen, Aalborg University, Denmark (project coordinator), 2) P. Sørensen, Aalborg University Hospital, Denmark, 3) P. M. Rossini, Universita' Cattolica del Sacro Cuore, Italy, 4) R. Wassim & A. Laurent-Applegate, Centre Hospitalier Universitaire Vaudois, Switzerland, 5) T. Stieglitz, Albert Ludwigs Universität Freiburg, Germany, 6) D. Guiraud, Laboratoire d'Informatique de Robotique et de Microelectronique de Montpellier, France, 7) S. Micera, École polytechnique fédérale de Lausanne, Switzerland, 8) F. Sebelius, Lund University, Sweden, 9). K. Yoshida, Indiana University-Purdue University Indianapolis, USA, 10). X. Navarro, Universitat Autonoma de Barcelona, Spain, 11) J. Tilly, Novosense AB, Sweden, 12) JL Divoux, Axonic, France.


Thomas Stieglitz

Tim Boretius

Paul Cvancara

David Guiraud

Thomas Guiho

Victor Manuel López-Alvarez

Xavier Navarro

On biocompatibility and stability of transversal intrafascicular multichannel electrodes -TIME

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

I. INTRODUCTION

NTERFACES to peripheral are a research topic for more than 50 years in rehabilitation engineering. Only few approaches have been transferred from animal experiments in clinical trials or even in approved medical products. Upper limb interfaces are under investigation if hand grasp shall be restored after spinal cord injury or stroke or if sensory feedback shall be delivered after hand amputation in prosthetic hand control or phantom limb pain treatment. Different nerve interface concepts were recently investigated in subchronic and chronic clinical trials on the ulnar and median nerve: circumneural cuff-electrodes [START_REF] Tan | A neural interface provides long-term stable natural touch perception[END_REF], micromachined intraneural needle arrays [START_REF] Davis | Restoring motor control and sensory feedback in people with upper extremity amputations using arrays of 96 microelectrodes implanted in the median and ulnar nerves[END_REF] and flexible, polymerbased intrafascicular electrodes [START_REF] Stieglitz | Development of a neurotechnological system for relieving phantom limb pain using transverse intrafascicular electrodes (TIME)[END_REF]. Our approach of a transversial intrafascicular multichannel electrodes (TIME) has been developed with a focus to treat phantom limb pain after hand amputation [START_REF] Stieglitz | Development of a neurotechnological system for relieving phantom limb pain using transverse intrafascicular electrodes (TIME)[END_REF]- [5]. In this paper, we report on the investigations on device stability and biocompatibility that have been performed to meet the essential requirements of the active implantable medical device directive (90/385/EEC) as prerequisite to enter human clinical trials and results of a subchronic pilot study that led to some design changes T. Stieglitz, P. Čvančara are with the Laboratory for Biomedical Microtechnology, Department of Microsystems Engineering (IMTEK), University of Freiburg, Freiburg, Germany (stieglitz@imtek.de, cvancara@imtek.de).

II. MATERIALS AND METHODS

An electrode concept has been developed and investigated up

T. Boretius was with the same affiliation during the TIME project and is now with neuroloop GmbH, Freiburg, Germany (tboretius@neuroloop.de).

to human clinical trials for intrafascicular implantation.

A. TIME Electrode Design

Micromachining techniques have been used to develop a polymer-based electrode made of a polyimide-platinum sandwich with sputtered iridium oxide as electrode coating. The microsystem was assembled with an alumina interconnector to a helically wound cable made of MP35N that ended in a miniaturized plug (Omnetics Nano). 14 stimulation and two counter electrodes were placed on each device [START_REF] Raspopovic | Restoring Natural Sensory Feedback in Real-Time Bidirectional Hand Prostheses[END_REF].

B. Mechanical and Electrochemical Characterization

Mechanical loading is supposed to occur mainly on the helically cable that will be routed percutaneously from the nerve through the muscles and the skin. Bending and stretching load cycles have been performed for 250,000 times on MP35N wires with polyesterimide insulation that have been helically wound to a cable and placed into a silicone rubber hose with a diameter of 1.8 mm. Stimulation pulses have been applied in phosphate buffered saline solution to determine the chemically safe maximum charge injection capacity. Test cycles ran for up to 250 million pulses for sputtered iridium oxide and electrode site diameters of 80 µm.

C. Biocompatibility and Biostability

According to ISO 10993 (Biological Evaluation of Medical Devices), several investigations have been performed. Cytotoxicity testing has been done with probes that have passed the whole manufacturing process. L929 cells have been chosen according to the standard. Direct contact and extract tests have been performed. Qualitative and quantitative assessment has been performed. Sensitivity and chronic reactivity tests have been performed in rodent models. Histology has been performed [START_REF] Badia | Biocompatibility of chronically implanted transverse intrafascicular multichannel electrode (TIME) in the rat sciatic nerve[END_REF] as well as investigations on selectivity of the transversal implantation of the intrafascicular electrode concept [START_REF] Badia | Comparative analysis transverse intrafascicular multichannel, longitudinal intrafascicular and multipolar cuff electrodes for the selective stimulation of nerve fascicles[END_REF].

Stability of the electrodes in the first-in-man-trial has been assessed by electrode impedance measurements during stimulation. Therefore, the magnitude of the voltage excursion of the cathodic phase was divided by the amplitude X. Navarro and V M Lozez-Alvarez are with the Department of Cell Biology, Physiology and Immunology, Faculty of Medicine, Universitat Autonoma de Barcelona, Bellaterra, Spain (xavier.navarro@uab.cat, victormanuel.lopez@uab.cat) D. Guiraud and T. Guiho are with the DEMAR Team, LIRMM, INRIA, University of Montpellier, Montpellier, France (David.Guiraud@lirmm.fr, thomas.guiho@inria.fr)

On biocompatibility and stability of transversal intrafascicular multichannel electrodes -TIME

Thomas Stieglitz, Tim Boretius, Paul Čvančara, David Guiraud, Thomas Guiho, Victor Manuel Lopez-Alvarez, Xavier Navarro I of the stimulation pulse. Explanted electrodes were investigated under light and scanning electron microscope. Focused ion beam was used to generate cross sectional views from the interfaces of the polyimide and the thin-film metallization.

Design and process changes have been applied based on the findings of the first human clinical trial. Modified TIME have been implanted in a second clinical trial.

III. RESULTS

Electrodes have been developed (Fig. 1) and characterized with respect to mechanical stability of the cable, stability of the thin-film under stimulation and biocompatibility in vitro and in vivo. Cables did not break over 250,000 bending cycles and stimulation sited did not show changes in charge injection capacity that was determined safe for up to 120 nC per stimulation site [START_REF] Raspopovic | Restoring Natural Sensory Feedback in Real-Time Bidirectional Hand Prostheses[END_REF]. Only mild foreign body reaction was investigated in preclinical studies [START_REF] Badia | Biocompatibility of chronically implanted transverse intrafascicular multichannel electrode (TIME) in the rat sciatic nerve[END_REF] with the electrodes in the nerve. Selectivity was superior to cuff and longitudinal intrafascicular electrodes [START_REF] Raspopovic | Restoring Natural Sensory Feedback in Real-Time Bidirectional Hand Prostheses[END_REF]. The TIME was stable and established a realiable interface with the ulnar and median nerve in a human for 30 days [START_REF] Raspopovic | Restoring Natural Sensory Feedback in Real-Time Bidirectional Hand Prostheses[END_REF]. Impedance measurements proved that 7 out of 8 counter electrodes and 50 out of 56 stimulation sites were working after 30 days.

Optical inspection after explantation showed intact electrode metal but delamination tendencies at large counter electrodes [START_REF] Čvančara | On the stability of implanted thin-film stimulation electrodes[END_REF]. Redesign of TIME resulted in segmented counter electrodes and inclusion of silicon carbide /diamond like carbon adhesion layers [START_REF] Ordonez | Thin-films and microelectrode arrays for neuroprosthetics[END_REF] to improve metal to polyimide adhesion. The connector assembly has been modified to reduce the number of handling steps. Electrodes have been certified "MR conditional" for 3 T MR imaging of the head. Currently, impedance monitoring of electrodes in the second clinical trial shows well performing electrodes after more than five months now.

IV. DISCUSSION

Polymer-based devices made out of a polyimide-thin-film sandwich showed to be an alternative [START_REF] Raspopovic | Restoring Natural Sensory Feedback in Real-Time Bidirectional Hand Prostheses[END_REF] to intraneural [START_REF] Davis | Restoring motor control and sensory feedback in people with upper extremity amputations using arrays of 96 microelectrodes implanted in the median and ulnar nerves[END_REF] and cuff-electrode [START_REF] Tan | A neural interface provides long-term stable natural touch perception[END_REF] arrays to chronically interface peripheral nerves in humans in the upper extremity. Stability of thin-film metallization is the key parameter that limits long-term implantation of these neural interfaces. Implanted electrodes are currently working well for about 5 months in a second clinical trial (unpublished data). Neural implants with a large number of electrode sites still use percutaneous wires in lack of fully implantable pulse generators with high channel count connectors. This situation is still the largest hurdle to transfer these neural interfaces into implantable medical products for a large patient population.

V. CONCLUSIONS Thin-film based multichannel electrodes proved to be able to establish a reliable and stable interface to peripheral nerves in human clinical trials. However, before commercialization into clinically approved devices can take place, fully implantable system solutions have to become available to make them attractive for chronic implantation.

  This work has been funded by the European Union within Framework program 7 in the projects TIME (CP-FP-INFSO 224012) and EPIONE (FP7-HEALTH-2013-INNOVATIO-1602547).

Fig. 1 .

 1 Fig. 1. TIME electrode consisting of micromachined electrode array, ceramic carrier, cable and connector. Inset shows details on arrangement of stimulation sites and counter electrode (GND).

ACKNOWLEDGMENT

The authors thank all project partners for valuable discussion and support in the projects. We thank our patients for their willingness to participate in the clinical trials and donating us so much of their life time.