Thanh-Ha Do

Salvatore Tabbone
email: tabbone@loria.fr

Oriol Ramos
email: oriolrt@cvc.uab.cat

New Approach for Symbol Recognition Combining Shape Context of Interest Points with Sparse Representation

In this paper, we propose a new approach for symbol description. Our method is built based on the combination of shape context of interest points descriptor and sparse representation. More specifically, we first learn a dictionary describing shape context of interest point descriptors. Then, based on information retrieval techniques, we build a vector model for each symbol based on its sparse representation in a visual vocabulary whose visual words are columns in the learned dictionary. The retrieval task is performed by ranking symbols based on similarity between vector models. The evaluation of our method, using benchmark datasets, demonstrates the validity of our approach and shows that it outperforms related state-of-theart methods.

I. INTRODUCTION

Symbol recognition system are composed of two phases: symbol description and symbol retrieval. The description phase consist of defining local shape descriptors, invariant to similarity transforms, robust to local symbol distortions and robust to document noise. The retrieval phase consist of implementing matching algorithms together with indexing, or hashing, techniques to effective retrieve queried symbols. This paper focus in the symbol description phase, while symbol retrieval relies on state-of-the-art information retrieval techniques that have proven to perform well in video retrieval [START_REF] Sivic | Video google: a text retrieval approach to object matching in videos[END_REF] as well symbol retrieval [START_REF] Nguyen | Symbol descriptor based on shape context and vector model of information retrieval[END_REF].

Regarding to shape descriptors and based on the objective of encoding the shape of a symbol, Marc ¸al et. al. [START_REF] Marc | Symbol Spotting in Digital Libraries[END_REF] divide description techniques into three different main categories. These categories are photometric description, geometric description and syntactic and structural description. Photometric description is suitable for recognizing complex symbols, e.g., logos. Techniques in this category include SIFT descriptor [START_REF] Lowe | Object recognition from local scale-invariant features[END_REF], moment-based descriptors [START_REF] Cheng | A symbol recognition system[END_REF], [START_REF] Chong | Translation and scale invariants of legendre moments[END_REF], [START_REF] Khotanzad | Invariant image recognition by zernike moments[END_REF], and generic Fourier descriptor (GFD) [START_REF] Zhang | Shape-based image retrieval using generic fourier descriptor[END_REF]. SIFT descriptor characterizes each interest point by the local edge distribution around the point. This is very useful to describe complex symbols, but it loses effectiveness when representing simpler ones (see Section IV). Moment-based descriptors have some advantages 1 This work has been partially supported by the Spanish project TIN2012-37475-C02-02 in symbol description comparing to other descriptors. For instance, they are invariant to translation, scaling, and rotation transforms. In addition, we can recover original symbols from moment descriptors [START_REF] Chong | Translation and scale invariants of legendre moments[END_REF], [START_REF] Khotanzad | Invariant image recognition by zernike moments[END_REF]. However, they still have some shortcomings, e.g., do not allow multi-resolution analysis of a shape in radial direction [START_REF] Zhang | Review of shape representation and description techniques[END_REF]. GFD is extracted from spectral domain by applying 2-D Fourier transformation on polar shape symbol. Hence, it overcomes the problem of noise sensitivity while still be invariant under affine transformations.

Geometric description techniques are primitive-based methods that have shown to be useful when the symbols are nonisolated and be affected by occlusions [START_REF] Mokhtarian | Robust and efficient shape indexing through curvature scale space[END_REF], [START_REF] Neumann | Integration of local and global shape analysis for logo classification[END_REF], [START_REF] Stein | Structural indexing: Efficient 2d object recognition[END_REF]. Some examples of such primitives are contours, closed regions, connected components, skeletons, etc. to enumerate some of the most popular ones. Although these descriptors can easily be computed, they are usually poorly discriminant [START_REF] Neumann | Integration of local and global shape analysis for logo classification[END_REF], and sometimes the matching process is time consuming [START_REF] Mokhtarian | Robust and efficient shape indexing through curvature scale space[END_REF]. In addition, there are also several primitives describing symbols using geometric information [START_REF] Lu | Region-based shape representation and similarity measure suitable for content-based image retrieval[END_REF] or vector signatures [START_REF] Dosch | Vectorial signatures for symbol discrimination[END_REF]. In general, they are invariant under similarity transformations, but depend on a prior normalization step to achieve invariance and are very sensitive to noise at vector level.

There has been a great number of works on finding good syntactic and structural descriptions [START_REF] Bunke | Attributed programmed graph grammars and their application to schematic diagram interpretation[END_REF], [START_REF] Lladós | Symbol recognition by error-tolerant subgraph matching between region adjacency graphs[END_REF], [START_REF] Mas | Representing and parsing sketched symbols using adjacency grammars and a grid-directed parser[END_REF], [START_REF] Wolfson | On curve matching[END_REF]. These descriptors aim at defining relationships between primitives. In [START_REF] Bunke | Attributed programmed graph grammars and their application to schematic diagram interpretation[END_REF], [START_REF] Mas | Representing and parsing sketched symbols using adjacency grammars and a grid-directed parser[END_REF], the authors propose rule-based descriptions whose performance are highly affected by noisy data. In [START_REF] Lladós | Symbol recognition by error-tolerant subgraph matching between region adjacency graphs[END_REF], [START_REF] Wolfson | On curve matching[END_REF], the authors propose structural descriptors which present symbols as one-dimensional string or by an attribute relational graph. In general, graph-based descriptors are powerful tools for symbol description but the computation time linked to them is huge since we have to deal with sub-graph isomorphism, which is NP-hard. In summary, most of photometric descriptors requires well-segmented symbols to satisfactory perform while geometric descriptors have low discriminant capacities and structural descriptors are computationally demanding.

