Structural properties of the minimum cut of partially-supplied graphs.

It is well known that information about the structure of a graph is contained within its minimum cut. Here we investigate how the minimum cut of one graph informs the structure of a second, related graph. We consider pairs of graphs G and H, with respective Laplacian matrices L and M, and call H partially supplied provided M is a Schur complement of L. Our results show how the minimum cut of H relates to the structure of the larger graph G.

An eigenvector interlacing property of graphs that arise from trees by Schur complementation of the Laplacian.

The literature is replete with rich connections between the structure of a graph G = (V, E) and the spectral properties of its Laplacian matrix L. This paper establishes similar connections between the structure of G and the Laplacian L* of a second graph G*. Our interest lies in L* that can be obtained from L by Schur complementation, in which case we say that G* is partially-supplied with respect to G. In particular, we specialize to where G is a tree with points of articulation r ∈ R and consider the partially-supplied graph G* derived from G by taking the Schur complement with respect to R in L. Our results characterize how the eigenvectors of the Laplacian of G* relate to each other and to the structure of the tree.

A population genetic approach to mapping neurological disorder genes using deep resequencing.

Deep resequencing of functional regions in human genomes is key to identifying potentially causal rare variants for complex disorders. Here, we present the results from a large-sample resequencing (n  =  285 patients) study of candidate genes coupled with population genetics and statistical methods to identify rare variants associated with Autism Spectrum Disorder and Schizophrenia. Three genes, MAP1A, GRIN2B, and CACNA1F, were consistently identified by different methods as having significant excess of rare missense mutations in either one or both disease cohorts. In a broader context, we also found that the overall site frequency spectrum of variation in these cases is best explained by population models of both selection and complex demography rather than neutral models or models accounting for complex demography alone. Mutations in the three disease-associated genes explained much of the difference in the overall site frequency spectrum among the cases versus controls. This study demonstrates that genes associated with complex disorders can be mapped using resequencing and analytical methods with sample sizes far smaller than those required by genome-wide association studies. Additionally, our findings support the hypothesis that rare mutations account for a proportion of the phenotypic variance of these complex disorders.

Direct measure of the de novo mutation rate in autism and schizophrenia cohorts.

The role of de novo mutations (DNMs) in common diseases remains largely unknown. Nonetheless, the rate of de novo deleterious mutations and the strength of selection against de novo mutations are critical to understanding the genetic architecture of a disease. Discovery of high-impact DNMs requires substantial high-resolution interrogation of partial or complete genomes of families via resequencing. We hypothesized that deleterious DNMs may play a role in cases of autism spectrum disorders (ASD) and schizophrenia (SCZ), two etiologically heterogeneous disorders with significantly reduced reproductive fitness. We present a direct measure of the de novo mutation rate (µ) and selective constraints from DNMs estimated from a deep resequencing data set generated from a large cohort of ASD and SCZ cases (n = 285) and population control individuals (n = 285) with available parental DNA. A survey of ∼430 Mb of DNA from 401 synapse-expressed genes across all cases and 25 Mb of DNA in controls found 28 candidate DNMs, 13 of which were cell line artifacts. Our calculated direct neutral mutation rate (1.36 × 10(-8)) is similar to previous indirect estimates, but we observed a significant excess of potentially deleterious DNMs in ASD and SCZ individuals. Our results emphasize the importance of DNMs as genetic mechanisms in ASD and SCZ and the limitations of using DNA from archived cell lines to identify functional variants.

On the Fiedler vectors of graphs that arise from trees by Schur complementation of the Laplacian.

The utility of Fiedler vectors in interrogating the structure of graphs has generated intense interest and motivated the pursuit of further theoretical results. This paper focuses on how the Fiedler vectors of one graph reveal structure in a second graph that is related to the first. Specifically, we consider a point of articulation r in the graph G whose Laplacian matrix is L and derive a related graph G{r} whose Laplacian is the matrix obtained by taking the Schur complement with respect to r in L. We show how Fiedler vectors of G{r} relate to the structure of G and we provide bounds for the algebraic connectivity of G{r} in terms of the connected components at r in G. In the case where G is a tree with points of articulation r ∈ R, we further consider the graph GR derived from G by taking the Schur complement with respect to R in L. We show that Fiedler vectors of GR valuate the pendent vertices of G in a manner consistent with the structure of the tree.