G Lucius

F Le

Roy D Aulagnier
email: denis.aulagnier@fr.thalesgroup.com

S Azou
email: azou@enib.fr

An algorithm for extremal eigenvectors computation of Hermitian matrices and its FPGA implementation

Keywords: Field Programmable Gate Arrays, High-level Synthesis, Hermitian eigenpairs. I

We consider the problem of implementing an algorithm for the extraction of leading eigenvectors of a small Hermitian matrix on field-programmable gate array (FPGA). The evolution of FPGAs can now handle increasingly bandwidth problems or larger in size. Jacobi algorithms are usually implemented in FPGA for real matrix size not exceeding 20*20. The increase in size or complex number problem may lead to use other algorithms such as Lanczos, which are rarely implemented on FPGA. Recently, it has been pointed out that the Lanczos method can efficiently address the extreme eigenvalues computation problem on FPGA, for medium size real matrices. This paper presents an algorithm for the extraction of extremal eigenvalues and corresponding eigenvectors for small Hermitian matrix using a high-level approach for the architecture synthesis.

INTRODUCTION

Estimation of direction of arrival (DOA) parameters is involved in many fields such as telecommunication, radar, sonar [START_REF] Bienvenu | Influence of the spatial coherence of the background noise on high resolution passive methods[END_REF] or seismic [START_REF] Kirlin | Covariance analysis for seismic signal processing[END_REF]. DOA estimation relies on subspace methods that typically consist in achieving a spectral decomposition of the covariance matrix of the measurements. The decomposition usually requires the computation of a few eigenvalues and their corresponding eigenvectors of a complex Hermitian matrix. Depending on the application and the instantaneous bandwidth, real-time constraints may require the use of FPGA to take advantage of parallel computing. Implementation of the Lanczos algorithm is very uncommon on FPGAs and appears only recently. In [START_REF] Rafique | A High Throughput FPGA-Based Implementation of the Lanczos Method for the Symmetric Extremal Eigenvalue Problem[END_REF], it is shown that FPGAs are suitable for medium size matrices (a few hundreds) and high-bandwidth applications, but the case of Hermitian matrices is not considered. We propose to investigate the Hermitian case and also to compute the eigenvectors; moreover, we focus on the particular scenario where the measurement process leads to small covariance matrices. The proposed algorithm is implemented on a FPGA using a High-Level Synthesis (HLS) approach. The paper is organized as follows: section II gives a short overview of existing methods for solving the extremal eigenvalues problem. Then, section III details a particular algorithm and its variants are discussed.

Finally, before some conclusions, we describe the proposed architecture resulting from use of some HLS tools.

II. MATHEMATICAL BACKGROUND

The extremal eigenvalues/eigenvectors problem can be solved in different ways. The choice of the algorithm depends on the matrix properties, its size, and the number of desired eigenvalues. As part of a wideband receiver, high sampling frequencies lead to a large amount of dataflow that requires maximizing the computation efficiency. In the present paper, we consider the case of a n*n complex Hermitian matrix denoted by A , with n relatively small (a few tens), for which the first two largest eigenvalues and associated eigenvectors are computed. Then, the algorithm is chosen to avoid unnecessary calculations and take part of the Hermitian properties of the matrix.

Semi-direct

Lanczos Householder

Iterative

Jaco bi QR Power The main numerical methods to solve the eigenproblem can be classified in three categories (fig 1). Direct methods are not often used because they are limited to the case of a very small matrix size (n<4), by using the analytical expressions for the eigenpairs. For larger problems, there are semi-directs and iterative methods. Semi-direct methods use an intermediate matrix and continue the diagonalization with an iterative method, whereas iterative methods such as the Jacobi method are completely iterative. Generally, conventional methods such as Jacobi, compute the eigenvalues and eventually the eigenvectors with a complexity ( )

Eigenproblem

Direct

3 n Ο
. Their most common use is when all eigenvalues are required. However, when only a few eigenvalues are needed, it is sometimes preferable to use appropriate methods such as the Power method [START_REF] Golub | Matrix computations[END_REF]. It is also possible to use semi-direct methods that combine a matrix transformation with Lanczos or Householder methods and then compute a part of eigenpairs with an iterative algorithm. The Power method can be used to quickly obtain the leading eigenvectors of the matrix A . However the convergence depends on the eigenvalues distribution and a very large number of iterations can be required when the eigenvalues are close, which prevents obtaining a good approximation in a reasonable time in the context of a high dataflow. It is well known that a Hermitian matrix has some particular properties that simplify the eigendecomposition. Thus, a Hermitian matrix is a square self-adjoint matrix, diagonalizable, with real eigenvalues [START_REF] Axler | Linear algebra done right[END_REF]. In our case, it is more interesting to go through an intermediate tridiagonal matrix as shown in Fig 2 . The remaining calculations are then easier thanks to the reduced number of data to be manipulated. We propose a three stage semi-direct algorithm, whose particularities are detailed in section 3. It consists in a tridiagonalisation via Lanczos, followed by the bisection method, to obtain the eigenvalues; then the inverse iteration is performed to get corresponding eigenvectors.

Lanczos Bisection

Inverse iteration

A Input matrix T Tridiagonal matrix 2 1 , λ λ Eigenvalues Eigenvectors 2 1 , v v

III. CHOICE OF ALGORITHMIC VARIANTS

A. Background DOA estimation methods generally use the noise or signal subspaces [START_REF] Chen | Introduction to Direction-of-arrival Estimation[END_REF]. These subspaces being orthogonal, the complete eigendecomposition is not really necessary and represents a superfluous computational cost. Moreover, the pseudo-spectrum projection does not really need the exact eigenvector but only the subspace spanned. Subsequently, we therefore seek the subspace spanned by the first two eigenvectors. There are methods to perform a partial diagonalization such as Lanczos or Householder transformation methods. Applied to a Hermitian matrix, they produce a real symmetric tridiagonal matrix. This particular structure simplifies the rest of the algorithm. The bisection method is used to compute the eigenvalues by dichotomy. Once this first step is terminated, it remains to find the two corresponding eigenvectors using the inverse iteration. This one is a variation of the Power method applied to the inverse matrix. Starting with a correct approximation of the eigenvalues, this method will usually find the corresponding eigenvectors in one iteration.

B. The Lanczos method

The Lanczos method is an iterative method based on Krylov space. It allows, from an initial vector 0