In this paper, we extend the work done in [START_REF] Nguyen | Symbol descriptor based on shape context and vector model of information retrieval[END_REF] by providing a sparse representation of local descriptors based on keypoints. Sparse representation has been widely used in image denoising, separating, and extracting text regions [START_REF] Elad | An algorithm for designing overcomplete dictionaries for sparse representation[END_REF], [START_REF] Zhao | Text detection in images using sparse representation with discriminative dictionaries[END_REF].

But, to the best of our knowledge, sparse representation has not been applied to symbol descriptors. In this way, we achieve a sparse description of invariant descriptors which will improve the retrieval performances.

More specifically, we first compute shape context of interest points in symbols and use them as training dataset for learning a sparse dictionary by means of the K-SVD algorithm [START_REF] Elad | An algorithm for designing overcomplete dictionaries for sparse representation[END_REF]. Then, we consider the learned dictionary as a visual vocabulary whose visual words are each of the entries of this dictionary. Next, we construct a vector model for every symbol based on its sparse representation in the vocabulary and we adapt the tf-idf approach to the sparse representation. Finally, the retrieval task is performed by ranking symbols based on their similarity with the query where the similarity is computed based on the vector model approach.

We have organized the rest of this paper as follows. In Section II, we present some fundamental background on shape context and shape context of interest points descriptors. Our proposed method and retrieval model are presented in Section III and we report experimental results in Section IV. Finally, we conclude and discuss the future work in Section V.

II. RELATED WORK

In this section, we present the main background for shape context and shape context of interest point as well as their main invariant properties under rotation and scaling transforms.

A. Shape Context

Shape context (SC) is one of the descriptors with higher accuracy rates in many shapes recognition tasks and was introduced in [START_REF] Belongie | Shape matching and object recognition using shape contexts[END_REF]. Shape boundaries, either internal and external, are sampled in n points. For each point p i on the symbol contour, Belongie et al compute its coarse histogram h i of the relative coordinates of the remaining n -1 points:

h i (l) = card{c = p i : (c -p i ) ∈ bin(l)}, l = 1, L (1)
where c are contours points expressed in log-polar coordinates and L is the number of bins of the SC histogram at point p i . Thus, for each symbol S, its SC is the real matrix H = {h 1 , ..., h n } with dimensions L × n.

Since all measurements are computed with respect to all points that are sampled from internal or external contours on the symbol, SC is therefore invariant under shape translation. Invariance under scaling is obtained by normalizing all radial distances by the mean distance among all point pairs in the symbol. Moreover, it is inherently insensitive to small perturbations of symbols, and indeed it is robust to small nonlinear transforms.

B. Shape Context of Interest Points

SC defined so far show two main drawbacks when applied to symbol retrieval tasks. On the one hand, as most of photometric descriptors, we need to segment symbols well enough for having satisfactory retrieval performance. On the other hand, matching function is computationally time-demanding if the number of boundary points is large.

Inspired by the works of detecting efficiently an object from its key-points (also known as interest points) [START_REF] Agarwal | Learning to detect objects in images via a sparse, part-based representation[END_REF], [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], the authors in [START_REF] Nguyen | Symbol descriptor based on shape context and vector model of information retrieval[END_REF] proposed a new approach, named Shape context of interest point (SCIP). In their approach, SC is only defined around interest points. More specifically, interest points IP = {p 1 , p 2 , . . . , p r } and contour points C = {c 1 , . . . , c n } of a given symbol are detected. Indeed, each of these interest points p i is thus a reference point to compute the SC of a symbol. Because the IP set is rarely a subset of C for most of the cases [START_REF] Tabbone | Behavior of the laplacian of gaussian extrema[END_REF], the same rotation normalization method for SC cannot be applied to SCIP. Instead, dominant orientation of interest point information for orientation normalization is used. In more detail, each interest point p i is represented by its coordinates and the dominant orientation:

p i = {x i , y i , e i }.
The relative log-polar coordinates of contour points c j ∈ C is denoted by c i j = (log r ij , θ ij ) in which r ij is the normalized distance from p i to c j , and θ ij = --→ p i c j , e i . The coarse histogram at p i is computed as:

hi (l) = card{c i j = p i : (c i j -p i ) ∈ bin(l)}, l = 1, L (2)
Then, the SCIP descriptor is the set H = { h1 , h2 , . . . , hr }, where each hi is a histogram of L bins.

III. SPARSE REPRESENTATION AND SYMBOL RETRIEVAL

Querying symbols on a dataset using SCIP descriptor needs to assign accurately each SCIP descriptor to a visual word. In the proposed approach we avoid this step by describing each SCIP descriptor by a linear combination of visual words being each entry of a learned dictionary A. In this section, we will first explain how to learn a dictionary from a set of SCIP descriptors providing sparse representation and then, how to built vector models permitting to us querying symbols in a dataset.

A. Learned Dictionary of SCIPs

An over-complete dictionary A for sparse representation is a dictionary built from a family of training signals in which each signal has an optimally sparse approximation in A.

In this paper, we use SCIPs { Hn } N n=1 extracted from a set of N training symbols as a family of training signals. Each training signal hi ∈ R L has an optimally sparse approximation

x i satisfying h * i -hi 2 ≤ with h * i = Ax i . min xi,A i x i 1 subject to hi -Ax i 2 2 ≤ (3)
Such a dictionary can be obtained by solving the problem defined in Equation 3. To do this, Aharon et al [START_REF] Elad | An algorithm for designing overcomplete dictionaries for sparse representation[END_REF] proposed a 2 steps iterative algorithm called K-SVD. In this algorithm, they iteratively adjust A via two main stages: sparse coding stage and update dictionary stage. In the sparse coding stage, all sparse representations X = {x i } i of Y = { hi } i are computed while keeping A fixed. These sparse representations can be computed by an algorithm that approximates the solution of Equation 4. The algorithm used by the authors, and also by us in this approach, is the orthogonal matching pursuit (OMP) algorithm [START_REF] Tropp | Signal recovery from random measurements via orthogonal matching pursuit[END_REF].

