On Laurent Vuillon Google Scholar Profil

**B. Bado, B. Hubert, L. Vuillon** Semantic Frontiers: Unearthing Trends with AI and Knowledge Graphs. ESOMAR Congress in Athens (2024).

**A. Gheeraert, C. Lesieur, V. Batista, L. Vuillon, I Rivalta** Connected Component Analysis of Dynamical Perturbation Contact Networks
. The Journal of Physical Chemistry B 2023, 127, 35, 7571–7580 2023

Describing protein dynamical networks through amino acid contacts is a powerful way to analyze complex biomolecular systems. However, due to the size of the systems, identifying the relevant features of protein-weighted graphs can be a difficult task. To address this issue, we present the connected component analysis (CCA) approach that allows for fast, robust, and unbiased analysis of dynamical perturbation contact networks (DPCNs). We first illustrate the CCA method as applied to a prototypical allosteric enzyme, the imidazoleglycerol phosphate synthase (IGPS) enzyme from Thermotoga maritima bacteria. This approach was shown to outperform the clustering methods applied to DPCNs, which could not capture the propagation of the allosteric signal within the protein graph. On the other hand, CCA reduced the DPCN size, providing connected components that nicely describe the allosteric propagation of the signal from the effector to the active sites of the protein. By applying the CCA to the IGPS enzyme in different conditions, i.e., at high temperature and from another organism (yeast IGPS), and to a different enzyme, i.e., a protein kinase, we demonstrated how CCA of DPCNs is an effective and transferable tool that facilitates the analysis of protein-weighted networks.

**M. Ohlmann, J. Garnier, L. Vuillon** Metanetwork: A R package dedicated to handling and representing trophic metanetworks
. Ecology and Evolution 13 (8), e10229 2023

Trophic networks describe interactions between species at a given location and time. Due to environmental changes, anthropogenic perturbations or sampling effects, trophic networks may vary in space and time. The collection of network time series or networks in different sites thus constitutes a metanetwork. We present here the R package metanetwork, which will ease the representation, the exploration and analysis of trophic metanetwork data sets that are increasingly available. Our main methodological advance consists in suitable layout algorithm for trophic networks, which is based on trophic levels and dimension reduction in a graph diffusion kernel. In particular, it highlights relevant features of trophic networks (trophic levels, energetic channels). In addition, we developed tools to handle, compare visually and quantitatively and aggregate those networks. Static and dynamic visualisation functions have been developed to represent large networks. We apply our package workflow to several trophic network data sets.

**M. Ohlmann, J. Garnier, L. Vuillon** Metanetwork: Handling and Representing Trophic Networks in Space and Time
. CRAN r-project 2023

A toolbox to handle and represent trophic networks in space or time across aggregation levels. This package contains a layout algorithm specifically designed for trophic networks, using dimension reduction on a diffusion graph kernel and trophic levels. Importantly, this package provides a layout method applicable for large trophic networks.

**S. Lespinats, B. Colange, D. Dutykh, L. Vuillon** Procédé de détermination de l’état d’un système
. Patent CEA-CNRS-USMB, FR3102263A1, 2020.

A method for determining the state of a system among a plurality of states, includes acquiring values of a reference physical quantity of the system corresponding to a plurality of points in an original space, each value being paired with one point of the plurality of points and with one state of the system; embedding a portion of the points in a representation space, the representation space being in bijection with a sub-variety of the original space, each point in the representation space being paired with one state; determining a pairing function that pairs any position of the original space with a position in the representation space; determining the position in the representation space of a point of the original space paired with an acquired value, and determining the state of the system from the position of the point paired with the acquired value in the representation space.

**P. Dulio, A. Frosini, S. Rinaldi, L. Tarsissi, L. Vuillon** Further steps on the reconstruction of convex polyominoes from orthogonal projections
. Journal of Combinatorial Optimization 44 (4), 2423-2442 6 2022

A remarkable family of discrete sets which has recently attracted the attention of the discrete geometry community is the family of convex polyominoes, that are the discrete counterpart of Euclidean convex sets, and combine the constraints of convexity and connectedness. In this paper we study the problem of their reconstruction from orthogonal projections, relying on the approach defined by Barcucci et al. (Theor Comput Sci 155(2):321–347, 1996). In particular, during the reconstruction process it may be necessary to expand a convex subset of the interior part of the polyomino, say the polyomino kernel, by adding points at specific positions of its contour, without losing its convexity. To reach this goal we consider convexity in terms of certain combinatorial properties of the boundary word encoding the polyomino. So, we first show some conditions that allow us to extend the kernel maintaining the convexity. Then, we provide examples where the addition of one or two points causes a loss of convexity, which can be restored by adding other points, whose number and positions cannot be determined a priori.

**B. Colange, L. Vuillon, S. Lespinats, D. Dutykh** MING: An interpretative support method for visual exploration of multidimensional data
. Information Visualization 21 (3), 246-269 2022

Dimensionality reduction enables analysts to perform visual exploration of multidimensional data with a low-dimensional map retaining as much as possible of the original data structure. The interpretation of such a map relies on the hypothesis of preservation of neighborhood relations. Namely, distances in the map are assumed to reflect faithfully dissimilarities in the data space, as measured with a domain-related metric. Yet, in most cases, this hypothesis is undermined by distortions of those relations by the mapping process, which need to be accounted for during map interpretation. In this paper, we describe an interpretative support method called Map Interpretation using Neighborhood Graphs (MING) displaying individual neighborhood relations on the map, as edges of nearest neighbors graphs. The level of distortion of those relations is shown through coloring of the edges. This allows analysts to assess the reliability of similarity relations inferred from the map, while hinting at the original structure of data by showing the missing relations. Moreover, MING provides a local interpretation for classical map quality indicators, since the quantitative measure of distortions is based on those indicators. Overall, the proposed method alleviates the mapping-induced bias in interpretation while constantly reminding users that the map is not the data.

**A. Gheeraert, L. Vuillon, L. Chaloin, O. Moncorgé, T. Very, S. Perez, V. Leroux, I. Chauvot de Beauchêne, D. Mias-Lucquin, M.-D. Devignes, I. Rivalta, B. Maigret** Singular Interface Dynamics of the SARS-CoV-2 Delta Variant Explained with Contact Perturbation Analysis
. Journal of Chemical Information and Modeling 62 (12), 3107-3122 4 2022

Emerging SARS-CoV-2 variants raise concerns about our ability to withstand the Covid-19 pandemic, and therefore, understanding mechanistic differences of those variants is crucial. In this study, we investigate disparities between the SARS-CoV-2 wild type and five variants that emerged in late 2020, focusing on the structure and dynamics of the spike protein interface with the human angiotensin-converting enzyme 2 (ACE2) receptor, by using crystallographic structures and extended analysis of microsecond molecular dynamics simulations. Dihedral angle principal component analysis (PCA) showed the strong similarities in the spike receptor binding domain (RBD) dynamics of the Alpha, Beta, Gamma, and Delta variants, in contrast with those of WT and Epsilon. Dynamical perturbation networks and contact PCA identified the peculiar interface dynamics of the Delta variant, which cannot be directly imputable to its specific L452R and T478K mutations since those residues are not in direct contact with the human ACE2 receptor. Our outcome shows that in the Delta variant the L452R and T478K mutations act synergistically on neighboring residues to provoke drastic changes in the spike/ACE2 interface; thus a singular mechanism of action eventually explains why it dominated over preceding variants.

