Séverine Rivollier
email: rivollier@emse.fr

Johan Debayle
email: debayle@emse.fr

Jean-Charles Pinoli
email: pinoli@emse.fr

Représentation intrinsèque multi-échelle des images à tons de gris par Voisinages Adaptatifs Généraux (VAG)

Les représentations multi-échelles usuelles (pyramides, ondelettes, . . .) manquent généralement de robustesse dues à leur caractère non-adaptatif (extrinsèque). En effet, les échelles d'analyse sont déterminées globalement et fixées a priori, indépendamment du contexte local de l'image. Par ailleurs, ces approches multi-échelles font généralement abstraction des propriétés physiques (principe de formation d'image, . . .) et/ou psychophysiques (perception visuelle humaine, . . .) des images.

L'objet de cet article est donc de répondre à cette problématique en introduisant une nouvelle représentation d'image (intrinsèque), caractérisée par des Voisinages Adaptatifs Généraux (VAG), qui est simultanément adaptative avec les échelles d'analyse, les structures spatiales et les intensités des images. Ces VAG permettent, d'une part, de mettre en place différents opérateurs adaptatifs de traitement d'image en substituant les fenêtres opérationnelles (masques, noyaux, . . .) usuelles par ces voisinages adaptatifs généraux. D'autre part, différents descripteurs adaptatifs locaux peuvent être définis pour analyser une image à tons de gris de manière adaptative, locale et multi-échelle, suivant des critères géométriques, morphologiques, topologiques, . . .

Introduction

Les représentations multi-échelles usuelles (pyramides, ondelettes, . . .) conduisent à une identification et une localisation souvent insuffisantes des différentes structures présentes dans une image. Ces difficultés sont liées à leur caractére non-adaptatif (extrinsèque). En effet, les échelles d'analyse sont déterminées globalement et fixées a priori, indépendamment du contexte local de l'image. Des approches plus adaptatives (intrinsèques) existent, telles que celles basées sur les filtres par diffusion anisotrope, mais elles comportent encore des a priori. Par ailleurs, ces approches multi-échelles font généralement abstraction des propriétés physiques (principe de formation d'image, . . .) et/ou psychophysiques (perception visuelle humaine, . . .) de l'image, liées à ses intensités. Cela conduit à un manque de robustesse de ces représentations.

Cet article introduit la représentation intrinsèque d'une image par VAG (section 1), permettant, d'une part, la mise en place de différents opérateurs adaptatifs de traitement d'image, tels que le filtrage moyen à VAG (section 2). D'autre part, différents descripteurs adaptatifs locaux peuvent être définis pour analyser une image à tons de gris de manière adaptative, locale et multi-échelle (section 3).

V h m (x) := C h -1 ([h(x) -m ;h(x) + m ]) (x) (1
f + △ g = f + g - f g M (2)
α × △ f = M -M M -f M α (3)
M désigne la borne supérieure de l'intervalle de numérisation des intensités. Afin d'offrir une impression visuelle de la construction de ces voisinages adaptatifs généraux, une représentation en dimension 1 (D ⊆ R) avec les opérations du modèle CLIP ( + = +, × = ×, -= -), est donnée dans la figure 1. Définis sur le support spatial D de l'image (Figure 3), ils sont adaptatifs à la fois en espace, en intensité et en échelle. A l'inverse, les voisinages {B r (.)} r (disques isotropes homothétiques centrés de rayon r), généralement utilisés comme fenêtres d'analyse pour la définition d'opérateurs de traitement d'image, sont de forme et de taille fixées a priori.

ligne mesure liée au critère d'analyse h(x) x [h(x) -m, h(x) + m] V h m (x)
D x 1 B r (x 1 ) x 2 B r (x 2 ) x 3 V h m (x 3 ) x 4 V h m (x 4 ) r, m Fig. 3 -Voisinages isotropes B r (x) vs. VAG V h m (x)
2 Traitement d'image à VAG De multiples opérateurs de traitement d'image (filtres spatiaux statistiques, filtres morphologiques, . . .) utilisent une fenêtre opérationnelle, se déplacant sur l'image pixel par pixel, permettant de modifier la valeur d'intensité du pixel considéré en fonction de celles des points inclus dans son voisinage d'analyse. Pour ce type d'opérateurs, la fenêtre opérationnelle utilisée est souvent de taille et de forme fixées (donc globale à tous les points de l'image), générant des effets indésirables tel que le flou qui augmente en fonction du degré (taille de la fenêtre) du filtre.

Les opérateurs de traitement d'image à VAG sont introduits en substituant ces fenêtres opérationnelles isotropes (disques B r (.) de rayon r) par les VAG (V h m (.)) qui sont adaptatifs.

La figure 4 Le modèle vectoriel GLIP est généralement choisi en fonction des propriétés physiques de l'image (principe de formation d'image, . . .) ou de la prise en compte des lois de la perception visuelle humaine.

3 Analyse d'image à VAG Outre l'introduction de ces opérateurs adaptatifs de traitement d'image, cette nouvelle représentation d'image permet aussi de définir des descripteurs à VAG, permettant une analyse adaptative et intrinsèque des images à tons de gris. En effet, pour chaque point x de l'image f , il est possible de réaliser différentes mesures du VAG de luminance V f m (x), telles que l'aire, l'orientation, le nombre de concavités, . . . [START_REF] Glasbey | Image analysis for the biological sciences[END_REF][START_REF] Riley | Quantitative shape measurements of distal volcanic ash[END_REF], permettant ainsi de définir des cartogarphies suivant la mesure considérée [START_REF] Rivollier | Analyse spectrale morphologique adaptative d'image[END_REF].

De manière plus explicite, la cartographie C d'une image f , liée à la mesure µ (aire, périmètre, . . .), est définie par : D'autres critères d'analyse à VAG pourraient être définis en considérant des mesures différentes de celles de Minkowski. Suivant la mesure considérée, la caractérisation d'une image à tons de gris serait de nature géométrique (longueur, orientation, . . .), morphologique (circularité, compacité, . . .), topologique (nombre de concavités, . . .), etc.

C : D → R x → µ(V f m (x)) (4

Conclusion et perspectives

  ) où C X (x) représente la composante connexe par arcs (avec la topologie usuelle sur X) de X ⊆ D contenant x. La fonction critère h est représentée dans un modèle GLIP[START_REF] Oppenheim | Generalized Superposition[END_REF][START_REF] Pinoli | A General Comparative Study of the Multiplicative Homomorphic,Log-Ratio and Logarithmic Image Processing Approaches[END_REF], c'est-à-dire dans un espace vectoriel muni des lois d'addition vectorielle + et de multiplication scalaire × .Par exemple, pour la structure d'image classique CLIP (Classical Linear Image Processing), les lois + et × correspondent aux opérations usuelles entre images, respectivement + et ×. Plus particulièrement, la structure LIP[START_REF] Pinoli | A General Comparative Study of the Multiplicative Homomorphic,Log-Ratio and Logarithmic Image Processing Approaches[END_REF] (Logarithmic Image Processing), avec ses lois vectorielles+ △ et ×△ définies ci-dessous, présente l'avantage d'être cohérente avec les modèles de formation d'image par transmission, par réflexion/transmission multiplicative et avec plusieurs lois et caractéristiques de la perception visuelle humaine.

Fig. 1 -

 1 Fig. 1 -Représentation monodimensionnelle du VAG V h m (x) suivant le critère h et la tolérance d'homogénéité m dans le cadre du modèle CLIP. Pratiquement, la figure 2 illustre les VAG de deux points calculés avec le critère de luminance (avec le modèle CLIP), sur une image de rétine (fournie par le Service d'Ophtalmologie du CHU de Saint-Etienne).

Fig. 2 -

 2 Fig. 2 -Les VAG des deux points de l'image originale (a) sont respectivement homogènes (b), avec la tolérance 20, par rapport au critère de luminance.

  illustre la restauration d'une image f (Le Joueur de Fifre, Edouard Manet, 1866) à l'aide d'un filtrage moyen usuel (utilisant le disque B 3 de rayon r = 3 pour fenêtre opérationnelle) et d'un filtrage moyen à VAG (voisinages de luminance V f 50 (x) au sens LIP avec la tolérance d'homogénéité m △ = 50, pour fenêtres opérationnelles adaptatives). Le critère d'homogénéité étant celui de la luminance, la fonction h est égale à f .

Fig. 4 -

 4 Fig. 4 -Filtrage moyen usuel vs. filtrage moyen à VAG

  ) où V f m (x) désigne le VAG de luminance du point x suivant la tolérance d'homogénéité m dans la structure GLIP. La figure 5 illustre les cartographies, représentées sous forme d'images, de différents descripteurs à VAG (les mesures utilisées sont les fonctionnelles de Minkowski [4]) de l'image 'Goldhill'. Les VAG sont calculés dans le modèle CLIP avec la tolérance d'homogénéité m = 40. Le ton de gris de chaque point x de l'image résultante correspond à la mesure discrète (aire, périmètre ou nombre d'Euler) du VAG V f 40 (x).

  Fig. 5 -Cartographies (b-d) des fonctionnelles de Minkowski à VAG de l'image 'Goldhill' (a) avec la tolérance d'homogénéité m = 40 suivant le critère de luminance dans le modèle CLIP.

Fig. 6 -

 6 Fig. 6 -Caractérisation multi-échelle de l'aire à VAG de l'image originale f (a) suivant différentes tolérances d'homogénéité (b-e). Le ton de gris de chaque point x des cartographies (b-e) représente l'aire de son VAG.

  Une nouvelle représentation d'image est introduite, caractérisée par des Voisinages Adaptatifs Généraux (VAG), qui est simultanément adaptative avec les échelles d'analyse, les structures spatiales et les intensités. Ces VAG permettent, d'une part, de mettre en place différents opérateurs adaptatifs de traitement d'image en substituant les fenêtres opérationnelles usuelles par ces voisinages adaptatifs généraux. D'autre part, différents descripteurs adaptatifs locaux peuvent être définis pour analyser une image à tons de gris de manière adaptative, locale et multi-échelle, suivant des critères géométriques, morphologiques, topologiques, . . . Les auteurs étudient actuellement l'évolution des descripteurs à VAG en fonction de la tolérance d'homogénéité m . Cette analyse en profondeur pourrait mener à l'extraction de points ou régions d'intérêt significatifs, suivant la mesure considérée, d'une image à tons de gris. Par ailleurs, cette nouvelle représentation d'image par VAG ouvre de larges perspectives pour le développement de nouvelles méthodes adaptatives, locales et multi-échelles d'analyse d'image [8].

  chaque point x de l'image f est associé un ensemble de VAG appartenant au support spatial D de f . Ces voisinages, notés {V h m (x)} m , sont connexes et homogènes par rapport à une fonction critère h (telle que la luminance ou le contraste local de f ) suivant une tolérance d'homogénéité notée m . La définition explicite d'un VAG est la suivante :

	1 Représentation intrinsèque d'une
	image par VAG
	L'approche récemment publiée sous le sigle TIVAG (Trai-
	tement d'Image à Voisinages Adaptatifs Généraux) / GA-
	NIP (General Adaptive Neighborhood Image Processing)
	[1, 2] fournit un cadre général et opérationnel pour le trai-
	tement et l'analyse d'image adaptative, locale, et multi-
	échelle.
	Elle est basée sur une représentation intrinsèque d'image
	par Voisinages Adaptatifs Généraux (VAG) qui présentent
	trois caractéristiques principales répondant à la probléma-
	tique énoncée en introduction. Ils sont adaptatifs à la fois :
	• en espace : les voisinages sont de taille et de forme
	adaptées au contexte local de l'image,
	• en échelle : les échelles d'analyse sont fournies par
	l'image elle-même et non fixées a priori,
	• en intensité : les voisinages sont définis suivant une
	structure GLIP (Generalized Linear Image Proces-
	sing) permettant de considérer les caractéristiques phy-
	siques et/ou psychophysiques de l'image à étudier.

A


PhD Colm T O'dushlaine

PhD Elaine Kenny

PhD Eleisa Heron

DClinPsyc Gary Donohoe

PhD Derek W Morris

MRCPsych Michael Gill

The International

Schizophrenia Consortium

MRCPsych Aiden Corvin
email: acorvin@tcd.ie

Emma M Quinn

Michael C O'donovan

George K Kirov

Nick J Craddock

Peter A Holmans

Nigel M Williams

Lucy Georgieva

Ivan Nikolov

N Norton

H Williams

Draga Toncheva

Vihra Milanova

Michael J Owen

Christina M Hultman

Paul Lichtenstein

Emma F Thelander

Patrick Sullivan

Andrew Mcquillin

Khalid Choudhury

Susmita Datta

Jonathan Pimm

Srinivasa Thirumalai

Vinay Puri

Robert Krasucki

Jacob Lawrence

Digby Quested

Nicholas Bass

Hugh Gurling

Caroline Crombie

Gillian Fraser

Leh Soh

Nicholas Kuan

David Walker

Clair St

Douglas H R Blackwood

Walter J Muir

Kevin A Mcghee

Ben Pickard

Pat Malloy

Alan W Maclean

Margaret Van Beck

Naomi R Wray

Peter M Visscher

Stuart Macgregor

Michele T Pato

Helena Medeiros

Frank Middleton

Celia Carvalho

AymanFanous Christopher Morley

David Conti

James A Knowles

Carlos Paz Ferreira

M Helena Antoniomacedo

Carlos N Azevedo

Massachusetts General Hospital Jennifer L Pato

Douglas M Stone

Manuel A R Ruderfer

Stanley Ferreira

Shaun M Purcell

Jennifer L Stone

Kimberly Chambert

Douglas M Ruderfer

Finny Kuruvilla

Stacey B Gabriel

Kristin Ardlie

Mark J Daly

Edward M Scolnick

Molecular Pathways involved in Neuronal Cell Adhesion and Membrane Scaffolding contribute to Schizophrenia and Bipolar Disorder Susceptibility

Keywords: Schizophrenia, Bipolar Disorder, pathways, GWAS, neuronal cell adhesion

Susceptibility to schizophrenia and bipolar disorder may involve a substantial, shared contribution from thousands of common genetic variants each of small effect. Identifying if risk variants map to specific molecular pathways is potentially biologically informative. We report a molecular pathway analysis using the SNP ratio test (SRT) which compares the ratio of nominally significant (p<0.05) to non-significant SNPs in a given pathway to identify 'enrichment' for association signals. We applied this approach to discovery (the International Schizophrenia Consortium (ISC) (n=6,909)) and validation (Genetic Association Information Network (GAIN) (n=2,729)) schizophrenia genome-wide association study (GWAS) datasets. We investigated each of the 212 experimentally validated pathways described in Kyoto Encyclopaedia of Genes and Genomes (KEGG) in the discovery sample. Nominally significant pathways were tested in validation sample, five pathways were significant (p=0.03-0.001); only the Cell Adhesion Molecules (CAM) pathway withstood conservative correction for multiple-testing. Interestingly, this pathway was also significantly associated with bipolar disorder (Wellcome Trust Case Control Consortium (WTCCC) (n=4,847)) (p=0.01). At a gene-level CAM genes associated in all three samples (NRXN1 and CNTNAP2) have previously been implicated in specific language disorder, autism and schizophrenia. The Cell Adhesion Molecules (CAM) pathway functions in neuronal cell adhesion, which is critical for synaptic formation and normal cell signaling. Similar pathways have also emerged from a pathway analysis of autism, suggesting that mechanisms involved in neuronal cell adhesion may contribute broadly to neurodevelopmental psychiatric phenotypes.

Introduction

Despite substantial progress, much of the genetic variation in schizophrenia susceptibility remains to be attributed. [START_REF] Stefansson | Large recurrent microdeletions associated with schizophrenia[END_REF][START_REF] O'donovan | Identification of loci associated with schizophrenia by genome-wide association and followup[END_REF][START_REF]International Schizophrenia Consortium. Rare chromosomal deletions and duplications increase risk of schizophrenia[END_REF][START_REF] Schizophrenia | Common polygenic variation contributes to risk of schizophrenia that overlaps with bipolar disorder[END_REF] Our recent data suggests a spectrum of risk variation including rare variants and a substantial contribution from thousands of common susceptibility variants of small effect. [START_REF] Schizophrenia | Common polygenic variation contributes to risk of schizophrenia that overlaps with bipolar disorder[END_REF] Additionally, many of these common variants may also contribute to bipolar disorder but not other common complex disease, which accords with epidemiological support for some genetic overlap between these disorders. [START_REF] Lichtenstein | Common genetic determinants of schizophrenia and bipolar disorder in Swedish families: a population-based study[END_REF] Identifying and confirming small genetic effects is likely to be challenging and a substantial barrier to translational research in psychoses.

Investigating genomic data at the level of molecular pathways rather than at individual single nucleotide polymorphisms (SNPs) is a potentially promising approach. Pathway-based analyses of genomic data may offer several advantages over traditional genetic association analyses. First, by increasing study power if, as has been suggested, the joint action of common variants within pathways play a major role in predisposing to complex genetic disorders. [START_REF] Lesnick | A genomic pathway approach to a complex disease: axon guidance and Parkinson disease[END_REF] Second, in being robust to the influence differences in linkage disequilbrium (LD) (e.g. between study populations or SNP arrays) may have on identification of associated variants. Third, by providing additional information relating to function over and above the statistical SNP GWAS data. Namely, implicating a molecular pathway in a disease process may be more biologically informative than interpreting involvement of an anonymous genetic marker.

A number of formal pathway-based analytical methods have been described [START_REF] Lesnick | A genomic pathway approach to a complex disease: axon guidance and Parkinson disease[END_REF][START_REF] Askland | Pathways-based analyses of whole-genome association study data in bipolar disorder reveal genes mediating ion channel activity and synaptic neurotransmission[END_REF][START_REF] Subramanian | Gene set enrichment analysis: a knowledge-based approach for interpreting genome-wide expression profiles[END_REF][START_REF] Wang | Pathway-Based Approaches for Analysis of Genomewide Association Studies[END_REF][START_REF] O'dushlaine | The SNP ratio test: pathway mining of genome-wide association datasets[END_REF][START_REF] Holmans | Gene ontology analysis of GWAS study data sets provides insights into the biology of bipolar disorder[END_REF] and are reviewed elsewhere. [START_REF] Wang | Pathway-Based Approaches for Analysis of Genomewide Association Studies[END_REF][START_REF] Hong | Strategies and issues in the detection of pathway enrichment in genome-wide association studies[END_REF] In this study we used the SNP-ratio test (SRT) [START_REF] O'dushlaine | The SNP ratio test: pathway mining of genome-wide association datasets[END_REF] for the following reasons. The SRT is similar to approaches using methods based on gene set enrichment analysis (GSEA) [START_REF] Wang | Pathway-Based Approaches for Analysis of Genomewide Association Studies[END_REF] in that it tests for enrichment of statistically associated SNPs in a pathway using empirical p-values. As the SRT uses all SNPs in the pathway it can account for situations where LD, extending beyond the gene of interest, generates false positives at a SNP-level. The test is robust to allelic or locus heterogeneity and can capture information from multiple signals at a given locus. Because the application of the test is at a pathway rather than gene level, this also precludes the need to adjust for gene size. However, all pathway-based methods are limited by the quality of the pathway annotation available and differences in how pathways are defined. The SRT can be applied flexibly to different pathway resources. For this study we selected only pathways identified in the Kyoto Encyclopaedia of Genes and Genomes (KEGG) database [START_REF]Kyoto Encyclopaedia of Genes and Genomes[END_REF] as these have been experimentally validated. Inevitably, pathways will be enriched for well-studied genes, but in a hypothesis-free test this should not affect the type 1 error rate. For this reason we did not weight pathways based on prior evidence for involvement in the aetiology of schizophrenia or psychosis.

The purpose of this study was to apply a pathway-based approach to analysis of GWAS data from two large schizophrenia samples. The initial step was an exploratory analysis in the International Schizophrenia Consortium (ISC) dataset. We investigated 212 experimentally-validated pathways from the KEGG database for evidence that specific pathways were enriched for SNPs associated with schizophrenia (p≤0.05). Molecular risk pathways identified as meeting this significance threshold were then validated in a large independent dataset (p≤0.05). A secondary purpose of the study was to investigate the overlap between the validated pathways and bipolar disorder using the same statistical association criteria.

Materials and methods

Participants and genotyping

The International Schizophrenia Consortium was established to promote rapid progress towards the identification of genetic risk factors for schizophrenia. The sample included in the GWAS analysis included 3,322 patients with DSM-IV diagnosis of schizophrenia and 3,587 controls from the same European populations. Single nucleotide polymorphisms (SNPs) were assayed using the Affymetrix Genome-Wide Human SNP 5.0 and 6.0 arrays. [START_REF]International Schizophrenia Consortium. Rare chromosomal deletions and duplications increase risk of schizophrenia[END_REF] The analysis provided data on 739,995 SNPs, with a genomic inflation factor of 1.09. Full details are provided elsewhere. [START_REF] Schizophrenia | Common polygenic variation contributes to risk of schizophrenia that overlaps with bipolar disorder[END_REF] The Genetic Association Information Network (GAIN) is a public-private partnership of the Foundation for the National Institutes of Health, Inc. (FNIH) with the goal of finding genetic causes for common diseases including schizophrenia. Details on inclusion criteria and participants are available elsewhere. [START_REF]Genetic Association[END_REF][START_REF] Suarez | Genomewide linkage scan of 509 European-ancestry and African American families with schizophrenia: suggestige evidence of linkage at 8p23.3-p21.2 and 11p.13.1-q14.1 in the combined sample[END_REF] The schizophrenia study (ID phg000013) [START_REF]Genome-wide association study of 14,000 cases of seven common disease and 3,000 shared controls[END_REF] The final GWAS analysis included 457,796 SNPs (28,629 SNPs and 196 individuals were removed as flagged by WTCCC on quality control grounds).

Data analysis

Pathway analysis methodology

We identified all genic SNPs that mapped to the 212 identified KEGG pathways capturing 4,760 genes (Release 48.0, October 2008). First SNPs were linked to genes via the GenBank sequence database using Human Genome Organisation (HUGO) gene nomenclature, which assigns a unique symbol to every gene. This generated a list of 3,269,098 SNPs known to lie within genes with HUGO gene symbols. A SNP from the GWAS dataset was assigned to a gene only if its coordinates lie within the National Center for Biotechnology Information (NCBI) annotated start and stop coordinates of the gene. We also included the region 5kb upstream and 2kb downstream of each gene to account for variants in potential promoter regions.

SNP ratio test (SRT)

In the discovery dataset, association analyses were performed for each SNP in a given pathway using the Armitage trend test. The SNP ratio test (SRT) than describes the ratio of nominally significant (p<0.05) to non-significant SNPs for each pathway. An empirical p-value is generated for each pathway by comparing this ratio to ratios based on simulated datasets (Figure 1).

Figure 1 here

These datasets were simulated by randomising the case/control status of individuals in our original dataset 1000 times and then repeating the association analysis. For each simulation, we take the M most significant SNPs, where M corresponds to the number of SNPs below the cut-off used in the original dataset, e.g. p<0.05. The use of M, rather than reapplying the p-value threshold should prevent any inflation in empirically significant pathways due to an excess of false positive SNPs in the original GWAS (due to e.g. genotyping error, or other bias). Following this, we counted the number of times a simulated ratio was higher than the original ratio. We did this for each pathway, thus correcting for spurious enrichment of significant SNPs due to factors such as Linkage Disequilibrium (LD). Further details on the SRT methodology are provided in O'Dushlaine et al (2009).

Pathways that provided significant evidence (p<0.05) for enrichment with associated SNPs, were than tested using the same approach in the validation dataset. Finally, we tested the significant pathways identified in schizophrenia in the WTCCC bipolar disorder dataset. All file manipulations were carried out using PERL within a UNIX framework. Statistical analyses were conducted using STATA 10.

Results

Pathway analysis results

Of the 212 KEGG pathways examined in the ISC dataset, 47 had significant enrichment of associated SNPs when compared to simulated datasets (Table 1; full pathway details are provided in Supplementary Table 1). This represented more than we expected by chance (n~11). Five of these 47 pathways were associated in the GAIN schizophrenia sample: Cell adhesion molecules (CAM) (hsa04514),(p=0.001); Cell cycle (hsa04110), (p=0.015); Vesicular trafficking (SNARE)(hsa04130), (p=0.016); Tight junction (hsa04530), (p=0.03) and Glycan structuresbiosynthesis 1 (hsa01030), (p=0.03) pathways. Only the CAM pathway exceeded a conservative correction, assuming independence, for the number of pathways taken to the replication phase.

Interestingly, the CAM pathway was also significantly associated in the bipolar disorder dataset (p=0.026). However, pathways are not independent (e.g. CAM and Tight junction overlap at a molecular level and are involved in the same functions) and genes may be involved in multiple pathways. We would expect only two of the five schizophrenia pathways to be nominally significant in the GAIN dataset by chance with an α of 0.05 for the empirical p-value. An exploratory analysis of the other four pathways, indicated additional support for Glycan structuresbiosynthesis 1 (p=0.0009) and Tight junction (p=0.015) pathways in bipolar disorder (Table 1). We did not see the same replication across the six non-psychiatric diseases in the Wellcome Trust Case Control consortium. [START_REF]Genome-wide association study of 14,000 cases of seven common disease and 3,000 shared controls[END_REF]

Table 1 here

Implicated genes in the schizophrenia risk pathways

We next examined where the SNP-signals were coming from in the different datasets. Specifically, details in the overlap at SNP level between the schizophrenia datasets are provided in Supplementary Table 3. The most significant finding in the GAIN replication set was for the CAM pathway, where there was a substantial enrichment for association in genes involved in neuronal functioning (Supplementary Figure 2). Twenty-eight genes, of 110 contributing to the analysis, had significantly associated SNPs in both datasets and 14 SNPs across 6 of these genes (CDH4, GLG1, NRXN1, CNTN1, HLA-DQA2 and PDCD1LG2) share common risk alleles in both datasets.

For the Tight Junction pathway, 27 of 128 genes had significantly associated SNPs in both schizophrenia datasets (Supplementary Figure 3). Nine SNPs across 8 genes (CDC42, CTNNA2, HCLS1, HRAS, PRKCH, MYH11, MYH15, and PARD3) sharing common risk alleles (Supplementary Table 2).

In the Glycan structures-biosynthesis 1 pathway 30 of 111 represented genes were associated in both samples and 6 SNPs across 5 genes (MAN2A1, GALNT2, GALNT13, OGT and XYLT1) shared common risk alleles (Supplementary Figures 6A-C and Table 2). For the SNARE pathway, 6 of 36 genes have significantly associated SNPs in both schizophrenia datasets with two genes attributed to the same SNPs (Supplementary Figure 5). All 12 significantly associated SNPs in these two genes for both datasets (STX18 and TSNARE1) share common risk alleles (see Supplementary Table 2). The finding for the Cell Cycle pathway is driven entirely by multiple SNPs in the same gene (MAD1L1) sharing the same risk alleles in both datasets (Supplementary Figure 4).

Gene overlap between schizophrenia and bipolar disorder

Where molecular pathways overlapped between schizophrenia and bipolar disorder we were interested in establishing if this represented the effect of the same key genes. We examined overlap at a gene-level between the ISC schizophrenia and WTCCC bipolar samples. For the CAM pathway 49 genes had at least one significant SNP in ISC and 22 of these had significant SNPs in WTCCC;

for the Tight Junction pathway 47 genes had at least 1 significant SNP in ISC and 16 of these genes were replicated; and for the N-glycan biosynthesis pathway 50 genes had at least 1 significant SNP in ISC and 24 of these replicated. This suggests substantial overlap in key genes in both disorders.

However, there was less concurrence at the level of identified risk SNPs and alleles between the disorders. For example, in the CAM pathway nine genes had the same risk SNPs, including CDH4 (Supplementary Table 2). For the Tight Junction pathway, seven genes had the same risk SNPs including PRKCH, CTNNA2 and MYH15. In the Glycan structures-biosynthesis 1 pathway seven genes shared common risk SNPs at seven genes, including MAN2A1.

Discussion

We report a genomic pathway analysis of psychosis capturing 212 experimentally validated molecular pathways using discovery (ISC) and validation (GAIN) datasets. In the discovery dataset we identified evidence for involvement of a relatively large number of pathways (47 of 212 tested).

Five of these pathways replicated in the replication sample, which was more than were expected by chance, one of these (CAM) survived conservative multiple testing correction. This sample may have been underpowered to detect more modest effects; a hypothesis that can be directly tested with the imminent availability of larger GWAS datasets, for example through the Psychiatric GWAS Consortium (PGC). [START_REF] Committee | Genomewide association studies: history, rationale, and prospects for psychiatric disorders[END_REF] Three of the five-CAM, Tight junction and SNARE-are involved in processes critical to neurodevelopment and synaptic function. Genes involved in all three have previously been implicated in schizophrenia susceptibility. There is significant overlap between the CAM and Tight junction pathways and both are relevant to synaptic formation and neurotransmission at glutamatergic and GABAergic synapses. [START_REF] Kang | Induction of GABAergic postsynaptic differentiation by alpha-neurexins[END_REF] There is substantial evidence to support their involvement in cognitive and neuropsychiatric disorders. Genes involved in each of these pathways have been implicated in genetic disorders which impact on cognition (see the Genes to Cognition Database). [START_REF] Croning | G2Cdb: the Genes to Cognition database[END_REF] Interestingly, a recent autism study reported involvement of similar neuronal cell adhesion pathways. [START_REF] Wang | Common genetic variants on 5q14.1 associate with autistic spectrum disorders[END_REF] A key issue is whether the same genes are involved across neuropsychiatric disorders. Taking the comparision of schizophrenia and bipolar disorder we identified substantial overlap in nominally associated SNPs between the schizophrenia (ISC) and bipolar disorder (WTCCC) datasets. This suggests that certain genes may be critical in altering pathway function.

Several of the the genes identified as contibuting to risk pathways had previously been identified by genetic association or studies of copy number variation in schizophrenia or other neuropsychiatric disorder phenotypes (https://slep.unc.edu/evidence/). Of these a number had first been reported in the autism literature. We identified shared risk alleles in both schizophrenia samples at SNPs rs9309200 and rs1915220 at NRXN1 (OMIM: 600565). Disruption of NRXN1 has been reported as a risk factor for both schizophrenia [START_REF] Kirov | Comparative genome hybridization suggests a role for NRXN1 and APBA2 in schizophrenia[END_REF][START_REF] Rujescu | Disruption of the neurexin 1 gene is associated with schizophrenia[END_REF][START_REF] Walsh | Rare structural variants disrupt multiple genes in neurodevelopmental pathways in schizophrenia[END_REF] and autism. [START_REF] Marshall | Structural variation of chromosomes in autism spectrum disorder[END_REF][START_REF] Szatmari | Mapping autism risk loci using genetic linkage and chromosomal rearrangements[END_REF] Axonal neurexins form transynaptic complexes with neuroligins on dendrites and are required for the formation of synaptic contacts and for efficient neurotransmission including maintaining normal postsynaptic NMDA receptor function. Significant association involving the gene CNTNAP2 (OMIM:604569) was detected in all three psychosis samples. CNTNAP2 is a neurexin superfamily member, which is part of a neurogenetic pathway that is disturbed in different forms of language impairment [START_REF] Vernes | A functional genetic link between distinct developmental language disorders[END_REF] and autism. [START_REF] Alarcon | Linkage, association, and gene-expression analyses identify CNTNAP2 as an autism-susceptibility gene[END_REF][START_REF] Arking | A common genetic variant in the neurexin superfamily member CNTNAP2 increases familial risk of autism[END_REF][START_REF] Bakkaloglu | Molecular cytogenetic analysis and resequencing of contactin associated protein-like 2 in autism spectrum disorders[END_REF] Friedman and colleagues [START_REF] Friedman | CNTNAP2 gene dosage variation is associated with schizophrenia and epilepsy[END_REF] have reported genomic deletions of varying sizes involving CNTNAP2 in three non-related patients with schizophrenia and epilepsy but not in 512 healthy controls.

Neurexin directly interacts with the cytoskeleton membrane scaffolding protein CASK (OMIM: 300171), which contains associated SNPs in both schizophrenia datasets. Part of the Tight Junction gene pathway in KEGG, CASK may have a role in synaptic plasticity by coupling synaptic vesicle exocytosis to neuronal cell adhesion. [START_REF] Cohen | Human CASK/LIN-2 binds syndecan-2 and protein 4.1 and localizes to the basolateral membrane of epithelial cells[END_REF][START_REF] Setou | Kinesin superfamily motor protein KIF17 and mLin-10 in NMDA receptor-containing vesicle transport[END_REF] Tight junctions are composed of at least three types of transmembrane protein-occludin, claudin and junctional adhesion molecules (JAMs) and a cytoplasmic region containing three large protein complexes, the ZO protein complex, the CRB3-Pals1-PATJ protein complex and the PAR-3-aPKC-PAR6 complex. The transmembrane elements mediate cell adhesion and are thought to constitute the intracellular and paracellular diffusion barriers. The CRB3 and PAR transmembrane complexes are involved in the maintenance of cell polarity and the ZO cytoplasmic complexes organize coupling with other cytoplasmic proteins and to actin microfilaments. We identified a significant enrichment of associated SNPs in genes involving the PAR complex (CDC42 (OMIM: 116952); PAR3 (OMIM:606745); PAR6 (OMIM:607484) and PRKCZ (OMIM:176982)). The PAR complex establishes cell polarity for myelination [START_REF] Chan | The polarity protein Par-3 directly interacts with p75NTR to regulate myelination[END_REF] and for normal dendritic spine development. [START_REF] Zhang | The polarity protein PAR-3 and TIAM1 cooperate in dendritic spine morphogenesis[END_REF] Recent evidence suggests that CDC42 may have a critical role in DISC-1 related cell-migration through interaction with the gene NUDEL. [START_REF] Shen | Nudel binds Cdc42GAP to modulate Cdc42 activity at the leading edge of migrating cells[END_REF] Reduced expression of CDC42 has previously been demonstrated in the DLPFC of subjects with SCZ and this was correlated with decreased dendritic spine density in schizophrenia. [START_REF] Hill | Molecular mechanisms contributing to dendritic spine alterations in the prefrontal cortex of subjects with schizophrenia[END_REF] Incidentally, GSK3B (OMIM: 605004) which is also modulated by DISC-1, is part of the Cell Cycle Pathway, although not directly contributing to susceptibility in this study. [START_REF] Mao | Disrupted in schizophrenia 1 regulates neuronal progenitor proliferation via modulation of GSK3beta/beta-catenin signaling[END_REF] The third pathway identified in all three samples, involved carbohydrate structures attached to glycolipids, glycoproteins and proteoglycans. These are known to play a critical role in many biological processes including cell adhesion during development, immune and inflammatory response, molecular trafficking, signal transduction and endocytosis. [START_REF] Ohtsubo | Glycosylation in cellular mechanisms of health and disease[END_REF] In mouse models regulation of glycan binding is required for most of the physiological functions of NCAM including brain morphogenesis, axonal trafficking and higher cognitive functioning. [START_REF] Weinhold | Genetic ablation of polysialic acid causes severe neurodevelopmental defects rescued by deletion of the neural cell adhesion molecule[END_REF][START_REF] Angata | Molecular dissection of the ST8Sia IV polysialyltransferase. Distinct domains are required for neural cell adhesion molecule recognition and polysialylation[END_REF] The diversity of glycan functions is matched by a potentially vast array of hundreds if not thousands of potential structures.

None of the overlapping risk alleles identified by this study map to genes previously implicated in psychosis. In fact, where these genes have been linked to human disease previously it has been with connective tissue disorders (e.g. MAN2A1 (OMIM:154582), CHST3 (OMIM: 603799), XYLT1 (OMIM: 608124)) or lipid metabolism (GALNT2). [START_REF] Willer | Newly identified loci that influence lipid concentrations and risk of coronary artery disease[END_REF] Pathway information should not be taken a face-value, it is important to examine the gene results.

For example, inspection of the Cell Cycle Pathway result indicated that this association was driven by the MAD1L1 gene, implicating the gene but not the pathway. Potential confounds in considering these data are that the methodology may be susceptible to bias in linkage disequilibrium (LD) in the case group, or that the data may reflect increased gene size or greater marker density in the pathways enriched for association. We correct for potential LD bias by randomizing case-control status but maintaining LD structure and repeating association tests to create a distribution of ratios (N=1000 simulations). This process retains the existing LD structure, giving a background estimate.

Spurious associations arising from LD would lie within this background range. We found no evidence for increased gene size or greater SNP density for associated versus non-associated pathways (Mann-Whitney p=0.07, n=5 replicated pathways). However, we note that the significance of a pathway is somewhat reliant on the existence of a minimum number of SNPs (~20) which, by extension, relates to factors such as average gene length (Supplementary Figure 2). Specifically, if a pathway has a paucity of SNPs, the likelihood of significant SNPs from a given simulation mapping to this pathway is reduced. Thus, poorly "covered" pathways are difficult to test, a limitation for GWAS in general (Supplementary Figure 2). By selecting only experimentally-validated pathways we restricted the number of genes included in this analysis. Incorporating other pathway tools to expand the number of genes captured in follow up these findings may be useful, although there is a lack of consensus across methods as to how pathways are defined and classified. [START_REF] Elbers | Using genome-wide pathway analysis to unravel the aetiology of complex diseases[END_REF] It is worth noting that the SRT does not correct for multiple testing at a pathway-level. This is non-trivial because molecular processes can involve more than one pathway, hence our strategy of replicating the exploratory findings. However, the multiplicity problem is greatly reduced by this approach relative to a SNP-level analysis.

This study implicates pathways involved in neuronal cell adhesion and synaptic function in molecular susceptibility to psychosis. Intriguingly, there is now significant convergence using different genetic analyses on key molecules in these pathways being broadly involved in neurodevelopmental disorders including psychosis, autism and language disorders. This may be of significant diagnostic and therapeutic importance. Our study identified identified multiply associated SNPs at several genes, for example, MAD1L1, CDH4 and TSNARE1. Examining LDrelationships at these loci suggests that this may represent multiple signals. For example, the 26 associated SNPs at MAD1L1 can be captured by 6 tagging SNPs. More definitive interpretation of individual loci will require additional re-sequencing. For further investigation of these pathways in independent datasets, we would propose testing a model that expands promoter and other regulatory regions, includes investigation of other genetic models (e.g. epistasis), allows estimation of effect size/predictive value and investigates whether the pathways identified are associated with age at onset and course of disease. Twinned with ongoing targeted DNA sequencing studies this may be informative in quantifying and specifying the impact of discrete molecular pathways on different clinical outcomes. Further functional work is required in particular to investigate neuronal cell adhesion and membrane scaffolding given the growing convergence across studies of neurodevelopmental disorders on these mechanisms.

ISC

Figure 1 :

 1 Figure 1: Sample SRT results. Example of (a) an SRT non-significant pathway and (b) an SRT significant pathway, using the ISC data. The original ratio of significant to non-significant SNPs is shown as a vertical red line. hsa01030 contains 246 significant and 3151 non-significant SNPs in the original GWAS, hsa04730 contains 196 significant and 3243 non-significant SNPS in the original GWAS dataset.

Figure 1 :

 1 Figure 1: Sample SRT results. Example of (a) an SRT non-significant pathway and (b) an SRT significant pathway, using the ISC data. The original ratio of significant to nonsignificant SNPs is shown as a vertical red line. hsa01030 contains 246 significant and 3151 non-significant SNPs in the original GWAS, hsa04730 contains 196 significant and 3243 non-significant SNPS in the original GWAS dataset.

Table 1 SRT results for ISC, GAIN and WTCCC. "s"=number of significant SNPs in pathway, "n"=number of non-significant SNPs in pathway, "p" = empirical p-value from comparing ratio of significant to non-significant SNPs to ratios in simulated datasets.

 1

					GAIN			WTCCC
	Pathway ID s	ns	p	s	ns	p	s	ns	p	Pathway name
	hsa01030	246	3151	0.007 231	3111	0.033 231	1796	0.001	Glycan structures-biosynthesis 1
	hsa04110	70	831	0.027 77	799	0.015 84	601	0.14	Cell cycle
	hsa04130	47	417	0.017 51	409	0.016 26	297	0.46	SNARE
	hsa04514	270	3613	0.022 319	3469	0.001 255	2235	0.03	Cell Adhesion Molecules (CAMs)
	hsa04530	332	4375	0.003 310	4315	0.034 308	2633	0.02	Tight Junction

ACKNOWLEDGEMENTS

We would like to thank all the participating patients, institutions and medical staff without whose contribution this work would not have been possible. We acknowledge the support of our funders in particular Science Foundation Ireland and the Health Research Board. We appreciate useful comments made by anonymous reviewers.

This work was supported by Science Foundation Ireland and the Health Research Board.

The authors report no conflict of interest.


of co-exposures to various pesticides to determine cocktails

Keywords:

Nonparametric bayesian modelling of co-exposures to various pesticides to determine cocktails

Amélie Crépet

Nonparametric bayesian modelling of co-exposures to various pesticides to determine cocktails par Amélie Crepet This work introduces a specific application of Bayesian nonparametric models in food risk analysis framework. The goal is to determine mixture of pesticides residues which are simultaneously present in the diet, to give directions for future toxicological experiments for studying possible combined effects of those mixtures. Namely, the distribution of the exposures to a large number P of pesticides is assessed from the available consumption data and contamination analyses. We propose to model the co-exposures to the P pesticides by a Dirichlet process mixture based on a multivariate Gaussian kernel so as to determine clusters of individuals with similar co-exposure patterns. The posterior distributions and the optimal partition are computed through a Gibbs sampler based on stick-breaking priors. To reduce computational time due to the high dimensional data, a random block sampling is used. Other nonparametric Bayesian models such as models based on Indian Buffet process will be developed to propose a simultaneously classification of the individuals and the pesticides in groups.

Adresse : Amélie Crepet

AFFSA-DERNS-AQR-PC 27-31 Av. Général Leclerc, 94701 Maisons-Alfort, France E-mail : a.crepet@affsa.fr Session : Classification


The role of simulation in medical training and assessment

Sinha A, Flood K, Kessel D, Johnson S, Hunt C, Woolnough H, Vidal FP, Villard PF, Holbray R, Crawshaw CM, Bulpitt A, John NW, Bello F, Phillips R, Gould DA.

Purpose

An overview of the current use of simulation in medical training and assessment, reflecting on its advantages and disadvantages, as well as speculating on its future.

Content Organization

An overview to medical simulation has been provided. In the context of procedural interventional radiology training, we start with the definition and history of simulation, address its increasing importance in medicine reflect on its theoretical basis and current evidence and finally review its advantages/ limitations and prospects for the future.

Summary

There are a number of influences that have driven the development of simulation. Currently the visuospatial and manipulation skills required in interventional radiology are learnt in a traditional apprenticeship model. However Working Time Directives in the UK and Europe limit in-hospital work hours of trainees, reducing the time and case mix available to train. Other drives include the development of new technologies for diagnosis and management. Furthermore, there are now major ethical considerations with patient safety and medical errors being high on the medical and political agendas. Some animal and fixed models have also been used to reproduce some of the training objectives, but they are an imperfect substitute for the 'real patient' experience. They also have ethical limitations, are expensive and limited in number.

Simulation in clinical learning has been shown to provide excellent opportunities for safe and effective learning. Simulation is taken from the Latin word simulare, 'to copy, represent'. It can be regarded as a method to enable learning and training of individuals and teams by recreating 'real' clinical situations. This allows them to learn, practise and repeat procedures as often as necessary in order to correct mistakes, develop their professional competencies, fine tune their skills and ultimately improve patient outcomes. It also allows comparison of performance of groups of individuals at the same level, so that performance standards can be set. Tasks can also be staged according to experience level, enabling novices to practice core skills before attempting complex procedures.

The initial interest in simulation began in other 'high risk' industries such as aviation and the military. These industries share a highly complex and hazardous nature similar to healthcare, where training and testing in the 'real world' is considered too costly and dangerous to undertake.

A wide range of technologies and methods are currently utilised in medical simulation, including: basic models created using tissue mimics or rapid prototyping, often part-task trainers; animals; simulated patients; scenarios and computer-based systems. The latter may involve hybrid or augmented reality models, or immersive, 'high fidelity' virtual reality and integrated simulators. Kneebone et al (2008) states that the use of simulated patients and simulated environments uses context to enhance realism, with added potential for skills to transfer to similar scenarios, and even to cross boundaries into different contexts.

The medical community has come under much criticism for adopting and implementing educational innovations without robust evidence for their efficacy. The field of simulation has also been subjected to intense scrutiny for the same reason. Bradley and Postlethwaite (2003) explain that the field itself is theory-rich, and that understanding of learning theories is relevant to, and underpins, the effective use of simulation in medical education. They go on to discuss the relevance of the various learning theories such as behaviourism, constructivism, reflective practice, situated learning and activity theory.

An important aspect of evidence-based simulation lies in its validity. Although this is new to surgery, validation has been well developed in psychology and behavioural sciences. A valid instrument measures what it is intended to measure and trains skills that transfer to procedures in patients in the clinical environment. There are subjective and objective approaches to the determination of validity which are divided into four types: Face validity: extent to which the simulation appears to be a correct representation of the real world task.

Content validity: degree to which an expert judges the simulator as correctly replicating the physical processes of the real world task.

Construct validity: ability of the simulation to correctly replicate and measure key procedure steps: it indicates the simulation's ability to assess features that are important for correct performance of the target procedure.

Concurrent validity: ability of scores on a test on the simulator to predict actual performance in real life.

As can be seen there are many advantages that simulation will bring into the medical field. The risks to patients and learners are avoided, with reduction of undesired interference. Tasks can be created to meet the requirements of the training curriculum. Skills can then be practised repeatedly and training, tailored to individuals, with retention and accuracy being increased. Transfer of training from classroom to the real, clinical situation, and trainee performance evaluation, can also be enhanced. However, there are limitations of simulation that have to be recognised as well. The most important being the lack of robust, highly valid and experimental data on current high fidelity medical simulators. High fidelity simulators are also very expensive and require dedicated facilities, personnel and technological support.

The future of medical simulation is very optimistic with increased research going into the robust validation of simulators that use high fidelity where that has been identified as appropriate. A clear message needs to be sent out that research needs to be focused on higher level outcomes in order to provide convincing evidence across the whole spectrum of the efficacy and effectiveness of simulationbased education.


Nicolas Ollinger
email: nicolas.ollinger@lif.univ-mrs.fr

Gaétan Richard

Four states are enough!

Keywords: Cellular automata, intrinsic universality, bulking, particles and collisions

come

Introduction

Universal machines are, in some way, the simplest type of complex machines with respect to computational aspects: the sum of all possible behaviors. Universality is also a convenient tool in computation as a way to transform data, that can be further manipulated by the machine, into code. Therefore, computation universality is one of the basic ingredients of self-reproducing cellular automata first introduced by von Neumann [START_REF] Neumann | Theory of Self-Reproducing Automata[END_REF] and in the subsequent works of Codd [START_REF] Codd | Cellular Automata[END_REF] and others 1 to achieve construction universality. Since then, universality has been studied on its own in the case of two-dimensional and one-dimensional cellular automata. For a detailed study, see the book chapter [START_REF] Ollinger | Universalities in cellular automata[END_REF].

In the 60s and 70s, universality was mainly studied for high-dimensional cellular automata (2D, 3D). In this context, it seems natural to achieve universality by taking inspiration from real-world computers by simulating components of boolean circuits. Wires, gates, clocks, fan-out, signal crossing, etc are embedded into the configuration space of some local rule. Using these components, under the assumption that the family of elements is powerful enough, one obtains a universal cellular automaton under every reasonable hypothesis: from boolean circuits, one can wire finite state machines and memory to simulate sequential machines like Turing machines; or, one can wire finite state machines encoding the local rule of a cellular automaton and put infinitely many copies of that machine on a regular lattice, using wires to connect and synchronize the grid of automata to simulate the behavior of the encoded cellular automaton. This way, Banks [START_REF] Banks | Universality in cellular automata[END_REF][START_REF] Banks | Information processing and transmission in cellular automata[END_REF] was able to construct very small universal 2D cellular automata.

In the 70s and 80s, the study of cellular automata shifted to the one-dimensional space, motivated by the formal study of parallel algorithmics and formal languages recognition. In 1D, boolean circuits are no more a natural tool, but, as a configuration looks like a biinfinite tape, simulation of sequential machines like Turing machines is straightforward and provides the basis for a notion of computational (that is Turing) universality. This approach was developed by Smith III [START_REF] Smith | III, Simple computation-universal cellular spaces[END_REF]. A major difficulty with Turing universality is the lack of a formal precise and general definition. The problem arises from two sources. First, a good commonly accepted formal definition of universality for Turing machines does not seem to exist. Second, encoding finitely described Turing machine configurations into infinite configurations, giving a reasonable halting condition, and a decoding of the result, are delicate tasks. For a discussion on this formalization problem, see the study by Durand and Róka [START_REF] Durand | The game of life: universality revisited[END_REF] of the universality of Conway's Game of Life [START_REF] Berlekamp | Winning ways for your mathematical plays[END_REF].

In 1D, one can also consider simulating the cells of a simulated cellular automaton by blocks of cells of a simulator cellular automaton, leading to a notion of intrinsic universality. This notion, that coincides with the notion of boolean circuit universality in the case of 2D cellular automata [START_REF] Durand | The game of life: universality revisited[END_REF][START_REF] Ollinger | Universalities in cellular automata[END_REF], was first pointed out in the one-dimensional case by Banks [START_REF] Banks | Universality in cellular automata[END_REF][START_REF] Banks | Information processing and transmission in cellular automata[END_REF] in the conclusion of his 2D construction, then rediscovered by Albert and Čulik II [START_REF] Albert | II, A simple universal cellular automaton and its one-way and totalistic version[END_REF]. An attempt of a formal definition was given in Durand and Róka [START_REF] Durand | The game of life: universality revisited[END_REF]. Whereas intrinsic universality implies Turing universality, one can prove that the converse is false, see Ollinger [START_REF] Ollinger | Automates cellulaires : structures[END_REF]. The main topic of this paper is to prove that four states are enough to achieve intrinsic universality in 1D with first neighbors neighborhood.

The paper continues as follows. In section 2, proper definitions of cellular automata and two definitions of intrinsic universality are proposed together with the main structural results. In section 3, the construction of small universal cellular automata is discussed. In section 4, the details of the construction of a 4 states intrinsically universal cellular automaton are given. In section 5, the more difficult question of non universality is considered. Theorem 1 (Hedlund [START_REF] Hedlund | Endormorphisms and automorphisms of the shift dynamical system[END_REF], Richardson [START_REF] Richardson | Tessellations with local transformations[END_REF]). A map is the global function of a cellular automaton if and only if it is a continuous map commuting with translations.

Definitions and Properties

This theorem allows us to manipulate cellular automata by their global function, composing them, inverting bijective ones, taking cartesian products, etc being sure that the result is still the global function of a cellular automaton. For a proper study of cellular automata and their properties, one can read the survey of Kari [START_REF] Kari | Theory of cellular automata: A survey[END_REF].

A cellular automaton A is a subautomaton of a cellular automaton B, denoted as A B, if there exists an injective map ϕ :

S A → S B such that ϕ • G A = G B • ϕ, where ϕ(c) = ϕ • c for all configurations c ∈ S Z d A . For all m ∈ (Z + ) d , n ∈ Z + and k ∈ Z d , the m, n, k -rescaling of a cellular automaton (d, S, N, f ) is the cellular automaton with global function G m,n,k = b m • σ k • G n • b -m where b m : S Z d → S m Z d is the bijective m-packing map satisfying, for all c ∈ S Z d , z ∈ Z d and α ∈ m, the equation b m (c)(z)(α) = c(mz + α), b -m is the inverse of b m , and m ⊆ Z d is the m-block satisfying z ∈ m if and only if for all i ∈ {1, . . . , d}, 0 z i m i .
The injective bulking quasi-order i on cellular automata is defined thanks to subautomaton and rescaling. A cellular automaton A is simulated by a cellular automaton B, denoted A i B, if there exists two rescalings m, n, k and m , n , k such that A m,n,k B m ,n ,k . This relation is a quasi-order with 2 interesting structural properties, see [START_REF] Ollinger | Automates cellulaires : structures[END_REF]. It admits a maximal equivalence class that captures the notion of intrinsic universality used in most constructions of the literature. Moreover, the maximal class U i admits a stronger characterization. Definition 1. A cellular automaton A is intrinsically universal with respect to injective bulking if, for all cellular automata B, there exists a rescaling m, n, k such that B A m,n,k .

A cellular automaton A is a mixautomaton of a cellular automaton B, denoted as A B, if there exists a map φ : S A → 2 S B with disjoint images, i.e., such that for all s, s ∈ S A , φ(s) ∩ φ(s

) = ∅, such that φ • G A ⊇ G B • φ.
The mixed bulking quasi-order m on cellular automata is defined thanks to mixautomaton and rescaling. A cellular automaton A is simulated by a cellular automaton B, denoted A m B, if there exists two rescalings m, n, k and m , n , k such that A m,n,k B m ,n ,k . This relation is a quasi-order with interesting structural properties, see Theyssier [START_REF] Theyssier | Automates cellulaires : un modèle de complexités[END_REF]. As injective bulking is a refinement of mixed bulking, mixed bulking admits a maximal equivalence class that captures the notion of intrinsic universality used in most constructions of the literature. Moreover, the maximal class U m admits a stronger characterization. Definition 2. A cellular automaton A is intrinsically universal with respect to mixed bulking if, for all cellular automaton B, there exists a rescaling m, n, k such that B A m,n,k .

Until now, all cellular automata known to be universal for mixed bulking can be shown universal for injective bulking (even if it is sometimes technical and painful).

Open Problem 1. Does U i = U m ?
For a proper study of bulkings, their motivation and structural properties, see Delorme et al. [START_REF] Delorme | Bulking I: an abstract theory of bulking[END_REF][START_REF] Delorme | Bulking II: Classifications of cellular automata[END_REF]. In the following, we will always consider injective bulking and the class U i unless explicitly specified.

A nice property of intrinsic universality is that its formal definition captures constructions of the literature and provides a tool to prove non universality. A first natural question is to discuss decidability. Given a cellular automaton, can we decide if it is universal? Theorem 2 (Ollinger [START_REF] Ollinger | The intrinsic universality problem of one-dimensional cellular automata[END_REF]). The problem of deciding whether an arbitrary cellular automata is intrinsically universal is undecidable.

This theorem is proved by reducing the nilpotency problem of cellular automata on periodic configurations, obtained by Mazoyer and Rapaport [18]. This reduction works for both definitions of universality. As expected, there is no automatic method to test whether a cellular automaton is intrinsically universal.

Constructing Small Universal Cellular Automata

History

Intrinsic universality is a recursively enumerable property. To prove that a given cellular automaton is universal, it is sufficient to prove that it simulates a fixed intrinsically universal cellular automaton. The undecidability comes from the fact that the size of the blocks needed to simulate one cell can grow unrecursively large with respect to the given cellular automaton.

An intrinsically universal cellular automaton has to simulate cells: an entity computing a local rule and transmitting information to its neighbors. It is a straightforward exercise to construct an intrinsically universal cellular automaton with a small neighborhood and less than twenty states. For a general technique and examples, see [START_REF] Ollinger | Universalities in cellular automata[END_REF]. How does one optimize the number of states with respect to a fixed neighborhood?

In dimension 2, with von Neumann neighborhood {(0, 0), (1, 0), (0, 1), (-1, 0), (0, -1)}, encoding boolean circuits, Banks was able to construct a 2 states universal automaton. Notice that finite configurations are encoded into ultimately periodic configurations by intrinsically universal cellular automata.

Theorem 3 (Banks [START_REF] Banks | Universality in cellular automata[END_REF][START_REF] Banks | Information processing and transmission in cellular automata[END_REF]). There exists an intrinsically universal 2D cellular automaton with von Neumann neighborhood and 2 states.

In dimension 1, a first technique, by Banks, consists of transforming a given universal cellular automaton of dimension 2 by having it simulating one dimensional cellular automata on a torus. The price to pay is either an extended neighborhood (neighbors are far from each other) or an extended set of states.

Corollary 4 (Banks [START_REF] Banks | Universality in cellular automata[END_REF][START_REF] Banks | Information processing and transmission in cellular automata[END_REF]). There exists an intrinsically universal 1D cellular automaton with 2 states and a neighborhood of size 5.

Even though boolean circuits simulation is difficult, it can still be achieve in dimension 1. By a careful design, we were able in [START_REF] Ollinger | The quest for small universal cellular automata[END_REF] to construct a universal automaton with 6 states and first neighbors neighborhood {-1, 0, 1}. In this paper, we shall improve this result and give a universal automaton with first neighbors and only 4 states.

In the realm of Turing universality, the smallest universal automaton in dimension 1 has 2 states:

Theorem 5 (Cook [START_REF] Cook | Universality in elementary cellular automata[END_REF]). Rule 110 is Turing universal.

The construction makes heavy use of particles and collisions to simulate special variation of tag systems, see Richard [START_REF] Richard | Rule 110: universality and catenations[END_REF] for a formal proof using bidimensional tools for particles and collisions (as used for the 4 states automaton). Unfortunately, a careful study of the set of collisions used show that, contrary to what is claimed by Wolfram [START_REF] Wolfram | A new kind of science[END_REF], the construction cannot be used to prove intrinsic universality of rule 110.

Open Problem 2. Is rule 110 intrinsically universal?

Particles and collisions

Many of previous constructions can be described using the analogy of particles and collisions to encode and compute information. To define these objects, we use the approach developed in [START_REF] Ollinger | Collisions and their catenations: Ultimately periodic tilings of the plane[END_REF] considering spacetime diagrams as tilings of S Z 2 with local constraints. Therefore, we need to introduce some concepts from discrete geometry: a coloring C is an application from a subset Sup(C) ⊂ Z 2 to S. Such coloring is finite if Sup(C) is finite. Three natural operations on colorings are translation of a coloring C by a vector u ∈ Z 2 defined by (u 1c) is a pair (C, L) where C is a finite coloring, L is a finite sequence of n particles P i = (B i , C i , u i , B i ), satisfying the following conditions:

• C)(z + u) = C(z); disjoint union of two colorings C and C with Sup(C) ∩ Sup(C ) = ∅ defined by C ⊕ C (z) = C(z)(resp. C (z)) for all z ∈ Sup(C )(resp. Sup(C )); at last, restriction of a coloring C to D ⊂ Z 2 is denoted by C |D . (a) A background (b) A particle (c) A collision
• consecutive particles on the list agree on their common background (for all i ∈ Z n , B i = B i+1 );

• particles and finite perturbation form a star ( I = C ⊕ i∈Zn,k∈N ku i •C i cuts the plane in n 4-connected zones and for all i

∈ Z n , C ⊕ k∈N (ku i • C i ⊕ ku i+1 • C i+1
) cuts the plane in two 4-connected zones. Let P i be the one right of P i );

• C = I ⊕ i B i|P i is a space-time diagram.
To describe easily complex space-time diagrams, one idea is to symbolize particles as lines and collisions as points, giving birth to a planar map called catenation scheme as the one in upper-left corner of Fig. 3. Formally, a catenation scheme is a planar map whose vertices are labeled by collisions and edges by particles which are coherent with regards to collisions. Since catenation schemes are symbolic representations, it is not clear that there exist associated space-time diagrams. In fact, to go back from a catenation scheme to a "real" space-time diagram, one must give explicit relative positions of collisions as, for example, by giving the number of repetitions for each particle (edge) of the scheme. Such a set of integers is called affectation and is valid if the resulting object is a space-time diagram. The main result given for catenation schemes is that set of valid affectations can be computed from finite catenation schemes.

Theorem 6 ([23]

). Given a finite catenation scheme, the set of valid affectations is a computable semi-linear set.

In this paper, the constructed automaton is based on particles and collisions and thus, heavily relies on the methodology used for catenation scheme. However, since the particles and collisions are explicitly constructed, they are very small and posses many good combinatorial properties. Therefore we do not need the whole power of catenation scheme and can often give simpler arguments for our specific case. The rest of the paper is devoted to construct the automaton and prove it is intrinsically universal. This is done in two steps: first, we give the automaton and show, using catenation scheme, that it can somehow "simulate" the local behavior of any automaton. Then, we show how to assemble those local simulations into a global one.

Constructing a Small Universal Cellular Automaton

Using particles and collisions, we shall give in this section the construction of a 1D universal cellular automaton with first neighbors and only 4 states. The proof is divided in two parts: first, we give the general scheme of the simulation and then we study the details of the construction. Theorem 7. There exists an intrinsically universal 1D cellular automaton for mixed bulking with first neighbors neighborhood and 4 states.

Building an elementary block

To build a universal cellular automaton, we design a widget able to simulate any transition of a cellular automaton using an elementary block. Before going on with this block, one point to notice is that it is sufficient to simulate one-way cellular automata to be intrinsically universal. Therefore, our elementary block is constructed such that it takes three inputs (one transition function and two arguments) and outputs three values (one transition function and two "copies" of the result).

To provide a good view of the automaton, all needed materials are depicted in Fig. 2 and Fig. 3. The first figure gives the local transition function and particles, the second one gives the catenation scheme along with all interesting extracts of corresponding space-time diagram. The rest of this section is devoted to describe and explain the contents of these two figures. The local transition function is fully depicted on the top of Fig. 2. In fact, it is not a real transition rule since some cases (denoted by interrogation marks) are not used and thus can take arbitrary values.

Even though giving the rules of our cellular automata would be sufficient, we will explain the intuition behind our local transition function as an aid to understanding the automaton. The first part of the explaination is devoted presenting background and particles used in the construction. Those structures are depicted in the corresponding part of Fig. 2. For each structure, we give a meaningful extract of space time, its name along with used local transition function cases. The formal definition can be trivially extracted from those diagrams.

One requirement of our cellular automaton is that, contrary to other known constructions, it does not use a uniform background but a bi-colored check-board (B). With this new approach, we need two states f (l, , r) f (l, , r)

? ? f (l, , r) f (l, , r)
Question marks denotes cases that are not chosen and can be chosen arbitrary

Background and Particles

(B) ( ← - ) ( -→ ) (⇑) ( ← - ) ( -→ ) Signals (l) (m) (R) Collisions (a) (b) (c) (d) (e) (f) (g)
(a')

(g) (g') R R R R l l l + m (a) (b) (c) (d) (e) (f) (g)
Figure 3: Constructed block and collisions (instead of one) for the background but this allows us to have a greater range of particles since each remaining state can lead to two distinct particles according to its alignment within the background. Thus, with the two remaining states, we can construct four different particles ( ← -, -→ , ← -, -→ ). Furthermore, since the background has two different phases, one can construct an additional particle (⇑) by taking advantage of the gap between the two phases. Those are the main particles used in the construction.

To encode information, the basic idea is to use groups of parallel particles that we call signals, depicted in the corresponding section of Fig. 2. In these groups, information can be encoded in two different ways: either by the number and type of the particles used or by relative position between those particles. Here, we use both approaches. As noted earlier, to simulate a one-way cellular automaton, we need to encode three main types of information: the left state (i.e., state of the left neighbor) is encoded in unary by the number of (regularly spaced) -→ particles (signal l). In a similar manner, the center state is encoded in unary by the number of (regularly spaced)

←particles (signal m). The local transition function is encoded as an array of integers, with each integer encoded by spaces between a pair of particles ← -(signal R): the j-th element of the array corresponds to the space between the j-th and the j + 1-th particle of the signal. To be exact, the space is two plus the sum of numbers of between two consecutive (for the previously mentioned states). This way of counting may seem a little obscure but is chosen to give nice formulae in the end of this section. In the rest of the paper, names of symbols are also used when speaking of encoded values.

During computation, other kind of signals appear: First, a mirror image of signal R (R ) which encodes the same information using -→ particles (going in the opposite direction). At last, an altered version of R , which we denotes as R , appears. In this altered version, some of the leftmost -→ particles are replaced by -→ . With such construction, two main types of problem can occur. The first one is that a small shift of one particle can change the behavior of the collision. The second one is that two particles which are coming closer can interact with each others. For those reasons, one is often expected to give a set of exact positions for every particle and show that those positions do not present any of the previous problem. In our case, one very interesting property is that our construction cannot have the first problem due to the fact that particles can only be placed in one way relative to the background. Thus we can state the following lemma: Lemma 8. When two of the particles (or signals) described above collide, the occurring collision is always the same.

Proof. As studied by J. P Crutchfield et al. [START_REF] Hordijk | Upper bound on the products of particle interactions in cellular automata[END_REF], the number of ways two particles (or signals) can collide depends on the relative position between those two particles. Possible relative positions takes into account repetition vectors of those particles and constraints induced by backgrounds. In our case, repetition vectors are either (1, 1), (0, 2) or (-1, 1) which suggests the possibility of two distinct collisions. However, the background forbids one of those possibility leaving only one possible case.

With this very strong property, we can forget about exact position of particles and focus on symbolic behavior. Let us go and construct the dynamic. The scheme of elementary block is depicted in Fig. 3 (along with extracts of all induced collisions). The block is made the following way: left and right borders are delimited by ⇑ particle. At the bottom, we have a left state signal l, a rule R and a center state signal m. The left state signal is going through the rule (collision f ) and then collides with center state signal (collision c). This collision outputs an unused copy of the left signal to the right. This signal is erased when encountering the right border (collision g). Collision c also sends a signal encoding the sum of left and center state to the left. This new signal is encountering (collision d) the mirror copy R (created when R crossed the left border during collision b). During collision d, the number of particle of R altered2 is exactly the encoded value (i.e., the sum of left and center signals). The signal embedding the sum is destroyed by the collision and the altered rule R proceed to the right. After crossing another rule R (collision e), the altered rule R collides with the right border and produces at the same time a new center state signal and a left state signal (located right of the border) in collision a.

Additional cases needed for each collision in the local transition function are made explicit at the bottom of Fig. 3. This scheme gives us a symbolic block which somehow "computes" the rule. Now, let us prove that this symbolic behavior does really correspond to a valid space-time diagram and look at the details of the computed function. The following proposition deals with the first problem by ensuring that, under reasonable conditions, the scheme of the symbolic block is a valid space-time diagram. Moreover, it gives some additional results on regularity of this block.

Proposition 9. For any encoded rule R such that spaces between particles are even numbers larger than four, for any reasonable encoded value in left and middle state signal (i.e. both not null and their values are such that their sum is less than the number of integers encoded in R) the scheme of the symbolic block corresponds to a valid space-time diagram. Moreover, for a fixed R, the size of the space-time diagram does not depend on the encoded states and those blocks can tile the plane.

Proof. First of all, the previous lemma ensures us that there is only one type of collision for each pair of particles; The non null condition ensures that all particles exist. The proof that collisions are valid can be directly deduced from extracts given in Fig. 3. Due to the fact that constraints are local, periodicity considerations are sufficient to prove the validity of the collisions occurring. In fact, it is sufficient to check the validity of one repetition of each periodic portion and the joint between different portion. The case of collisions c, e, f and g is easily dealt with since the perturbation inside the collision is periodic: adding one (or more) particles is the same as increasing the size of the periodic portion of the collision. Collision b requires space between particles ←to be greater than four. For collision d, the constraint is just that there are at least one particles -→ left (i.e. sum of left and right values is less that the number of integers encoded in R). The last significant point is in collision a: since the vertical portion in the collision has periodicity (0, 4), it requires that inter-space in R being even (this inter-space is of course the same as in R). If all these constraints are respected (which is the case for our proposition) then the resulting catenation scheme can be implemented as a valid space-time diagram. That is, there exists a space-time diagram where particles and collisions are positioned in the same way as in the catenation scheme. Now let us fix R, this implies that encoded values in states signals are bounded. Therefore, all signals are of bounded size and, up to increasing the size of the cell, they can be considered as objects with negligible size. With this, it is sufficient to take relative positions of signal as in the scheme of Fig. 3 to achieve same size blocks. More formally, if we chose for origin the collision a and take s a value large enough relative to the size of collisions and signals; the positions of particles are chosen to ensure collisions around the following positions: f at (s, s), c at (1.5s, 1.5s), g at (2s, 2s), b at (0, 2s), d at (.5s, 2.5s), e at (1.5s, 3.5s) and a at (2s, 4s). Thus, it is possible to achieve a symbolic block with "approximate" positions. By the fact that particles always interact in the same way, such block correspond to a valid space-time diagram.

The last point is to prove that such space-time diagrams, associated to elementary blocks, tile the plane: that is, that the small approximations that we have left occurs in the previous paragraph can not add and become large. Before that point, the first remark is that symbolic blocks already tile the plane if we respect the exacts values. Now if we look in details at Fig. 3, borders are left untouched by all collisions and rule signals are only shifted by a constant when encountering a border. This implies that crossings of rule signals and borders (collisions b) form a regular grid on the plane. Finally, the position of all other collisions only depends on a small number of neighbor points on this grid. It is directly visible for e and a. Positions of collisions f , g and c also depend on a but its position is fixed by the previous case. At last, collision d depends on c which was already treated.

With this result, we have an elementary block able to do simple computation according to a rule R and which can tile the plane. Before combining those elementary blocks in the next section, we must first study exactly which function is computed by our block. For the same periodicity reason as previously, it is sufficient to look at what happens in the case of collision a in Fig. 3. Lemma 10. Let R(i) 1≤i≤N be the array of N integers encoded in R and x l (resp. x m ) be the one encoded in l (resp. m); then the block leaves R unchanged and outputs m and l with encoded values respectively R(x l + x m ) + x l + x m -(N + 1) and R(x l + x m )/2.

Thus we can construct a block parametrized by some rule R which is represented as a sequence of integers. As long as all elements of this sequence are even integers greater that four. The block behaves as denoted in the previous lemma for any pair of input encoding values x l ,x m such that the sum x m + x l is less than the number of integer in the sequence R. Note that we do not care for the moment if the input condition is preserved on the outputs. This block computation is like a cell in a cellular automaton except that it sends different values for left and right states. This difference prevents us from giving a direct simulation and requires quite additional work to get rid of this problem and be able to iterate the use of elementary blocks. A better way to overcome this problem would be to alter the automaton or use unused cases in the local transition function to ensure equality of outputs. However, for the moment, we do not manage to do such a thing. Therefore an alternative (and quite combinatorial) solution is presented in the following to use this elementary blocks in intrinsic simulation.

Combining blocks

To simulate a cellular automaton using elementary blocks, the idea is to iterate them as depicted in Fig. 5 and choose a rule which emulates the behavior of the cellular automaton, the states being encoded into inputs and outputs of the blocks. Although we can make a wide range of possible rules for the blocks, restrictions on the form of the outputs is too tight for us to directly encode the transition rule inside it (or more precisely, we do not currently know how to do this).

To overcome this difficulty, we choose to group elementary blocks by two in the way depicted in Fig. 4: we use the right output of the first one as the input for the second one. In this way, we have a new basic block which has three inputs x l ,x m , x m and three outputs x l , x m and x m . The relation between inputs and outputs is still fully determined by the rule R in the following way: denoting as l 0 the intermediate value, we have that At this point, we want this double blocks to "emulate" the local transition function of any cellular automaton. In fact, since there exists intrinsically universal one-way cellular automata, we can restrict ourselves without loss of generality to the case of one-way cellular automata (1, S, {0, 1}, f ) with f : S 2 → S.

x m = R(x l + x m ) + x l + x m (N + 1), x l 0 = R(x l + x m )/2, x m = R(x l 0 + x m) + x l 0 + x m(N + 1) and lastly x l = R(x l 0 + x m)/2.
As we only need two inputs, we choose to search the encoding in which the values of m are all equal to a fixed constant c. To maintain this choice throughout the iterations of blocks, we must have that c = x m = x m that is R(x l 0 + x m) + x l 0 + x m(N + 1) = m which can be restated as R(x l 0 + c) = (N + 1) -x l 0 . Now, we must find two encodings ξ l and ξ m from N to Q such that if ξ l (x l ) = q and ξ m (x m ) = q then the block satisfies ξ l (l ) = ξ m (m ) = f (q, q ). Those two encodings are based on a vision of integers as written in binary. First, let us assimilate the set S as strictly positives integers {1, 2, 3, . . . , |S|}. Thus, if we denote as k the value log(|S| + 1) any s ∈ S can be written as the binary word s 1 s 2 . . . s k .

Then, we choose to work with integers represented by binary elements of size (4+8k +3) (that is between 0 and 2 4+8k+3 -1). Informally, those binary representations can be understood as follows: the first 3 bits 10 (header ) serve to recognize the kind of signal encountered; each of the k blocks of 8 bits (digits) is used to encode one bit of the state; lastly the remaining 4 bits are used to ensure that constraints on parity are respected (footer ). With this representation, let s = s 1 s 2 . . . s k ∈ S, we define ξ l (x) = s if and only if x is of the form 0101 (⊥⊥s i 0⊥⊥00) 1≤i≤k ⊥⊥⊥ where ⊥ denotes an arbitrary bit. The same way, we define ξ m (x) = s if and only if x is on the form 0000 (⊥⊥00⊥⊥s i 0) 1≤i≤k ⊥⊥⊥.

The last point is to prove that we can choose the function R such that, for any pair (x l , x m ) such that ξ l (x l ) = s and ξ m (x m ) = s , we have ξ l (x l ) = ξ m (x m ) = f (s, s ). For this, let us assume the following arbitrary restrictions: we choose to set the number N (which is the domain of R) to 2 4+8k+3 -1 and the value c = x m = x m = 2 4+8k+2 as depicted in Tab. 1.

Let us now study the form of values present inside the block. Those values are depicted in Tab. 1. The first remark is that in the sum (x l + x m ); it is possible to retrieve both the value of s and s in an unambiguous way. Thus the result of our output can take the value f (s, s ) = t 1 t 2 . . . t k . The choice of the value R(x l , x m ) can be divided in two parts: we chose it to be on the form 01XX (Y Y XXY Y XX)100; X bits will serve to set the value of x m and Y bits the one of x l . Since x m = R(x l + x m ) + x l + x m -(N + 1), we can see that the X bits allows us to set the corresponding digits of x m ensuring that ξ m (x m ) = t.

For the Y part, if we set it as indicated in the table, then we can see that the sum (x l0 + x m) begins with 11 as the two first bits and thus is ensured to be distinct from any valid (x l + x m ) sum. Therefore, it is possible to choose R(x l0 + x m) as the value indicated previously to respect the constraint x m = x m . Moreover with our previous choice, the output l does satisfy ξ l (x l ) = t.

As a final note, it is important to note that neither of our encoded values can be zero (for x m , one must recall that s cannot be zero

(x l + x m ) 10 • • ( ti 1 •• 11 •• ) 100 x m 0000 ( ⊥⊥ 00 ⊥⊥ t i 0 ) ⊥⊥⊥ x l 0 010⊥ ( ⊥ ti 1⊥ ⊥1 1⊥ ) ⊥10 N -x l 0 + 1 101⊥ ( ⊥t i 0⊥ ⊥0 0⊥ ) ⊥10 x l
0101 ( ⊥⊥ t i 0 ⊥⊥ 00 ) ⊥⊥⊥ ⊥ denotes arbitrary value and • value to be fixed. Here, one can notice that we use a mixed bulking since we have some "junk" which we cannot control but end up not interfering with the simulation. One relevant problem is to know whether we can get rid of this junk and thus achieve injective bulking. In this case, we conjecture that such achievement would be possible by using the following scheme: do one step of computation then take some time to get rid of the junk. However, we have not pursed this reflexion any further since the workload to achieve this result seems too high with respect to the interest of the result.

Thanks to the previous encoding, we can now simulate any cellular automaton in the following way: we input blocks with the rule corresponding to the automaton and containing an encoding of each state of the initial configuration. As each block simulates one cell, we can "see" the evolution of the simulated cellular automaton in the space time diagram.

However, the blocks are not aligned horizontally but are organized in a diagonal way (see for example Fig. 5). This problem can be worked around with a well-known construction. The idea is the following: instead of directly simulating an initial automaton (1, S, {-1, 0}, f ) we use the automaton (1, S = {B} ∪ S → ∪ S ↑ ∪ S ↑ → , f ) defined by for all s, s ∈ S:

f (s → , B) = s → f (B, s ↑ ) = s ↑ f (s ↑ → , B) = s → f (B, s ↑ → ) = s ↑ f (s → , s ↑ ) = f (s, s ) ↑ → f (x, y) = B otherwise
Informally, the intermediate automaton runs the following way: states are replaced by signals going either vertically (↑) or diagonally (→). When both signals meet, we make one step of computation and output two copies of the result (one going up and one going to the upper-right). This way, it is possible to simulate the initial automaton with any wanted scaling and correct the slope by scaling until we find a block at the same level (see Fig. 5). Therefore, one cell s of the initial cellular automaton can be simulated with cells on the forms s ↑ → B m for any fixed m ∈ N.

Conclusion

We have constructed a four states intrinsically universal cellular automaton with first neighbors neighborhood. Thanks to the formal definition, a proof of non universality is possible for given cellular automata. However, due to the undecidability of the property, there is no general method. Still, several invariants can be used, coming from the study of the bulking quasi-orders.

A first interesting problem is the pattern problem. Given a cellular automaton, a finite configuration and a pattern, the question is to decide if the pattern appears in the orbit of the configuration. For Turing universal, thus also for intrinsically universal cellular automata, the problem has maximal complexity. For simpler cellular automata it is decidable.

Theorem 11. The pattern problem is undecidable for any intrinsically universal cellular automaton.

A second interesting problem is the verification problem. Given a cellular automaton, a finite pattern and a state, the question is to decide if the state is obtained by iterating the local rule on the pattern until it consists of only one state. A simple simulation permits to test this property in polynomial time. By adapting the classical proof of Ladner [START_REF] Ladner | The circuit value problem is log space complete for p[END_REF], one can prove that it is P-complete in general. For simpler cellular automata, the complexity can be lower.

Theorem 12. The verification problem is P-complete for any intrinsically universal cellular automaton.

Unfortunately, in the case of rule 110, the pattern problem is undecidable and the verification problem has been shown P-complete by Neary and Woods: Theorem 13 (Neary and Woods [START_REF] Neary | P-completeness of cellular automaton rule 110[END_REF]). Rule 110 is P-complete.

Open Problem 3. Develop more tools to prove non universality.

A

  d-dimensional cellular automaton is a tuple (d, S, N, f ) where S is the finite set of states, N ⊆ finite Z d is the finite neighborhood, and f : S N → S is the local rule of the cellular automaton. A configuration c ∈ S Z d is a coloring of the space Z d by S. The global function G : S Z d → S Z d maps a configuration c to its image G(c) by applying the local rule synchronously and uniformly according to N , i.e., for all z ∈ Z d , G(c)(z) = f (c |z+N ). The set of configurations S Z d is endowed with the Cantor topology, i.e., the product topology over Z d of the discrete topology on S. This topology is metric, compact, and perfect. Under this topology, continuity corresponds to locality, as clopen sets correspond to sets of all configurations having a finite pattern in a given finite set, i.e., if C ⊆ S Z d is a clopen, there exists M ⊆ finite Z d such that for all c ∈ C, c ∈ S Z d c |M = c |M ⊆ C. Adding invariance by translation, one can enforce uniformity and characterize cellular automata. The translation, or shift, over S with translation vector p ∈ Z d , is the map σ p : S Z d → S Z d , satisfying, for all c ∈ S Z d and z ∈ Z d , σ p (c)(z + p) = c(z).

Figure 1 :

 1 Figure 1: Base elements of constructions Backgrounds (see Fig. 1a) are triplets B = (C, u, v) where: C is a finite coloring and u, v two non-collinear vectors ensuring that i,j∈Z 2 (iu + jv) • C is a space-time diagram (this space-time diagram is often also referred as B when no confusion is possible). Particles (see Fig. 1b) are quadruplets P = (C, u, B, B ) where C is a finite coloring, u a vector, B l and B r two backgrounds ensuring that I = k∈Z ku • C separates the plane in two 4-connected domains L and R (L being the left-one according to u) so that B |L ⊕ I ⊕ B |R is a space-time diagram, where B |L denotes the restriction of the coloring induced by B on L. A collision (see Fig.1c) is a pair (C, L) where C is a finite coloring, L is a finite sequence of n particles P i = (B i , C i , u i , B i ), satisfying the following conditions:

Figure 2 :

 2 Figure 2: Local rule and particles

Figure 4 :

 4 Figure 4: Symbolic chaining of elementary blocks (encoding of state is omitted)

Figure 5 :

 5 Figure 5: Straightening simulation (light grey squares represents blocks encoding ↑ states, medium → and dark ↑ → ones.)

  ).

		header (	digits	) footer
	N	1111 ( 11	11	11	11 ) 111
	x l	0101 ( ⊥⊥ s i 0 ⊥⊥ 00 ) ⊥⊥⊥
	x m	0000 ( ⊥⊥ 00 ⊥⊥ s i 0 ) ⊥⊥⊥
	x m	1000 ( 00	00	00	00 ) 000
	x l + x m	01xx ( ⊥⊥ s

i ⊥ ⊥⊥ s i ⊥ ) ⊥⊥⊥ where xx = 01 or 10 R

Table 1 :

 1 Encoding of states inside values

Last alteration is an erasing rather than a change of the particle but this does not change the behavior