x i = min x x 0 subject to hi -Ax 2 2 ≤ (4)
In the update dictionary stage, an updating rule is used to optimize the sparse representations of the training signals.

In general, the way to update the dictionary is different from one learning algorithm to another. In K-SVD algorithm, the updating rule is applied column-wise on the dictionary's matrix A. Thus, each column a i0 of A is updated sequentially such as minimizing the residual error in Equation 5:

Y -AX 2 F = (Y - i =i0 a i x T i ) -a i0 x T i0 2 F = E i0 -a i0 x T i0 2 F (5)
since all columns in A other than i 0 -th column are fixed, E i0 is also fixed. Thus, the minimization of Equation 5 depends only on the optimal a i0 and x T i0 , where x T i0 refers to the i 0 -th row of X. This problem is therefore converted to a problem of approximating a matrix E i0 by a rank 1 matrix by minimizing the Frobenius norm. Moreover, to ensure the sparsity in vector x, [START_REF] Elad | An algorithm for designing overcomplete dictionaries for sparse representation[END_REF] defined a group of indexes Ω i0 where x T i0 is different to zeros, and E R i0 is the E i0 matrix restricted to those indexes. Then, the minimization of Equation 5 is equivalent to the minimization with respect to x i0 of the equation:

E i0 Ω i0 -a i0 x T i0 Ω i0 2 F = E R i0 -a i0 x R i0 2 F (6)
The optimal solution x R i0 in Equation 6has the same support as the original x T i0 , and can be found by calculating the singular value decomposition (SVD) of the error matrix E R i0 .

B. Visual vector model

After applying the K-SVD algorithm on the set of SCIPs descriptors { Hn } N n=1 used as training dataset, we have learned a dictionary A ∈ R L×K as well as the sparse representations of all SCIPs in that dataset. In the remainder of this section we will explain how we can built up a visual vector model from the sparse representation of SCIP descriptor that we will use for retrieval tasks in the experimental sections.

Without loss of generality, we can assume that h ∈ R L is one SCIP descriptor in { Hn } N n=1 and x ∈ R K is the sparse representation of h given the dictionary A. Instead of assigning a single visual word, typically the nearest centroid of a cluster given by a k-means algorithm like in [START_REF] Nguyen | Symbol descriptor based on shape context and vector model of information retrieval[END_REF], [START_REF] Sivic | Video google: a text retrieval approach to object matching in videos[END_REF], h can be seen as a linear combination of the columns of the dictionary A. Therefore, we have to adapt the vector model construction to the sparse representation of SCIP descriptors.

Let I be the indexes set where x is different to 0. We define the characteristic vector v ∈ R K as being the 0-1 valued vector v(k) = 1 if i ∈ I and 0 otherwise. For example, if I = {1, p -1, p, q, q + 1} then v = {1 1 , 0 2 , . . . , 1 p-1 , 1 p , 0 p+1 , . . . , 1 q , 1 q+1 , 0 q+2 , . . . , 0 K }. For each training symbol n, Hn = { hn 1 , hn 2 , . . . , hn rn } is its SCIP descriptor set and r n is number of interest points detected for such symbol. Then, v n i denotes the characteristic vector of hn i , which is defined by the sparse representation x n i of hn i given the learned dictionary A. Thus, the columns of the dictionary matrix A will play the role of words in a visual word vocabulary framework.

Similarly to the tf-idf approach used in information retrieval for building vector models, we define tf and idf factors to describe, respectively, the document contents and the importance degree of terms. Herein, documents and symbols are identified. Thus, f n k is the frequency of the word k in a symbol n and tf k,n =

f n k maxs f n s
. Observe that we can easily computed these frequencies through the characteristic vector:

f n k = rn i v n i (k).
The idf factor is similarly defined as usual on information retrieval systems but also adapting its definition to the sparse representation of SCIP descriptors. The importance in distinguishing a relevant symbol from non-relevant one in a database is measured by log N l k , where l k is the number of symbols in which the word k appears.

l k = card{n = 1, N |f n k = 0}
Therefore, the vector model for a given symbol is defined by the weighted frequency for all words k in our visual vocabulary:

w n (k) = tf k,n × idf k = f n k max s f n s × log N l k , (7)

C. Retrieval Symbol

For each query symbol s q i in the set of query symbols S q = {s q 1 , s q 2 , . . . , s q m }, its vector model is computed in the same way described in section III-B. We first compute its SCIP descriptor Hq i = { hq 1 , . . . , hq ri }. Then, using the learned dictionary A, we find the sparse representation of each element in Hq i by applying the OMP algorithm [START_REF] Tropp | Signal recovery from random measurements via orthogonal matching pursuit[END_REF] to solve Equation 4. Finally, we compute the vector model, named w q i , as summarized in Equation 7.

Next, the similarity of a query symbol s q i ⊆ S q and symbols in a database s n ⊆ S is computed as the cosine distance between two vectors w q i and w n : distance(w q i , w n ) =

w q i , w n |w q i | × |w n | (8)
where •, • is the dot product. Finally, symbols in the database are ranked based on their similarity to the query symbol s q i .

IV. EXPERIMENTAL RESULTS