**M. Achoch, G. Feverati, K. Salamatian, L. Vuillon, C. Lesieur** Cross-Talk Between Intramolecular and Intermolecular Amino Acid Networks Orchestrates the Assembly of the Cholera Toxin B Pentamer via the Residue His94
. AI2SD 2022: International Conference on Advanced Intelligent Systems for Sustainable Development pp 391–404

Protein assembly is the mechanism of combining two or more protein chains. Living organisms to trigger biological activity often uses this mechanism. The cholera toxin B subunit pentamer (CtxB5), the binding moiety of CtxAB5, a member of the AB5 toxin family, is presented here as a model for studying protein assembly. Experimental results showed the importance of histidine residues in CtxB5 assembly. Nevertheless, the histidines are located outside the pentamer interfaces suggesting an indirect role. Gemini and Spectral-Pro, two network-based models developped in our team, were used in combination with in silico mutations produced with Fold X to investigate this question. All the residues of the pentamer interfaces, so-called hotspots, were identified and some appeared to be chemical neighbors of the His 94, making possible a propagation path of conformational changes from the His 94 to the interface to regulate the pentamer assembly. Mutations of the residues along intra-to-inter amino acid paths produce non additive mutational perturbations of the interface energy, indicating influences of His 94 on its hotspot neighbors to regulate the interface. The role of intra-to-inter amino acid paths in regulating the pentamer interface was confirmed by applying similar approach to the heat labile toxin B pentamer (LTB5), which share 84% sequence identity, structural and functional similarity with CtxB5. Different intra-to-inter amino acid paths were identified for LTB5 consistently with the different assembly mechanisms followed by both toxin pentamers. These results open up avenues for understanding why these two toxins follow different assembly mechanisms.

**J. Shillcock, C. Lagisquet, J. Alexandre, L. Vuillon, J. Ipsen** Model biomolecular condensates have heterogeneous structure quantitatively dependent on the interaction profile of their constituent macromolecules
. AI2SD 2022: Soft Matter 18 6674-6693 2022

Biomolecular condensates play numerous roles in cells by selectively concentrating client proteins while excluding others. These functions are likely to be sensitive to the spatial organization of the scaffold proteins forming the condensate. We use coarse-grained molecular simulations to show that model intrinsically-disordered proteins phase separate into a heterogeneous, structured fluid characterized by a well-defined length scale. The proteins are modelled as semi-flexible polymers with punctate, multifunctional binding sites in good solvent conditions. Their dense phase is highly solvated with a spatial structure that is more sensitive to the separation of the binding sites than their affinity. We introduce graph theoretic measures to quantify their heterogeneity, and find that it increases with increasing binding site number, and exhibits multi-timescale dynamics. The model proteins also swell on passing from the dilute solution to the dense phase. The simulations predict that the structure of the dense phase is modulated by the location and affinity of binding sites distant from the termini of the proteins, while sites near the termini more strongly affect its phase behaviour. The relations uncovered between the arrangement of weak interaction sites on disordered proteins and the material properties of their dense phase can be experimentally tested to give insight into the biophysical properties, pathological effects, and rational design of biomolecular condensates.

**E. Aledavood, A. Gheeraert, A. Forte, L. Vuillon, I. Rivalta, F. Luque, C. Estarellas** Elucidating the Activation Mechanism of AMPK by Direct Pan-Activator PF-739
. Frontiers in Molecular Biosciences 8, 760026 2 2021

Adenosine monophosphate-activated protein kinase (AMPK) is a key energy sensor regulating the cell metabolism in response to energy supply and demand. The evolutionary adaptation of AMPK to different tissues is accomplished through the expression of distinct isoforms that can form up to 12 heterotrimeric complexes, which exhibit notable differences in the sensitivity to direct activators. To comprehend the molecular factors of the activation mechanism of AMPK, we have assessed the changes in the structural and dynamical properties of β1- and β2-containing AMPK complexes formed upon binding to the pan-activator PF-739. The analysis revealed the molecular basis of the PF-739-mediated activation of AMPK and enabled us to identify distinctive features that may justify the slightly higher affinity towards the β1−isoform, such as the β1−Asn111 to β2−Asp111 substitution, which seems to be critical for modulating the dynamical sensitivity of β1- and β2 isoforms. The results are valuable in the design of selective activators to improve the tissue specificity of therapeutic treatment.

**L. Pacini, R. Dorantes-Gilardi, L. Vuillon, C. Lesieur** Mapping function from dynamics: Future challenges for network-based models of protein structures
. Frontiers in Molecular Biosciences 8, 744646 2 2021

Proteins fulfill complex and diverse biological functions through the controlled atomic motions of their structures (functional dynamics). The protein composition is given by its amino-acid sequence, which was assumed to encode the function. However, the discovery of functional sequence variants proved that the functional encoding does not come down to the sequence, otherwise a change in the sequence would mean a change of function. Likewise, the discovery that function is fulfilled by a set of structures and not by a unique structure showed that the functional encoding does not come down to the structure either. That leaves us with the possibility that a set of atomic motions, achievable by different sequences and different structures, encodes a specific function. Thanks to the exponential growth in annual depositions in the Protein Data Bank of protein tridimensional structures at atomic resolutions, network models using the Cartesian coordinates of atoms of a protein structure as input have been used over 20 years to investigate protein features. Combining networks with experimental measures or with Molecular Dynamics (MD) simulations and using typical or ad-hoc network measures is well suited to decipher the link between protein dynamics and function. One perspective is to consider static structures alone as alternatives to address the question and find network measures relevant to dynamics that can be subsequently used for mining and classification of dynamic sequence changes functionally robust, adaptable or faulty. This way the set of dynamics that fulfill a function over a diversity of sequences and structures will be determined.

**C. Lagisquet, E. Pelantová, S. Tavenas, L. Vuillon** On the Markov numbers: fixed numerator, denominator, and sum conjectures
. Advances in Applied Mathematics 130, 102227 6 2021

The Markov numbers are the positive integer solutions of the Diophantine equation x^2+y^2+z^2=3xyz. Already in 1880, Markov showed that all these solutions could be generated along a binary tree. So it became quite usual (and useful) to index the Markov numbers by the rationals between 0 and 1 which stand at the same place in the Stern-Brocot binary tree. The Frobenius conjecture claims that each Markov number appears at most once in the tree. In particular, if the conjecture is true, the order of Markov numbers would establish a new strict order on the rationals. Aigner suggested three conjectures to better understand this order. The first one has already been solved for a few months. We prove that the other two conjectures are also true. Along the way, we generalize Markov numbers to any couple (p,q) of nonnegative integers (not only when they are relatively primes) and conjecture that the unicity is still true as soon as p≤q. Finally, we show that the three conjectures are in fact true for this superset.

**C. Lesieur, L. Vuillon** Topology Results on Adjacent Amino Acid Networks of Oligomeric Proteins
. Allostery: Methods and Protocols, 113-135 2021

