Connectivity of Triangulation Flip Graphs in the Plane.

Given a finite point set P in general position in the plane, a full triangulation of P is a maximal straight-line embedded plane graph on P. A partial triangulation of P is a full triangulation of some subset P ' of P containing all extreme points in P. A bistellar flip on a partial triangulation either flips an edge (called edge flip), removes a non-extreme point of degree 3, or adds a point in P \ P ' as vertex of degree 3. The bistellar flip graph has all partial triangulations as vertices, and a pair of partial triangulations is adjacent if they can be obtained from one another by a bistellar flip. The edge flip graph is defined with full triangulations as vertices, and edge flips determining the adjacencies. Lawson showed in the early seventies that these graphs are connected. The goal of this paper is to investigate the structure of these graphs, with emphasis on their vertex connectivity. For sets P of n points in the plane in general position, we show that the edge flip graph is ⌈ n / 2 - 2 ⌉ -vertex connected, and the bistellar flip graph is ( n - 3 ) -vertex connected; both results are tight. The latter bound matches the situation for the subfamily of regular triangulations (i.e., partial triangulations obtained by lifting the points to 3-space and projecting back the lower convex hull), where ( n - 3 ) -vertex connectivity has been known since the late eighties through the secondary polytope due to Gelfand, Kapranov, & Zelevinsky and Balinski's Theorem. For the edge flip-graph, we additionally show that the vertex connectivity is at least as large as (and hence equal to) the minimum degree (i.e., the minimum number of flippable edges in any full triangulation), provided that n is large enough. Our methods also yield several other results: (i) The edge flip graph can be covered by graphs of polytopes of dimension ⌈ n / 2 - 2 ⌉ (products of associahedra) and the bistellar flip graph can be covered by graphs of polytopes of dimension n - 3 (products of secondary polytopes). (ii) A partial triangulation is regular, if it has distance n - 3 in the Hasse diagram of the partial order of partial subdivisions from the trivial subdivision. (iii) All partial triangulations of a point set are regular iff the partial order of partial subdivisions has height n - 3 . (iv) There are arbitrarily large sets P with non-regular partial triangulations and such that every proper subset has only regular triangulations, i.e., there are no small certificates for the existence of non-regular triangulations.

Computing simplicial representatives of homotopy group elements.

A central problem of algebraic topology is to understand the homotopy groups π d ( X ) of a topological space X. For the computational version of the problem, it is well known that there is no algorithm to decide whether the fundamental group π 1 ( X ) of a given finite simplicial complex X is trivial. On the other hand, there are several algorithms that, given a finite simplicial complex X that is simply connected (i.e., with π 1 ( X ) trivial), compute the higher homotopy group π d ( X ) for any given d ≥ 2 . However, these algorithms come with a caveat: They compute the isomorphism type of π d ( X ) , d ≥ 2 as an abstract finitely generated abelian group given by generators and relations, but they work with very implicit representations of the elements of π d ( X ) . Converting elements of this abstract group into explicit geometric maps from the d-dimensional sphere S d to X has been one of the main unsolved problems in the emerging field of computational homotopy theory. Here we present an algorithm that, given a simply connected space X, computes π d ( X ) and represents its elements as simplicial maps from a suitable triangulation of the d-sphere S d to X. For fixed d, the algorithm runs in time exponential in size ( X ) , the number of simplices of X. Moreover, we prove that this is optimal: For every fixed d ≥ 2 , we construct a family of simply connected spaces X such that for any simplicial map representing a generator of π d ( X ) , the size of the triangulation of S d on which the map is defined, is exponential in size ( X ) .

Prion infections and anti-PrP antibodies trigger converging neurotoxic pathways.

Prions induce lethal neurodegeneration and consist of PrPSc, an aggregated conformer of the cellular prion protein PrPC. Antibody-derived ligands to the globular domain of PrPC (collectively termed GDL) are also neurotoxic. Here we show that GDL and prion infections activate the same pathways. Firstly, both GDL and prion infection of cerebellar organotypic cultured slices (COCS) induced the production of reactive oxygen species (ROS). Accordingly, ROS scavenging, which counteracts GDL toxicity in vitro and in vivo, prolonged the lifespan of prion-infected mice and protected prion-infected COCS from neurodegeneration. Instead, neither glutamate receptor antagonists nor inhibitors of endoplasmic reticulum calcium channels abolished neurotoxicity in either model. Secondly, antibodies against the flexible tail (FT) of PrPC reduced neurotoxicity in both GDL-exposed and prion-infected COCS, suggesting that the FT executes toxicity in both paradigms. Thirdly, the PERK pathway of the unfolded protein response was activated in both models. Finally, 80% of transcriptionally downregulated genes overlapped between prion-infected and GDL-treated COCS. We conclude that GDL mimic the interaction of PrPSc with PrPC, thereby triggering the downstream events characteristic of prion infection.

RFECS: a random-forest based algorithm for enhancer identification from chromatin state.

Transcriptional enhancers play critical roles in regulation of gene expression, but their identification in the eukaryotic genome has been challenging. Recently, it was shown that enhancers in the mammalian genome are associated with characteristic histone modification patterns, which have been increasingly exploited for enhancer identification. However, only a limited number of cell types or chromatin marks have previously been investigated for this purpose, leaving the question unanswered whether there exists an optimal set of histone modifications for enhancer prediction in different cell types. Here, we address this issue by exploring genome-wide profiles of 24 histone modifications in two distinct human cell types, embryonic stem cells and lung fibroblasts. We developed a Random-Forest based algorithm, RFECS (Random Forest based Enhancer identification from Chromatin States) to integrate histone modification profiles for identification of enhancers, and used it to identify enhancers in a number of cell-types. We show that RFECS not only leads to more accurate and precise prediction of enhancers than previous methods, but also helps identify the most informative and robust set of three chromatin marks for enhancer prediction.