q , to construct a subspace ] [ ) , ( 0 0 1 n 0 0 n q ,A , ,Aq q q - = … A K . At the k th iteration, a k*k tridiagonal matrix k T is created from the original matrix A . k
T is composed of k α and k β , diagonal and sub-diagonal elements respectively (see Fig 3). In the end, the matrix T is similar to the matrix A and therefore has the same eigenvalues in the generated subspace n K . In the case of a finite representation, a loss of orthogonality may be observed after a few cycles. The current Lanczos vector loses its orthogonality compared to the previous vectors and reorthogonalization is necessary to keep an orthonormal basis and avoid spurious eigenvalues. However, if we are only interested in extreme eigenvalues, the loss of orthogonality does not affect them [START_REF] Demmel | Applied numerical linear algebra[END_REF][START_REF] Cullum | Lanczos algorithms for large symmetric eigenvalue computations[END_REF] and the reorthogonalization is not necessary. The overall computational cost can be computed easily using Fig. 3. Cost is then reduced to 2n 28n 8n

(l6) ; v β (l5) *w; α v v (l4) *v; w α (l3) w; v v (l2) *t; β v (l1) ; v/β w w; t 1 k if 1..n k ,β α k k H k 1 k 1 k k k = - = = + = - = = = > = - - A A Fig. 3.

Lanczos algorithm, two vectors working version without reorthogonalization

For large matrix, the Lanczos method without reorthogonalization is more interesting in terms of computational cost [START_REF] Golub | Matrix computations[END_REF], its implementation will be discussed in the next section. Compared to the Householder method, both of them have the advantage of making the tridiagonal transformation into a known number of iterations, but the presence of a matrix product penalizes Householder with a 93 10 7 48 16

2 3 4 - + + - n n n n
cost. Nevertheless, comparison (Fig 4 ) shows an intersection of computational costs, which reveals that the Householder method may be preferable in case of very small matrices.

C. Bisection method

The bisection method allows to get the eigenvalues of the tridiagonal matrix T . Compared to other methods such as the QR algorithm that achieves the full diagonalization, the bisection method is used here to compute one eigenvalue at a time and avoid unnecessary calculation. It uses the simplified expression of the characteristic polynomial of T to find the roots. The approach consists in using the Sturm sequence evaluated at a point c ,

) c det( (c) p k k I T - =
. Thus, the number of sign changes in the sequence is equal to the number of eigenvalues of T smaller than c . Then, the searched eigenvalue is estimated by dichotomy until a given precision is reached. The Gerschgorin theorem [START_REF] Varga | Geršgorin and his circles[END_REF] is used to obtain a rough approximation of the eigenvalues, and then to identify the first interval bisection.

D. Inverse iteration

The inverse iteration method is very similar to the Power method, except that it applies to the inverse of the A matrix. As we don't keep Lanczos vectors due to non-orthogonalization, use of eigenvalues is our unique choice and this method can compute the eigenvector corresponding to the minimum eigenvalue. From an initial vector 1 x , we form a vector sequence

… , , k , x k 2 1 = each one being computed as k 1 1 k x x - + = A
; this sequence is known to converge towards the minimal eigenvectors.

Due to the large computational burden involved by the matrix inverse calculation, the inverse iteration approach is not applied in this way. Multiplying the last equation by A we obtain

k k x x = +1 A
. As the matrix A is constant, we have every reason to make its LU decomposition to bring this system into two triangular systems, which is easier to solve. As a result, the system to solve takes the form

⎪ ⎩ ⎪ ⎨ ⎧ = = + y x x y k k 1 * * U L .
Thus, we solve the first system to find y and replace it in the second system to find

1 + k
x . This technique is also known as forward and backward substitution. If u is an approximated eigenvalue of λ resulting from the bisection method, then

I A u
has an eigenvalue closed to zero and the inverse iteration converges to the eigenvector associated with λ . We can therefore calculate any eigenvector, if we have an approximation of its corresponding eigenvalue.

IV. EXPERIMENTAL RESULTS

A. Computational cost analysis

Taking into consideration that two real operations are required for a complex addition, six real operations for a complex multiplication and thirteen for a complex division, the exact computational cost of each method can be deduced and compared to algorithms for real matrices. One of the main advantages of using Lanczos without orthonormalization is that the computational cost does not depend on the data but only on the size of the matrix. In the case of Lanczos, the ratio of computational costs for complex/real cases stabilizes at a value of four, which shows that a single iteration consists mainly of multiplications accumulations. The Lanczos process is mainly composed of a matrix-vector product (l3, Fig 3), representing 85% of the computational cost of one iteration for 20 = n

; this ratio increases asymptotically with n .

B. High-Level Synthesis tools

HLS is the automated design process design that converts a high-level design specification into a Register Transfer Level (RTL) implementation. This type of tools emerged in the later 80's, but their adoption has increased these last years with third generation tools, which commonly uses ANSI C/C++/System C as input languages description [START_REF] Martin | High-level synthesis: Past, present, and future[END_REF]. During this work, we used the Xilinx Vivado HLS tool that enables to generate an adapted implementation for Xilinx components. In the case of floating-point operations; they will be implemented by the appropriate floating-point Xilinx Core Generator cores [START_REF]Xilinx, Vivado Design Suite User Guide : High-Level Synthesis[END_REF].

Vivado HLS tool allows architecture design exploration using directives in the form of pragma directly in the GUI. Within functions, C/C++ descriptions are generally implemented as series of loops. Much of design exploration goes through loop directives. The most significant ones are pipelining or unrolling for loops that share or parallelize resources. As we are potentially dealing with a large amount of data, memory directives are crucial too. Partitioning or reshaping data in the memory can avoid bottlenecks. These features allow generating various architecture designs from a single input code and therefore the architecture exploration is faster than rewriting the VHDL code.

C. Architecture exploration of the Lanczos method

As the Lanczos computational cost is essentially composed by the matrix-vector multiplication (l3), the implementation result depends mostly on this operation. The strong dependence of data between l1, l2, l4, l5 and l6 in one iteration of Lanczos leads to a parallelization potential only due to the matrix-vector multiplication. Pipelining is used to maximize the efficiency of resources and the matrix-vector multiplication is implemented as n parallel dot vector products. The architecture exploration can quickly converge to an efficient solution by analyzing the performance data provided by the tool. Fig. 6 shows an example of architecture exploration; the inflexion point from the asymptotic curve of candidate solutions represents the most effective one. Setting the number of dot-vector products in parallel or the number of adders/multipliers in this function carries out most of the exploration. Artifacts with high initiation interval reflect bottlenecks; as a result, memory access and parallelism must match.

D. Architecture of the bisection method

As for the Lanczos method, bisection is essentially composed of mulacc and potential parallelism is limited due to the iterative nature of the algorithm. Mismatch between throughput and latency during the Sturm sequence leads to underutilization of the pipeline. To completely fill the pipeline, multiple eigenvalues are solved simultaneously. Thereby, up to four eigenvalues can be computed without increasing resources. However, HLS tool finds its limits for this kind of function; optimization and architecture exploration are difficult without explicitly writing the architecture in the C code.

E. Architecture exploration of the inverse iteration

Inverse iteration revolves around the LU decomposition in terms of complexity. Even if the LU decomposition using Cholesky's algorithm is optimized for Hermitian matrices we firstly use the Crout's algorithm to perform the decomposition because reordering loops is easier in this way. The LU decomposition uses a lot of mulacc, which leads to many bottlenecks. To avoid mulacc architecture, reordering loops in the C code is used to compute one monomial term at a time sweeping the whole matrix before performing accumulation. We present the results for n=16 (Tab I), p eigenvectors and q bisection iterations; in our case q has never exceeded 13. Result of implementation on XC7VX485T device @300MHz for p eigenvalues

V. CONCLUSION & FUTURE WORK

We presented a three-stage semi-direct algorithm for the computation of eigenvectors of a Hermitian matrix implemented as a pipelined architecture using a HLS approach instead of VHDL. It has been shown that this approach allows to quickly and easily explore several designs for getting efficient solutions. However, handover for this kind of tool requires a particular way to write C/C++ code and adaptation time is required. Several additional improvements have been identified: we intend to develop the Cholesky's algorithm for the LU decomposition using the Hermitian symmetry of the matrix. In the case of a lower dynamic input, it would be interesting to work with fixed-point numbers that are more suited to FPGA's and their DSP blocks. And finally, some algorithmic variants have been identified for smaller matrices, keeping in mind the known and fixed execution time constraint.

Fig. 1 .

 1 Fig. 1. Classification of Eigen methods

Fig. 2 .

 2 Fig. 2. Three stages proposed algorithm

Fig. 4 .

 4 Fig. 4. Comparison of computational costs for Lanczos and Householder.

Fig. 5 .

 5 Fig. 5. Implementation of the dot vector productFlexibility is obtained by instantiating one or more dot vector products. Expressing as much as possible operations as loops provided architecture flexibility. Dot-vector product is implemented using only one pipelined multiplier and two adders (real and imaginary parts) as a reduction tree (fig5).

Fig. 6 .

 6 Fig. 6. Architecture exploration of the Lanczos method for n=16

TABLE I .

 I IMPLEMENTATION RESULTS FOR N=16

	Algorithm	Theoretical ops	DSP48	Throughput
	Lanczos	39904	69	31,6 μs
	Bisection	p*1664	6	q*3,2μs
	Inverse iteration	p*10790	p*295	370 ns

a.


Alejandro Estaña

Nathalie Sibille

Elise Delaforge

Marc Vaisset

Juan Cortés
email: juan.cortes@laas.fr

Pau Bernadó
email: pau.bernado@cbs.cnrs.fr

Realistic ensemble models of intrinsically disordered proteins using a structure-encoding coil database

Keywords: Intrinsically disordered proteins, Conformational sampling, Residual dipolar couplings, Protein fragment database

Intrinsically Disordered Proteins (IDPs) play fundamental roles in signaling, regulation and cell homeostasis by specifically interacting with their partners. The structural characterization of these interacting regions remains challenging and requires the integration of extensive experimental information. Here we present an approach that exploits the structural information encoded in tripeptide fragments from coil regions of high-resolution structures. Our results indicate that a simple building approach that disregards the sequence context provides a good structural representation of fully disordered regions. Conversely, the description of partially structured motifs calls for the consideration of sequence-dependent structural preferences. By using NMR Residual Dipolar Couplings and SAXS data for multiple IDPs we demonstrate that the appropriate combination of these two building strategies produces ensemble models that correctly describe the secondary structural classes and the population of partially structured regions. This study paves the way for the extension of structure prediction and protein design to disordered proteins.

Introduction

Intrinsically Disordered Proteins or Regions (IDPs/IDRs) play crucial roles in multiple biological processes and are directly involved in several pathologies, including cancer and neurodegeneration [START_REF] Uversky | Intrinsically disordered proteins in human diseases: Introducing the D2 concept[END_REF][START_REF] Csizmok | Dynamic protein interaction networks and new structural paradigms in signaling[END_REF][START_REF] Babu | Intrinsically disordered proteins: Regulation and disease[END_REF]. The inherent plasticity of this family of proteins facilitates a range of functions that are complementary to those of their folded counterparts [START_REF] Xie | Functional anthology of intrinsic disorder. 1. Biological processes and functions of proteins with long disordered regions[END_REF]. In most cases, the activity of IDPs is manifested when interacting with globular partners to trigger signaling or metabolic cascades [START_REF] Tompa | Intrinsically disordered proteins: Emerging interaction specialists[END_REF]. These interactions are mediated by Short Linear Motifs (SLiMs) that recognize regions of the partner surface in a highly specific manner [START_REF] Van Roey | Short linear motifs: Ubiquitous and functionally diverse protein interaction modules directing cell regulation[END_REF]. The presence of transiently formed structural motifs in SLiMs facilitates partner recognition and tunes the thermodynamics and kinetics of interactions [START_REF] Mohan | Analysis of molecular recognition features (MoRFs)[END_REF][START_REF] Pancsa | Interactions via intrinsically disordered regions: What kind of motifs?[END_REF][START_REF] Schneider | Visualizing the molecular recognition trajectory of an intrinsically disordered protein using multinuclear relaxation dispersion NMR[END_REF]. To understand these functional mechanisms, it is pivotal to identify and characterize these partially structured elements inserted into IDPs.

The relatively flat conformational energy landscape of IDPs has notably hampered their structural characterization. Experimental data obtained by Nuclear Magnetic Resonance (NMR) and Small-Angle X-ray Scattering (SAXS) provide information on conformational trends at the residue level, the presence of transient long-range contacts, and the overall size of the ensemble of conformations [START_REF] Eliezer | Biophysical characterization of intrinsically disordered proteins[END_REF]. However, the quantitative interpretation of these data requires the use of computational approaches that account for their ensemble averaging properties. These computational approaches are based on the construction of large conformational ensembles, which are subsequently refined by integrating the experimental data using restrained Molecular Dynamics (MD) simulations [START_REF] Dedmon | Mapping long-range interactions in alpha-synuclein using spin-label NMR and ensemble molecular dynamics simulations[END_REF][START_REF] Silvestre-Ryan | Average conformations determined from pre data provide highresolution maps of transient tertiary interactions in disordered proteins[END_REF], sub-ensemble selection (Ozenne et al., 2012b;[START_REF] Krzeminski | Characterization of disordered proteins with ensemble[END_REF][START_REF] Bernadó | Structural characterization of flexible proteins using small-angle X-ray scattering[END_REF], or Bayesian statistics [START_REF] Fisher | Modeling intrinsically disordered proteins with bayesian statistics[END_REF]. Chemical Shifts (CSs) and Residual Dipolar Couplings (RDCs) measured in partially aligned media are the most sensitive probes to quantify conformational restrictions at the residue level and to define secondary structural elements [START_REF] Dyson | Unfolded proteins and protein folding studied by NMR[END_REF][START_REF] Jensen | Quantitative determination of the conformational properties of partially folded and intrinsically disordered proteins using NMR dipolar couplings[END_REF]. Conversely, ensembles refined with SAXS data describe the overall properties of the protein in solution [START_REF] Bernadó | Structural analysis of intrinsically disordered proteins by small-angle X-ray scattering[END_REF][START_REF] Receveur-Brechot | How random are intrinsically disordered proteins? a small angle scattering perspective[END_REF]. Consequently, conformational ensembles that simultaneously describe both sources of complementary information are excellent structural models of proteins in solution [START_REF] Sibille | Structural characterization of intrinsically disordered proteins by the combined use of NMR and SAXS[END_REF][START_REF] Cordeiro | Small-angle scattering studies of intrinsically disordered proteins and their complexes[END_REF]. Multiple computational tools using different levels of description have been developed to characterize IDPs when no or limited experimental information is available. Current disorder prediction tools, which are based on the statistical analysis of protein sequences, provide rough estimations of partly structured regions in IDPs [START_REF] Deng | An overview of practical applications of protein disorder prediction and drive for faster, more accurate predictions[END_REF], although the exact secondary structure classes are poorly defined.

In principle, a more accurate characterization can be provided by MD-based methods. However, despite significant advances in the extension of MD methods to IDPs [START_REF] Piana | Water dispersion interactions strongly influence simulated structural properties of disordered protein states[END_REF][START_REF] Henriques | Molecular dynamics simulations of intrinsically disordered proteins: force field evaluation and comparison with experiment[END_REF], their applicability to exhaustively explore the conformational space of these proteins is still limited. Knowledge-based approaches have emerged as an alternative to overcome some of these limitations. These approaches usually describe the conformational properties of individual residues using the so-called coil libraries, which contain residue-specific {φ, ψ} angles from fragments of experimentally determined protein structures that do not form secondary structural elements [START_REF] Smith | Analysis of main chain torsion angles in proteins: Prediction of NMR coupling constants for native and random coil conformations[END_REF][START_REF] Feldman | A fast method to sample real protein conformational space[END_REF][START_REF] Jha | Statistical coil model of the unfolded state: Resolving the reconciliation problem[END_REF][START_REF] Bernadó | A structural model for unfolded proteins from residual dipolar couplings and small-angle X-ray scattering[END_REF][START_REF] Fitzkee | The protein coil library: A structural database of nonhelix, nonstrand fragments derived from the pdb[END_REF][START_REF] Ting | Neighbor-dependent ramachandran probability distributions of amino acids developed from a hierarchical dirichlet process model[END_REF][START_REF] Esteban-Martin | Refinement of ensembles describing unstructured proteins using nmr residual dipolar couplings[END_REF][START_REF] Shen | Prediction of nearest neighbor effects on backbone torsion angles and nmr scalar coupling constants in disordered proteins[END_REF]. Despite their simplicity, coil models provide an accurate description of NMR parameters such as J-couplings [START_REF] Smith | Analysis of main chain torsion angles in proteins: Prediction of NMR coupling constants for native and random coil conformations[END_REF][START_REF] Shen | Prediction of nearest neighbor effects on backbone torsion angles and nmr scalar coupling constants in disordered proteins[END_REF] and RDCs [START_REF] Bernadó | A structural model for unfolded proteins from residual dipolar couplings and small-angle X-ray scattering[END_REF][START_REF] Jensen | Quantitative determination of the conformational properties of partially folded and intrinsically disordered proteins using NMR dipolar couplings[END_REF], and SAXS curves [START_REF] Bernadó | Structural analysis of intrinsically disordered proteins by small-angle X-ray scattering[END_REF] for flexible peptides and disordered proteins. To ensure a large conformational exploration, the most common methods sequentially append individual residues using peptide planes [START_REF] Bernadó | A structural model for unfolded proteins from residual dipolar couplings and small-angle X-ray scattering[END_REF] or Cα atoms [START_REF] Feldman | A fast method to sample real protein conformational space[END_REF] as building units. These coil models are normally used as background ensembles for the subsequent refinement using experimental data [START_REF] Dedmon | Mapping long-range interactions in alpha-synuclein using spin-label NMR and ensemble molecular dynamics simulations[END_REF][START_REF] Silvestre-Ryan | Average conformations determined from pre data provide highresolution maps of transient tertiary interactions in disordered proteins[END_REF]Ozenne et al., 2012b;[START_REF] Krzeminski | Characterization of disordered proteins with ensemble[END_REF][START_REF] Bernadó | Structural characterization of flexible proteins using small-angle X-ray scattering[END_REF][START_REF] Fisher | Modeling intrinsically disordered proteins with bayesian statistics[END_REF]. Therefore, they are not supposed to identify secondary structural elements in IDPs, although conformations can be biased by including information from secondary structure predictors (Feldman and Hogue). This limitation is caused by the amino acid type specific conformational database that overlooks the sequence and structural context [START_REF] Feldman | A fast method to sample real protein conformational space[END_REF][START_REF] Jha | Statistical coil model of the unfolded state: Resolving the reconciliation problem[END_REF][START_REF] Bernadó | A structural model for unfolded proteins from residual dipolar couplings and small-angle X-ray scattering[END_REF]. Consequently, approaches such as TraDES and Flexible-Meccano provide realistic models for purely random coil regions, but do not capture structural features involving multiple consecutive residues. The omission of coordinated effects precludes the capacity of current approaches to predict structural classes and their populations, and hamper their application for advanced purposes.

Here we present a new approach to build atomistic models of IDPs that uses an extensive coil library of three-residue fragments (called tripeptides herein), which are the minimal fragments containing structural information [START_REF] Huang | Direct prediction of NMR residual dipolar couplings from the primary sequence of unfolded proteins[END_REF]. The exploitation of the structural information encoded in the library provides accurate descriptions of RDCs and SAXS datasets for multiple disordered proteins presenting distinct secondary structural motifs. This observation suggests that, by capturing conformational restrictions in turns, αhelices, and β-strands inserted in IDPs, our structural ensembles are realistic models of these proteins. The relative population, the internal coordination that transiently stabilizes these secondary structural elements, and the fluctuating behavior of these elements naturally emerge from our strategy. Our study seeks to extend structure prediction approaches to disordered chains, thereby enabling the identification of the structural perturbations that deleterious point mutations or alternative splicing exert on IDPs and IDRs.

Results

Computational models

A tripeptide coil database was built from high-resolution, experimentally determined protein structures (see Method Details). Tripeptides capture the conformational variability of the 20 proteinogenic amino acids while accounting for the effects of the closest neighboring residues. Using this tripeptide database and a simple steric term to avoid atom overlap, we generated ensembles of 100,000 conformations for several IDPs using the different building strategies explained below. N-HN RDCs and SAXS curves were computed from the resulting ensembles using standard methods (see Method Details) and were compared with the experimental datasets. RDCs for MAPK Kinase 7 (MKK7) [START_REF] Kragelj | Structure and dynamics of the MKK7-JNK signaling complex[END_REF], the fragment 955-1097 of the Erythrocyte binding antigen 181 (eba181) [START_REF] Blanc | Intrinsic disorder within the erythrocyte binding-like proteins from plasmodium falciparum[END_REF]), p15 (De Biasio et al., 2014), sic1 (Mittag et al., 2010), Measles virus ntail (ntailMV) [START_REF] Jensen | Intrinsic disorder in measles virus nucleocapsids[END_REF], Sendai virus ntail (ntailSV) [START_REF] Jensen | Quantitative conformational analysis of partially folded proteins from residual dipolar couplings: Application to the molecular recognition element of sendai virus nucleoprotein[END_REF], the unique domain of the src kinase (src) [START_REF] Pérez | Structural characterization of the natively unfolded N-terminal domain of human c-Src kinase: Insights into the role of phosphorylation of the unique domain[END_REF], K18 fragment of Tau protein (K18) [START_REF] Mukrasch | Highly populated turn conformations in natively unfolded tau protein identified from residual dipolar couplings and molecular simulation[END_REF], and full-length Tau protein [START_REF] Schwalbe | Predictive atomic resolution descriptions of intrinsically disordered htau40 and alpha-synuclein in solution from NMR and small angle scattering[END_REF] were used to probe the residue-specific sampling of the models, including the presence of partiallyformed secondary structural elements. The agreement of the different building strategies with the experimental data was quantified using Q-factors [START_REF] Cornilescu | Validation of protein structure from anisotropic carbonyl chemical shifts in a dilute liquid crystalline phase[END_REF] (Table S1). Moreover, SAXS curves for p15 [START_REF] De Biasio | p15PAF is an intrinsically disordered protein with nonrandom structural preferences at sites of interaction with other proteins[END_REF], src [START_REF] Arbesú | The unique domain forms a fuzzy intramolecular complex in Src family kinases[END_REF], and Tau [START_REF] Mylonas | Domain conformation of tau protein studied by solution smallangle X-ray scattering[END_REF] were used to probe the overall size and shape of the ensembles constructed.

The coil model describes disordered regions in IDPs

As a first approach, we built the conformations by randomly selecting {φ, ψ} values from the database in a residue-specific manner without taking into account the neighboring residues. Only residues preceding prolines were specifically selected from the database, since the Ramachandran distributions of these residues differ considerably [START_REF] Macarthur | Influence of proline residues on protein conformation[END_REF][START_REF] Ting | Neighbor-dependent ramachandran probability distributions of amino acids developed from a hierarchical dirichlet process model[END_REF]. This building mode, which we call single-residue-based sampling (SRS), can be considered a Flory model since the sequence context of the building units is not used. The RDC profiles computed using the SRS strategy nicely reproduced the experimental ones for large sections of all the proteins (Fig. 7, blue lines). Conversely, other regions displaying large (positive or negative) RDCs were not properly reproduced by SRS ensembles. Not surprisingly, this lack of agreement was observed in known α-helical regions with positive RDCs (ntailMV, ntailSV and MKK7), extended regions with strongly negative N-HN RDCs (p15), and turns displaying sharp positive peaks (eba181, K18 and Tau).

Note that inaccuracies in the representation of partially structured regions have also been observed when using similar building strategies, such as Flexible-Meccano [START_REF] Bernadó | A structural model for unfolded proteins from residual dipolar couplings and small-angle X-ray scattering[END_REF]Ozenne et al., 2012a). The proteins with highly populated secondary structural elements, such as ntailMV, ntailSV and MKK7 present large Q-factors (around 100).