In this chapter, we focus on topology measurements of the adjacent amino acid networks for a data set of oligomeric proteins and some of its subnetworks. The aim is to present many mathematical tools in order to understand the structures of proteins implicitly coded in such networks and subnetworks. We mainly investigate four important networks by computing the number of connected components, the degree distribution, and assortativity measures. We compare each result in order to prove that the four networks have quite independent topologies.

**K. Medková, E. Pelantová, L. Vuillon** Derived sequences of complementary symmetric Rote sequences
. * RAIRO-Theoretical Informatics and Applications. *

Complementary symmetric Rote sequences are binary sequences which have factor com- plexity C(n) = 2n for all integers n ≥ 1 and whose languages are closed under the exchange of letters. These sequences are intimately linked to Sturmian sequences. Using this connection we investigate the return words and the derivated sequences to the prefixes of any complementary symmetric Rote sequence v which is associated with a standard Sturmian sequence u. We show that any non-empty prefix of v has three return words. We prove that any derivated sequence of v is coding of three interval exchange transformation and we determine the parameters of this transformation. We also prove that v is primi- tive substitutive if and only if u is primitive substitutive. Moreover, if the sequence u is a fixed point of a primitive morphism, then all derivated sequences of v are also fixed by primitive morphisms. In that case we provide an algorithm for finding these fixing morphisms.

**L. Pacini, L. Vuillon, C. Lesieur** Induced Perturbation Network and tiling for modeling the L55P
Transthyretin amyloid fiber.
. Procedia Computer Science 178, 8-17.