We have evaluated our method with the GREC2 synthetic benchmark. This dataset contains occurrences of 50 different symbols obtained by linear transforms (rotation and scaling) and by applying deformation and degradations processes. We have used 50 symbols as queries to retrieve similar symbols to them in the following subsets: dataset D 1 includes 250 symbols generated by linear transforms (rotation and scaling); dataset D 2 includes 75 symbols generated by strong non-rigid transforms; and dataset D 3 includes 75 symbols generated by strong non-rigid transforms and Kanungo noise. The number of occurrences for each class is not the same for all of them: ranging from 1 to 10 times in dataset 1; from 1 to 11 in dataset 2 and ranging 0 to 11 in dataset 3. We use the set D i , i = 1, . . . , 3 to construct the learned dictionary using K-SVD algorithm where the number of columns K is 512.

To examine the effectiveness of the proposed descriptor, we have compared it to 6 state-of-the-art methods for symbol recognition, namely R-signature [START_REF] Tabbone | A new shape descriptor defined on the radon transform[END_REF], GFD [START_REF] Zhang | Generic fourier descriptor for shape-based image retrieval[END_REF], Zernike moments [START_REF] Tahmasbi | Classification of benign and malignant masses based on zernike moments[END_REF], SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], SC [START_REF] Belongie | Shape matching and object recognition using shape contexts[END_REF] and SCIP [START_REF] Nguyen | Symbol descriptor based on shape context and vector model of information retrieval[END_REF]. In addition, for Zernike moments descriptors, we have built two descriptors. The first descriptor, G 1 includes 32 low-order moments while the second one, G 2 , includes 32 hight-order moment. We have only considered the magnitude of Zernike moments for both descriptors G 1 and G 2 and for each one, the computed moments satisfy the following conditions:

G 1 =          3 ≤ n ≤ 10 |m| ≤ n n -|m| = 2k k ∈ N G 2 =          10 ≤ n ≤ 17 |m| ≤ n n -|m| = 4k
k ∈ N For SIFT, SC and SCIP descriptors we have used k-means algorithm to build the visual dictionary, where each cluster centroid is a visual word. The number of clusters is 175 for the three descriptors. The similarity measure for retrieval tasks is always the cosine distance, as defined in Equation 8. We have used precision-recall rate, denoted by R and P respectively, to evaluate the retrieval task: R = the relevant symbols retrieved the relevant symbols existing in the database P = the relevant symbols retrieved the number of retrieved symbols Finally, we have conducted two experiments to assess the goodness of the proposed approach. The first experiment aims at finding the best size of SCIP descriptor (L) while the second experiment aims at evaluating the retrieval performance.

For the first experiment, devoted to find the best dictionary corresponding with the size of SCIP (L value), we have compared the averages precision and recall rates performed on dataset D 1 for the number of bins log(r) ranging from 3 to 5 and the number of bins for θ is set to 12 and 16, respectively. Therefore, the descriptor dimension L = θ ×log(r) belongs to {36, 48, 60, 64, 80}. Figure 1 shows that we have obtained the best precision and recall rates when L = 12×3 or L = 16×3.

We show results for the second experiment in figure 2. As it was also observed in [START_REF] Nguyen | Symbol descriptor based on shape context and vector model of information retrieval[END_REF], we can observe that SIFT descriptor loses its effectiveness when applied to symbols. SCIP descriptor have proved to be more suitable for symbol retrieval than SIFT in technical documents. Building a visual vocabulary based on sparse representation provides better results than using cluster algorithms like k-means and assigning just one visual word to each local descriptor. Results also show that our approach outperforms the compared methods in datasets D 1 and D 2 while for the D 3 dataset GFD show better performance. This result can be explained by the fact that the key-point detection step is sensitive to noises.

Some retrieval examples are giving using our method in Figure 3. Thanks to the SCIP descriptor and sparse representation, we can remark that our approach is robust to scale and rotation.

V. CONCLUSIONS AND FUTURE WORK

In this paper, we have proposed a new approach for symbol description based on SCIP descriptors and sparse representation. This new approach is invariant under rotation, scaling, and distortion, since SCIP descriptor is. Also, it is well-adapted to degraded and noisy symbols since sparse approaches are robust to this kind of degradations.

Obtained results for benchmark dataset have proven that our descriptor is suitable for symbol description for retrieval task and competitive to related state-of-the-art methods. Indeed, by describing each SCIP descriptor as a linear combination of visual words we have achieved better system performance.

In the future, we would like to apply this approach to symbol spotting problem in large graphical documents where symbols can not be easily segmented.

5 Fig. 1 .

 51 Fig. 1. The effect of L on the precision and recall rate

Fig. 2 .

 2 Fig. 2. Retrieval effectiveness with recall/precision rates in datasets: D 1 (left), D 2 (center) and D 3 (right). The legend is the same for all plots.

Fig. 3 .

 3 Fig. 3. Some retrieval examples in D 1 : the query symbol is in the first column; other columns are the nearest matches ranked from left to right.

http://www.cvc.uab.es/grec2003/SymRecContest/


Benjamin M Neale

Yan Kou

Li Liu

Avi Ma'ayan

Kaitlin E Samocha

Aniko Sabo

Chiao-Feng Lin

Christine Stevens

Li-San Wang

Vladimir Makarov

Paz Polak

Seungtai Yoon

Jared Maguire

Emily L Crawford

Nicholas G Campbell

Evan T Geller

Otto Valladares

Chad Shafer

Han Liu

Tuo Zhao

Guiqing Cai

Jayon Lihm

Ruth Dannenfelser

Omar Jabado

Zuleyma Peralta

Uma Nagaswamy

Donna Muzny

Jeffrey G Reid

Irene Newsham

Yuanqing Wu

Lora Lewis

Yi Han

Benjamin F Voight

Elaine Lim

Elizabeth Rossin

Andrew Kirby

Jason Flannick

Menachem Fromer

Khalid Shakir

Tim Fennell

Kiran Garimella

Eric Banks

Ryan Poplin

Stacey Gabriel