Structural information encoded in the tripeptide database identifies partially formed secondary structural elements

We generated large conformational ensembles using a three-residue-based sampling strategy (TRS) that selects {φ, ψ} values for each residue i, taking into account the amino acid type and the conformation of the neighboring residues i -1 and i + 1 (see Method Details). In general, RDCs derived from the TRS strategy adopted less negative or even positive values compared to those obtained from the SRS strategy (Fig. 7, green lines). In some cases, such as for eba181 and ntailMV, almost the entire RDC profile remained positive. We attribute this systematic deviation towards positive values to an overpopulation of α-helical conformations in the tripeptide database, as previously observed when using coil libraries derived from globular proteins [START_REF] Jha | Statistical coil model of the unfolded state: Resolving the reconciliation problem[END_REF][START_REF] Schweitzer-Stenner | Construction and comparison of the statistical coil states of unfolded and intrinsically disordered proteins from nearest-neighbor corrected conformational propensities of short peptides[END_REF]. Interestingly, some local features observed in the experimental profiles, which were not reproduced by the SRS strategy, were captured by the TRS strategy. Theoretical RDCs for α-helical regions in ntailMV, ntailSV and MKK7 were systematically more positive than those corresponding to their flanking regions. In fact, these were the only three cases for which the Q-factor for the TRS was better than that of the SRS. Moreover, turns in K18 and Tau were naturally pinpointed by the TRS strategy, producing sharp peaks in the RDC profile. Note that more negative RDC values were also observed in some cases, such as the N-terminus of p15. These observations indicate that some tripeptide sequences in the database are enriched in particular conformational classes that are present in solution.

