Mathieu Nancel

Stanislav Aranovskiy

Rosane Ushirobira

Denis Efimov

Sébastien Poulmane

Nicolas Roussel

Géry Casiez

Next-Point Prediction for Direct Touch Using Finite-Time Derivative Estimation

Keywords: touch input, latency, lag, prediction technique

End-to-end latency in interactive systems is detrimental to performance and usability, and comes from a combination of hardware and software delays. While these delays are steadily addressed by hardware and software improvements, it is at a decelerating pace. In parallel, short-term input prediction has shown promising results in recent years, in both research and industry, as an addition to these efforts. We describe a new prediction algorithm for direct touch devices based on (i) a state-of-the-art finite-time derivative estimator, (ii) a smoothing mechanism based on input speed, and (iii) a post-filtering of the prediction in two steps. Using both a preexisting dataset of touch input as benchmark, and subjective data from a new user study, we show that this new predictor outperforms the predictors currently available in the literature and industry, based on metrics that model user-defined negative side-effects caused by input prediction. In particular, we show that our predictor can predict up to 2 or 3 times further than existing techniques with minimal negative side-effects.

INTRODUCTION

End-to-end latency in interactive systems is the sum of all hardware and software delays (e.g. sensing, recognition, stored memory, rendering) between a physical input and the displaying of its effects (e.g. respectively a key press and the appearance of the corresponding letter on screen).

Current direct touch systems present end-to-end latencies ranging from 50 to 280 ms [START_REF] Casiez | Characterizing Latency in Touch and Button-Equipped Interactive Systems[END_REF][START_REF] Ng | Designing for Low-latency Direct-touch Input[END_REF]. These values are above perception thresholds and degrade performance. Previous studies have shown that users can notice end-to-end latencies as low as 2 ms with a pen [START_REF] Ng | In the Blink of an Eye: Investigating Latency Perception During Stylus Interaction[END_REF] and 5 to 10 ms with a finger [START_REF] Ng | Designing for Low-latency Direct-touch Input[END_REF]. Performance is degraded from 25 ms in dragging tasks with a finger [START_REF] Jota | How Fast is Fast Enough? A Study of the Effects of Latency in Direct-touch Pointing Tasks[END_REF]. Deber et al. further show that improvements in latency as small as 8 ms are noticeable from a wide range of baseline latencies [START_REF] Jota | How Fast is Fast Enough? A Study of the Effects of Latency in Direct-touch Pointing Tasks[END_REF]. While we can expect that next generations of touch interactive systems will exhibit less latency using, for example, higher frequency input and output, this comes at the cost of higher power consumption and its complete suppression seems unlikely.

In combination with latency reduction, latency compensation using next-point prediction techniques offers a promising avenue to cope with latency. In dragging tasks, these techniques use previous touch positions to predict the next ones in a near future in order to estimate the current finger position [START_REF] Nancel | Next-Point Prediction Metrics for Perceived Spatial Errors[END_REF]. The existing prediction techniques are mainly based on Taylor series [START_REF] Cattan | Reducing Latency with a Continuous Prediction: Effects on Users' Performance in Direct-Touch Target Acquisitions[END_REF][START_REF] Lincoln | Position lag reduction for computer drawing[END_REF][START_REF] Wang | Touch tracking device and method for a touch screen[END_REF][START_REF] Zhao | Prediction-based touch contact tracking[END_REF][START_REF] Zhou | Electronic device and method for providing tactile stimulation[END_REF], Kalman filters [START_REF] Laviola | Double Exponential Smoothing: An Alternative to Kalman Filter-based Predictive Tracking[END_REF][START_REF] Liang | On Temporal-spatial Realism in the Virtual Reality Environment[END_REF][START_REF] Moussavi | Methods and apparatus for incremental prediction of input device motion[END_REF][START_REF] Wang | Multi-touch tracking method[END_REF][START_REF] Wu | On latency compensation and its effects on head-motion trajectories in virtual environments[END_REF], curve fitting [START_REF]Curve fitting based touch trajectory smoothing method and system[END_REF], heuristic approaches [START_REF] Kim | Mobile terminal and touch coordinate predicting method thereof[END_REF], and neural networks [START_REF] Henze | Software-reduced Touchscreen Latency[END_REF][START_REF] Henze | Improving Software-reduced Touchscreen Latency[END_REF]. Only a few of them have been evaluated [START_REF] Cattan | Reducing Latency with a Continuous Prediction: Effects on Users' Performance in Direct-Touch Target Acquisitions[END_REF][START_REF] Henze | Software-reduced Touchscreen Latency[END_REF]. Nancel et al. have shown that input prediction introduces noticeable side-effects such as jitter or spring-effect. They characterized and proposed metrics to measure these side-effects [START_REF] Nancel | Next-Point Prediction Metrics for Perceived Spatial Errors[END_REF]. They report that participants perceived latency as less disturbing than the side-effects introduced by current prediction techniques when trying to fully compensate latency. As a result, next-point prediction techniques can only be useful if they can compensate some of the latency while minimizing the side-effects they introduce.

We contribute a new prediction algorithm for direct touch devices designed to offer good trade-offs between latency reduction and side-effects. It is based on a state-of-the-art, finite-time differentiator that provides estimation of the first, second and third time derivatives of the input position in a predefined, limited time. It is combined with a smoothing mechanism that dampens the amplitude of the prediction depending on the user's input speed, to minimize jitter [START_REF] Casiez | 1e Filter: A Simple Speed-based Low-pass Filter for Noisy Input in Interactive Systems[END_REF][START_REF] Nancel | Next-Point Prediction Metrics for Perceived Spatial Errors[END_REF].

Using a pre-existing large dataset of touch input as benchmark, we show that this new predictor outperforms the predictors currently available in the literature and industry for direct touch input, based on metrics that model user-defined negative side-effects caused by input prediction. These results were then confirmed in a controlled user experiment.

The paper makes the following contributions:

• the introduction of the HOM finite-time derivative estimator to the HCI community, to go beyond computing derivatives limited to straightforward calculations,

• the adaptation of HOM to include a speed-based smoothing mechanism, and its first application to latency compensation with direct touch,

• the design and application of an optimization algorithm for the parameters of a HOM-based input predictor that can be adapted to system and user requirements,

• the validation of a stroke dataset from the literature to serve as benchmark for new predictors (in appendix),

• the formulation of a unique metric for the benchmarking of input prediction algorithms,

• an extensive, simulation-based validation of the resulting technique against state-of-the-art input predictors,

• a user experiment providing subjective comparison of our prediction technique against state of the art predictors, for different tasks and levels of compensation.

After addressing the related work we describe our prediction technique before detailing its evaluation.

RELATED WORK

Our review of the related work first covers measures and human factors related to end-to-end latency on direct touch surfaces before detailing current next-point prediction techniques and time derivative estimation methods.

End-to-end Latency in Direct Touch

In 2012 Ng et al. measured latency on various touch devices and found end-to-end latencies ranging from 60 to 200 ms [START_REF] Ng | Designing for Low-latency Direct-touch Input[END_REF]. More recently Casiez et al. found end-to-end latency on current touch devices ranging from 48 to 276 ms and show it is affected by the hardware, operating system and toolkit [START_REF] Casiez | Characterizing Latency in Touch and Button-Equipped Interactive Systems[END_REF]. The authors further show that the input latency (time from a physical action of the user on an input device to the reception of the corresponding event by the system) is in the range 14 to 25 ms using native toolkits on Android devices and that most of the end-to-end latency comes from the output latency (time elapsed between calling the repaint of the display and its actual update) which is affected by the operating system, graphic card and physical screen.

The impact of end-to-end latency on user perception and performance in direct touch interaction is well covered in the literature. For dragging tasks, users can reliably perceive touchscreen latency as low as 5-10 ms [START_REF] Ng | Designing for Low-latency Direct-touch Input[END_REF] as they can easily notice the physical distance between their finger and the associated visual stimulus [START_REF] Deber | How Much Faster is Fast Enough? User Perception of Latency & Latency Improvements in Direct and Indirect Touch[END_REF]. For tapping tasks, the perception threshold is higher at 24 ms [START_REF] Jota | How Fast is Fast Enough? A Study of the Effects of Latency in Direct-touch Pointing Tasks[END_REF]. The thresholds are even lower using a pen. Ng et al. reported 2 ms for dragging and 6 ms for scribbling [START_REF] Ng | In the Blink of an Eye: Investigating Latency Perception During Stylus Interaction[END_REF]. Jota et al. showed that performance is affected from 25 ms in dragging tasks with a finger [START_REF] Jota | How Fast is Fast Enough? A Study of the Effects of Latency in Direct-touch Pointing Tasks[END_REF].

To sum up, current systems show latencies above perception and performance thresholds. Ideally even the most efficient systems showing 50 ms latency should reduce their latency by 25 ms to prevent human performance degradation, and by 40 ms to make the latency un-noticeable. Deber et al. have also shown that improvements in latency as small as 8 ms are noticeable from a wide range of baseline latencies [START_REF] Jota | How Fast is Fast Enough? A Study of the Effects of Latency in Direct-touch Pointing Tasks[END_REF]. If one can expect current hardware will improve in a near future to reduce latency, its complete suppression is unlikely.

Next-point Prediction Techniques

Nancel et al. [START_REF] Nancel | Next-Point Prediction Metrics for Perceived Spatial Errors[END_REF] detailed existing related work on next-point prediction techniques that fall into four main categories: Taylor series [START_REF] Cattan | Reducing Latency with a Continuous Prediction: Effects on Users' Performance in Direct-Touch Target Acquisitions[END_REF][START_REF] Lincoln | Position lag reduction for computer drawing[END_REF][START_REF] Wang | Touch tracking device and method for a touch screen[END_REF][START_REF] Zhao | Prediction-based touch contact tracking[END_REF][START_REF] Zhou | Electronic device and method for providing tactile stimulation[END_REF], Kalman filter [START_REF] Laviola | Double Exponential Smoothing: An Alternative to Kalman Filter-based Predictive Tracking[END_REF][START_REF] Liang | On Temporal-spatial Realism in the Virtual Reality Environment[END_REF][START_REF] Moussavi | Methods and apparatus for incremental prediction of input device motion[END_REF][START_REF] Wang | Multi-touch tracking method[END_REF][START_REF] Wu | On latency compensation and its effects on head-motion trajectories in virtual environments[END_REF], curve fitting [START_REF]Curve fitting based touch trajectory smoothing method and system[END_REF] and heuristic approaches [START_REF] Kim | Mobile terminal and touch coordinate predicting method thereof[END_REF]. See Nancel et al. for a detailed description of these techniques [START_REF] Nancel | Next-Point Prediction Metrics for Perceived Spatial Errors[END_REF]. More recently Henze et al. used neural networks for prediction and found their technique to be more precise than first-, secondand third-order polynomial extrapolations [START_REF] Henze | Software-reduced Touchscreen Latency[END_REF][START_REF] Henze | Improving Software-reduced Touchscreen Latency[END_REF]. Their neural networks were trained on a very large data collection. We could unfortunately not integrate this technique in our study, as the data and code to train new networks to our experiment's latencies and device were not available at the time. The approach in [START_REF] Henze | Improving Software-reduced Touchscreen Latency[END_REF] and the one presented in this article thus remain to be compared.