Mark Depristo

Jack R Wimbish

Braden E Boone

Shawn E Levy

Catalina Betancur

Shamil Sunyaev

Eric Boerwinkle

Joseph D Buxbaum
email: joseph.buxbaum@mssm.edu

Edwin H Cook

Bernie 18

Devlin

Richard A Gibbs

Kathryn Roeder
email: kathryn.roeder@gmail.com

Gerard D Schellenberg

James S Sutcliffe

Mark J Daly
email: mjdaly@atgu.mgh.harvard.edu

Patterns and rates of exonic de novo mutations in autism spectrum disorders

We assess the role of de novo mutations in autism spectrum disorders (ASD) by sequencing the exomes of ASD cases and their parents (n= 175 trios). Fewer than half of the cases (46.3%) carry a missense or nonsense de novo variant and the overall rate of mutation is only modestly higher than the expected rate. In contrast, there is significantly enriched connectivity among the proteins encoded by genes harboring de novo missense or nonsense mutations, and excess connectivity to prior ASD genes of major effect, suggesting a subset of observed events are relevant to ASD risk. The small increase in rate of de novo events, when taken together with the connections among the proteins themselves and to ASD, are consistent with an important but limited role for de novo point mutations, similar to that documented for de novo copy number variants. Genetic models incorporating these data suggest that the majority of observed de novo events are unconnected to ASD, those that do confer risk are distributed across many genes and are incompletely penetrant (i.e., not necessarily causal). Our results support polygenic models in which spontaneous coding mutations in any of a large number of genes increases risk by 5 to 20-fold. Despite the challenge posed by such models, results from de novo events and a large parallel case-control study provide strong evidence in favor of CHD8 and KATNAL2 as genuine autism risk factors.

Autism spectrum disorders (ASD) are believed to have genetic and environmental origins, yet in only a modest fraction of individuals can specific causes be identified [START_REF] Lichtenstein | The genetics of autism spectrum disorders and related neuropsychiatric disorders in childhood[END_REF][START_REF] Hallmayer | Genetic Heritability and Shared Environmental Factors Among Twin Pairs With Autism[END_REF] . Copy number variants (CNVs), often de novo and covering multiple adjacent genes, have been identified as conferring risk [START_REF] Pinto | Functional impact of global rare copy number variation in autism spectrum disorders[END_REF][START_REF] Sanders | Multiple recurrent de novo CNVs, including duplications of the 7q11.23 Williams syndrome region, are strongly associated with autism[END_REF] . While these CNVs provide important leads to underlying biology, they rarely implicate single genes, are rarely fully penetrant, and many confer risk to a broad range of conditions including ID, epilepsy, and schizophrenia [START_REF] Sebat | Rare structural variants in schizophrenia: one disorder, multiple mutations; one mutation, multiple disorders[END_REF] . There are also documented instances of rare single nucleotide variants (SNVs) that are highly penetrant for ASD [START_REF] Betancur | Etiological heterogeneity in autism spectrum disorders: more than 100 genetic and genomic disorders and still counting[END_REF] .

Large-scale genetic studies make clear that the origins of ASD risk are multifarious, and recent estimates based on CNV data put the number of independent risk loci in the hundreds [START_REF] Sanders | Multiple recurrent de novo CNVs, including duplications of the 7q11.23 Williams syndrome region, are strongly associated with autism[END_REF] . Yet knowledge regarding specific risk-determining genes and the overall genetic architecture for ASD remains incomplete. Although new sequencing technologies provide a catalog of most variation in the genome, the profound locus heterogeneity of ASD makes it challenging to distinguish variants that confer risk from the background noise of inconsequential SNVs. De novo variation, being less frequent and potentially more deleterious, could offer insights into risk-determining genes. For this reason we sought to carefully evaluate the observed rate and consequence of de novo point mutations in the exomes of ASD subjects.

We performed exome sequencing of 175 ASD probands and their parents across five centers with multiple protocols and validation techniques (Supplementary Information). We used a sensitive and specific analytic pipeline based on current best practices [START_REF] Li | Fast and accurate long-read alignment with Burrows-Wheeler transform[END_REF][START_REF] Depristo | A framework for variation discovery and genotyping using next-generation DNA sequencing data[END_REF][START_REF] Mckenna | The Genome Analysis Toolkit: a MapReduce framework for analyzing next-generation DNA sequencing data[END_REF] to analyze all data and observed no heterogeneity of mutation rate among centers.

In the entire sample, we observed 161 coding region point mutations (101 missense, 50 silent and 10 nonsense), with an additional 2 conserved splice site (CSS) SNVs and 6 frameshift indels validated and included in pathway analyses (Supplementary Table 1).

To determine whether the rate of coding region point mutations was elevated, we estimated the mutation rate in light of coverage and base context using two parallel approaches (Supplementary Information). Based on both models, the exome target should have a significantly increased (≈30%) mutation rate compared to the genome. Conservatively, by assuming the low-end of the estimated mutation rate from recent whole-genome data (1.2x10 -8 ) [START_REF] Conrad | Variation in genome-wide mutation rates within and between human families[END_REF] , we estimate a mutation rate of 1.5x10 -8 for the exome sequence captured here. The observed point mutation rate of 0.92/exome is slightly but not significantly elevated versus expectation (Table 1) and is insensitive to adjustment for lower coverage regions (Supplementary Information). Indeed our rate is similar to Sanders et al. (in press).

Per-family events were distributed according to the Poisson distribution (Table 1), yielding no evidence for ASD tracing to high rates of de novo mutation. The relative rates of 'functional' (missense, nonsense, CSS and read-through) versus silent changes did not deviate from expectation (Table 2). We did, however, observe 10 nonsense mutations (6.2%), which exceeded expectation (3.3%) (one-tailed P=0.04; Supplementary Information).