A hybrid sampling strategy simultaneously describes structural properties of disordered and partially ordered regions

The satisfactory description of disordered and partially structured regions achieved with the SRS and TRS strategies, respectively, prompted us to apply with those computed using the hybrid SRS-TRS sampling strategy (red solid lines). Fragments highlighted in orange correspond to regions considered partially structured, for which the TRS was applied (see Table S2 for details).

a hybrid building approach. In this approach, residues belonging to a partially structured region defined a priori were incorporated into the model using the TRS strategy, while the rest of the chain was built with the SRS strategy. For the nine proteins tested, we defined the partially structured regions on the basis of the experimental N-HN RDCs and previously reported structural analyses 165 (see Table S2). In this regard, SRS-derived RDCs were compared with the experimental ones, and those regions presenting a systematic deviation were initially assigned as partially structured. The exact borders of these regions were subsequently refined by testing multiple alternatives. The Q-factors, revealed excellent agreement between the simulated and the experimental RDC 170 profiles for all the proteins tested (Fig. 8 and Table S1). This metric thereby indicates that the hybrid strategy, which simultaneously describes disordered and partially structured regions, notably improved the SRS and TRS chain building approaches. However, the level of Q-factor improvement depended on the percentage of the sequence involved in secondary structural elements (Table S1). In highly disordered proteins such as eba181, the improvement of the hybrid method with respect to the SRS approach was modest, with Computed RDCs for the α-helical regions of MKK7, ntailMV and ntailSV nicely reproduced the experimentally observed bell-shape and the saw-teeth.

Importantly, the description of the positive RDCs did not compromise that of the disordered regions as the model captured their relative intensity. Other characteristic features observed in the experimental RDC profiles, such as turns in eba181, K18 and Tau (see below), the broken helix in the 60-75 fragment of src caused by two consecutive glycine residues [START_REF] Pérez | Structural characterization of the natively unfolded N-terminal domain of human c-Src kinase: Insights into the role of phosphorylation of the unique domain[END_REF], and the sharp inverse γ-turn of W61 of p15 [START_REF] De Biasio | p15PAF is an intrinsically disordered protein with nonrandom structural preferences at sites of interaction with other proteins[END_REF], naturally emerged when using the hybrid approach. Remarkably, this building method did not require the specification of either the type or the population of secondary structures. Protein Tau is a particularly challenging example due to its size and the presence of multiple structural features, which have been extensively studied by NMR [START_REF] Mukrasch | Highly populated turn conformations in natively unfolded tau protein identified from residual dipolar couplings and molecular simulation[END_REF]Ozenne et al., 2012b;[START_REF] Schwalbe | Predictive atomic resolution descriptions of intrinsically disordered htau40 and alpha-synuclein in solution from NMR and small angle scattering[END_REF].

Seven regions of Tau were defined as structured using the hybrid approach, four of them being the well described turns found in the repeat region corresponding to the K18 construct [START_REF] Mukrasch | Highly populated turn conformations in natively unfolded tau protein identified from residual dipolar couplings and molecular simulation[END_REF]Ozenne et al., 2012b). The presence of highly positive RDC values found in these four turns were captured by the hybrid approach in both proteins (Fig. 8), thereby indicating the realistic conformational representation of their sub-sequences in the database.

CSs were used to further validate the conformational ensembles built with the hybrid SRS-TRS strategy. In this regard, averaged Cα, Cβ, CO and NH CSs for ntailMV were computed from the ensembles using the program SPARTA+ [START_REF] Shen | Sparta+: a modest improvement in empirical nmr chemical shift prediction by means of an artificial neural network[END_REF] and then compared with the experimental ones (Fig. S4).