Protein structures are complex spatial systems, formed by the three-dimensional arrangement of amino acids, that interact through atomic contacts. It is fundamental to understand the perturbation mechanisms associated with the amino acid mutations that lead to changes in a protein dynamics, as such mutations can lead to diseases. We present a methodology based on Amino Acid Networks and the use of Induced Perturbation Networks to infer the impact of amino acid mutations on a protein’s dynamics and the use of a tiling formalism to model protein aggregation. We apply this methodology to the case study of the L55P Transthyretin (TTR) variant, one of the most pathogenic mutations of TTR, due to its increased tendency to aggregate into amyloid fibers. We show that another pathogenic variant, V30M TTR, produces different results, reflecting a different pathogenic mechanism compared to that another pathogenic variant, V30M TTR, produces different results, reflecting a different pathogenic mechanism compared to L55P TTR and that the results differ for pathogenic and non-pathogenic variants (L55P and V30M TTR pathogenic variants versus L55P TTR and that the results differ for pathogenic and non-pathogenic variants (L55P and V30M TTR pathogenic variants versus T119Y and T119M non-pathogenic variants).

**B. Colange, L. Vuillon, S. Lespinats, D. Dutykh** Interpreting Distortions in Dimensionality Reduction by Superimposing Neighbourhood Graphs
. * Paper presented at IEEE VIS 2019 Conference. *

To perform visual data exploration, many dimensionality reduction methods have been developed. These tools allow data analysts to represent multidimensional data in a 2D or 3D space, while preserving as much relevant information as possible. Yet, they cannot preserve all structures simultaneously and they induce some unavoidable distortions. Hence, many criteria have been introduced to evaluate a map's overall quality, mostly based on the preservation of neighbourhoods. Such global indicators are currently used to compare several maps, which helps to choose the most appropriate mapping method and its hyperparameters. However, those aggregated indicators tend to hide the local repartition of distortions. Thereby, they need to be supplemented by local evaluation to ensure correct interpretation of maps. In this paper, we describe a new method, called MING, for `Map Interpretation using Neighbourhood Graphs'. It offers a graphical interpretation of pairs of map quality indicators, as well as local evaluation of the distortions. This is done by displaying on the map the nearest neighbours graphs computed in the data space and in the embedding. Shared and unshared edges exhibit reliable and unreliable neighbourhood information conveyed by the mapping. By this mean, analysts may determine whether proximity (or remoteness) of points on the map faithfully represents similarity (or dissimilarity) of original data, within the meaning of a chosen map quality criteria. We apply this approach to two pairs of widespread indicators: precision/recall and trustworthiness/continuity, chosen for their wide use in the community, which will allow an easy handling by users.

**A. Gheeraert, L. Pacini, V.S Batista, L.Vuillon, C.Lesieur, I. Rivalta** Exploring Allosteric Pathways of a V-Type Enzyme with Dynamical Perturbation Networks
. *The Journal of Physical Chemistry B 123 (16), 3452-3461, 2019*,

Elucidation of the allosteric pathways in proteins is a computational challenge that strongly benefits from combination of atomistic molecular dynamics (MD) simulations and coarse-grained analysis of the complex dynamical network of chemical interactions based on graph theory. Here, we introduce and assess the performances of the dynamical perturbation network analysis of allosteric pathways in a prototypical V-type allosteric enzyme. Dynamical atomic contacts obtained from MD simulations are used to weight the allosteric protein graph, which involves an extended network of contacts perturbed by the effector binding in the allosteric site. The outcome showed good agreement with previously reported theoretical and experimental extended studies and it provided recognition of new potential allosteric spots that can be exploited in future mutagenesis experiments. Overall, the dynamical perturbation network analysis proved to be a powerful computational tool, complementary to other network-based approaches that can assist the full exploitation of allosteric phenomena for advances in protein engineering and rational drug design.

**E. Domenjoud, B. Laboureix, and L. Vuillon** Facet Connectedness of Arithmetic Discrete Hyperplanes with Non-Zero Shift
. *LNCS, International Conference on Discrete Geometry for Computer Imagery*,

We present a criterion for the arithmetic discrete hyperplane to be facet connected when θ is the connecting thickness. We encode the shift μ in a numeration system associated with the normal vector and we describe an incremental construction of the plane based on this encoding. We deduce a connectedness criterion and we show that when the Fully Subtractive algorithm applied to has a periodic behaviour, the encodings of shifts μ for which the plane is connected may be recognised by a finite state automaton.

**A. Frosini and L. Vuillon** Tomographic reconstruction of 2-convex polyominoes using dual Horn clauses
. *Theoretical Computer Science 777, 329-337, 2019*,

Among the very many research interests of Maurice Nivat, a special role, according to the produced literature, was played by the study of the algorithmic and combinatorial aspects of connected finite discrete sets of points called polyominoes. In particular, he addressed the problem of a faithful reconstruction of some subclasses of them by imposing convexity constraints. The present study fits in this research line, and relies on a well known algorithm that Maurice Nivat and co-authors defined 1996 for the reconstruction of hv-convex polyominoes by orthogonal projections in polynomial time. Here, we consider a hierarchy on this class of polyominoes, and we continue a longstanding research on the reconstruction of its first levels by specializing the above mentioned result. The algorithm we propose bases on the possibility of characterizing the elements of the second level of the hierarchy, by a logic formula belonging to Dual-Horn and so polynomially solvable. Some related open problems are also presented.

**R. Dorantes-Gilardi, L. Bourgeat, L. Pacini, L. Vuillon and C. Lesieur** In proteins, the structural responses of a position to mutation rely on the Goldilocks principle: not too many links, not too few
. *Physical Chemistry Chemical Physics*,
vol. 20,(39), (2018) 25399-25410.

A disease has distinct genetic and molecular hallmarks such as sequence variants that are likely to produce the alternative protein structures accountable for individual responses to drugs and disease development. Thus, to set up customized therapies, the structural influences of amino acids on one another need to be tracked down. Using network-based models and classical analysis of amino acid and atomic packing in protein structures, the influence of first shell neighbors on the structural fate of a position upon mutation, is revisited. Regardless of the type and position in a structure, amino acids satisfy on average over their neighbors, a low and similar number of atomic interactions, the average called the neighborhood watch (Nw). The structural tolerance of a position to mutation depends on the modulation of the composition and/or proximity of neighbors to maintain the same Nw, before and after mutation, at every position. Changes, upon mutation of the number of atomic interactions at the level of individual pairs (wij) are structurally tolerated but influence structural dynamics. Robust, fragile and rescue interactions can be identified with Nw and wij, offering a framework to classify sequence variants according to position-dependent structural changes.

**A.
Casagrande et L. Vuillon,** Sciences
humaines et sociales et méthodes du numérique, un mariage
heureux ?. *Les
Cahiers du numérique*,
vol. 13,(3), (2017) 115-136.

Un nouveau domaine de recherche a vu le jour récemment au travers d’un manifeste rédigé en 2010 : les humanités numériques. Ces dernières ont comme objectif de combiner les sciences humaines et sociales (SHS) avec les méthodes du numérique. Or, ce mariage semble difficile au premier abord car chaque discipline possède son propre univers sémantique ainsi que ses propres méthodologies : la communication n’est pas toujours évidente. Malgré ces difficultés, nous souhaitons montrer dans cet article que les méthodes du numérique en se mettant à l’écoute des problématiques des SHS peuvent apporter davantage de légitimité aux résultats des recherches en SHS. Nous présentons un exemple de recherche entre chercheurs en mathématiques-informatique et chercheurs en psychologie qui a consisté à réaliser un contrôle négatif sur une expérience sur le thème de la mémoire.

**C. Reutenauer
and L. Vuillon,** Palindromic
Closures and Thue-Morse Substitution for Markoff Numbers,
*Uniform
Distribution Theory *12
(2017), no. 2, 25-35.

We state a new formula to compute the Markoff numbers using iterated palindromic closure and the Thue-Morse substitution. The main theorem shows that for each Markoff number m, there exists a word v ∈ {a, b}∗ such that m − 2 is equal to the length of the iterated palindromic closure of the iterated antipalindromic closure of the word av. This construction gives a new recursive construction of the Markoff numbers by the lengths of the word s involved in the palindromic closure. This construction interpolates between the Fibonaccinumbers and the Pell numbers.

**L.
Vuillon, D. Dutykh and F. Fedele,** "Some
special solutions to the Hyperbolic NLS equation."
Communications
in Nonlinear Science and Numerical Simulation (2018).

The Hyperbolic Nonlinear Schrödinger equation (HypNLS) arises as a model for the dynamics of three-dimensional narrow-band deep water gravity waves. In this study, the symmetries and conservation laws of this equation are computed. The Petviashvili method is then exploited to numerically compute bi-periodic time-harmonic solutions of the HypNLS equation. In physical space they represent non-localized standing waves. Non-trivial spatial patterns are revealed and an attempt is made to describe them using symbolic dynamics and the language of substitutions. Finally, the dynamics of a slightly perturbed standing wave is numerically investigated by means a highly accurate Fourier solver.

**I.
Gambini and L. Vuillon, **Tiling
the space by polycube analogues to Fedorov’s polyhedra,
*Fundamenta
Informaticae*,
**146**,
(2) (2016), 197–209.

We investigate minimal polycubes in terms of volume that tile the R3 space like the Fedorov’s polyhedra. In fact the 5 Fedorov’s polyhedra are convex polyhedra that tile the space by translation and we construct geometrical discrete objects formed by union of cubes with the same number of faces than the Fedorov’s polyhedra.

**M.
Achoch, R. Dorantes-Gilardi, C. Wymant, G. Feverati, K. Salamatian,
L. Vuillon and C. Lesieur,** Protein
structural robustness to mutations : an in silico investigation,
*Physical
Chemistry Chemical Physics*,
(2016).

Proteins possess qualities of robustness and adaptability to perturbations such as mutations, but occasionally fail to withstand them, resulting in loss of function. Herein, the structural impact of mutations is investigated independently of the functional impact. Primarily, we aim at understanding the mechanisms of structural robustness pre-requisite for functional integrity. The structural changes due to mutations propagate from the site of mutation to residues much more distant than typical scales of chemical interactions, following a cascade mechanism. This can trigger dramatic changes or subtle ones, consistent with a loss of function and disease or the emergence of new functions. Robustness is enhanced by changes producing alternative structures, in good agreement with the view that proteins are dynamic objects fulfilling their functions from a set of conformations. This result, robust alternative structures, is also coherent with epistasis or rescue mutations, or more generally, with non-additive mutational effects and compensatory mutations. To achieve this study, we developed the first algorithm, referred to as Amino Acid Rank (AAR), which follows the structural changes associated with mutations from the site of the mutation to the entire protein structure and quantifies the changes so that mutations can be ranked accordingly. Assessing the paths of changes opens the possibility of assuming secondary mutations for compensatory mechanisms.

**A.
Casagrande, E. Loza-Aguirre and L. Vuillon,**
*Improving
strategic scanning information analysis : an optimized measure for
information proximity evaluation*.
In Third International Conference on Entreprise Systems (IEEE
conference). Bale. 2015.

Strategic Scanning activities become less effective when faced with managing information overload. This paper introduces “nearness measure” (NM), a measure for information proximity evaluation. We also present and analyze the principles and properties of a graphical representation of the measure. We compare the measure to the usual Cosine similarity (CS). Even when the algorithm that calculates NM between texts is larger than CS in terms of complexity, NM with a minimization phase expresses an analysis of the documents from the general to the specific that is the opposite to what CS does. Thus, the manager using NM would require less time to explore collected information.

E. Domenjoud, X. Provençal and L. Vuillon ``Palindromic language of thin discrete planes ''

We work on the Reveill`es hyperplane P(v, 0, omega) with normal vector v in Rd, shift mu = 0 and thickness omega in R. Such a hyperplane is connected as soon as omega is greater than some value _(v,0), called the connecting thickness of v with null shift. In the case where v satisfies the so called Kraaikamp and Meester criterion, at the connecting thickness the hyperplane has very specific properties. First of all the adjacency graph of the voxels forms a tree. This tree appeared in many works both in discrete geometry and in discrete dynamical systems. In addition, it is well known that for a finite coding of length n of discrete lines, the number of palindromes in the language is exactly n + 1. We extend this notion of language to labeled trees and we compute the number of distinct palindromes. In fact for our voxel adjacency trees with n letters we show that the number of palindromes in the language is also n+1. This result establishes a first link between combinatorics on words, palindromic languages, voxel adjacency trees and connecting thickness of Reveill`es hyperplanes. It also provides a better understanding of the combinatorial structure of discrete planes.

X. Provençal and L. Vuillon ``Discrete segments of Z3 constructed by synchronization of words'' Discrete Applied Mathematics, Volume 183, 11 March 2015, Pages 102-117

We study a natural and naive composition algorithm what takes three input words written on two-letter alphabets and synchronizes then into a word on a three-letter alphabet. We show that in the case where the three input words are compatible Christoffel words, the algorithm provides a synchronization of the letters what allows the geometrical interpretation of the input words to be inherited by the output word forming a 3D discrete line segment. A second approach is considered while applying our composition algorithm to words defined by stripes meeting at a corner of a discrete planes. We show that, under certain conditions, the output of the algorithm correspond to the normal vector of the plane.

L. Vuillon and C. Lesieur ``From local to global changes in proteins: a network view'' Current Opinion in Structural Biology Volume 31, April 2015, Pages 1–8

To fulfill the biological activities in living organisms, proteins are endowed with dynamics, robustness and adaptability. The three properties co-exist because they allow global changes in structure to arise from local perturbations (dynamics). Robustness refers to the ability of the protein to incur such changes without suffering loss of function; adaptability is the emergence of a new biological activity. Since loss of function may jeopardize the survival of the organism and lead to disease, adaptability may occur through the combination of two local perturbations that together rescue the initial function. The review highlights the relevancy of computational network analysis to understand how a local change produces global changes.

C. Lesieur and L. Vuillon ``From Tilings to Fibers – Bio-mathematical Aspects of Fold Plasticity'' Oligomerization of Chemical and Biological Compounds, Dr. Claire Lesieur (Ed.), ISBN: 978-953-51-1617-2, InTech, DOI: 10.5772/58577.

Protein oligomers are made by the association of protein chains via intermolecular amino acid interactions (interaction between subunits) forming so called protein interfaces. This chapter proposes mathematical concepts to investigate the shape constraints on the protein interfaces in order to promote oligomerization. First, we focus on tiling the plane (2 dimensions) by translation with abstract shapes. Using the fundamental Theorem of Beauquier-Nivat, we show that the shapes of the tiles must be either like a square or like a hexagon to tile the whole plane. Second, we look in more details at the tiling of a cylinder and discuss its relevancy in constructing protein fibers. The universality of such “building” properties are investigated through biological examples. This chapter is written four-hand by a mathematician and a biologist in order to present bio-mathematical aspects of fiber constructions.

G. Feverati, M. Achoch, L. Vuillon and C. Lesieur ``Intermolecular β-Strand Networks Avoid Hub Residues and Favor Low Interconnectedness: A Potential Protection Mechanism against Chain Dissociation upon Mutation'' PLOS ONE 10.1371/journal.pone.0094745

Altogether few protein oligomers undergo a conformational transition to a state that impairs their function and leads to diseases. But when it happens, the consequences are not harmless and the so-called conformational diseases pose serious public health problems. Notorious examples are the Alzheimer's disease and some cancers associated with a conformational change of the amyloid precursor protein (APP) and of the p53 tumor suppressor, respectively. The transition is linked with the propensity of β-strands to aggregate into amyloid fibers. Nevertheless, a huge number of protein oligomers associate chains via β-strand interactions (intermolecular β-strand interface) without ever evolving into fibers. We analyzed the layout of 1048 intermolecular β-strand interfaces looking for features that could provide the β-strands resistance to conformational transitions. The interfaces were reconstructed as networks with the residues as the nodes and the interactions between residues as the links. The networks followed an exponential decay degree distribution, implying an absence of hubs and nodes with few links. Such layout provides robustness to changes. Few links per nodes do not restrict the choices of amino acids capable of making an interface and maintain high sequence plasticity. Few links reduce the “bonding” cost of making an interface. Finally, few links moderate the vulnerability to amino acid mutation because it entails limited communication between the nodes. This confines the effects of a mutation to few residues instead of propagating them to many residues via hubs. We propose that intermolecular β-strand interfaces are organized in networks that tolerate amino acid mutation to avoid chain dissociation, the first step towards fiber formation. This is tested by looking at the intermolecular β-strand network of the p53 tetramer.

A. Casagrande, H. Lesca et L. Vuillon ``Un outil pour surmonter la surcharge d’information de la veille stratégique'' Colloque VSST Nancy (France), 23-25 octobre 2013, 17p.

Dans cette communication, nous proposons le concept d’« informations voisines », nous indiquons son utilité dans le processus de veille anticipative stratégique (VAS), face au problème de la surcharge d’information notamment occasionnée par l’usage de l’Internet. Nous présentons un prototype d’outil informatique visant à instrumenter le concept ainsi qu’un cas d’application. Le concept est particulièrement utile lorsque la veille stratégique est orientée « exploitation des informations à caractère anticipatif » pour l’anticipation, ceux-ci étant généralement noyés dans de gros volumes de données. Nous expérimentons notre prototype sur la problématique de la valorisation du CO2 et nous montrons ainsi que cet outil permet un réel gain de temps pour rendre utilisable les informations collectées, par les décideurs.

G. Feverati, C. Lesieur and L. Vuillon ``SYMMETRIZATION: RANKING AND CLUSTERING IN PROTEIN INTERFACES'' Mathematics of Distances and Applications.

Purely geometric arguments are used to extract information from three-dimensional structures of oligomeric proteins, that are very common biological entities stably made of several polypeptidic chains. They are characterized by the presence of an interface between adjacent amino acid chains and can be investigated with the approach proposed here. We introduce a method, called symmetrization, that allows one to rank interface interactions on the basis of inter-atomic distances and of the local geometry. The lowest level of the ranking has been used previously with interesting results. Now, we need to complete this picture with a careful analysis of the higher ranks, that are for the first time introduced here, in a proper mathematical set up. The interface finds a very nice mathematical abstraction by the notion of weighted bipartite graph, where the inter-atomic distance provides the weight. Thus, our approach is partially inspired to graph theory decomposition methods but with an emphasis to “locality”, namely the idea that structures constructed by the symmetrization adapt to the local scales of the problem. This is an important issue as the known interfaces may present major differences in relation to their size, their composition and the local geometry. Thus, we looked for a local method, that can autonomously detect the local structure. The physical neighborhood is introduced by the concept of cluster of interactions. We discuss the biological applications of this ranking and our previous fruitful experience with the lowest symmetrized level. An example is given, using the prototypical cholera toxin.

E. Domenjoud and L. Vuillon ``Geometric palindromic closure'' uniform distribution theory 7 (2012), no. 2, 109-140.

We de fine, through a set of symmetries, an incremental construc- tion of geometric objects in Zd. This construction is directed by a word over the alphabet {1,...,d}. These objects are composed of d disjoint components linked by the origin and enjoy the nice property that each component has a central sym- metry as well as the global object. This construction may be seen as a geometric palindromic closure. Among other objects, we get a 3 dimensional version of the Rauzy fractal. For the dimension 2, we show that our construction codes the standard discrete lines and is equivalent to the well known palindromic closure in combinatorics on words.

A. Blondin massé, G. Paquin, H. Tremblay and L. Vuillon ``On Generalized Pseudostandard Words Over Binary Alphabets'' Journal of Integer Sequences, Vol. 16 (2013), Article 13.2.11

In this paper, we study generalized pseudostandard words over a two-letter alphabet, which extend the classes of standard Sturmian, standard episturmian and pseudostandard words, allowing different involutory antimorphisms instead of the usual palindromic closure or a fixed involutory antimorphism. We first discuss pseudoperiods, a useful tool for describing words obtained by iterated pseudopalindromic closure. Then, we introduce the concept of normalized directive bi-sequence (Θ, w) of a generalized pseudostandard word, that is the one that exactly describes all the pseudopalindromic prefixes of it. We show that a directive bi-sequence is normalized if and only if its set of factors does not intersect a finite set of forbidden ones. Moreover, we provide a construction to normalize any directive bi-sequence. Next, we present an explicit formula, generalizing the one for the standard episturmian words introduced by Justin, that computes recursively the next prefix of a generalized pseudostandard word in term of the previous one. Finally, we focus on generalized pseudostandard words having complexity 2n, also called Rote words. More precisely, we prove that the normalized bi-sequences describing Rote words are completely characterized by their factors of length 2.

G. Feverati, M. Achoch, J. Zrimi, L. Vuillon and C. Lesieur ``Beta-Strand Interfaces of Non-Dimeric Protein Oligomers Are Characterized by Scattered Charged Residue Patterns'' PLoS ONE 7(4): e32558.

Protein oligomers are formed either permanently, transiently or even by default. The protein chains are associated through intermolecular interactions constituting the protein interface. The protein interfaces of 40 soluble protein oligomers of stœchiometries above two are investigated using a quantitative and qualitative methodology, which analyzes the x-ray structures of the protein oligomers and considers their interfaces as interaction networks. The protein oligomers of the dataset share the same geometry of interface, made by the association of two individual β-strands (β-interfaces), but are otherwise unrelated. The results show that the β-interfaces are made of two interdigitated interaction networks. One of them involves interactions between main chain atoms (backbone network) while the other involves interactions between side chain and backbone atoms or between only side chain atoms (side chain network). Each one has its own characteristics which can be associated to a distinct role. The secondary structure of the β-interfaces is implemented through the backbone networks which are enriched with the hydrophobic amino acids favored in intramolecular β-sheets (MCWIV). The intermolecular specificity is provided by the side chain networks via positioning different types of charged residues at the extremities (arginine) and in the middle (glutamic acid and histidine) of the interface. Such charge distribution helps discriminating between sequences of intermolecular β-strands, of intramolecular β-strands and of β-strands forming β-amyloid fibers. This might open new venues for drug designs and predictive tool developments. Moreover, the β-strands of the cholera toxin B subunit interface, when produced individually as synthetic peptides, are capable of inhibiting the assembly of the toxin into pentamers. Thus, their sequences contain the features necessary for a β-interface formation. Such β-strands could be considered as ‘assemblons’, independent associating units, by homology to the foldons (independent folding unit). Such property would be extremely valuable in term of assembly inhibitory drug development.

I. Gambini and L. Vuillon ``How many faces can polycubes of lattice tilings by translation of R3 have?'' Electronic Journal of Combinatorics, P199, 2011

We construct a class of polycubes that tile the space by translation in a latticeperiodic way and show that for this class the number of surrounding tiles cannot be bounded. The first construction is based on polycubes with an L-shape but with many distinct tilings of the space. Nevertheless, we are able to construct a class of more complicated polycubes such that each polycube tiles the space in a unique way and such that the number of faces is 4k + 8 where 2k + 1 is the volume of the polycube. This shows that the number of tiles that surround the surface of a space-filler cannot be bounded.

I. Gambini and L. Vuillon ``Non lattice periodic tilings of R3 by single polycubes'' To appear in Theoretical Computer Science 2012

In this paper, we study a class of polycubes that tile the space by translation in a non lattice periodic way. More precisely, we construct a family of tiles indexed by integers with the property that Tk is a tile having k >= 2 has anisohedral number. That is k copies of Tk are assembled by translation in order to form a metatile. We prove that this metatile is lattice periodic while Tk is not a lattice periodic tile.

A. Frosini, S. Rinaldi, K. Tawbe and L. Vuillon ``Reconstruction of 2-convex polyominoes'' LAMA research report

A polyomino P is called 2-convex if for every two cells belonging to P , there ex- ists a monotone path included in P with at most two changes of direction. This paper studies the tomographical aspects of 2-convex polyominoes from their hori- zontal and vertical pro jections and gives an algorithm that reconstructs all 2-convex polyominoes in polynomial time.

D. Jamet , G. Paquin, G. Richomme and L. Vuillon ``On the fixed points of the iterated pseudopalindromic closure'' Theoretical Computer Science 412, Issue 27, 2974-2987, 2011, special issue "Combinatorics on Words (WORDS 2009), 7th International Conference on Words"

First introduced in the study of the Sturmian words, the iterated palindromic closure was generalized to pseudopalindromes. This operator allows one to construct words with infinitely many pseudopalindromic prefixes, called pseudostandard words. We provide here several combinatorial properties of the fixed points under the iterated pseudopalindromic closure.

A. Blondin Massé , S. Brlek, S. Labbé and L. Vuillon ``Palindromic complexity of codings of rotations'' Theoret. Comput. Sci. 412 (2011) 6455-6463.

We study the structure of inﬁnite words obtained by coding rotations on partitions of the unit circle by inspecting the return words. The main result is that every factor of a coding of rotations on two intervals has at most 4 complete return words, where the bound is realized only for a ﬁnite number of factors. As a byproduct we obtain that when the partition consists of two intervals, then the corresponding word is full, that is, it realizes the maximal palindromic complexity. We also provide a combinatorial proof for the special case of complementary-symmetric Rote sequences by considering both the palindromes and the antipalindromes occurring in it.

E. Domenjoud , D. Jamet , D. Vergnaud and L. Vuillon ``Enumeration Formula for (2, n)-Cubes in Discrete Planes'' Discrete applied mathematics 160, 15 (2012) 2158-2171

We compute the number of local conﬁgurations of size 2 ×n on naive discrete planes using combinatorics on words, 2-dimensional Rote sequences and Berstel-Pocchiola diagrams.

F. De Carli, A. Frosini, S. Rinaldi and L. Vuillon ``How to construct convex polyominoes on DNA Wang tiles ? '' LAMA research report

In this article, we describe a general method for constructing various shapes of convex polyominoes using DNA Wang tiles. we recall the basic definitions and notations of two-dimensional languages and tiling systems and some basic definitions on polyominoes, in particular the definitions of convex, directed-convex, and parallelogram polyominoes. We describe the algorithm to transform tiles of a tiling system into labelled Wang tiles. We show explicitly the set of labelled Wang tiles that allows us to construct convex polyominoes. We give an example of a parallelogram polyomino built on labelled Wang tiles. The last part concerns the transformation of labelled Wang tiles into DNA Wang tiles. Moreover, we show that it is possible to control the size of the polyominoes to be constructed, by means of a DNA strand.

K. Tawbe, F. Cotton and L. Vuillon ``Evolution of Brain Tumor and Stability of Geometric Invariants’’ International Journal of Telemedicine and Applications Volume 2008 (2008), Article ID 210471, 12 pages

**This paper
presents a method to reconstruct and to calculate geometric
invariants on brain tumors. The geometric invariants considered in
the paper are the volume, the area, the discrete Gauss curvature, and
the discrete mean curvature. The volume of a tumor is an important
aspect that helps doctors to make a medical diagnosis. And as doctors
seek a stable calculation, we propose to prove the stability of some
invariants. Finally, we study the evolution of brain tumor as a
function of time in two or three years depending on patients with MR
images every three or six months.**

P. Domosi, G. Horvath and L. Vuillon ``On Shyr-Yu Theorem'' Theoretical Computer Science, Volume 410 (2009)

**An
alternative proof of Shyr-Yu Theorem is given. Some generaliza- tions
are also considered using fractional root decompositions and frac-
tional exponents of words. **

G. Paquin and L. Vuillon ``A characterization of balanced episturmian sequences'' Electronic Journal of Combinatorics. Volume 14 (2007)

**It
is well-known that Sturmian sequences are the non ultimately periodic
sequences that are balanced over a 2-letter alphabet. They are also
characterized by their complexity: they have exactly $(n+1)$ distinct
factors of length $n$. A natural generalization of Sturmian sequences
is the set of infinite episturmian sequences. These sequences are not
necessarily balanced over a $k$-letter alphabet, nor are they
necessarily aperiodic. In this paper, we characterize balanced
episturmian sequences, periodic or not, and prove Fraenkel's
conjecture for the special case of episturmian sequences. It appears
that balanced episturmian sequences are all ultimately periodic and
they can be classified in 3 families. **

S. Brlek, A. Frosini, S. Rinaldi and L. Vuillon ``Tilings by translation: enumeration by a rational langage approach'' Electronic Journal of Combinatorics Volume 13 (1), 2006.

**Theoretical Computer Science, Volume
319, Issues 1-3, Pages 1-484 (10 June 2004). **

S. Brlek, S. Dulucq, A. Ladouceur and L. Vuillon ``Combinatorial properties of smooth infinite words'' Theoretical Computer Science,

**We describe some combinatorial
properties of an intriguing class of infinite words connected with
the one defined by Kolakoski, defined as the fixed point of the
run-length encoding $\Delta$. It is based on a bijection on the free
monoid over $\Sigma =\{ 1,2\}$, that shows some surprising mixing
properties. All words contain the same finite number of square
factors, and consequently they are cube-free. This suggests that they
have the same complexity as confirmed by extensive computations. We
further investigate the occurrences of palindromic subwords. Finally
we show that there exist smooth words obtained as fixed points of
substitutions (realized by transducers) as in the case of $K$. **

C. Frougny and L. Vuillon ``Coding of two-dimensional constraints of finite type by substitutions'' JALC, 2005,volume 10 (4) pages 465-482.

**We give an automatic method to
generate transition matrices associated with two-dimensional
contraints of finite type by using squared substitutions of constant
dimension. **

A. Frosini, M. Nivat and L. Vuillon ``An introductive analysis of periodical discrete sets from a tomographical point of view'' Theoretical Computer Science

**In this paper we introduce a
new class of binary matrices whose entries show periodical
configurations, and we furnish a first approach to their analysis
from a tomographical point of view. In particular we propose a
polynomial-time algorithm for reconstructinf matrices with a special
periodical behavior from their horizontal and vertical projections.
We succeeded in our aim by using reductions involving polyominooes
which can be characterized by means of 2-SAT formulas. **

I. Gambini and L. Vuillon ``An algorithm for deciding if a polyomino tiles the plane by translations'' Theoret. Informatics Appl. 41, 147-155 (2007).

**For
polyominoes coded by their boundary word, we describe a quadratic
$O(n^2)$ algorithm in the boundary length $n$ which improves the
naive $O(n^4)$ algorithm. Techniques used emanate from algorithmics,
discrete geometry and combinatorics on words.**

F. Chavanon, M. Latapy, M. Morvan, E. Rémila and L. Vuillon ``Graph encoding of 2D-gon tilings'' Theoretical Computer Science

**2D-gon
tilings with parallelograms are a model used in physics to study
quasicrystals, and they are also important in combinatorics for the
study of aperiodic structures. In this paper, we study the graph
induced by the adjacency relation between tiles. This relation can
been used to encode simply and efficiently 2D-gon tilings for
algorithmic manipulation. We show for example how it can be used to
sample random 2D-gon tilings. **

B. Durand and L. Vuillon Editors of the Special Issue of TCS on ``Tilings of the Plane''

**Theoretical Computer Science, Volume
303, Issues 2-3, Pages 265-554 (15 July 2003). **

L. Vuillon ``Balanced words'' Bull. Belg. Math. Soc. Simon Stevin 10 (2003), no. 5, 787-805.

**This article presents a survey about
balanced words. The balance property provides from combinatorics on
words and is used as a characteristic property of the well-known
Sturmian words. The main goal of this survey is to study various
generalizations of this notion with applications and with open
problems in number theory and in theoretical computer science. We
also prove a new result about the balance property of hypercubic
billiard words. **

A. Del Lungo, A. Frosini, M. Nivat and L. Vuillon ``Discrete tomography: reconstruction under periodicity constraints'' Automata, Languages and Programming, 29th International Colloquium, ICALP 2002, Malaga, Spain, July 8-13, 2002, Proceedings, Springer, Lecture Notes in Computer Science, volume 2380,(2002), 38-56.

**We study the reconstruction problem
on some new classes consisting of binary matrices with periodicity
properties, and we propose a polynomial-time algorithm for
reconstructing these binary matrices from their othogonal discrete
X-rays. **

P. Hubert and L. Vuillon ``Complexity of cutting words on regular tilings'' European Journal of Combinatorics, Volume 28 , Issue 1, table of contents Pages: 429 - 438, 2007 .

**We show that the complexity of a
cutting word $u$ in a regular tiling by a polyomino $Q$ is equal to
$P_n(u)= (p+q-1)n +1$ for all $n \geq 0,$ where $P_n(u)$ counts the
number of distinct factors of length $n$ in the infinite word $u$ and
where the boundary of $Q$ is constructed by $2p$ horizontal and $2q$
vertical unit segments. **

J. Berstel and L. Vuillon ``Coding rotations on intervals'' Theoretical Computer Science 281, (2002), 99-107.

**We show that the coding of rotation
by $\alpha$ on m intervals with rationally independent lengths can be
recoded over m Sturmian words of angle $\alpha.$ More precisely, for
a given m an universal automaton is constructed such that the edge
indexed by the vector of values of the ith letter on each Sturmian
word gives the value of the ith letter of the coding of rotation. **

C. Magnien, H. D. Phan and L. Vuillon `` Characterization of lattices induced by (extended) chip firing games'' Discrete mathematics and theoretical computer science procedings AA (DM-CCG), 2001, 229-244.

**The Chip Firing Game (CFG) is a
discrete dynamical model used in physics, computer science and
economics. It is known that the set of configurations reachable from
an initial configuration can be ordered as a lattice. We first
present a structural result about this model, which allow us to
introduce some useful tools for describing those lattices. Then we
establish that the class of lattices that are the configuration space
of a CFG is strictly between the class of distributive lattices and
the class of upper locally distributive (ULD) lattices. Finally we
propose an extension of the model, the coloured Chip Firing Game,
which generates exactly the class of ULD lattices. **

L. Vuillon ``On the number of return words in infinite words constructed by interval exchange transformations'' Pure Mathematics and Applications, Volume 18 (2007), Issue No. 3-4

**In this article, we count the number
of return words in some infinite words with complexity $2n+1$. We
also consider some infinite words given by codings of rotation and
interval exchange transformations on $k$ intervals. We prove that the
number of return words over a given word $w$ for these infinite words
is exactly $k.$ **

J. Justin and L. Vuillon ``Return words in Sturmian and episturmian words'' Theoretical Informatics and Applications 34 (2000) 343-356.

**Considering each occurence of a word
$w$ in a reccurent infinite word, we define the set of return words
of $w$ to be the set of all distinct words beginning with an
occurence of $w$ and ending exactly just before the next occurence of
$w$ in the infinite word. We give a simpler proof of the recent
result (of the second author) that for each factor $w$ of a Sturmian
word there exist exactly two return words of $w.$ Then, considering
episturmian infinite words, which are a natural generalization of
Sturmian words, we study the position of the occurrences of any
factor in such infinite words and we determinate the return words. At
last, we apply these results in order to get a kind of balance
property of episturmian words and to calculate the recurrence
function of these words. **

I. Fagnot and L. Vuillon ``Generalized balances in Sturmian words'' Discrete Applied Mathematics, Volume 121, Issues 1-3, (2002), 83-101.

**One of the numerous
characterizations of Sturmian words is based on the notion of
balance. An infinite word x on the {0,1} alphabet is balanced if,
given two factors w and w' of x having the same length, the
difference between the number of 0 in w (denoted by |w|0) and the one
of w' is at most 1, i.e. ||w|0 - |w'|0| <= 1. It is well known
that a word is Sturmian if and only if it is balanced. In this paper,
the balance notion is generalized by considering the number of
occurrences of a word u in w (denoted by |w|u) and w'. The following
is obtained ****Theorem
Let x be a Sturmian word. Let u, w and w' be three factors of x. If
|w|=|w'|, we have | |w|u - |w'|u | <= |u|. ****We
will also give another balance property called equilibrium. This
notion permits us to give a new characterization of Sturmian words.
The proofs use word graphs and return words technics. **

L. Vuillon ``A characterisation of Sturmian words by return words'' European Journal of Combinatorics (2001) 22, 263-275.

**We present a new characterization of
Sturmian sequences using return words. Considering each occurrence of
a word $w$ in a recurrent sequence, we define the set of return words
over $w$ to be the set of all distinct words beginning with an
occurrence of $w$ and ending with the next occurrence of $w$ in the
sequence. It is shown that a sequence is a Sturmian sequence if and
only if for each non empty word $w$ appearing in the sequence the
cardinality of the set of return words over $w$ is equal to two. **

V. Berthé and L. Vuillon ``Palindromes and two-dimensional Sturmian sequences'' J. Autom. Lang. Comb., 6 (2001), 121--138.

**This paper introduces a
two-dimensional notion of palindrome for rectangular factors of
double sequences: these palindromes are defined as centrosymmetric
factors. This notion provides a characterization of two-dimensional
Sturmian sequences in terms of two-dimensional palindromes,
generalizing to double sequences the results in the article of X.
Droubay and G. Pirillo. **

V. Berthé et L. Vuillon ``Suites doubles de faible complexité'' Journal de Theorie des Nombres de Bordeaux 12 (2000), 179-208.

**Nous donnons une représentation
géométrique des suites doubles uniformément récurrentes de
fonction de complexité rectangulaire $mn+n$. Nous montrons que ces
suites codent l'action d'une $Z^2$-action définie par deux rotations
irrationnelles sur le cercle unité. La preuve repose sur une étude
des suites doubles dont les lignes sont des suite sturmiennes de
m\^eme langage. **

J. Mairesse and L. Vuillon ``Optimal Sequences in a Heap Model with Two Pieces'' Theoret. Comput. Sci. 270 1-2 (2002), 525-560.

**In a heap model, solid blocks, or
pieces, pile up according to the Tetris game mechanism. An optimal
sequence is an infinite sequence of pieces minimizing the asymptotic
growth rate of the heap. In a heap model with two pieces, we prove
that there always exists an optimal sequence which is either periodic
or Sturmian. We completely characterize the cases where the optimal
is periodic and the ones where it is Sturmian. The proof is
constructive, providing an explicit optimal sequence. We also
consider the model where the successive pieces are choosen at random,
independently and with some given probabilities. We study the
expected growth rate of the heap. For a model with two pieces, the
rate is either computed explicitly or given as an infinite series. We
show an application for a system of two processes sharing a resource,
and we prove that a greedy schedule is not always optimal. **

L. Vuillon ``Local configurations in discrete planes'' Bull. Belg. Math. Soc. 6 (1999), 625-636.

**We study the number of local
configurations in a discrete plane. We convert this problem into a
computation of a double sequence complexity. We compute the number
$C(n,m)$ of distinct $n\times m$ patterns appearing in a discrete
plane. We show that $C(n,m)=nm$ for all $n$ and $m$ positive
integers. The coding of this sequence by a $Z^2$-action on the
unidimensional torus gives information about the structure of a
discrete plane. Furthermore, this sequence is a generalized Rote
sequence with complexity $P(n,m)=2nm$ for all $n$ and $m$ positive
integers and with a symmetric complementary language for rectangular
words. **

V. Berthé and L. Vuillon "Tilings and rotations: a two-dimensional generalization of Sturmian sequences'' Discrete Math. 223 (2000), 27-53.

**We study a two-dimensional
generalization of Sturmian sequences corresponding to an
approximation of a plane: these sequences are defined on a
three-letter alphabet and code a two-dimensional tiling obtained by
projecting a discrete plane. We show that these sequences code a
$Z^2$-action generated by two rotations on the unit circle. We first
deduce a new way of computing the rectangle complexity function. Then
we provide an upper bound on the number of frequencies of rectangular
factors of given size. **

L. Vuillon ``Combinatoire des motifs d'une suite sturmienne bidimensionnelle'' Theoret. Comput. Sci. 209 (1998), no. 1-2, 261-285.

**avec**
**les figures Figure
1 ,Figure 2 ,Figure 3
,Figure 4 ,Figure 5 .
Nous étudions une généralisation des suites sturmiennes en
construisant une ``surface plissée", donnée par
l'approximation d'un plan par trois sortes de faces carrées
orientées suivant les trois plans de coordonnées. \`A cette
surface, on associe par projection un pavage du plan par trois sortes
de losanges. On définit sur ce pavage une fonction de complexité en
comptant le nombre de motifs distincts d'une fen\^{e}tre de taille
donnée. Nous donnons, en étudiant les prolongements des motifs, la
forme explicite de cette fonction dans le cas d'une fen\^{e}tre
triangulaire et d'une fen\^{e}tre en forme de parallélogramme. **

**Habilitation
à diriger des recherches, Université Paris VII, 28 novembre 2001 :
``Mots infinis, suites doubles et pavages'' **

**de**
**1993 à 1996, thèse à l'Institut
de Mathématiques de Luminy (Aix-Marseille II), sous la direction du
Professeur G. RAUZY: **

**La
thèse a été financée par le CNRS / MRE / DRET de Septembre 1994 à
Septembre 1996: Bourse de Docteur Ingénieur. **