We examined the missense mutations as such variation can cause loss of function 11 using PolyPhen2 scores [START_REF] Kryukov | Most rare missense alleles are deleterious in humans: implications for complex disease and association studies[END_REF] to measure mutation severity. These also showed no deviation from random expectation. The observed PolyPhen2 scores clearly deviate from standing variation in the parents (Table 2): Such variation, even the rarest category, has survived selective pressure and is not an appropriate control for de novo events.

We observed 3 genes with two de novo mutations: BRCA2 (2 missense), FAT1 (2 missense) and KCNMA1 (1 missense, 1 silent). A gene with two or more non-synonymous de novo hits across a panel of trios might suggest strong candidacy. However, simulations (Supplementary Information) show that two such hits are inadequate to define a gene as a conclusive risk factor given the number of observed events in the study.

From analyses of secondary phenotypes (Supplementary Tables 23), the most striking result is that paternal and maternal age, themselves highly correlated (r 2 =0.679, P-value<0.0001), each strongly predicts the number of de novo events per offspring (paternal age P=0.0013, maternal age P=0.000365), consistent with aggregating mutations in germ cells in the paternal line [START_REF] Crow | The origins, patterns and implications of human spontaneous mutation[END_REF] . Consistent with genetic theory, there is an increased rate of de novo mutation in female versus male cases (1.214 for females vs. 0.914 for males); however, the difference is not significant, perhaps owing to limited sample size. Considering phenotypic correlates, we observed no rate difference between subjects with strict autism versus those with a broader ASD diagnosis, between positive and negative family history, or any significant effect of de novo mutation on verbal, nonverbal or full scale IQ (Supplementary Table 3).

While hundreds of loci are apparently involved in autism [START_REF] Sanders | Multiple recurrent de novo CNVs, including duplications of the 7q11.23 Williams syndrome region, are strongly associated with autism[END_REF] and de novo mutations therein affect ASD risk, modeling of different numbers of risk genes and penetrances (Supplementary Information) shows that a model of hundreds of genes with high penetrance mutations is excluded by our data; however, more modest contributions of de novo variants are not. For example, 10-20% of cases carrying a de novo risk-conferring event and conferring ten to twentyfold increased risk, is consistent with these data (Supplementary Table 4). Thus, our data are consistent with either chance mutation or a modest role for de novo mutations on risk.

We therefore posed two questions of the group of genes harboring de novo functional mutations: do the protein products of these genes interact with each other more than expected, and are they unusually enriched in, or connected to, prior curated lists of ASD-implicated genes? Using an in silico approach (DAPPLE) [START_REF] Rossin | Proteins encoded in genomic regions associated with immune-mediated disease physically interact and suggest underlying biology[END_REF][START_REF] Lage | A large-scale analysis of tissue-specific pathology and gene expression of human disease genes and complexes[END_REF] the protein-protein connectivity in the set of 113 genes harboring 'functional' de novo mutations was evaluated. These analyses (Figure 1) showed significantly greater connectivity amongst the de novo identified proteins than would be expected by chance (P<0.001) (Supplementary Information).

Querying previously-defined, manually-curated lists of genes 6 associated with high risk for ASD with intellectual disability (ID; Supplementary Tables 5), ASD without ID, and high risk ID genes (Supplementary Tables 6), we asked whether there was significant enrichment for de novo mutations in these genes. Five genes with 'functional' de novo events were previously associated with ASD and/or ID (STXBP1, MEF2C, KIRREL3, RELN and TUBA1A); for four of these genes (all but RELN) the prior evidence indicated autosomal dominant inheritance.

We then assessed the average distance (D i , Supplementary Figure 2) of the de novo coding variants in brain-expressed genes (see supplement) to the ASD/ID list using a Protein-Protein Interaction background network. To enhance power, data from a companion study (Sanders et al.) were used, including the observed silent de novo variants and de novo variants in unaffected siblings as comparators. The average distance for non-synonymous variants was significantly smaller for the case set than the comparator set (3.66+0.42 versus 3.78+0.59; permutation P=0.033) (Figure 2). Much of this signal comes from 31 synaptic genes identified by three large-scale synaptic proteomic studies (D i =3.47+0.46 versus 3.57+0.60; permutation P=0.084) (Supplemental Figure 3; see also Supplemental Fig. 4 for the complete data). Taken in total, these independent gene set analyses, along with the modest enrichment of de novo variants over background rates in ASD, indicate that a proportion of the de novo events observed in this study likely contribute to autism risk.

Using whole-exome sequencing of autism trios, we demonstrate a rate, functional distribution and predicted impact of de novo mutation largely consistent with chance mutational processes governed by sequence context. This lack of significant deviation from random mutational processes suggests a more limited role for the contribution of de novo mutations to ASD pathogenesis than has previously been suggested [START_REF] Lage | A large-scale analysis of tissue-specific pathology and gene expression of human disease genes and complexes[END_REF] , and specifically highlights the fact that observing a single de novo mutation, even an apparently 'severe' LOF allele, is insufficient to implicate a gene as a risk factor. Yet the pathway analyses presented here assert that the overall set of genes hit with 'functional' de novo mutations are not random and are biologically related to each other and to previously identified ASD/ID candidate genes. Modeling the de novo mutational process under a range of genetic models reveals that some models are inconsistent with the observed data -e.g., one hundred rare, fully penetrant Mendelian genes similar to Rett syndrome -while others are not such as spontaneous 'functional' mutation in a 1,000 genes that would increase risk by ten or twentyfold (Supplementary Table 4). Models that fit the data are consistent with the relative risks estimated for most de novo CNVs 4 and suggest that de novo SNVs, like most CNVs, often combine with other risk factors rather than fully cause disease. Furthermore, these models suggest that de novo SNVs events will likely explain <5% of the overall variance in autism risk (Supplementary Table 4).