The simulated CSs were in good agreement with the experimental ones, and they clearly captured deviations from the purely random coil behavior represented by the SRS ensemble. These observations substantiate the results obtained when using RDCs.

Comparison to SAXS data

SAXS accurately probes the overall properties of conformational ensembles in solution, thus complementing the residue-specific information provided by RDCs and CSs [START_REF] Cordeiro | Small-angle scattering studies of intrinsically disordered proteins and their complexes[END_REF][START_REF] Sibille | Structural characterization of intrinsically disordered proteins by the combined use of NMR and SAXS[END_REF]. Simulated SAXS profiles were computed from the ensembles using standard procedures (see Method Details). Overall, excellent agreement between experimental and simulated profiles was observed for the three proteins, with χ 2 of 1.93, 1.04, and 1.52 for src, p15 and Tau, respectively (Fig. S1). For src and Tau, these values were notably better than those obtained with the SRS (χ 2 of 2.70 and 2.02) and the TRS (χ 2 of 2.58 and 2.15) sampling approaches. For p15, the profiles achieved the three sampling strategies showed an excellent correlation with the experimental profile, with χ 2 near 1.0. These results strongly suggest that the ensembles built with the hybrid approach properly describe the overall properties of IDPs.

Prediction of local conformations and secondary structural elements

The previous sections demonstrate that the ensembles built with the hybrid approach are realistic models of IDPs in solution. Next, we explored the structural features of the resulting models using the helical region in ntailMV, the extended region at the N-terminus of p15, and the turns in eba181 and K18 as examples.

For ntailMV, the hybrid strategy notably enriched the structured region in α-helical conformations while it was depleted in extended (β-S) and polyproline-II (β-P) (Fig. 9a). This structural enrichment in helical conformations induced positive RDC values in this region. The conformational analysis of the ensemble built for the N-terminus of p15 indicated a strong enrichment in extended conformations, β-S and β-P, whereas α-helical ones were depleted (Fig. 9b).

Interestingly, neither β-S nor β-P were homogeneously populated along the segment, and either one or the other became dominant depending on the specific sequence.

A highly relevant feature of the hybrid strategy is its ability to identify turns from sequences. Four turns have been localized in eba181 based on their positive RDCs [START_REF] Blanc | Intrinsic disorder within the erythrocyte binding-like proteins from plasmodium falciparum[END_REF], however the sizes of these RDCs differed (Fig. 8).

While turns 3 (DASL) and 4 (DDAK) presented highly positive values, turns 1 (DPEK) and 2 (DPNT) were only slightly positive thereby suggesting distinct structural features. Fig. 10 shows the conformations adopted by the residues involved in the four turns. In all turns, residue i + 1 adopted an α-helical conformation. However, while residue i in turns 1 and 2 was mainly extended due to the following proline, it was α-helical in turns 3 and 4. This structural difference most probably explains the different RDC values of the four turns.

According to current definitions (de Brevern, 2016), the four turns can be considered β-turns, types I and VIII being compatible with the conformation of the residue i + 1. Nevertheless, the sequence composition clearly suggests that turns 1 and 2 with D and P in positions i and i + 1, respectively, are type I β-turns (de Brevern, 2016). In another example, the four turns identified in K18 were enriched in α-helical conformations in their two central residues (Fig. S2), an observation that is in line with the original study [START_REF] Mukrasch | Highly populated turn conformations in natively unfolded tau protein identified from residual dipolar couplings and molecular simulation[END_REF]. However, residues in position i + 1 (L253, L248, L315 and F346) sampled the region {φ = -90, ψ = 0} whereas residues i + 2 (K254, N285, S316, and K347) adopted mainly an α-helical conformation with {φ = -60, ψ = -30}. Although resembling type I β-turns, they did not adopt the canonical conformation (de Brevern, 2016).

Coordinated formation of structural elements

We further studied how secondary structural elements are formed within the conformational ensembles using the helical region in MKK7 as an example (Fig. 11a). The Secondary Structure-map (SS-map) [START_REF] Iglesias | SS-map: Visualizing cooperative secondary structure elements in protein ensembles[END_REF], which allows the quantification of multiple structured elements within conformational ensembles, was used for this analysis. According to the SS-map, the ensemble of the N-terminal region of MKK7 presented scarcely populated helical regions of virtually all sizes from 4 up to 28 residues. Although the helix encompassing the whole 28-residue-long region was found in the ensemble, its population was extremely low, and shorter α-helices were preferred. In this regard the most populated helices (around 5%) involved eight and nine residues in non-overlapping segments of the protein. Interestingly, the N-terminal region of this fragment seemed more prone to form long α-helices expanding up to 15 residues. The continuum of multiple overlapping helical sections observed in the ensemble of MKK7, which induces the bell-shape of the resulting RDC profile, highlights the conformational complexity of helical regions in IDPs.

We tested two alternative procedures to introduce helicity into ensembles generated using a Flory model (i.e. the SRS strategy in our implementation) that are frequently used to describe NMR data [START_REF] De Biasio | p15PAF is an intrinsically disordered protein with nonrandom structural preferences at sites of interaction with other proteins[END_REF]Ozenne et al., 2012b;[START_REF] Pérez | Structural characterization of the natively unfolded N-terminal domain of human c-Src kinase: Insights into the role of phosphorylation of the unique domain[END_REF][START_REF] Wells | Structure of tumor suppressor p53 and its intrinsically disordered n-terminal transactivation domain[END_REF][START_REF] Bernadó | A self-consistent description of the conformational behavior of chemically denatured proteins from nmr and small angle scattering[END_REF]. Firstly, a 25% increase in α-helical conformations was imposed for each of the residues within the region, but no structural coordination between residues was forced (Fig. 11b). Secondly, a canonical α-helix spanning the 28-residue-long region was introduced in 25% of the conformations (Fig. 11c). When the helical tendency was increased at the residue level, the resulting ensemble displayed multiple short helices spanning the whole region. However, the population of longer helices decreased dramatically. Consequently, resulting RDCs were positive but with values close to zero and they did not display residue-specific features. When a canonical α-helix was forced within the complete region no shorter helices spontaneously formed in the remaining 75% of the ensemble.

As a result of this conformational homogeneity, the RDC profile adopted large positive values with the saw-teeth shape induced by the continuous α-helix.

However, RDCs did not present the overall bell-shape observed experimentally.

To further evaluate the ensembles generated with the aforementioned procedures, we also used two-dimensional plots that display the deviation with respect 295 to a canonical α-helix (see Fig. S3 and the associated explanations in SI). In these plots, each conformation is represented by a point with the x coordinate corresponding to the distance between the first N and last C backbone atoms of the 28-residue fragment, and the y coordinate corresponding to the average distance between H-bond donor and acceptor atoms within this fragment. The 300 wide structural heterogeneity found in ensembles built with the hybrid approach was clearly highlighted using this representation. In contrast, distributions produced by the two other approaches were less likely from a physical point of view. In particular, the discontinuity in the conformational space produced by imposing a given percentage of a canonical helix is unrealistic. Indeed, although this last procedure can yield good agreement between computationally generated ensembles and experimental data in some cases, these ensembles are inaccurate representations of the conformational heterogeneity expected in partially structured regions in IDPs.

A SS-map analysis was also performed in the helical regions of ntailSV and ntailMV (Fig. 12). As in the case of MKK7, the co-existence of multiple overlapping short α-helices was observed. However, in contrast to MKK7, these two proteins displayed a triangular shape in the SS-map, in agreement with their similar amino acid sequence and function. This shape arises from the presence at the N-terminus of the motif of multiple residues with a strong tendency to trigger the formation of α-helical segments. The most prevalent initial residues of the detected helices in our ensembles were aspactic acid and serine. These two amino acids have been identified as helix N-capping amino acids, which stabilize α-helices with their side chain by forming a hydrogen bond at positions 2 or 3 in the helix [START_REF] Jensen | Quantitative conformational analysis of partially folded proteins from residual dipolar couplings: Application to the molecular recognition element of sendai virus nucleoprotein[END_REF][START_REF] Lovell | Structure validation by Cα geometry: φ, ψ and Cβ deviation[END_REF]. This observation suggests that the N-capping properties of these amino acids are encoded in the tripeptide database and that their capacity to initiate helical motifs naturally emerges in ensembles built with the hybrid strategy.

Discussion

Partially structured motifs are key elements to trigger signaling events and to regulate transcription and metabolic pathways [START_REF] Tompa | Intrinsically disordered proteins: Emerging interaction specialists[END_REF]. The localization and characterization of these motifs inserted within fully disordered fragments have been the focus of intense research [START_REF] Tompa | Intrinsically disordered proteins: Emerging interaction specialists[END_REF][START_REF] Van Roey | Short linear motifs: Ubiquitous and functionally diverse protein interaction modules directing cell regulation[END_REF][START_REF] Mohan | Analysis of molecular recognition features (MoRFs)[END_REF]. Here we present an approach that exploits the structural information encoded in tripeptide fragments extracted from coil regions of experimentally determined protein structures to build realistic structural ensembles of IDPs/IDRs, including scarcely populated structured motifs.