If current next-point prediction techniques can compensate some of the latency, they also introduce prediction artifacts. Nancel et al. characterized the side-effects introduced by these techniques and noticed by participants and classified them in 7 categories: lateness, over-anticipate, wrong distance, wrong orientation, jitter, jumps, and spring effect [START_REF] Nancel | Next-Point Prediction Metrics for Perceived Spatial Errors[END_REF].

In addition they developed quantitative metrics that correlate positively with the frequency of perceived side-effects.

With the exception of the curve fitting and neural networks techniques, all other techniques rely on the use of speed and acceleration determined from the finger positions. These derivatives are estimated using simple time differentiation based on the two previously acquired positions or computed speeds. Simple time differentiation techniques have the benefit of being straightforward to implement and fast to execute. Furthermore they use the most recent information available and thus introduce a small latency in the estimation of speed or acceleration. However the resulting computation of speed and acceleration are generally noisy, which results in higher chances to notice side-effects. Yet, more advanced techniques to estimate derivatives also exist.

Time Derivative Estimation Techniques

Numerical differentiation is a key issue in the domains of signal processing and control engineering as it appears in many problems where a noisy signal needs to be reconstructed or filtered. There are many methods providing numerical differentiation with different levels of performance (the most important of them being sensitivity to measurement noises, computational complexity, and estimation delay). Popular techniques include statistical approaches such as the minimum least squares method [START_REF] Duncan | Numerical differentiation and parameter estimation in higher-order linear stochastic systems[END_REF]. In recent years, novel deterministic approaches have been proposed yielding good results in terms of robustness to noise and computational aspects.

In this framework, we may cite the approach based on the sliding mode methods [START_REF] Efimov | A Hybrid Robust Non-Homogeneous Finite-Time Differentiator[END_REF][START_REF] Levant | Robust exact differentiation via sliding mode technique[END_REF], algebraic methods [START_REF] Fliess | Non-linear estimation is easy[END_REF][START_REF] Ushirobira | A forecasting algorithm for latency compensation in indirect human-computer interactions[END_REF] or the homogeneous systems method [START_REF] Ménard | Fixed-time observer with simple gains for uncertain systems[END_REF][START_REF] Perruquetti | Finite-time observers: application to secure communication[END_REF]. Minimum least squares and sliding mode approaches either have to be computed off-line, or present significant chattering, defined as an undesirable phenomenon of oscillations with finite frequency and amplitude. Algebraic methods are robust to noise but introduce some delay in the estimations. The homogeneousbased differentiator has a fast rate of convergence and good robustness with respect to disturbances. It appears as the most appropriate numerical differentiation technique in the context of latency compensation. In the following we refer to this technique as 'HOM', short for homogeneous.

We clarify that the HOM finite-time derivative estimator is not a next-point prediction algorithm. It is a general-purpose method introduced in 2008 [START_REF] Perruquetti | Finite-time observers: application to secure communication[END_REF], initially to secure communications. This paper is highly cited in the control theory community, showing the method's applicability in various contexts, but never for latency compensation until 2016 [START_REF] Ushirobira | A forecasting algorithm for latency compensation in indirect human-computer interactions[END_REF].

In [START_REF] Ushirobira | A forecasting algorithm for latency compensation in indirect human-computer interactions[END_REF], the HOM differentiator was compared to other differentiators for basic latency compensation with a mouse. However that involved minimal validation, using small datasets and simplistic metrics based on predicted-to-actual distances; such metrics were later shown to be limited and possibly misleading [START_REF] Nancel | Next-Point Prediction Metrics for Perceived Spatial Errors[END_REF]. Therefore the results in [START_REF] Ushirobira | A forecasting algorithm for latency compensation in indirect human-computer interactions[END_REF] remain to be confirmed, especially for direct touch for which latency can be more noticeable than with a mouse. HOM has never been used for latency compensation with direct touch. In fact, despite its 10 years of existence it was never brought to the HCI literature, in which the typical method to compute derivatives remains mostly limited to straightforward calculations of the form (p i p i 1 )/(t i t i 1 ) relative to the last input event i, where p i is the value of the signal at the instant t i .

Another approach based on finite impulse response (FIR) filters has been proposed recently in [START_REF] Aranovskiy | Frequency domain forecasting approach for latency reduction in direct human-computer interaction[END_REF]. It demonstrates good robustness properties with respect to measurement noise, but still requires more computational capacities (involves matrix manipulations with 16 times 16 matrices for both X and Y) without a corresponding quality of differentiation improvement comparing to HOM differentiator. In addition the FIR has at least 16 tunable gains for each axis, against 5 for HOM.

THE TURBOTOUCH PREDICTOR

Given a measured position1 x m (t k ) at a time t k , the TURBO-TOUCH predictor (TTp) algorithm2 attempts to estimate a real object's position x(t k ) using features of the ongoing trajectory. The measured position is always sensed with a certain latency L:

x m (t k ) = x(t k L) In practice the value L is not constant, but for algorithm design and performance evaluation purposes we impose the assumption that an averaged constant value L 0 is available. Therefore, we can define the estimation error e(t k ) between the real position x(t k ) and its estimate x(t k ):

e(t k ) = x(t k ) x(t k ) ⇡ x m (t k + L 0 ) x(t k )
The approximate equality becomes exact assuming L 0 = L, in such a case the error between the real position x(t k ) and the estimate x(t k ) is exactly the difference between the further measured position x m (t k + L 0 ) and the estimate x(t k ).

Perhaps intuitively, there exists a trade-off between highfrequency oscillations of the predicted cursor, or "jitter", and how promptly a predicted cursor reacts to quick changes in trajectory or in speed. This trade-off is more noticeable when large amounts of latency need to be compensated. Nancel et al. [START_REF] Nancel | Next-Point Prediction Metrics for Perceived Spatial Errors[END_REF] reported that:

• estimators that use only the most recent measured positions tend to react faster to input change, but increase the chances of cursor jitter. Using points further away in the past lowers the risk of jitter, but delays the cursor's response to sudden changes of input speed and direction,

• participants' reports of jitter were negatively correlated with reports of "lateness" of the cursor, from which we infer that compensating smaller amounts of latency lowers the risks of noticeable jitter, but increase the noticeable lag,

• participants reported more jittery cursor movements when moving slowly. No correlation was observed between slow movements and reported "lateness", but it is trivial to calculate that, for a constant latency, lower speeds result in smaller-and therefore less noticeable-offsets.

To summarize, when most of the latency is to be compensated, estimations calculated from most "recent" measures react faster to sudden changes of trajectory, but increase the chances of jitter. Jitter, however, is more noticeable when the user is moving slowly.

To cope with the aforementioned trade-off, the main feature of the proposed design is that the prediction is smoothly turned off when the instant velocity of the controlled object, further denoted as V (t), is sufficiently low. This simultaneously limits jitter with admissibly small prediction error for low velocities, and provides fast cursor reactions for medium and high velocities.

The proposed estimator behaves according to the following rules, where V low is a general parameter.

• If V (t k ) V low , then the predictor behaves normally by extrapolating from the most recent features of the trajectory.

• If V (t k ) < V low , then the main goal of the estimator is to avoid any noise amplification, and a good strategy is to turn off estimation and bypass the measurements.

• To avoid discontinuities (jumps) in estimation, the switching is smoothed with an exponential weighting function.

• Finally, to remove any remaining noise in the predicted positions, we apply a light filtering using the 1e filter [START_REF] Casiez | 1e Filter: A Simple Speed-based Low-pass Filter for Noisy Input in Interactive Systems[END_REF].

Estimator Description

We use the estimator

x(t k ) = x m (t k ) + a(t k ) ⇣ f > x (t k ) • q x ⌘ (1)
where f > x (t k ) • q x is the estimation of the input movement since the most recently measured position x m (t k ). It is composed of an estimate of the vector of time derivatives

f x (t k ) := [x (1) m (t k ), x (2) m (t k ), x (3)
m (t k )] > and a constant gain vector q x 2 R 4 obtained by off-line optimization (see below). a(t k ) 2 R + is the exponential weighting function that implements the smoothing mentioned above.

The estimate fx (t k ) is computed using HOM [START_REF] Perruquetti | Finite-time observers: application to secure communication[END_REF].

s x (t k ) = HOM (s x (t k 1 ), x m (t k ), a x , l x , D t ) , fx (t k ) = [s x,2 (t k ), s x,3 (t k ), s x,4 (t k )] > , (2)
where s x (t k ) is the state vector of the differentiator, a x > 0 and l x 2 [ 0.2, 0] are the differentiator's parameters obtained by off-line optimization (see below) , and D t is the integration interval, a general parameter. The HOM is a discrete-time approximation of the continuous-time differential equation 2

6 6 6 4 ṡx,1 (t k ) ṡx,2 (t k ) ṡx,3 (t k ) ṡx,4 (t k ) ṡx,5 (t k ) 3 7 7 7 5 = 2 6 6 6 6 4 s x,2 (t k ) 5a x |e x (t k )| 1+ l x sign(e x (t k )) s x,3 (t k ) 10a 2 x |e x (t k )| 1+2l x sign(e x (t k )) s x,4 (t k ) 10a 3 x |e x (t k )| 1+3l x sign(e x (t k )) s x,5 (t k ) 5a 4 x |e x (t k )| 1+4l x sign(e x (t k )) a 5 x |e x (t k )| 1+5l x sign(e x (t k )) 3 7 7 7 7 5 (3)
with s x,i the i-th element of s x , and

e x (t k ) = s x,1 (t k ) x m (t k ).
The exponential weighting function a(t k ) above is computed as

a(t k ) = a(t k 1 ) + g a (a ? (t k ) a(t k 1 )) (4)
with 0 < g a < 1 a general parameter and

a ? (t k ) = ⇢ 1 if V (t k ) V low , 0 if V (t k ) < V low . (5)
The estimator's constant gain vector q x is obtained via off-line minimization of the estimation cost function defined below.

Readers will have noted that neither the actual latency L nor the expected average latency L 0 appear in the computations above. This is because L 0 is a parameter of the training process in which the values of a x , l x , and q x are optimized (see below). These values therefore correspond to a specific inputoutput setup (from which the training data is gathered) as well as a specific amount of latency compensation. Compensating for a new latency therefore requires to run a new optimization.

Note also that the parameters a x , l x and q x are obtained through an optimization process whose main purpose is to minimize metrics of prediction error, not to estimate speed, acceleration, and jerk as closely as possible to physical units. For that reason, the estimates ṡx,n (t k ) need to be remapped to physical scales before they can be used as estimations of speed, acceleration, or jerk, e.g. in Eq. 5:

V x (t k ) = µ ⇥ s x,2 (t k ).
The parameter µ is obtained through off-line optimization (see below).

Switched Estimator Algorithm

We now describe every step of a typical, real-time use of our switched estimator algorithm. For the sake of simplicity and understanding the algorithm is described in a 2D context but