Considering the two companion manuscripts, 18 genes with two functional de novo mutations are observed in the complete data. Using simulations, 11.91 genes on average harbor functional mutations by chance (Supplementary Table 7). Thus, a set of 18 genes with two or more hits is not quite significant (p=0.063). Matching loss-of-function variants, however, at SCN2A, KATNAL2 and CHD8 (Supplementary Table 7) are unlikely to occur by chance because the expected very low rate of de novo nonsense, splice and frameshift variants. We evaluated these strong candidates further using exome sequencing on 935 cases and 870 controls and at both KATNAL2 and CHD8, three additional LoF mutations were observed in cases with none in controls (no additional LoF mutations were seen at SCN2A). Using data from more than 5000 individuals in the NHLBI Exome Variant Server as additional controls, 3 LoF mutations were seen in KATNAL2 but none again in CHD8, making the additional observation of 3 CHD8 LoF mutations in our cases significant evidence (p<0.01) of this being a genuine autism susceptibility gene. Not all genes with double hits are nearly so promising (Supplementary Information; Supplementary Tables 89) supporting the estimate above that most such observations are simply chance events. Overall, these data underscore the challenge of establishing individual genes as conclusive risk factors for ASD, a challenge that will require larger sample sizes and, likely, deeper analytic integration with inherited variation.

METHODS (for online version only)

Phenotype assessment. Affected probands were assessed by research-reliable research personnel using Autism Diagnostic Interview-Revised (ADI-R) and the Autism Diagnostic Observation Schedule-Generic (ADOS) and DSM-IV diagnosis of a pervasive developmental disorder was made by a clinician. All probands met criteria for autism on the ADI-R and either autism or ASD on the ADOS, except for the 3 subjects from AGRE that were not assessed with the ADOS. In all 85% of probands were classified with autism on both the ADI-R and ADOS.

Exome sequencing, variant identification, and de novo detection. Exome capture and sequencing was performed at each site using similar methods. Exons were captured using the Agilent 38Mb SureSelect v2 (University of Pennsylvania and Broad Institute n=118), the NimbleGen Seq Cap EZ SR v2 (Mt Sinai School of Medicine, Vanderbilt University n=51), or NimbleGen VCRome 2.1 (Baylor n=6). After capture, another round of LM-PCR was performed to increase the quantity of DNA available for sequencing. All libraries were sequenced using an IlluminaHiSeq2000.