Although Flory models, which do not consider the sequence context, generate conformational ensembles with the capacity to reproduce diverse experimental data for disordered chains, they fail to predict and model partially structured elements. Our results demonstrate that the tripeptide database, which accounts for this sequence context, contains structural features that are subsequently found experimentally in solution. Whereas libraries involving larger fragments have been shown to be powerful tools for the prediction of probable (stable) conformations of globular proteins and peptides [START_REF] Han | Global properties of the mapping between local amino acid sequence and local structure in proteins[END_REF][START_REF] Kolodny | Small libraries of protein fragments model native protein structures accurately[END_REF][START_REF] Rohl | Protein structure prediction using Rosetta[END_REF][START_REF] Baeten | Reconstruction of protein backbones from the brix collection of canonical protein fragments[END_REF][START_REF] Shen | Improved PEP-FOLD approach for peptide and miniprotein structure prediction[END_REF][START_REF] Mackenzie | Tertiary alphabet for the observable protein structural universe[END_REF], our results highlight that our extensive database of three-residue fragments is enough to represent the conformational variability and local structural propensities in IDPs. Moreover, representing the conformational variability of disordered chains requires a broad sampling of structures, which would not be guaranteed using databases of larger fragments. In this regard our tripeptide database emerges as optimal for this purpose.

The general agreement between experimental and simulated RDCs implies that the residue-specific structural information encoded in our tripeptide database is coherent with the conformational behavior of IDPs in solution. This is a remarkable observation as the database has been derived from coil regions of crystallographic structures, which are susceptible to experience packing contacts and/or reduced mobility. Therefore, the sequence context is a major determinant of structural propensities, regardless of the state (globular/disordered) or the environment (crystal/solution). However, for some sequences, a less accurate agreement between the experimental and simulated RDC profiles has been observed. We attribute this local lack of agreement to the limited conformational coverage of these sequences in our database. With the increasing number of experimentally determined high-resolution protein structures, we expect that more extensive and higher quality tripeptide databases will be built in the future, which will further improve the quality of conformational ensembles generated with our method.

Our approach relies on the discrimination between disordered and partially structured regions to subsequently apply the SRS and TRS sampling strategies, respectively. Here we have used the experimental RDCs and previous studies of the considered proteins to define both regions. In the absence of RDCs, other experimental data and bioinformatics predictions can be used to identify partially structured motifs. CSs, which are the primary information derived from NMR, are also very sensitive to small conformational bias at the residue level [START_REF] Tamiola | Sequence-specific random coil chemical shifts of intrinsically disordered proteins[END_REF][START_REF] Schwarzinger | Sequence-dependent correction of random coil nmr chemical shifts[END_REF]. Partially structured motifs can also be discriminated from fully disordered regions by their faster NMR transverse relaxation rates [START_REF] Jensen | Intrinsic disorder in measles virus nucleocapsids[END_REF][START_REF] De Biasio | p15PAF is an intrinsically disordered protein with nonrandom structural preferences at sites of interaction with other proteins[END_REF]. Multiple bioinformatics tools based on different principles identify regions prone to forming structures [START_REF] Deng | An overview of practical applications of protein disorder prediction and drive for faster, more accurate predictions[END_REF]. Another interesting source to distinguish structured elements is sequence conservation analysis. In IDPs, motifs involved in protein-protein interactions present slower mutational rates when compared to non-functional regions [START_REF] Ota | Sequence conservation of protein binding segments in intrinsically disordered regions[END_REF]. The tripeptide database can also be used to identify structured regions. In several examples, such as ntailSV, MKK7, and p15, the TRS sampling strategy pinpointed partially structured regions and turns when yielding larger RDC values (either positive or negative) than the rest of the chain. This observation is caused by the conformational enrichment that these sequences present in the database, which biases the sampling and narrows the RDC averaging. In this context, and in the absence of experimental information, a simple TRS ensemble can provide insights into structurally relevant motifs within IDPs.

Partially structured motifs are not permanently folded in IDPs. They can be seen as an equilibrium between conformations hosting distinct smaller structured elements that are in continuous exchange driven by their extension or shortening. In other words, these sequences lack the internal coordination to form permanent secondary structural motifs and, as a consequence, are susceptible to partial unfolding events. Recognition processes exploit this structural heterogeneity to efficiently achieve the desired biological tasks. Binding affinities of the co-existing conformers are modulated by the entropic penalty caused by the folding of the recognition motif fragment that remains disordered in the unbound state [START_REF] Pancsa | Interactions via intrinsically disordered regions: What kind of motifs?[END_REF]. Moreover, recognition kinetics studies have demonstrated the existence of transiently populated encounter complexes, and different conformational states of the recognition element most probably present distinct energy barriers to achieve the final bound form [START_REF] Schneider | Visualizing the molecular recognition trajectory of an intrinsically disordered protein using multinuclear relaxation dispersion NMR[END_REF][START_REF] Sugase | Mechanism of coupled folding and binding of an intrinsically disordered protein[END_REF][START_REF] Delaforge | Deciphering the dynamic interaction profile of an intrinsically disordered protein by nmr exchange spectroscopy[END_REF]. In the context of RDCs, the coexistence of multiple partially folded helical elements in the same region leads to the bell-shaped RDC profile and the saw-teeth, which report on the prevalence of the different helical fragments. Importantly, this structural heterogeneity is nicely captured by our hybrid sampling strategy, thereby highlighting the correspondence between the information encoded in the database and the conformational sampling of IDPs in solution. This feature is exemplified by the helix N-capping properties that we observed in the ensembles of ntailMV and ntailSV.

In summary, we have developed a method to build realistic conformational ensembles of IDPs and IDRs that describes scarcely populated secondary structural elements embedded in otherwise fully disordered regions. Our strategy is based on an extensive database of tripeptide structures and on the sepa-ration between disordered and partially structured regions within the chain.

Conformationally-biased ensembles generated with our approach will be better starting models for programs that integrate experimental data to derive structural models of IDPs. This will be specially relevant for strategies such as those based on the maximum entropy principle, aiming at minimizing the structural perturbation exerted to the initial ensemble to fit the experimental data [START_REF] Esteban-Martin | Refinement of ensembles describing unstructured proteins using nmr residual dipolar couplings[END_REF][START_REF] Rozycki | Saxs ensemble refinement of escrtiii chmp3 conformational transitions[END_REF]. Moreover our approach detects binding motifs involved in partner recognition that are, in most cases, linked to biological tasks. Our approach has the potential to anticipate structural effects caused by point mutations with an eventual role in disease, and the insertion or deletion of disordered fragments originating from alternative splicing processes. In this regard, we believe that our approach is the first step towards extending structural bioinformatics and protein design to disordered proteins. experiments; A.E., N.S., J.C. and P.B analyzed the data; A.E., J.C. and P.B. wrote the paper.

440

Sampling methods

Conformations were built incrementally from N-to C-termini in a residueby-residue manner. When placing a new residue, its backbone angles {φ, ψ, ω} were extracted from the coil database. An all-atom model was used for the backbone, whereas a simplified model was used for the side-chains, considering a pseudo-atom placed at the Cβ position for each residue, as previously proposed [START_REF] Levitt | A simplified representation of protein conformations for rapid simulation of protein folding[END_REF][START_REF] Bernadó | A structural model for unfolded proteins from residual dipolar couplings and small-angle X-ray scattering[END_REF]Ozenne et al., 2012a).

When placing a new residue, collisions with the previously built residues were tested.

In case of collision, a new configuration of the residue was sampled and tested. This was repeated until a valid configuration was found or a maximum number trials of 100 (n col f ail = 100) was reached. In these cases a backtracking search process was applied, which consisted of removing the last three residues and restarting sampling from this point. When the backtracking process resulted unsuccessful, the chain construction was restarted from the beginning.

Single-residue-based sampling (SRS): This strategy is similar to the one used in Flexible-Meccano [START_REF] Bernadó | A structural model for unfolded proteins from residual dipolar couplings and small-angle X-ray scattering[END_REF]Ozenne et al., 2012a). The backbone angles of each residue are sampled disregarding the neighboring residues. In this strategy, when the residue type is alanine, the angles are randomly selected among all tripeptide conformations of type X-Ala-Z, X and Z being any of the 20 amino acid types (i.e. 400 tripeptide sequence types). The process is slightly different when the Z residue is a proline. In this case, the conformation is selected from sequences X-Ala-Pro.