xm(tk) sx(tk-1) !(tk-1) sx(tk) = HOM( xm(tk), sx(tk-1), !x, "x, #t ) $! [V(tk) ≥ Vlow] + (1 -$!) !(tk-1) xm(tk) + %x(tk) T &x !(tk) tk: tk-1: xm(tk-1)
x(tk-1) input:

output: input: output:

x(tk) Parameters. The estimator has the following parameters:

• the HOM parameters: a x , a y > 0, l x , l y 2 [ 0.2, 0], D t > 0 (integration time step)

• the gains q x , q y 2 R 3 ,

• the HOM conversion ratio µ,

• the velocity threshold V low 0,

• the smoothing parameter 0 < g a < 1.

Internal variables. The internal variables of the estimator are the timer variable t 2 R, the differentiator states s x , s y 2 R 5 , and the weighting variable a 2 R.

Initialization. At the first time instance t 1 set t = t 1 , s x (t 1 ) = [x m (t 1 ), 0, 0, 0, 0] > , s y (t 1 ) = [y m (t 1 ), 0, 0, 0, 0] > , a(t 1 ) = 0, x(t 1 ) = x m (t 1 ), ŷ(t 1 ) = y m (t 1 ).
Estimation. At each time instance t k , k > 1:

Step 1. Get the new measurements.

Step 2. Pre-process the measurements. This step includes: input data verification, units conversion and time frames adjustment between the estimator and the measurements provider. The output of this step are the preprocessed values t k , x m (t k ) and y m (t k ).

Step 3. Update the internal variable t and the states s x (t k ), s y (t k ) as follows:

(a) Set s x (t k ) = s x (t k 1 ) and s y (t k ) = s y (t k 1 ). (b) While t < t k , repeat: i. Compute e x (t k ) = s x,1 (t k ) x m (t k
) and e y (t k ) = s y,1 (t k ) y m (t k ), where s x,i and s y,i are the i-th elements of the vectors s x and s y , respectively. ii. Update Step 4. Compute the estimate of 2D velocity absolute value

s x (t k ) = s x (t k ) + 2 6 6 6 6 4 s x,2 (t k ) 5a x |e x (t k )| 1+l x sign(e x (t k )) s x,3 (t k ) 10a 2 x |e x (t k )| 1+2l x sign(e x (t k )) s x,4 (t k ) 10a 3 x |e x (t k )| 1+3l x sign(e x (t k )) s x,5 (t k ) 5a 4 x |e x (t k )| 1+4l x sign(e x (t k )) a 5 x |e x (t k )| 1+5l x sign(e x (t k )) 3
V (t k ) = µ q (s x,2 (t k )) 2 + (s y,2 (t k )) 2 ,
and a ? as

a ? (t k ) = ⇢ 1 if V (t k ) > V low , 0 if V (t k )  V low .
Step 5. Update the internal variable a as a(t k ) = a(t k 1 ) + g a (a ? (t k ) a(t k 1 )) .

Step 6. Define the estimates of derivatives

fx (t k ) = [s x,2 (t k ), s x,3 (t k ), s x,4 (t k )] > , fy (t k ) = [s y,2 (t k ), s y,3 (t k ), s y,4 (t k )] > .
Step 7. Compute the estimates

x(t k ) = x m (t k ) + a(t k ) f > x (t k )q x , ŷ(t k ) = y m (t k ) + a(t k ) f > y (t k )q y .
Step 8. Post-process the estimates. This step includes units conversion and time frames adjustment between the estimator and an output device.

Implemented in C++, the above algorithm results in about 150 lines of code without the use of any external function.

One prediction takes 1.5 µs on average (95 th percentile = 2 µs, max = 44 µs) on an i7 4GHz processor, a few orders of magnitude below the amount of latency considered.

Parameters Tuning

The parameters used in the algorithm can be divided into two groups: the general parameters and the optimizationbased parameters. The general parameters are tuned manually, taking into account physical and hardware specifications of the exact estimation problem and input/output devices. The optimization-based parameters are tuned using a given dataset of movements specific to the considered estimation problem, minimizing metrics described below.

General Parameters

The general parameters used at runtime are the integration interval D t > 0 and the parameters of the speed-based smoothing: the velocity threshold V low 0 and the smoothing gain g a 2]0, 1[. V low depends on visual tolerance, g a on behavior change tolerance, and D t on computational capabilities, as detailed below.

• D t is less or equal to the measurement period T s . This value is a trade-off between computational time and accuracy, and depends on the target hardware. It is typically expressed as a proportion p of the system's average sampling period: D t = p.T s . For example, in our benchmark below we use the whole period (p = 1) on a sampling frequency of 120 Hz, so D t = 1 ⇥ 1000/120 = 8.33 ms.

• V low defines the minimum velocity at which the estimator is activated. It corresponds to the input speed below which the system latency is considered not noticeable; in our case, when the visual lag is hidden under the finger. The general idea is to switch the estimator on at a velocity for which the lag becomes noticeable to most users. The following formula is proposed for its adjustment:

V low = E max L 0 ,
where E max is the maximal admissible error in distance units. For example, if we assume that the end-to-end latency is 68 ms and a typical user is affected by a deviation greater than 7 mm (as an estimation of finger radius), then a reasonable choice would be V low = 7mm 68ms ⇡ 100 mm/s. The value of V low may be updated given users feedback.

• 0 < g a < 1 defines the exponential smoothing transient decay time, g a = 1 0.05 Ts t transients , where t transients is the admissible transient time of switching between two modes of the estimator. Assuming a desired transient time of 0.33 ms with 120 Hz sampling frequency, the corresponding value of g a is computed as g a = 1 0.05 8.33ms 0.33s ⇡ 0.73. These rule-of-thumb formulae define initial values for our general parameters and we found them to work well in practice. These parameters could benefit from empirical tuning or extended exploration of their range and effects, but this is left to future work.

Two other general parameters are used in the optimization of the other predictor's parameters (see below):

• The expected average lag value L 0 . The shifted measurements x m (t k + L 0 ) are further used to optimize the estimator's parameters.

• The jitter lower frequency bound F b is the oscillation frequency above which cursor movements are interpreted as undesirable jitter. Along with F b we consider HFG low and HFG high , the jitter amplification levels considered as "low" and "high", see below for the details on amplification level computation procedure. Based on our experiments these values are chosen as F b = 7Hz, HFG low = 5 and HFG high = 6.

Optimized Parameters

The parameters tuned via optimization are the time differential gains q x , q y 2 R 3 , the HOM conversion ratio µ, and the HOM differentiator parameters a x , a y 2 R + and l x , l y 2 [ 0.2, 0]. Note that HOM has been used in very different domains, and many application-related methods have been developed to tune its parameters. Our tuning protocol follows the general principles of these existing methods, but is adapted to the specific problem of latency compensation.

The estimation algorithm considers each axis separately, so the corresponding parameters are optimized separately as well. However, the tuning procedure is the same. Below we describe the tuning procedure for the x axis only.

The input data set D consists of equally spread time instances t k and the corresponding measurements x m (t k ), k = 1,. .., N.

For the tuning procedure it is assumed that a sufficiently large data set is available representing all kinds of possible / admissible movements.

Metrics used

• The high-frequency gain HFG( x) represents how the estimator amplifies the input oscillation frequencies above F b with respect to the measured position. We compute this value as follows. First, using fast Fourier transform (e.g. Matlab's fft function) we remove from the signals x and x m all the components below the frequency F b . Then, the ratio of the L 1 norms of the filtered signals is computed and considered as the noise amplification level.

• The mean average estimation error is computed as

E 1 ( x) = 1 N N 0 N N 0 Â i=1 |x m (t i + L 0 ) x(t i )|,
where N 0 is the maximum integer below L 0 T s , i.e. latency value expressed in number of sampling intervals. The mean average error with respect to no estimation, is further denoted as

E 0 1 = 1 N N 0 N N 0 Â i=1 |x m (t i + L 0 ) x m (t i )|.
• The maximum estimation error is computed as

E • ( x) = max i |x m (t i + L 0 ) x(t i )|.
The maximum error with respect to no estimation, is further denoted as

E 0 • = max i |x m (t i + L 0 ) x m (t i )|.
• The cost function J( x) of the estimation is computed as

J( x) = k 1 J 1 ( x) + k 2 J 2 ( x) + k 3 J 3 ( x),
where k 1 > 0, k 2 > 0 and k 3 > 0 are tunning constants and

J 1 ( x) = E 1 ( x) E 0 1 , J 2 ( x) = E • ( x) E 0 • , J 3 ( x) = 8 > < > : 0 if HFG high  HFG( x) HFG( x) HFG low HFG high HFG low if HFG low < HFG( x) < HFG high 1 if HFG( x)  HFG low
In our experiments we have

k 1 = k 2 = k 3 = 1.
However, these values can be modified given user experience feedback.

Parameter tuning

With the above, for any given estimate x we can compute the performance index J( x). Our goal is to find values for the parameters a x , l x , and q x that produce predictions that minimize this performance index over the given dataset D. Recall that the parameters a x and l x are used to compute the output fx of the HOM differentiator (2), so we can write

fx (t k ) = fx (t k |a x , l x ) ,
and q x is used to compute the estimate x, see (1),

x (t k |a x , l x , q x ) = x m (t k ) + a(t k ) f > x (t k |a x , l x ) q x .
We therefore use two optimization loops. The inner loop considers a x and l x as input parameters and attempts to find the best q x for the given dataset D and HOM output fx (t k |a x , l x ).

The output of this inner loop is defined as J inner (a x , l x ), the lowest cost function score for the chosen a x and l x . The second, outer loop searches for a x and l x using the best output of the inner loop.

The tuning algorithm is described as follows.

1. Define the dataset D and choose initial guesses for a x , l x .

2. For the chosen a x , l x compute fx (t k |a x , l x ) for all t k .

3. Perform the inner loop optimization for the chosen a x , l x and compute J inner (a x , l x ).

3.A.

Choose initial guess for q x . 3.B. Compute the estimate x (t k |a x , l x , q x ) for all t k . 3.C. Compute the estimate cost function J ( x|a x , l x , q x ). 3.D. Update q x in order to decrease the cost function value.

3.E. Repeat steps 3B-3D until the optimal (minimum) value of J ( x|a x , l x , q x ) is obtained. Define the corresponding value of q x as q opt x . 3.F. Compute3 J inner (a x , l x ) = J x|a x , l x , q opt x . 4. Update a x , l x in order to decrease the value of J inner (a x , l x ).

5. Repeat steps 2-4 until the optimal (minimum) value of J inner (a x , l x ) is obtained 4 . Define the corresponding values of a x as a opt x and of l x as l opt x .

6. Calculate µ as the inverse slope of the linear regression with null intercept between the instantaneous input speed 2 from the last iteration of step 3E, using the whole training dataset.

V (t k ) = p (x k x k 1 ) 2 +(y k y k 1 ) 2 t k t k 1 and HOM's first derivative estimation V (t k ) = p (s x,2 (t k )) 2 + (s y,2 (t k ))
The obtained values a opt x , l opt x and the corresponding optimized gains q opt x are the desired estimator's parameters.

Finally, the predicted positions are smoothed using the 1e filter in two steps. First, we filter the distance between the last detected input location (x m , y m ) and the HOM estimate ( x, ŷ), and adjust the predicted point according to that smoothed distance without changing its orientation from (x m , y m ). The idea is to limit back-and-forth oscillations of the prediction, e.g. due to extrapolation of measurement errors, without introducing a delay in responding to changes of direction. Second, we filter the coordinates of the resulting position to reduce the remaining jitter. For simplicity, the same parameters are used for the 1e filter in both steps. The parameters we use correspond to very light filtering, to avoid introducing latency, but in practice they result in a noticeable reduction of jitter without sacrificing reactivity to direction change.

BENCHMARK VALIDATION

To validate our approach, we compared our predictor against existing predictors in the literature and industry, and for different levels of latency compensation. Previous work [START_REF] Nancel | Next-Point Prediction Metrics for Perceived Spatial Errors[END_REF] showed that simple distance-based metrics only cover a small part of the negative side-effects caused by input prediction, and can even correlate negatively with some of them. Asking participants to systematically describe what is wrong with each predictor, in each task, and for each level of latency, is a tedious process: trying and commenting on each condition takes a lot of time. Such a study protocol would either have limited repetitions, or increased chances of fatigue effects.

Instead, we used the dataset of touch input events described in [START_REF] Nancel | Next-Point Prediction Metrics for Perceived Spatial Errors[END_REF] and made available online5 so other practitioners can quickly simulate and evaluate new input predictors. This dataset consists of 6,454 input strokes (touch-down to touchup) from 12 different participants, about one hour each, performing three tasks: panning, target docking, and drawing.

See Appendix for an analysis of the input data's independence to the predictors that were active at the time of capture.

To compare these predictors, we also used 6 side-effectmodelling metrics from the same article: [START_REF] Nancel | Next-Point Prediction Metrics for Perceived Spatial Errors[END_REF]. Mo(D) are the modes of how Nancel et al.'s participants rated each side-effect in terms of disturbance, between 1 ("Not disturbing at all") and 5 ("Unbearable / Unacceptable"), taken from Table 1 in [START_REF] Nancel | Next-Point Prediction Metrics for Perceived Spatial Errors[END_REF].

These metrics take sets of input-and predicted coordinates as input, and return scalar values of arbitrary scales, that have been shown to correlate linearly with the probability that participants report the corresponding side-effect. We reused the linear functions reported in Table 5 in [START_REF] Nancel | Next-Point Prediction Metrics for Perceived Spatial Errors[END_REF] to obtain these probabilities.

In all of what follows, and similar to the authors' treatment in [START_REF] Nancel | Next-Point Prediction Metrics for Perceived Spatial Errors[END_REF], we discarded the 5% shortest and 5% longest strokes of the dataset in duration.

Simulation-based Comparison

We compared our own predictor (TTp), the Double-Exponential Smoothing Predictor (DESP) from LaViola [START_REF] Laviola | Double Exponential Smoothing: An Alternative to Kalman Filter-based Predictive Tracking[END_REF], and 4 out of the 5 predictors presented in [START_REF] Nancel | Next-Point Prediction Metrics for Perceived Spatial Errors[END_REF] (not counting the control condition without prediction) (Table 2). The remaining predictor is KALMAN which in [START_REF] Nancel | Next-Point Prediction Metrics for Perceived Spatial Errors[END_REF] behaved comparably to the control condition (no prediction). The authors hypothesized that "Assuming most predictions were observed to have a low accuracy [...] the predictor would rely very little on its own predictions" (p. 277).

Name Working principle From

FIRST First-order Taylor series [START_REF] Cattan | Reducing Latency with a Continuous Prediction: Effects on Users' Performance in Direct-Touch Target Acquisitions[END_REF][START_REF] Lincoln | Position lag reduction for computer drawing[END_REF] SECOND Second-order Taylor series [START_REF] Zhao | Prediction-based touch contact tracking[END_REF] CURVE Second order polynomial curve fitting [START_REF]Curve fitting based touch trajectory smoothing method and system[END_REF] HEURISTIC

Heuristic emphasis on speed or acceleration [13] DESP Double exponential smoothing [14] TTP Derivative estimator with speed threshold

Table 2: Predictors used in this study. Grey lines represent the predictors used in [START_REF] Nancel | Next-Point Prediction Metrics for Perceived Spatial Errors[END_REF].

We could confirm that hypothesis: as the amount of compensated latency increased, KALMAN was the only predictor in our tests that predicted less and less, i.e. closer and closer to the last detected finger location. We discard KALMAN in the following analysis.

The following simulations are performed as if the predictors were compensating a portion of a fixed end-to-end latency: 68 ms, the same as in the original data. For instance, when the Compensated Latency parameter is set to 24 ms, the sideeffect metrics will be calculated using that prediction 24 ms in the future against the actual finger position 68 ms in the future. This is different from Appendix II in [START_REF] Nancel | Next-Point Prediction Metrics for Perceived Spatial Errors[END_REF], where metrics were calculated as if every latency was fully compensated.

We optimized the TTP parameters using a sample set of 56 gestures corresponding to 54 seconds of input in total, captured with a high-resolution OptiTrack system. D t was set to 8.33 ms, V low to 102.94 mm/s, and g a to 0.73, as defined above. Optimizing for a value of latency takes under 10 min.

Traditional Metrics

We first present the 'traditional' metrics used in the literature to evaluate the goodness of predictors: the root-mean-square error (RMSE) and the 95 th percentile of the distance between the predicted and the actual finger locations:

Looking for effects of Predictor and Compensated Latency on the error metrics RMSE and 95 th distance, we ran a mixeddesign analysis of variance for each side-effect, considering participant as random variable using the REML procedure of the SAS JMP package. We found significant effects of Predictor for both RMSE (F 5,625 = 207.5, p < 0.0001) and 95 th distance (F 5,625 = 557.7, p < 0.0001). For RMSE, Tukey posthoc tests found TTP (mean 100.5 px) significantly worse than CURVE (81.7 px) and FIRST (79.1 px), and significantly better than SECOND (158.7 px), with non-significant differences with DESP (104 px) and HEURISTICS (94.2 px). For 95 th distance, TTP (193.5 px) was significantly worse than HEURIS-TICS (170.1 px) and FIRST (167.6 px), and significantly better than DESP (240.6 px) and SECOND (408.4 px), with nonsignificant differences with CURVE (178.6 px).

We also found significant effects of Compensated Latency for RMSE and of Predictor ⇥ Compensated Latency for RMSE and 95 th distance, but will not detail them further than Fig. 2.

The results above would indicate that TTP fares reasonably well overall, but not as good as some, especially FIRST. However Nancel et al. found in [START_REF] Nancel | Next-Point Prediction Metrics for Perceived Spatial Errors[END_REF] that these distance-based metrics can have a strong negative correlation with other sideeffects, notably Jitter and Jumps.

We then compared these 6 predictors using the side-effect metrics from [START_REF] Nancel | Next-Point Prediction Metrics for Perceived Spatial Errors[END_REF] described in Table 1. The procedure was twofold, first considering each metric separately, then integrating them all into a generalized score. In both cases, the scores were calculated over the entire dataset, and separately for each participant of the original study.

Scores per Side-Effect

We first compared the predictors on each metric independently, so we could observe specific trade-offs between the amount of compensated latency and the probability of individual negative side-effect.

Looking for effects of Predictor and Compensated Latency on the probability p(SE) to notice a side-effect, we ran a mixeddesign analysis of variance for each side-effect, considering participant as random variable. Unsurprisingly (Fig. 3), we found significant effects of Predictor, Compensated Latency, and Predictor ⇥ Compensated Latency, all p < 0.001. We will not detail the later two further than Fig. 3. TTP emerges as the most stable predictor (lowest Jitter and Jumps) by a significant margin, i.e. 7 to 36 times lower than other predictors, and belongs to the 'best' groups for all sideeffects except Lateness. Interestingly, the other 'best' predictors often swap rankings depending the side-effect under consideration. For instance, HEURISTIC was comparatively as good for Wrong Orientation but among the worst in Overanticipation; DESP was among the best in Over-anticipation and among the worst in Jitter. In short, existing predictors trade some side-effects for others, while TTP demonstrates probabilities of side-effects equivalent or lower than the best predictors for most individual side-effects.

What

Overall score

Regarding Lateness, this metric is calculated as the mean of distances between the predicted location of the finger and the actual location of the finger (without latency) when the predicted location is behind the direction of the movement. Predicted points that are ahead are not considered in this calculation: predictors that consistently over-anticipate, e.g. HEURISTIC and CURVE, will fare well at Lateness.

More importantly, Lateness is essentially why prediction occurs in the first place, and therefore the main cause for all the other side-effects. Yet at the same time, it is the side-effect with the lowest Disturbance scores in [START_REF] Nancel | Next-Point Prediction Metrics for Perceived Spatial Errors[END_REF] (Table 1), in which participants reportedly suggested that [perceived] latency was normal, and better than bad prediction errors.

We calculated a general prediction score S P for each predictor P consisting in the sum of the expected probability p(SE P ) of each side effect SE for this predictor, weighted by the disturbance score Mo(D) SE from Table 1 for that side-effect:

S P = Â SE p(SE P ) ⇥ Mo(D) SE (6)
We used this score to compare the predictors overall in terms of expected overall disturbance: Looking for effects of Predictor and Compensated Latency on the overall score S P , we ran a mixed-design analysis of variance, considering participant as random variable. Unsurprisingly (Fig. 4), we found significant effects of Predictor, Compensated Latency, and Predictor ⇥ Compensated Latency, all p < 0.001. We will not detail the later two further than Fig. 4.

What interests us here is how TTP fared against other predictors overall. Post-hoc Tukey tests showed that TTP obtains scores (mean 24.6) significantly lower than any other Predictor overall. HEURISTIC comes second (50.6), significantly lower than any remaining Predictor. CURVE (75.7) is significantly better than DESP (89.1), with FIRST insignificantly different from both. Finally, SECOND obtained scores significantly worse than any other predictor (112.9).

To get a finer picture, we re-ran the above analyses for each amount of Compensated Latency. In each case, there was a significant effect of Predictor (p < .001), and Tukey post-hoc tests showed that TTP was either significantly better or nonsignificantly different from all other predictors in every case.

EXPERIMENT

In order to confirm the results of our benchmark, we ran a controlled experiment on an interactive tablet to gather and compare the opinions of real users on the aforementioned predictors. The experiment involved performing different tasks and different amounts of compensated latency. Participants were asked to rate the acceptability of each condition (Predictor ⇥ Task ⇥ Latency compensation). That yielded significantly more conditions than in [START_REF] Nancel | Next-Point Prediction Metrics for Perceived Spatial Errors[END_REF] (through the Latency compensation factor), so we asked participants to report existing side-effects rather than describe all issues themselves.

Participants

We recruited 9 participants: 2 left-handed, 2 female, aged 22 to 41 (µ 30.8, s 7.9). All were frequent computer users and used touch input more than one hour per day. Participants were not compensated.

Apparatus

Experiment software was implemented in C++ using Qt 5.9 on an iPad Pro 10.5" (Model A1701) running iOS 11.2. Using Casiez et al.'s method [START_REF] Casiez | Characterizing Latency in Touch and Button-Equipped Interactive Systems[END_REF], we determined an average 52.8 ms latency (SD 2.8). To get a latency comparable to Nancel et al., who used a Microsoft Surface Pro with an average latency of 72.6 ms [START_REF] Nancel | Next-Point Prediction Metrics for Perceived Spatial Errors[END_REF], we added 20 ms of artificial latency by buffering touch events. In this way we can compare more easily the results of this experiment to the results of the simulations. The iPad Pro's input frequency is 120 Hz, the same as reported in [START_REF] Nancel | Next-Point Prediction Metrics for Perceived Spatial Errors[END_REF].

Conditions

Compensated Latency

We presented participants with five levels of compensated latency: 0, 16, 32, 48, and 64 ms. That is a coarser granularity than in the benchmark above, but allowed us to experiment on different levels of latency compensation while ensuring that the experiment remained in realistic durations.

Tasks

We presented participants with three tasks: Drawing, similar to [START_REF] Nancel | Next-Point Prediction Metrics for Perceived Spatial Errors[END_REF], in which participants were instructed to draw a shape that was displayed on the background of the tablet (Fig. 5-a) with their finger at different speeds, along with anything else they wanted; Dragging, also similar to [START_REF] Nancel | Next-Point Prediction Metrics for Perceived Spatial Errors[END_REF], in which participants were instructed to drag a square object around with their finger and attempt to drop it within one of four square targets (Fig. 5-b), a task they could repeat as often as they wanted; and Writing, in which participants were instructed to write anything they wanted using their finger on the tablet. Specific minimization objectives such as "click the target as fast as you can" or "follow the shape as precisely as possible" impose constraints on user movements, which in turn might favor-or hide-side-effects caused by slow vs. fast movements, straight vs. curved vs. angled trajectories, etc.; improving performance also does not necessarily mean less noticeable prediction side-effects. We therefore applied the same design as [START_REF] Nancel | Next-Point Prediction Metrics for Perceived Spatial Errors[END_REF], i.e. looser instructions to encourage free exploration of the various conditions and favor larger ranges of "good" and "bad" predictor behaviors. Systematic assessment of performance with TTP is left for future work.

In all tasks the prediction was only used for immediate feedback: last part of the stroke starting from the last detected input for Writing and Drawing, object location for Dragging. Traces, the dragged object's location after release, and stored data if it were a real application, correspond to detected input.

Predictors

The predictors were the same as in the benchmark study: FIRST, SECOND, HEURISTIC, CURVE, DESP, and TTP. The names of the predictors were anonymized ("Technique 1", "Technique 2", etc.). For TTP we ran the optimization described in subsection "Parameters Tuning" above (p. ), and calibrated the parameters of the 1e filter by hand, for each level of latency compensation. As a result of this tuning, filtering was deactivated for 16 ms, the Beta parameter [START_REF] Casiez | 1e Filter: A Simple Speed-based Low-pass Filter for Noisy Input in Interactive Systems[END_REF] was set to zero in all remaining cases, and the cutoff frequency parameter was set to 45, 20, and 15 Hz respectively for 32, 48, and 64 ms of latency compensation.

Procedure

After being explained the goals and procedure of the experiment, participants were demonstrated each task on the tablet. A trial corresponds to one condition: Predictor, Task, Amount of compensated latency. In each trial, participants were instructed to use the touch interface for as long as they wanted in order to form an opinion regarding (a) whether they noticed issues with the interface, (b) how disturbing those issues were, and whether that would in their opinion prevent its use in a real setting, and (c) which issue was observed among a subset of the side-effects list discussed in [START_REF] Nancel | Next-Point Prediction Metrics for Perceived Spatial Errors[END_REF].

More precisely, after having spent some time in each condition, participants were instructed to:

1. Rate the acceptability of the predictor in that condition on a scale with values "No noticeable issue" (1), "Noticeable issues, but fine" (2), "Some issues, still usable" (3), "Issues, barely usable" (4), and "Unbearable / unacceptable" (5) 6 ; that scale mirrors the questionnaire used in [START_REF] Nancel | Next-Point Prediction Metrics for Perceived Spatial Errors[END_REF],

2. Tell whether they would not consider using this predictor in daily personal or professional use, and 3. If they would not, list the issues that justify that rejection from a list of side-effects composed of the six described in Table 1, and of two more reported by Nancel et al. as frequently used by their participants [START_REF] Nancel | Next-Point Prediction Metrics for Perceived Spatial Errors[END_REF]:

The acceptability rating set (1. above) is in the form "one neutral, four negatives", as per the studied problem: our goal is to distinguish levels and types of "imperfectness" in the predictions. A perfect prediction feels normal, and can only be observed by comparison to imperfect ones, e.g. through lateness or unwanted interface behaviors. Random: Could not understand the logic behind some aspects or all of the prediction trajectory.

Participants could also describe issues that were not in the list, but no other side-effect was reported.

Design

The presentation of the predictors and tasks was counterbalanced using two Latin Square designs, predictors first: all tasks were completed for a given predictor before switching to the next predictor. The ordering of the latency compensation was constant and increasing, from 0 ms to 64 ms.

In the end we obtained ratings and raw input and predicted data for 9 (participants) ⇥ 6 (predictors) ⇥ 3 (tasks) ⇥ 5 (latency) = 810 conditions. The study lasted 1 hour on average for each participant.

Results

We recorded a total of 10,270 strokes but removed the first 5 th duration percentile (< 12 ms) and last 5 th percentile (> 4629 ms) as Nancel et al. did [START_REF] Nancel | Next-Point Prediction Metrics for Perceived Spatial Errors[END_REF], leaving a total of 9,242 strokes.

In each Predictor⇥Task condition, participants spent on average 1 min (SD 0.6) interacting with the touch surface (sum of stroke durations). Participants spent on average 2.9 min (1.1) interacting with each Predictor. A multi-way ANOVA reveals that Task had a significant effect on interaction duration (F 2,136 = 5, p = .0079), with Writing conditions (mean 0.8 min) taking significantly longer than Drawing and Dragging (1 min).

Acceptability Ratings

Ratings in absolute value are represented in Fig. 6, aggregated for all participants and all tasks (the lower the better).

As it could be expected, we observe strong discrepancies between the ratings of each participant. For instance, two participants (P3, P7) never used ratings of 4 or above, one (P7) never used the 5th. Conversely, four participants (P5, P7-9) rated all amounts of compensated latency 3 or worse in at least one combination of Predictor ⇥ Task, including with the typical amounts of compensated latencies 0 and 16 ms.

Despite that, visual inspection of the means and confidence intervals (CI) reveal a clear trend in favor of TTP overall, and for amounts of compensated latencies of 32 ms and above. We ran a multi-way ANOVA by treating acceptability ratings as continuous values between 1 and 5 (the lower the better), and modeling participant as a random variable using SAS JMP's REML procedure. It confirmed that acceptability ratings were significantly affected by Predictor (F Due to the variability in the range of each participant' responses, we also inspected the ordering of these ratings. For each (Participant ⇥ Task ⇥ Latency) combination, we ranked each predictor from best (1) to worst [START_REF] Cattan | Reducing Latency with a Continuous Prediction: Effects on Users' Performance in Direct-Touch Target Acquisitions[END_REF]. We treated ties 'optimistically': equal ratings were considered ex-aequo and to the lowest ranking; for instance, if in a given condition the predictors A, B, C, D, E, F had ratings of 1, 1, 2, 3, 4, 4, their corresponding rankings would be 1, 1, 3, 4, 5, 5.

With this method, TTP was ranked first (including ties) 92.6% of the time, second 6.7% of the time, third 0.7% of the time, and never further. By comparison, the other predictors were ranked first 29.6 to 45.2% of the time, second 33.3 to 45.2% of the time, third 12.6 to 28.9% of the time, and fourth 1.5 to 9.6% of the time.

If we break down these rankings per level of compensated latency, we find that TTP was only ever ranked third with 0 ms of compensation. For 16, 32, and 64 ms it was ranked first (incl. ties) respectively 85.2, 92.6, and 96.3% of the time, second the rest of the time. For 48 ms it was always ranked first. Except at 0 ms (where all predictors are equivalent), no other predictor come near this level of plebiscite.

To summarize, TTP obtained consistently better ratings than all other predictors, both in absolute value and in ranking. Participants' average ratings ranged between 1 ("No noticeable issue") and 2 ("Noticeable issues, but fine") in all conditions, including up to 48 and 64 (Fig. 6).

Rejection for Real Use

In each Predictor ⇥ Task ⇥ Latency condition, participants were asked whether they would not consider using this predictor at this compensation setting in a similar task, for daily personal use and daily professional use (2 separate questions).

It is not trivial to perform traditional statistical analyses on such a question as a single measure. We cannot simplify it as 'the lowest level they started rejecting the predictor for that task' because it happened that participants ticked the box for a given level of latency compensation and not for higher levels. The corresponding data is essentially a binary variable for every combination of Participant ⇥ Predictor ⇥ Task ⇥ Latency, which can only be studied as a whole by considering histograms of responses. In what follows we limit our analysis to an inspection of number of responses.

Similarly to acceptability ratings, we observe a discrepancy between the participants' tolerance to prediction side-effects. For instance, for personal use, three participants (P2, P5, P8) rejected predictors at least once for each amount of compensated latency, i.e. including when there was no latency compensation at all (0 ms), while five (P1, P3-4, P6-7) only rejected conditions with 32 ms of compensation or higher; two (P3-4) only rejected conditions with 48 ms of compensation or higher. All participants but one (P8) were equally or more tolerant to perceived side-effects when considering personal use than when considering professional use. Counts of rejections are represented in Fig. 7. Upon simple visual inspection, we observe that participants' rejection of the TTP predictor tends to drop as the level of compensated latency increases, up until 32 and 48 ms for respectively personal and professional use. Rejection of all other predictors steadily increases starting from 0 or 16 ms.

Observed Side-effects

When a participant rejected a given condition, they were instructed to indicate the causes for that rejection. These measures have the same format as above: some participants for example reported "lateness" for low levels of compensation only and other issues starting from e.g. 32 ms. We therefore limit this analysis to an inspection of number of responses. Counts of mentions of each side-effect are shown in Fig. 8. We can make several observations: (1) "Jumps" and "Random behavior" are reported at least once for all predictors except TTP; "Multiple feedback" is reported at least once for all predictors except TTP and DESP. ( 2) "Spring effect" and "Wrong orientation" are reported for all predictors at least at 48 ms of compensation except for TTP for which it is only reported at 64 ms. (3) "Lateness" has been reported for all predictors, and at all levels of compensation except for HEURIS-TIC at 48 ms and above, and for TTP at 64 ms; while among the highest for 0 and 16 ms, reports of "Lateness" with TTP quickly drop starting from 32 ms. (4) "Jitter" and "Overanticipation" were reported at all levels above 0 ms for every predictor, but remain consistently lowest for TTP.

Breaking Down by Task

Inspecting the above results task by task reveals trends similar to [START_REF] Nancel | Next-Point Prediction Metrics for Perceived Spatial Errors[END_REF]. "Lateness" was mostly reported with Dragging (77.9% of reports), possibly because the finger was hiding most of the delay (in Drawing and Writing the prediction was connected to the last detected point by the stroke), and because participants are used to latency in direct touch. "Jitter" and "Jumps" were mostly reported with Dragging (resp. 77.2 and 75.2%), again possibly because the finger was hiding most of the trembling-in contrast, the dragged object was larger than the finger. "Over-anticipation" was reported at lower levels of compensation with Writing than with the two other tasks: all predictors but FIRST had reports at 16 ms in this task, while in Dragging and Drawing the reports start at 32, 48, or 64 ms. This is possibly because writing gestures are curvier and, being heavily practiced, faster than drawing and dragging gestures, eliciting brisker responses from the predictors. Finally, "Over-anticipation" was only reported at 64 ms of compensation with TTP for DRAGGING and DRAW-ING, while for all other predictors it was reported starting at 32 or 48 ms with these tasks.

Comparison with Benchmark Study

The findings from the benchmark and user studies were very similar: TTP was found consistently less disturbing both in theory (benchmark, see e.g. Fig. 4) and in practice (controlled study, Fig. 67). Issues of jitter, jumps, and spring effect were very seldom reported (Fig. 8), as predicted (Fig. 3). Reports of over-anticipation stayed low until 48 ms before rising suddenly, in both cases. Finally, some side-effects went even better in practice than predicted: reports of lateness experienced a steady drop starting from 32 ms, and disappeared for 64 ms; and wrong orientation was only observed at 64 ms.

Overall, the results of both studies speak in favor of using TTP at higher levels of latency compensation than the other predictors we tested. Participants 'rejected' the use of TTP for professional use less often at 32 and 48 ms of compensated latency than at any other amount, including 0 ms (Fig. 7). All side-effects but lateness, over-anticipation, and jitter were never reported for TTP at these levels of compensation, and the latter three were minimal compared to other predictors. This, we conclude, strongly supports our hypothesis that TTP can be used to forecast direct touch input further in the future than existing approaches.

DISCUSSION AND FUTURE WORK

We presented a new algorithm for next-point input prediction based on three components: (i) a state-of-the-art differentiator to quickly and accurately estimate the instantaneous time derivatives of the input movement in real time, (ii) a speedbased smoothing mechanism to solve the lateness/jitter tradeoff, and (iii) a two-step filtering of the resulting prediction to further decrease jitter without sacrificing angular responsiveness. The effectiveness of the resulting predictor, as demonstrated in a benchmark and a user study, can result from any or all of these components. In effect, the speed-based smoothing and two-steps filtering could theoretically benefit any prediction algorithm. The study of the individual effects of each component is left for future work.

We will also investigate the efficiency of TTP when using other common devices such as direct styli and indirect mice, and whether the calibration processes need to be adjusted in those setups.

Finally, predictors using more complex approaches such as Kalman filters and neuron networks could not be tested in this work for lack of accessible calibration procedures, but those approaches are very promising and we would like to compare them to our predictor in future work.

CONCLUSION

We presented a new prediction technique for direct touch surfaces that is based on a state-of-the-art finite-time derivative estimator, a smoothing mechanism based on input speed, and a two-step post-filtering of the prediction. Using the dataset of touch input from Nancel et al. as benchmark we compared our technique to the ones of the state-of-the-art, using metrics that model user-defined negative side-effects caused by input prediction errors. The results show that our prediction technique presents probabilities of side-effects equivalent or lower than the best predictors for most individual side-effects. This was confirmed in a user study in which participants were asked to rate the disturbance of existing predictors at different levels of latency compensation: our technique shows the best subjectives scores in terms of usability and acceptability. It remains usable up to 32 or 48 ms of latency compensation, i.e. two or three times longer than current techniques.

Figure 2 :

 2 Figure 2: Effects of Compensated Latency and Predictor on typical distance-based error metrics.

Figure 3 :

 3 Figure 3: Effects of Compensated Latency and Predictor on the probability to notice each side-effect.

Figure 4 :

 4 Figure 4: Expected disturbance score per Predictor and Latency Compensation. Error bars are 95% confidence intervals.

Figure 5 :

 5 Figure 5: Visual backgrounds of the tasks: (Left) in Drawing, a shape was displayed on the background, including straight and curves lines, and angles. (Right) in Dragging, four target squares were displayed at the corners of the display, slightly larger than the dragged object.

Figure 6 :

 6 Figure 6: Left: Average ratings for each predictor. Right: Average ratings for each predictor and amount of compensated latency. Error bars are 95% confidence intervals.

Figure 7 :

 7 Figure 7: Number of times the participants responded that a particular condition (Predictor ⇥ Task ⇥ Latency) would not be suitable for real use, either personal or professional, by amount of predicted latency.

Figure 8 :

 8 Figure8: Number of times the participants responded that a particular condition side-effect caused her rejection of a predictor for each level of compensated latency. Single points represent predictors for which a given side-effect was only reported for a unique level of compensation.

  Figure 1: General description of real-time prediction process, with step numbers. Input in green, previously computed variables in blue, general parameters in yellow, optimized parameters in orange.

	prediction:
	1,2
	prediction:		Time
		3	derivatives
			estimation
	√( sx,2(tk) 2 + sy,2(tk) 2 )	4	Speed-
			based
	5		smoothing
	6
	7		Input prediction
	8

could be easily extended in 3D. It can also be adapted for rotations or any other input channel used for pointing. Input signals. At each step the input signals are the time instance t k and the measurements x m (t k ), y m (t k ). Output signals. At each step the output signals are the estimations x(t k ), ŷ(t k ).

Table 1 :

 1 Negative side-effects reported by participants in

	Metric	Mo(D)	Description
	Lateness	1	"late, or slow to react"
	Over-anticipation	4	overreaction, "too far ahead in time"
	Wrong orientation	4	compared to input motion
	Jitter	5	"trembling around the finger location"
	Jumps	5	"jumping away from the finger at times"
	Spring Effect	2	"yo-yo around the finger"

  interests us here is how TTP fared against other predictors overall. Post-hoc Tukey tests showed that TTP caused significantly less Jitter (mean 1.6% vs. 11.9 to 56.9%) and Jumps (3.2% vs. 10.8 to 37%) than any other predictor that we tested. It was significantly better on Wrong Orienta-

	SECOND,
	HEURISTIC, and CURVE (resp. 20.8, 19.4, 9.2%), and not
	significantly different from the others: DESP (8%) and FIRST
	(8.3%). Finally, for Lateness, TTP (15.5%) was significantly
	better than SECOND (17.3%), significantly worse than FIRST,
	HEURISTIC, and CURVE (9.3 to 10.2%), and not significantly
	different from DESP.

tion (16.1%) than all other predictors (18.7 to 23.8%) except HEURISTIC (14.5%) from which it wasn't significantly different. It was significantly better on Spring Effect (8.3%) than HEURISTIC and SECOND (resp. 22.3 and 16.3%), and not significantly different from the others (8 to 8.4%). It was significantly better at Over-anticipation (6.8 %) than

The calculations that follow are described for the x coordinate only for simplicity, and must be performed for y as well in real use.

Our prediction algorithm and tuning process are available at ns.inria.fr/loki/TTp/.

The steps 3B-3E can be realized with a proper unconstrained optimization toolbox, e.g. fminsearch in Matlab.

[START_REF] Casiez | 1e Filter: A Simple Speed-based Low-pass Filter for Noisy Input in Interactive Systems[END_REF] The steps 2-5 can be realized with a proper constrained optimization toolbox, e.g. fmincon in

Matlab.[START_REF] Cattan | Reducing Latency with a Continuous Prediction: Effects on Users' Performance in Direct-Touch Target Acquisitions[END_REF] http://ns.inria.fr/mjolnir/predictionmetrics/

Participants were presented the rating labels, not the corresponding numbers. For readability we only report numbers in what follows.Multiple feedback: Seemed like more than one visible feedback at the same time.

ACKNOWLEDGMENTS

This work was supported by ANR (TurboTouch, ANR-14-CE24-0009).

APPENDIX: DATASET VALIDITY

The set of strokes that were used as input in this paper's benchmark study comes from previous work [START_REF] Nancel | Next-Point Prediction Metrics for Perceived Spatial Errors[END_REF], but to our knowledge such an offline validation has not been tried yet.

We must first verify a core requirement. Each stroke in this dataset was gathered when a predictor was active (Fig. 9-a). In order to be reusable as realistic input for new predictors, the strokes must be reasonably independent from that predictor, otherwise the simulated behavior of a new predictor using this data as input cannot be generalized.

To this extent, we calculated the predicted input corresponding to each predictor from [START_REF] Nancel | Next-Point Prediction Metrics for Perceived Spatial Errors[END_REF] (gray rows in Table 2), but using strokes from the entire dataset. We then calculated the side-effect-modeling metrics in Table 1 using these in-put+simulated coordinates, for different amounts of compensated latency: 8, 16, 24, 32, 40, 48, 56, 64, and 68 ms. These processes are illustrated in Fig. 9-b,c. In the following we call CAPTURE the predictor that was active at the time of capture of the strokes in the dataset (Px in Input Px in Fig. 9), and SIM-ULATED the predictor we applied to these input strokes in the current process (Px in Prediction Px in Fig. 9). a) Process in [START_REF] Nancel | Next-Point Prediction Metrics for Perceived Spatial Errors[END_REF]: [START_REF] Nancel | Next-Point Prediction Metrics for Perceived Spatial Errors[END_REF]. (b) Independence test: all input strokes are used to simulate all predictors (except the control condition with no prediction). (c) Consistency test: all input strokes but the ones used in [START_REF] Nancel | Next-Point Prediction Metrics for Perceived Spatial Errors[END_REF] by a given predictor are used to simulate that predictor (except for the control condition). Latencies are not displayed for clarity.

The validity of the dataset to simulate the effects and effectiveness of new input predictors relies on two hypotheses: Independence: For each metric and each compensated latency, the CAPTURE predictor should not affect the resulting metrics values (Fig. 9-b).

An analysis of variance (ANOVA) investigating the effects of CAPTURE on the probability that users would notice each side-effect (p(SE)), for each corresponding metric [START_REF] Deber | How Much Faster is Fast Enough? User Perception of Latency & Latency Improvements in Direct and Indirect Touch[END_REF] and each latency [START_REF] Fliess | Non-linear estimation is easy[END_REF], found no significant effect in all of the 54 combinations (Fig. 10-left). Note that running the same analysis, but investigating the effects of SIMULATED instead, does find systematic significant effects (p < .0001 in all 54 cases, see Fig. 10-right for an example). This is not surprising: different predictors applied to a given input dataset are expected to produce different side-effects. Consistency: The metric values obtained through simulation, i.e. when CAPTURE6 = SIMULATED(Fig. 9-c), should match the metrics values originally obtained in [START_REF] Nancel | Next-Point Prediction Metrics for Perceived Spatial Errors[END_REF] with CAPTURE.

We define a decision variable ORIGINAL that equals 1 if CAP-TURE= SIMULATED and 0 otherwise. An ANOVA investigating the effects of ORIGINAL on the resulting metrics values, for each metric and each latency, found no significant effect in all of the 54 combinations. These results support both the Independence and Consistency requirements, confirming that the data from Nancel et al. can be used to evaluate new predictors.


Clotilde Ribaut

Guillaume Bordeau

Pierre Perio

Karine Reybier

Valeŕie Sartor

Olivier Reynes

Paul-Louis Fabre

Nadia Chouini-Lalanne

EPR Spectroelectrochemical Investigation of Guanine Radical Formation and Environment Effects

Guanine radical detection was carried out by a new convenient and efficient method coupling electron paramagnetic resonance spectroscopy and indirect electrooxidation of guanine in different biological environments, from the free nucleotide to several types of DNA substrates. Compared to the widely used photoirradiation method, this method appeared more selective in the choice of the electrochemical mediator. Carried out in presence of a ruthenium mediator and PBN as spin trap, this method revealed two types of EPR spectra depending of the environment of the guanine radical. Both EPR spectra show the trapping of the neutral guanine radical G(-H) • obtained after fast deprotonation of the radical cation G •+ . However, they differ by the atom where the trapped radical is centered. This difference highlights the structural dependency of the environment on the nature of the radical formed. This work gave the evidence of an innovative method to detect in situ the guanine radical.

■ INTRODUCTION

Guanine radical is a key intermediate in the charge transfer processes responsible for DNA damage. [START_REF] Giese | Long-Distance Charge Transport in DNA: The Hopping Mechanism[END_REF] It is well-known that exposure to ionizing and ultraviolet radiation or reactive chemical species can lead to oxidative damage to DNA, a common event at the origin of mutagenesis, cell death and cancer. [START_REF] Dizdaroglu | Oxidatively Induced DNA Damage: Mechanisms, Repair and Disease[END_REF] Among the four bases, which composed the DNA, guanine is the main target as indicating by its lowest oxidation potential. [START_REF] Saito | Mapping of the Hot Spots for DNA Damage by One-Electron Oxidation: Efficacy of GG Doublets and GGG Triplets as a Trap in Long-Range Hole Migration[END_REF] In neutral aqueous solution, the one-electron oxidation of guanine residues leads initially to the guanine radical-cation (G •+ ). This radical-cation is rapidly converted into a neutral radical by deprotonation or hydrolysis (G(-H) • or G • ), which gives various two-and four-electron oxidation products according to the media. [START_REF] Joseph | One-Electron Oxidation of DNA: Reaction at Thymine[END_REF][START_REF] Rokhlenko | Lifetimes and Reaction Pathways of Guanine Radical Cations and Neutral Guanine Radicals in an Oligonucleotide in Aqueous Solutions[END_REF] Herein, we propose a new convenient method to detect and analyze the guanine radical.

The guanine radical species detection involves specific techniques due to its short lifetime, including UV-visible spectra, [START_REF] Galano | Guanosine + OH Radical Reaction in Aqueous Solution: A Reinterpretation of the UV-Vis Data Based on Thermodynamic and Kinetic Calculations[END_REF] flash-quench technique, [START_REF] Stemp | The Flash-Quench Technique in Protein-DNA Electron Transfer: Reduction of the Guanine Radical by Ferrocytochrome c[END_REF] pulse radiolysis, [START_REF] Steenken | How Easily Oxidizable Is DNA? One-Electron Reduction Potentials of Adenosine and Guanosine Radicals in Aqueous Solution[END_REF] laser flash photolysis [START_REF] Saito | Photoinduced DNA Cleavage via Electron Transfer: Demonstration That Guanine Residues Located 5′ to Guanine Are the Most Electron-Donating Sites[END_REF] and electron paramagnetic resonance. [START_REF] Schiemann | EPR Detection of Guanine Radicals in a DNA Duplex under Biological Conditions: Selective Base Oxidation by Ru(phen) 2 dppz 3+ Using the Flash-Quench Technique[END_REF] Studies on guanine radical are mainly focused on photoirradiation in the presence of photosensitizers including anthraquinones, [START_REF] Shao | Sequence Dependence of Charge Transport through DNA Domains[END_REF] naphtalimides, riboflavin and ruthenium complexes, [START_REF] Arkin | Long-Range Oxidation of Guanine by Ru(III) in Duplex DNA[END_REF] in order to oxidize the guanine. To the best of our knowledge, only few reports took an interest in other guanine oxidation techniques including the hydroxyl ( • OH) radical strong oxidant, [START_REF] Galano | Guanosine + OH Radical Reaction in Aqueous Solution: A Reinterpretation of the UV-Vis Data Based on Thermodynamic and Kinetic Calculations[END_REF] or electrooxidation, even though electrochemical oxidations are currently attractive. [START_REF] Costentin | Effect of Base Pairing on the Electrochemical Oxidation of Guanine[END_REF] Some studies focused on direct electrooxidation of nucleobases using specific electrodes such as pretreated glassy carbon electrode, [START_REF] Wang | Voltammetric Behavior and Detection of DNA at Electrochemically Pretreated Glassy Carbon Electrode[END_REF] tin-doped indium oxide coated glass plate [START_REF] Hong | Mediated Oxidation of Guanine by [Ru(bpy) 2 dpp] 2+ and their Electrochemical Assembly on the ITO Electrode[END_REF] or carbon-fiber ultramicroelectrode, [START_REF] Bi | Electrochemical Studies of Guanosine in DMF and Detection of Its Radical Cation in a Scanning Electrochemical Microscopy Nanogap Experiment[END_REF] while other studies centered in indirectly electrochemical oxidation of DNA. In fact, it has been demonstrated that some complexes generated in situ can oxidize guanine. [START_REF] Xie | Electrocatalytic Oxidation of Guanine, Guanosine, and Guanosine Monophosphate[END_REF] Furthermore, this indirect method does not require specific electrode, avoiding the surface functionalization step. [START_REF] Jackson | Electrochemistry at DNA-Modified Surfaces: New Probes for Charge Transport through the Double Helix[END_REF] In this report we present the detection of the guanine radical by EPR spectroelectrochemistry coupling the mediated electrooxidation of guanine with the spin trapping method (Scheme 1). The in situ combination of electrochemistry and EPR spectroscopy make for an ideal partnership since a oneelectron-transfer process from diamagnetic material must result in the formation of paramagnetic transient species. EPR spectroelectrochemical experiments provide information about the redox site activity by studying the contribution of various nuclei to the molecular orbital occupied by the unpaired electron. [START_REF] Murray | EPR Electrochemistry[END_REF] At first, the electrochemical mediator, a ruthenium(II) complex, is oxidized at the electrode; (2) the oxidation of guanine by Ru(III) takes place; (3) the spin trap entraps the resulting radical, probably neutral; (4) the EPR spectrum is recorded during the whole process (Scheme 1).

■ EXPERIMENTAL METHODS

General. Guanosine 5′-monophosphate, adenosine, cytidine, thymidine and N-tert-butyl-α-phenylnitrone (PBN) were purchased from Sigma-Aldrich and used without further purifications. Poly(dG-dC) 2 was obtained from Sigma and 18mer oligonucleotides were obtained from Eurogentec SA. Tris(2,2′-bipyridyl-4,4′-bis(hydroxymethyl))Ruthenium(II) hexafluorophosphate complex was synthetized following a reported procedure. [START_REF] Collins | L. Ruthenium(II) α-Diimine Complexes with One, Two, and Three 4,4′-Bis(hydroxymethyl)-2,2′-bipyridine and 4,4′-Bis(chloromethyl)-2,2′-bipyridine Ligands: Useful Starting Materials for Further Derivatization[END_REF] Sample Preparation. Solutions were prepared in phosphate buffer (pH 7.5, PBS 10 mM and NaCl 0.1 M) at room temperature with 1 mM of ruthenium complex, 25 mM of PBN and between 0.2 to 5 mM of duplex DNA or GMP, in a 2 mL flat quartz cell adapted to electrochemical measurements, using a three-electrode setup: the working and counter-electrode were platinum and the reference electrode was a silver wire. Solutions were thoroughly degassed with Argon prior to use.

Cyclic Voltammetry. Voltammetric experiments were carried out at room temperature by using an Autolab 20 potentiostat (EcoChemie). A classical three electrodes cell was used. The working electrode was a Pt disc (diameter 0.5 mm) or a GC disc (glassy carbon, diameter 1 mm, BioLogic). The counter electrode was a platinum wire. The reference electrode was a saturated calomel electrode (SCE). All experiments were carried out in phosphate buffer (pH 7.5, PBS 10 mM and NaCl 0.1 M) under argon atmosphere. Voltammetric results were analyzed with the help of DigiElch Software.

Electrochemical Coupled Electron Paramagnetic Resonance. The EPR spectrometer was coupled to a potentiostatgalvanostat (EG&G Princeton Applied Research-Model 362). A PHN 81 (Tacussel) voltameter was used to control the applied potential. A flat quartz cell adapted to electrochemical measurements (Bruker, Wissembourg, France) was used for analysis. The electrochemical reduction was performed using a three-electrode setup: the working and counter-electrode were platinum and the reference electrode was a silver wire (its potential was 0.056 V/SCE).

EPR spectra were obtained at X-band at room temperature on a Bruker EMX-8/2.7 (9.86 GHz) equipped with a highsensitivity cavity (4119/HS 0205) and a gaussmeter (Bruker, Wissembourg, France). WINEPR and SIMFONIA software (Bruker, Wissembourg, France) were used for EPR data processing and spectrum computer simulation. Typical scanning parameters were: scan number, 120; modulation amplitude, 1 G; modulation frequency, 100 kHz; microwave power, 20 mW; sweep width, 100 G; sweep time, 41.94 s; time constant, 20.48 ms; center field, 3 480 G; receiver gain 2 × 10 6 .

■ RESULTS AND DISCUSSION

Mediated Electrochemical Oxidation of Guanine. Previous works reported that ruthenium(III) complexes, with an adequate potential, oxidize guanine by electron transfer. [START_REF] Johnston | Electrochemical Measurement of the Solvent Accessibility of Nucleobases Using Electron Transfer between DNA and Metal Complexes[END_REF] In phosphate buffer at pH 7.5, an hydrophilic ruthenium complex tris(2,2′-bipyridyl-4,4′-bis(hydroxymethyl))ruthenium(II) hexafluorophosphate [START_REF] Collins | L. Ruthenium(II) α-Diimine Complexes with One, Two, and Three 4,4′-Bis(hydroxymethyl)-2,2′-bipyridine and 4,4′-Bis(chloromethyl)-2,2′-bipyridine Ligands: Useful Starting Materials for Further Derivatization[END_REF] was studied. The cyclic voltammograms of this ruthenium complex showed the Ru(III)/Ru(II) redox couple which appears reversible (Figure 1, curve A black). The oxidation peak current (forward) is linearly related to the Ru(II) complex concentration and to the square root of the potential scan speed v as for a simple diffusion controlled electron transfer (Scheme 2, step E). The redox potential E°is estimated by a mean value of E°= [Ep(forward) + Ep(backward)]/2 = 0.986 V vs SCE. When guanosine 5′monophosphate (GMP) was added (Figure 1, curves B and C), the oxidation peak of Ru(II) was enhanced and the reverse peak disappeared (curve B); when the potential scan rate v was increased (curve C), the backward peak appeared (reduction of Ru(III)). At a potential scan rate v = 0.1 V.s -1 , the oxidation peak is 4 times higher than that of Ru(II) complex; at v = 1 V• s -1 , the ratio drops to 3. The forward peak current grew also when the GMP concentration increased.

This behavior can be explained by an EC cat scheme (Electron transfer followed by a catalytic reaction) according to Scheme 2. Although the G •+ /G potential (1.04 V vs SCE [START_REF] Burrows | Oxidative Nucleobase Modifications Leading to Strand Scission[END_REF] ) is slightly higher than the Ru(III)/Ru(II) potential, the irreversibility of GMP oxidation draws the overall process.

Simulations carried out with the DigiElch software gave an order of magnitude of 2.5 × 10 3 l.mol -1 .s -1 for the chemical oxidation of GMP; however, it appears that the mechanism is more complex. Such cyclic voltammetry experiments were Scheme 1. Electrochemical/EPR Coupling Method Figure 1. Normalized cyclic voltammograms versus the potential scan rate (current I/v 1/2 ) in phosphate buffer (pH 7.5) at a GC electrode of Ru(II) complex 10 -3 M, potential scan rate v: (A) complex alone; (B and C) complex after addition of guanosine 5′-monophosphate 6.2 × 10 -3 M; (D) complex after addition of adenosine 5 × 10 -3 M.

Scheme 2. EC Catalytic Pathway of Guanine Oxidation by Ru(III)

carried out with the other nucleobases separately. When adenosine was added, the cyclic voltammograms where unchanged (Figure 1, curve D), which means that no reaction took place between Ru(III) and adenosine. For cytidine and thymidine (Figure 2), the same conclusions can be drawn.

Taking into account these results, the Ru(III) complex provides the oxidation of guanine to the radical-cation, which is further converted in the medium: [START_REF] Joseph | One-Electron Oxidation of DNA: Reaction at Thymine[END_REF][START_REF] Rokhlenko | Lifetimes and Reaction Pathways of Guanine Radical Cations and Neutral Guanine Radicals in an Oligonucleotide in Aqueous Solutions[END_REF] the process is quantitative and is named "indirect or mediated electrooxidation" of guanine. Moreover, the oxidation is selective because the other nucleobases are not oxidized.

EPR Spectroscopy. To demonstrate the formation of radical intermediates accompanying the one-electron mediated oxidation of guanine, electrochemistry was coupled with EPR spectroscopy using PBN (N-tert-butyl-α-phenylnitrone) as a spin trap. Experiments were indeed carried out at room temperature and guanine radical itself is not stable long enough to be observed. Two milliliter and 0.5 mL flat quartz cells adapted to electrochemical measurements were used for analysis. The electrochemical reduction was performed using a three-electrode setup: the working and counter-electrode were platinum, and the reference electrode was a silver wire. The applied potential was chosen to be the oxidation potential of Ru(II): E applied = 1 V. EPR spectra were obtained at X-band for samples containing Ru(II) complex 1 mM, PBN 25 mM and GMP 5 mM. All experiments were performed in phosphate buffer (10 mM PBS, 100 mM NaCl, pH = 7.5).

Experiments were first carried out on GMP. The EPR spectrum recorded in the presence of Ru(II), GMP and PBN after electrolysis (120 scans) consists in a multilined spectrum characterized, as demonstrated by simulation, by the hyperfine splitting constants a N PBN = 12.106 G, a N′ = 1.48 G, a H PBN = 3.5 G, a H′ = 2.6 G, and g = 2.0098 (Figure 3a). No peak was recorded in the absence of PBN, GMP, or Ru(II) (Figure S1, Supporting Information). Furthermore, control experiments with the other nucleosides showed no radical formation (Figure 3b).

Numerous experimental and theoretical studies showed the formation and evolution of the guanine radical G •+ . It is now well established that this radical is not stable under physiological conditions and it rapidly deprotonates. [START_REF] Rokhlenko | Lifetimes and Reaction Pathways of Guanine Radical Cations and Neutral Guanine Radicals in an Oligonucleotide in Aqueous Solutions[END_REF][START_REF] Adhikary | The Guanine Cation Radical: Investigation of Deprotonation States by ESR and DFT[END_REF] The deprotonation of G •+ has been described in terms of a release of the N1 proton (pK a = 3.9) to form the G(N1-H) • neutral radical. [START_REF] Adhikary | The Guanine Cation Radical: Investigation of Deprotonation States by ESR and DFT[END_REF] Some studies also suggested the formation of G(N10-H) • , in which the exocyclic nitrogen is deprotonated. [START_REF] Rokhlenko | Lifetimes and Reaction Pathways of Guanine Radical Cations and Neutral Guanine Radicals in an Oligonucleotide in Aqueous Solutions[END_REF] However, both calculations and experiments in water media are either more consistent with the N1 deprotonation mode or suggest a tautomerization process leading to G(N1-H) • from G(N10-H) • . [START_REF] Chatgilialoglu | Tautomerism in the Guanyl Radical[END_REF] The G(N1-H) • neutral radical has several possible resonance structures (Scheme S1). Indeed, various forms of G(N1-H) • have been described, including oxygen, [START_REF] Adhikary | The Guanine Cation Radical: Investigation of Deprotonation States by ESR and DFT[END_REF][START_REF] Ghosh | Role of the Guanine N1 Imino Proton in the Migration and Reaction of Radical Cations in DNA Oligomers[END_REF] C8, C5, [START_REF] Fleming | G-Quadruplex Folds of the Human Telomere Sequence Alter the Site Reactivity and Reaction Pathway of Guanine Oxidation Compared to Duplex DNA[END_REF] and N3 [START_REF] Adhikary | Direct Observation of the Hole Protonation State and Hole Localization Site in DNA-Oligomers[END_REF][START_REF] Adhikary | Prototropic Equilibria in DNA Containing One-Electron Oxidized GC: Intra-Duplex vs. Duplex to Solvent Deprotonation[END_REF] centered radicals depending on the oxidation mode.

In our hands, the radical detected corresponds to the radical adduct formed between the spin trap PBN (nitrogen and hydrogen coupling) and a radical derived from guanosine. The hyperfine splitting constants a N′ and a H′ exclude in this case an addition to O, C5, or C8 [START_REF] Goyal | Electrochemical and Enzymic Oxidation of Guanosine and 8-Hydroxyguanosine and the Effects of Oxidation Products in Mice[END_REF] and suggests an addition to nitrogen. The second hydrogen coupling would in this case be attributable to an H-N10 atom. In our experiment, we cannot determine on which exact nitrogen of the guanidine moiety (N1, N3, or N10) the radical was trapped, but according to previous studies, 27,28 a N3-centered radical is more probable (Schemes 3 and S2).

The following step consisted of applying this method in a biological environment, in order to detect the guanine radical in DNA substrate. DNA environment can strongly cause modifications in comparison with a single nucleotide. For example, it is well-known that nucleobase oxidation potentials vary according to their environment.

The same experiments were thus performed with 18-mer synthetic double-stranded oligonucleotides containing 0, 1, 2, 3, and 4 adjacent guanines, in order to determine potential sequence effect on the structure of the trapped radical, with following sequences respectively: 5′-TATTAATTATAATTAA-TA-3′; 5′-TATTATAAGTAATTATTA-3′; 5′-TATTATAA- GGTAATTATA-3′; 5′-TATTATAGGGTAATTATA-3′, and 5′-TATTATAGGGGTAATTAT-3′ and their complementary strands.

Indeed, in duplex DNA, guanine oxidation potential varies with the sequence particularly at multiple guanine sequences such as GG, GGG, or GGGG for which oxidation potential gradually dropped with increasing number of stacked guanine. [START_REF] Sugyama | Theoretical Studies of GG-Specific Photocleavage of DNA via Electron Transfer: Significant Lowering of Ionization Potential and 5′-Localization of HOMO of Stacked GG Bases in B-Form DNA[END_REF] A last experiment was carried out with long polynucleotide poly(dG-dC) 2 . The corresponding spectra are presented in Figure 4a,c, respectively. First, spectrum recorded with the oligonucleotide without guanine showed as expected no signal at all (Figure 4d). The other spectra are the same for poly(dG-dC) 2 and DNA duplex whatever the number of guanine bases. As demonstrated by the simulation carried out for 18-mer DNA with 4G (Figure 4b), the EPR spectra are characterized by the hyperfine splitting constants a N PBN = 11.2 G, a H PBN = 3.2 G, and a H′ = 2.1 G with g = 2.0098. In double-strand DNA, the G •+ radical is also not stable and rapidly deprotonates to form the G(-H) • radical but in a slower way than in the case of free guanosine. This slower deprotonation is due to the prototropic equilibrium with cytosine, which stabilizes the cation form by sharing the proton between the guanine and the cytosine along the hydrogen bond. [START_REF] Ghosh | Role of the Guanine N1 Imino Proton in the Migration and Reaction of Radical Cations in DNA Oligomers[END_REF][START_REF] Adhikary | Direct Observation of the Hole Protonation State and Hole Localization Site in DNA-Oligomers[END_REF] The deprotonation process is thus in competition with an hydration process, leading to the 8hydroxy-7,8-dehydroguanyl G(OH) • radical, which is the intermediate in the formation of 8-oxo-7,8-dehydroguanine, the most common oxidative damage in DNA. [START_REF] Burrows | Oxidative Nucleobase Modifications Leading to Strand Scission[END_REF] The nature of the hyperfine splitting constants is in favor of the trapping of the deprotonated radical form. Indeed, the disappearance of the second nitrogen coupling points out addition of PBN to a carbon and confirms that the radical trapping may takes place before hydration. In this case, as shown in scheme 4, the addition would take place through C8. The second hydrogen coupling would be attributable to the H-C8 atom. The differences between the radical trapped in the case of GMP and in duplex DNA can be explained with the structure of the double helix. O, N1 and N10 are involved in the hydrogen bonds with cytosine and thus located in the middle of the helix. On the other hand, C8 is the most accessible atom for PBN, and along all the resonance forms of the guanine radical, the C8-centered one is thus the most easily trapped.

All these results confirmed the one-electron mediated oxidation of guanine, isolated or in DNA environment, by the detection of the radical adduct formed between the spin trap PBN and a guanine radical intermediate. Moreover, the efficiency and the interest of this EPR spectroelectrochemical coupled method are demonstrated. Indeed, the observed EPR spectra are different according to the substrate: either free nucleotide or duplex DNA. Deprotonation pathway is confirmed for the first one-electron oxidation product, G •+ in agreement with previous reports. Furthermore, no difference in the signal was observed between the different sequences with one or more guanine, which supports the idea of a single oxidation occurring mainly at the 5′-G of multiple guanine sites such as GG or GGG. The difference observed in the EPR signals, between free guanosine and DNA, is due to the different accessibility of the neutral guanine cation for the PBN trapping and highlights the dependency of the environment on the nature and structure of the radical formed.

■ CONCLUSION

In conclusion, the indirect electrochemical oxidation/EPR spectroscopy coupling method has been shown to be a new attractive technique for the in situ guanine radical detection with its easier setup (i.e., working at room temperature) compared to other methods and a relevant tool to understand oxidative damage in DNA. Moreover, the guanine radical analysis has revealed two types of spectra depending of the environment of the guanine radical (free or in duplex DNA). Elucidation of other radical processes in DNA with this method is currently under investigation and will be reported in due course.

Figure 2 .

 2 Figure 2. Cyclic voltammograms in phosphate buffer (pH 7.5) at a Pt electrode of Ru(II) complex 10 -3 M, potential scan rate 0.1 V.s -1 : (A) complex alone; (B) complex after addition of cytidine 5 × 10 -3 M; (C) complex after addition of thymidine 5 × 10 -3 M.

Figure 3 .

 3 Figure 3. (a) EPR spectrum of the spin-trapped guanine radicals produced by the electrolysis of Ru(II) complex in the presence of PBN in PBS buffer at pH 7.5 at room temperature from GMP 5.10 -3 M (black) and simulated spectrum (red). (b) EPR spectra recorded in the same conditions with other nucleosides.

Scheme 3 .a

 3 Scheme 3. PBN-Trapped N3-Centered Guanine Radical in GMP a

Figure 4 .

 4 Figure 4. EPR spectra of the spin-trapped guanine radicals produced by the electrolysis of Ru(II) complex 1 × 10 -3 M in presence of PBN 25 × 10 -3 M in PBS buffer at pH 7.5 at room temperature from (a) double strand 18-mer DNA 5 × 10 -4 M with 1G, 2G, 3G, and 4G; (b) double strand 18-mer DNA 5 × 10 -4 M with 4G and simulated spectrum (red); (c) poly(dG-dC) 2 3.75 × 10 -2 M in base pairs; and (d) double strand 18-mer DNA 0.2 × 10 -3 M without G.

Author Contributions

The manuscript was written through contributions of all authors. All authors have given approval to the final version of the manuscript.

Notes

The authors declare no competing financial interest.