Sequence processing and variant calling was performed using a similar computational workflow at all sites. Data was processed with Picard (http://picard.sourceforge.net/), which utilizes base qualityscore recalibration and local realignment at known indels 8 and BWA [START_REF] Li | Fast and accurate long-read alignment with Burrows-Wheeler transform[END_REF] for mapping reads to hg19. SNPs were called using GATK [START_REF] Depristo | A framework for variation discovery and genotyping using next-generation DNA sequencing data[END_REF][START_REF] Mckenna | The Genome Analysis Toolkit: a MapReduce framework for analyzing next-generation DNA sequencing data[END_REF] for all trios jointly. The variable sites that we have considered in analysis are restricted to those that pass GATK standard filters. From this set of variants, we identified putative de novo mutations as sites where both parents were homozygous for the reference sequence and the offspring was heterozygous and each genotype call was made confidently (see Supplementary Information).

Validation of de novo events. Putative de novo events were validated by sequencing the carrier and both parents using Sanger sequencing methods (University of Pennsylvania, Mt. Sinai School of Medicine, Vanderbilt University, Baylor Medical College) or by Sequenom MALDI-TOF genotyping of trios (Broad).

Gene annotation. All identified mutations were then annotated using Refseq hg19. The functional impact of variants was assessed for all isoforms of each gene, with the most severe annotation taking priority. Splice site variants were identified as occurring within two basepairs of any intron/exon boundary.

Expectation of de novo mutation calculation.

To calculate the expected de novo rate, we assessed the mutability of all possible trinucleotide contexts in the intergenic region of the human genome for variation in two fashions: fixed genomic differences compared to chimpanzee and baboon [START_REF] Kryukov | Most rare missense alleles are deleterious in humans: implications for complex disease and association studies[END_REF] and variation identified from the 1,000 Genomes project. The overall mutation rate for the exome was then determined by summing the probability of mutation for all bases in the exome that were captured successfully. We also determined the Pathway analyses. We applied DAPPLE [START_REF] Rossin | Proteins encoded in genomic regions associated with immune-mediated disease physically interact and suggest underlying biology[END_REF] , which uses the InWeb database [START_REF] Lage | A large-scale analysis of tissue-specific pathology and gene expression of human disease genes and complexes[END_REF] , to determine whether there is excess protein protein interaction across the genes hit by a functional de novo event. We also assessed whether these genes were more closely connected to a list of ASD genes. [START_REF] Betancur | Etiological heterogeneity in autism spectrum disorders: more than 100 genetic and genomic disorders and still counting[END_REF] Modeling de novo events. We modeled a Poisson process consistent with the expected distribution defined by the mutation model and with the observed data. We varied the fraction of genes that influence risk, the probability a variant in a gene would be functional, and the penetrance of functional de novo events. We also simulated a random set of de novo events to estimate the probability of hitting a gene multiple times.

Association Analysis . We performed association tests using SKAT [START_REF] Wu | Rare-variant association testing for sequencing data with the sequence kernel association test[END_REF] , a generalization of C-alpha [START_REF] Neale | Testing for an unusual distribution of rare variants[END_REF] . Our primary analyses treat case-control data generated at Baylor and Broad separately (23 genes X 2 sites), but we also performed mega and meta-analyses (23 genes X 2 methods).

2

  Singletons, doubletons, and ≥3 (copies) are only those variants called in the parents from Wave 1. 3 Benign, Possibly Damaging, and Probably Damaging as defined by PolyPhen2.

Figure 1 .

 1 Figure1. Direct protein connections from InWeb, restricting to genes harboring de novo mutations for DAPPLE analysis. Two extensive networks are identified, the first centered on SMARCC2 with 12 connections across 11 genes and the second centered on FN1 with 7 connections across 6 genes. The P-value for each gene having as many connections as those observed color the nodes of the network.

Figure 2 .

 2 Figure 2. PPI network analysis for de novo variants and prior ASD genes (ASD112). Nodes are sized based on connectivity. Genes harboring de novo variants (left) and prior ASD genes (right) are colored blue with dark blue nodes represent genes that belong to one of these lists and are also intermediate proteins. Intermediate proteins (center) are colored in shades of orange based on a p-value computed using a proportion test where darker color represents a lower p-value. Green edges represent direct connections between genes harboring de novo variants (left) and prior ASD genes. All other edges, connecting to intermediate proteins are shown in grey.

Table 1 : Distribution of events per family

 1 Expected distribution of number of trios with a given event count as determined by the Poisson. Exp is the expectation for 175 trios based on the sequence-context mutation rate model M1 (Supplementary Materials) based on the count of the number of trios that have at least 10x coverage.

	Events per	All ASD trios			Random
	family	exon DN SNVs	1	Exp	2	Mut-Exp	3
	0	71		69.7	73.2
	1	62		64.2	63.8
	2	28		29.5	27.8
	3	10		9.1	8.1
	4	2		2.1	1.8
	5	1		0.4	0.3
				0.920	0.871
	1 Exon DN-SNVs include all single nucleotide variants in coding sequence but excludes indels and intronic variants.

2 3 Random Mut-

Table 2 : Rates of mutation annotation given variant type

 2

	Type of de novo mutation			De novo	1	Random De novo	Singletons	2	Doubletons	2	≥3	2
	Missense			62.7%		66.1%	59.5%		55.4%	48.8%
	Nonsense			6.2%		3.3%	1.2%		0.8%	0.4%
	Synonymous			31.1%		30.6%	39.3%		43.8%	50.8%
	Benign	3			35.0%		35.9%	46.6%		51.3%	63.4%
	Possibly Damaging	3		21.0%		18.9%	18.8%		17.7%	15.1%
	Probably Damaging	3	44.0%		45.2%	34.7%		31.0%	21.4%

1

All indels and failing variants were removed.

Acknowledgements

This work was directly supported by NIH grants R01MH089208 (MJD), R01 MH089025 (JDB), R01 MH089004 (GS), R01MH089175 (RG) and R01 MH089482 (JSS) and supported in part by NIH grants P50 HD055751 (EHC), RO1 MH057881 (BD), and R01 MH061009 (JSS). YK, GC, and SY are Seaver Fellows, supported by the Seaver Foundation. We thank Thomas Lehner (NIMH), Adam Felsenfeld (NHGRI), and Patrick Bender (NIMH) for their support and contribution to the project. We thank Stephan Sanders and Matthew State for discussions on the interpretation of de novo events. We thank David Reich for comments on the abstract and message of the manuscript. We acknowledge the assistance of Melissa Potter, Anna McGrew and Genea Crockett without whom these studies would not be possible, and Center for Human Genetics Research resources: Computational Genomics Core, Genetic Studies Ascertainment Core and DNA Resources core, supported in part by NIH NCRR grant UL1 RR024975, and the Vanderbilt Kennedy Center for Research on Human Development (P30 HD015052). We acknowledge partial support for U54 HG003273 (RG). JDB, BD, MD, RG, AS, GS, JSS are lead investigators in the Autism Sequencing Consortium (ASC). The ASC is comprised of groups sharing massively parallel sequencing data in autism.

Author Contributions

Laboratory work: AS, CS, GC, OJ, ZP, JDB, DM, IN, YW, LL, YH, SG, ELC, NGC, ETG Data Processing: BMN, KES, EL, AK, JF, MF, KS, TF, KG, EB, RP, MDP, SG, SY, VM, JL, JDB, AS, CS, UN, JGR, JRW, BEB, SEL, CFL, LSW, OV Statistical Analysis: BMN, LL, KES, CS, BFV, JM, ER, SS, PP, YK, AM, RD, CFL, LSW, HL, TZ, EB, RAG, JDB, CB, EHC, JSS, GDS, BD, KR, MJD PIs/Study design: EB, RAG, EHC, JDB, KR, BD, GDS, JSS, MJD Yan Kou, Li Liu, Avi Ma'ayan, Kaitlin E. Samocha, Aniko Sabo, and Chiao-Feng Lin contributed equally to this work. Eric Boerwinkle, Joseph D. Buxbaum, Edwin H. Cook, Jr., Bernie Devlin, Richard A. Gibbs, Kathryn Roeder, Gerard D. Schellenberg, James S. Sutcliffe, and Mark J. Daly are lead investigators of the ARRA Autism Sequencing Collaboration.

Author information

Data included in this manuscript has been deposited at dbGaP under accession number phs000298.v1.p1 and is available for download at http://www.ncbi.nlm.nih.gov/projects/gap/cgibin/study.cgi?study_id=phs000298.v1.p1

Reprints and permissions information is available at www.nature.com/reprints. The authors declare no competing financial interests. Correspondence and requests for materials should be addressed to Mark J. Daly, mjdaly@atgu.mgh.harvard.edu, Joseph D. Buxbaum joseph.buxbaum@mssm.edu and Kathryn Roeder kathryn.roeder@gmail.com. Supplementary Information is linked to the online version of the paper at www.nature.com/nature