Three-residue-based sampling (TRS): This strategy takes into account the sequence of the neighboring residues i -1 and i + 1 when sampling the conformation of residue i. In other words, when the amino acid types of residues i -1, i, i + 1 are X, Y, Z, respectively, the conformation of residue i is sampled from the corresponding class X-Y-Z in the tripeptide database. In addition, the conformation of these two neighbors is considered in order to restrict sampling to the most structurally probable regions. For this purpose, sampling of residue i is constrained to a subset of conformations of the tripeptide class X-Y-Z, such that the backbone angles of residue i-1 are within a given angular range (±20 • ) around its current conformation, which was built in the previous step. Since the conformation of residue i + 1 is not sampled in this building step, the structural restriction requires a back-step test. Once the conformation of residue i has been built, the conformation of the tripeptide formed by residues i -2, i -1, and i is checked to be present in the database of the corresponding sequence, considering the aforementioned angular tolerance. As for collision tests, this structural test can also fail. In this case, a backtracking process is also applied, with n str f ail = 250. Hybrid Sampling: The two sampling strategies SRS and TRS were combined in the hybrid strategy. Based on experimental RDCs and on additional information from previous studies, TRS is applied to sample partially structured regions while SRS is used for the disordered regions.

Computation of experimental properties from ensembles

Alignment properties and associated RDCs for each conformation were computed by exploiting the similarity between the radius of gyration and the alignment tensors as previously described [START_REF] Almond | Physical interpretation of residual dipolar couplings in neutral aligned media[END_REF][START_REF] Bernadó | A structural model for unfolded proteins from residual dipolar couplings and small-angle X-ray scattering[END_REF]. Reported RDCs correspond to averages over 100,000 conformations of each ensemble. Computational RDCs were homogeneously scaled to minimize discrepancy with the experimental ones. The agreement of the resulting RDCs with the experimental ones was evaluated using the Q-factor [START_REF] Cornilescu | Validation of protein structure from anisotropic carbonyl chemical shifts in a dilute liquid crystalline phase[END_REF]: Q = rms(D meas -D calc )/rms(D meas ), where D meas and D calc are the experimental and computed RDCs, respectively.

Ensemble-averaged SAXS data were computed from 2,000 randomly selected conformations from the ensembles generated with the three sampling strategies. Side-chains for each conformation were introduced with SCWRL4 [START_REF] Krivov | Improved prediction of protein side-chain conformations with SCWRL4[END_REF] before computation of its associated theoretical SAXS profile with CRYSOL [START_REF] Svergun | CRYSOL -a program to evaluate X-ray solution scattering of biological macromolecules from atomic coordinates[END_REF] using default parameters. The ensemble-averaged curve was compared with the experimental one by optimizing a scaling and a shift parameter, using χ 2 as a figure of merit. Averaged

Figure 1 :

 1 Figure1: Experimental N-HN RDCs (black solid lines) for the nine proteins analyzed compared with the theoretical RDCs computed using the SRS (blue solid line) and TRS (green solid line) sampling strategies. To facilitate visual analysis, RDCs from the SRS method were scaled considering only the regions defined as random coil in the hybrid approach .

Figure 2 :

 2 Figure 2: Experimental N-HN RDCs (black solid lines) for the nine IDPs studied compared

Figure 3 :

 3 Figure 3: Experimental (black) and hybrid building model (green) N-HN RDCs for two fragments of (a top) ntailMV and (b top) p15. Fragments highlighted in orange were considered partially structured and built using the TRS strategy. In bottom panels, the percentage of enrichment of secondary structure classes present in the ensemble built with the hybrid strategy compared with that built with the SRS strategy. Secondary structure classes were identified using definitions in related work (Ozenne et al., 2012b). Concretely, [βS : -100 > φ; -120 > ψ > 50], [βP : 0 > φ > -100; -120 > ψ > 50], [αR : 0 > φ; 50 > ψ > -120], [αL : φ > 0].

Figure 4 :

 4 Figure 4: Conformational sampling for the four turns identified in eba181. Each column displays the Ramachandran plots for the three first residues in turns 1 to 4 when using the SRS (blue) or the hybrid (green) sampling approaches.

Figure 5 :

 5 Figure 5: Structural analysis of the helical region in MKK7. (Top panels) Length and encompassing residues of the α-helices found in ensembles computed using (a) the hybrid sampling and two theoretical models imposing (b) 25% of enhanced helicity per residue, and (c) 25% population of a canonical α-helix in the 28-residue long segment. Colors from white to red indicate the population of helical segments found in the ensembles. (Bottom panels) Theoretical RDCs calculated from the above described ensembles (red lines) compared with the experimental ones (black lines).

  Figure 6: SS-map analysis for the helical regions in ntailMV and ntailSV displaying the length and the composing residues of the α-helices found in ensembles generated with the hybrid sampling strategy for both proteins. Color from white to red indicates the population of these helices. Vertical lines indicate aspartic acids and serines in the sequence that act as helix N-capping residues. Concretely, D484, D487, S488, S491, and D493 are highlighted for ntailMV, and D473, D475, S477, and D478 and highlighted for ntailSV.

Figure 7 :

 7 Figure7: Experimental N-HN RDCs (black solid lines) for the nine proteins analyzed compared with the theoretical RDCs computed using the SRS (blue solid line) and TRS (green solid line) sampling strategies. To facilitate visual analysis, RDCs from the SRS method were scaled considering only the regions defined as random coil in the hybrid approach.

Figure 8 :

 8 Figure8: Experimental N-HN RDCs (black solid lines) for the nine IDPs studied compared with those computed using the hybrid SRS-TRS sampling strategy (red solid lines). Fragments highlighted in orange correspond to regions considered partially structured, for which the TRS was applied (see TableS2for details).

Figure 9 :

 9 Figure 9: Experimental (black) and hybrid building model (green) N-HN RDCs for two fragments of (a top) ntailMV and (b top) p15. Fragments highlighted in orange were considered partially structured and built using the TRS strategy. In bottom panels, the percentage of enrichment of secondary structure classes present in the ensemble built with the hybrid strategy compared with that built with the SRS strategy. Secondary structure classes were identified using definitions in related work (Ozenne et al., 2012b). Concretely, [βS : -100 > φ; -120 > ψ > 50], [βP : 0 > φ > -100; -120 > ψ > 50], [αR : 0 > φ; 50 > ψ > -120], [αL : φ > 0].

Figure 10 :

 10 Figure10: Conformational sampling for the four turns identified in eba181. Each column displays the Ramachandran plots for the three first residues in turns 1 to 4 when using the SRS (blue) or the hybrid (green) sampling approaches.

Figure 11 :

 11 Figure 11: Structural analysis of the helical region in MKK7. (Top panels) Length and encompassing residues of the α-helices found in ensembles computed using (a) the hybrid sampling and two theoretical models imposing (b) 25% of enhanced helicity per residue, and (c) 25% population of a canonical α-helix in the 28-residue long segment. Colors from white to red indicate the population of helical segments found in the ensembles. (Bottom panels) Theoretical RDCs calculated from the above described ensembles (red lines) compared with the experimental ones (black lines).

Acknowledgments

The authors thank M. Zweckstetter (U. Göttingen), M. Blackledge and M.R.

Jensen (IBS-Grenoble

) for sharing experimental data. This work was supported by the European Research Council under the H2020 Programme (2014-2020) chemREP EAT [648030], and Labex EpiGenMed (ANR-10-LABX-12-01) awarded to P.B., and the ANR GPCteR (ANR-17-CE11-0022-01) to N.S. The CBS is a member of the French Infrastructure for Integrated Structural Biology-FRISBI (ANR-10-INSB-05). We used the HPC resources of the CALMIP supercomputing center under the allocation 2016-P16032.

Author Contributions

STAR Methods

Contact for Reagent and Resource Sharing

Further information and requests for resources and reagents should be directed to and will be fulfilled by the Lead Contact, Pau Bernadó (pau.bernado@cbs.cnrs.fr).

Method Details

Experimental NMR and SAXS data Details on the RDCs and SAXS data analyzed in this study can be found in the original articles cited in Section 2.1.

Structural database

The tripeptide database was built from a curated database of high-resolution experimentally determined protein structures. We used the SCOPe [START_REF] Fox | SCOPe: Structural classification of proteins-extended, integrating SCOP and ASTRAL data and classification of new structures[END_REF] 2.06 release, with entries having less than 95% sequence identity to each other. A total of 8,907,065 of three-residue fragments were extracted from these protein structures and classified on the basis of their sequence (8,000 tripeptide classes).

Conformations sampled by residues were assigned using the program DSSP [START_REF] Kabsch | Dictionary of protein secondary structure: Pattern recognition of hydrogen-bonded and geometrical features[END_REF], which allowed us to filter out fragments corresponding to α-helices and β-strands.

More precisely, we removed all tripeptides containing at least one residue involved in these types of secondary structures (i.e. DSSP types H, G, I, E and B) from the database. This applied to approximately 60% of the total number of tripeptides extracted from the SCOPe database. The remaining 40% of the tripeptides (3,645,381), which contained residues in loop/coil regions (i.e. DSSP types L, T, S), were included in the coil database.

Cα, Cβ, CO and NH chemical shifts were computed from ensembles of 5,000 conformations with SPARTA+ [START_REF] Shen | Sparta+: a modest improvement in empirical nmr chemical shift prediction by means of an artificial neural network[END_REF]. Side-chains for each conformation were introduced with SCWRL4 ( [START_REF] Krivov | Improved prediction of protein side-chain conformations with SCWRL4[END_REF] before the calculation. Random coil chemical shifts were computed using POTENCI [START_REF] Nielsen | Potenci: prediction of temperature, neighbor and ph-corrected chemical shifts for intrinsically disordered proteins[END_REF] and subtracted from the computed ones to facilitate the 530 interpretation.

Declaration of Interests

The authors declare no conflict of interest.


Jonathan Cacace
email: jonathan.cacace@unina.it

Riccardo Caccavale
email: riccardo.caccavale@unina.it

Michelangelo Fiore
email: mfiore@laas.fr

Rachid Alami
email: rachid.alami@laas.fr

Alberto Finzi
email: alberto.finzi@unina.it

Rachid Alamì

Attentional Plan Execution for Human-Robot Cooperation

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

Introduction

In social robotics, flexible and natural interaction with humans is often needed in the context of structured collaborative tasks. In these scenarios, the robotic system should be capable of adapting the execution of cooperative plans with respect to complex human activities and interventions. Many mechanisms are indeed involved in humans cooperation [START_REF] Bratman | Shared agency. Philosophy of the social sciences: philosophical theory and scientific practice[END_REF], such as joint attention, action observation, task-sharing, and action coordination [START_REF] Sebanz | Joint action: bodies and minds moving together[END_REF][START_REF] Mutlu | Coordination mechanisms in human-robot collaboration[END_REF]. Furthermore, communication between humans involve different modalities such as speech, gaze orientation, gestures [START_REF] Breazeal | Designing Sociable Robots[END_REF]. Several systems manage the human-robot cooperation by planning (totally or partially) the action sequence for the agents involved in the interaction [START_REF] Fong | The human-robot interaction operating system[END_REF][START_REF] Karpas | Robust execution of plans for human-robot teams[END_REF][START_REF] Shah | Improved human-robot team performance using chaski, a human-inspired plan execution system[END_REF]; however, planning and replanning processes can be timeexpensive and can therefore impair the naturalness and the effectiveness of the interaction. In order to flexibly combine and orchestrate structured activities and reactive actions we exploit the concept of cognitive control proposed by the cognitive neuroscience literature [START_REF] Norman | Attention to action: Willed and automatic control of behavior[END_REF][START_REF] Botvinick | Conflict monitoring and cognitive control[END_REF]. Inspired by supervisory attentional system and contention scheduling models [START_REF] Norman | Attention to action: Willed and automatic control of behavior[END_REF][START_REF] Cooper | Hierarchical schemas and goals in the control of sequential behavior[END_REF][START_REF] Botvinick | Conflict monitoring and cognitive control[END_REF], we propose an integrated framework that combines planning, attentional regulations, and multimodal human-robot interaction in order to flexibly adapt plan execution according to the executive context and the multimodal intraction processes.

System Architecture

In Fig. 1, we illustrate the overall architecture of the human-robot interaction system, the main components are described below. Multimodal Interaction and Dialogue management. The multimodal HRI framework is appointed to recognize the multiple human commands and actions, such as utterances, gaze directions, gestures or body postures, and to provide an interpretation of users intentions according to the dialogue context. Following the approach proposed by [START_REF] Rossi | An extensible architecture for robust multimodal human-robot communication[END_REF], the multimodal recognition process is composed of three layers: the lower layer contains the classifiers of the single modalities; the middle layer, the fusion engine, exploits a Support Vector Machine (SVM)-based late fusion and provides an integration of the multiple inputs; the upper layer, the dialogue manager [START_REF] Lucignano | A dialogue system for multimodal human-robot interaction[END_REF], integrates the representation of the dialogue modelled as a Partially Observable Markov Decision Process (POMDP) and accomplishes the semantic interpretation of observations according to the context and the inner knowledge. The main feature of such structure is that the results of each layer are N-best lists of possible interpretations, which are fed to the next layer to solve the ambiguities in cascade.

Human Aware Task Planning. The system is endowed with a Human-Aware Task Planner (HATP) [START_REF] Lallement | HATP: An HTN Planner for Robotics[END_REF] which is based on a Hierarchical Task Networks (HTN) and a SHOP-like [START_REF] Nau | Shop: Simple hierarchical ordered planner[END_REF] refinement process. HATP is able to produce hierarchical plans for multi-agent systems (including humans), generating different sequences for each agent. Each action has a finite number of precondition links to other actions (which can be part of any sequence), allowing HATP to generate collaborative subtasks where more agents are involved. Furthermore, the actions of the domain can be associated with a duration and a cost function, while specific social rules could be defined along with a cost for their violation. By setting a different range of parameters the plans can be tuned to adapt the robot behavior to the desired level of cooperation.

Executive System. The executive process is managed by two subsystems: the supervision system [START_REF] Fiore | On planning and task achievement modalities for human-robot collaboration[END_REF] and the the attentional system [START_REF] Caccavale | Attentional regulations in a situated human-robot dialogue[END_REF][START_REF] Caccavale | Plan execution and attentional regulations for flexible human-robot interaction[END_REF][START_REF] Caccavale | Attentional top-down regulation and dialogue management in human-robot interaction[END_REF]. The first one is to interact with the task planner, monitor the plan execution and formulate replanning requests. The second one exploits bottom-up (stimuli-oriented) and top-down (task-oriented) influences to regulate the plan execution and the dialogue policy. The attentional system manages a cognitive control cycle that continuously updates the systems working memory (WM) and a set of attentional behaviors (BP) exploiting the task structure defined in a long term memory (LTM). Each task to be executed is associated with a hierachical structure which is allocated in working memory, the leaves of this structure are concrete attentional behaviors whose activations are top-down and bottom-up regulated by the attentional influences (see [START_REF] Caccavale | Attentional regulations in a situated human-robot dialogue[END_REF][START_REF] Broquère | An attentional approach to human-robot interactive manipulation[END_REF]). In this context, the dialogue policies are assimilated to special interactive behaviors, while the generated human aware plans are exploited as a guidance for the action selection and execution.

Case Studies

The proposed architecture has been tested in a case study inspired by a humanrobot co-working domain [START_REF] Alami | On human-aware task and motion planning abilities for a teammate robot[END_REF] proposed in the context of the SAPHARI project (FP7-ICT-287513). The environment is set as follows: there are three work locations, each containing a slot (slot1, slot2, slot3) and a table that supports a set of objects including a glue bottle (glueBottle) and some brackets (bracket1, bracket2). The user and the robot must cooperatively install the brackets in the slots, by first cleaning the slot, then applying the glue in the area, and finally fixing the bracket on it. In this context, the integrated system can flexibly adapt plan execution to unexpected behaviors of the human, avoiding the computation of a new plan while enabling a smoother and more natural interaction. In the following, we provide some examples where the proposed systems allows for overcoming impasses during the interaction.

Handover to Search. In a first scenario, the robot is waiting for a bracket from the human in order to install it. In the planned sequence the human should bring the object to the robot, however, the human remains idle and does not interact as expected. According to the plan, the robot should keep waiting for the human, however, the attentional system comes into play: in the absence of external stimuli, the activations of the receive behavior decreases with time. Therefore, after some seconds of waiting, since the human does not cooperate in the task, the activations of the search behavior become dominant with respect to receive, hence the robot can abandon the handover behavior and can start searching for the object by itself. Take to Search. In a second scenario, we consider the case of a robot that should get the bracket1 and give it to the human, which is to fix it on a slot. As suggested by the plan, the robot travels to the table in order to get the object, but it is not there. Analogously, to the previous case, since no environmental stimulation is present for the take action, the attentional system switches to a search behavior where the robot inspects other locations looking for bracket1. As soon as the object is found, the take action becomes dominant again allowing the robot to continue the plan.

Handover to Place. In a third scenario, we assume that the human is to obtain the glueBottle in order to glue slot1. Following the plan, the robot tries to perform an handover, but the human moves away from the working space (see Fig. 2). The supervision system cannot replan since the human has not performed its action and the plan is still valid. However, the attentional system can solve the impasse without waiting for the human initiative. Indeed, the bottom-up stimulation of the give decreases as the robot-human distance increases, while the place activations remain stable (depending on the table position). When place wins the contention, the robot places the object on the work location allowing for plan continuation. Once the place is accomplished, the supervision system can manage the action substitution by changing the monitored human action from receive to take.

Fig. 1 .

 1 Fig. 1. The overall human-robot interaction architecture.

Fig. 2 .

 2 Fig. 2. Handover in the experimental scenario: (up) the human receives the glueBottle, (down) the robot switches from handover to place.

ACKNOWLEDGMENT

The research leading to these results has been supported by the RoDyMan and SAPHARI projects, which have received funding from the European Research Council under Advanced Grant agreement number 320992 and 287513, respectively. The authors are solely responsible for its content. It does not represent the opinion of the European Community and the Community is not responsible for any use that might be made of the information contained therein.