Search

International audience; Algebraic datatypes, and among them lists and trees, have attracted a lot of interest in automated reasoning and Satisfiability Modulo Theories (SMT). Since its latest stable version, the SMT-LIB standard defines a theory of algebraic datatypes, which is currently supported by several mainstream SMT solvers. In this paper, we study this particular theory of datatypes and prove that it is strongly polite, showing how it can be combined with other arbitrary disjoint theories using polite combination. The combination method uses a new, simple, and natural notion of additivity that enables deducing strong politeness from (weak) politeness.

We report a molecular assay, Methyl-HiC, that can simultaneously capture the chromosome conformation and DNA methylome in a cell. Methyl-HiC reveals coordinated DNA methylation status between distal genomic segments that are in spatial proximity in the nucleus, and delineates heterogeneity of both the chromatin architecture and DNA methylome in a mixed population. It enables simultaneous characterization of cell-type-specific chromatin organization and epigenome in complex tissues.

We show that every orthogonal polyhedron of genus at most 2 can be unfolded without overlap while using only a linear number of orthogonal cuts (parallel to the polyhedron edges). This is the first result on unfolding general orthogonal polyhedra beyond genus-0. Our unfolding algorithm relies on the existence of at most 2 special leaves in what we call the "unfolding tree" (which ties back to the genus), so unfolding polyhedra of genus 3 and beyond requires new techniques., Comment: 22 pages, 10 figures

A stacking operation adds a $d$-simplex on top of a facet of a simplicial $d$-polytope while maintaining the convexity of the polytope. A stacked $d$-polytope is a polytope that is obtained from a $d$-simplex and a series of stacking operations. We show that for a fixed $d$ every stacked $d$-polytope with $n$ vertices can be realized with nonnegative integer coordinates. The coordinates are bounded by $O(n^{2\log(2d)})$, except for one axis, where the coordinates are bounded by $O(n^{3\log(2d)})$. The described realization can be computed with an easy algorithm. The realization of the polytopes is obtained with a lifting technique which produces an embedding on a large grid. We establish a rounding scheme that places the vertices on a sparser grid, while maintaining the convexity of the embedding., Comment: 22 pages, 10 Figures

The recent next generation science standards in the United States have emphasized learning about complex systems as a core feature of science learning. Over the past 15 years, a number of educational tools and theories have been investigated to help students learn about complex systems; but surprisingly, little research has been devoted to identifying the supports that teachers need to teach about complex systems in the classroom. In this paper, we aim to address this gap in the literature. We describe a 2-year professional development study in which we gathered data on teachers’ abilities and perceptions regarding the delivery of computer-supported complex systems curricula. We present results across the 2 years of the project and demonstrate the need for particular instructional supports to improve implementation efforts, including providing differentiated opportunities to build expertise and addressing teacher beliefs about whether computational-model construction belongs in the science classroom. Results from students’ classroom experiences and learning over the 2 years are offered to further illustrate the impact of these instructional supports., National Science Foundation (U.S.). Discovery Research K– 12 (Grant 1019228)

The Clock Drawing Test—a simple pencil and paper test—has been used for more than 50 years as a screening tool to differentiate normal individuals from those with cognitive impairment, and has proven useful in helping to diagnose cognitive dysfunction associated with neurological disorders such as Alzheimer’s disease, Parkinson’s disease, and other dementias and conditions. We have been administering the test using a digitizing ballpoint pen that reports its position with considerable spatial and temporal precision, making available far more detailed data about the subject’s performance. Using pen stroke data from these drawings categorized by our software, we designed and computed a large collection of features, then explored the tradeoffs in performance and interpretability in classifiers built using a number of different subsets of these features and a variety of different machine learning techniques. We used traditional machine learning methods to build prediction models that achieve high accuracy. We operationalized widely used manual scoring systems so that we could use them as benchmarks for our models. We worked with clinicians to define guidelines for model interpretability, and constructed sparse linear models and rule lists designed to be as easy to use as scoring systems currently used by clinicians, but more accurate. While our models will require additional testing for validation, they offer the possibility of substantial improvement in detecting cognitive impairment earlier than currently possible, a development with considerable potential impact in practice., Robert E. Wise Research and Education Institution, United States. Defense Advanced Research Projects Agency (Contract D13AP00008), National Science Foundation (U.S.) (Award IIS-1404494), National Institute of Neurological Disorders and Stroke (U.S.) (Grants R01-NS17950, K23-NS60660, and R01-NS082386), National Heart, Lung, and Blood Institute (Contract N01-HC25195), National Institute on Aging (Grants R01 AG0333040, AG16492, and AG08122), National Institute of Mental Health (U.S.) (Grant RO1-MH073989), National Center for Advancing Translational Sciences (U.S.) (Clinical and Translational Science Award to the University of Florida UL1TR000064), University of Florida. Center for Movement Disorders and Neurorestoration

Research in human vision suggests that in a single fixation, humans can extract a significant amount of information from a natural scene, e.g. the semantic category, spatial layout, and object identities. This ability is useful, for example, for quickly determining location, navigating around obstacles, detecting threats, and guiding eye movements to gather more information. In this paper, we ask a new question: What can we see at a glance at a web page – an artificial yet complex “real world” stimulus? Is it possible to notice the type of website, or where the relevant elements are, with only a glimpse? We find that observers, fixating at the center of a web page shown for only 120 milliseconds, are well above chance at classifying the page into one of ten categories. Furthermore, this ability is supported in part by text that they can read at a glance. Users can also understand the spatial layout well enough to reliably localize the menu bar and to detect ads, even though the latter are often camouflaged among other graphical elements. We discuss the parallels between web page gist and scene gist, and the implications of our findings for both vision science and human-computer interaction., Google Award

Alzheimer’s disease (AD) is a severe age-related neurodegenerative disorder characterized by accumulation of amyloid-β plaques and neurofibrillary tangles, synaptic and neuronal loss, and cognitive decline. Several genes have been implicated in AD, but chromatin state alterations during neurodegeneration remain uncharacterized. Here we profile transcriptional and chromatin state dynamics across early and late pathology in the hippocampus of an inducible mouse model of AD-like neurodegeneration. We find a coordinated downregulation of synaptic plasticity genes and regulatory regions, and upregulation of immune response genes and regulatory regions, which are targeted by factors that belong to the ETS family of transcriptional regulators, including PU.1. Human regions orthologous to increasing-level enhancers show immune-cell-specific enhancer signatures as well as immune cell expression quantitative trait loci, while decreasing-level enhancer orthologues show fetal-brain-specific enhancer activity. Notably, AD-associated genetic variants are specifically enriched in increasing-level enhancer orthologues, implicating immune processes in AD predisposition. Indeed, increasing enhancers overlap known AD loci lacking protein-altering variants, and implicate additional loci that do not reach genome-wide significance. Our results reveal new insights into the mechanisms of neurodegeneration and establish the mouse as a useful model for functional studies of AD regulatory regions., Belfer Neurodegeneration Consortium, National Institutes of Health (U.S.) (National Institute of Neurological Disorders and Stroke (U.S.)/National Institute on Aging RO1NS078839), Swiss National Science Foundation (Early Postdoc Mobility Fellowship P2BSP3_151885), National Institutes of Health (U.S.) (National Human Genome Research Institute (U.S.) R01HG004037-07), National Institutes of Health (U.S.) (National Human Genome Research Institute (U.S.) RC1HG005334)

For all n, ε > 0), we show that the set of Poisson Binomial distributions on n variables admits a proper ε-cover in total variation distance of size n[superscript 2] + n · (1/ε)[superscript O(log[superscript 2] (1/ε)), which can also be computed in polynomial time. We discuss the implications of our construction for approximation algorithms and the computation of approximate Nash equilibria in anonymous games., Alfred P. Sloan Foundation (Fellowship), Microsoft Research (Faculty Fellowship), National Science Foundation (U.S.) (CAREER Award CCF-0953960), National Science Foundation (U.S.) (Award CCF-1101491)

Despite the large evolutionary distances between metazoan species, they can show remarkable commonalities in their biology, and this has helped to establish fly and worm as model organisms for human biology. Although studies of individual elements and factors have explored similarities in gene regulation, a large-scale comparative analysis of basic principles of transcriptional regulatory features is lacking. Here we map the genome-wide binding locations of 165 human, 93 worm and 52 fly transcription regulatory factors, generating a total of 1,019 data sets from diverse cell types, developmental stages, or conditions in the three species, of which 498 (48.9%) are presented here for the first time. We find that structural properties of regulatory networks are remarkably conserved and that orthologous regulatory factor families recognize similar binding motifs in vivo and show some similar co-associations. Our results suggest that gene-regulatory properties previously observed for individual factors are general principles of metazoan regulation that are remarkably well-preserved despite extensive functional divergence of individual network connections. The comparative maps of regulatory circuitry provided here will drive an improved understanding of the regulatory underpinnings of model organism biology and how these relate to human biology, development and disease. © 2014 Macmillan Publishers Limited.

To reduce costs and improve clinical relevance of genetic studies, there has been increasing interest in performing such studies in hospital-based cohorts by linking phenotypes extracted from electronic medical records (EMRs) to genotypes assessed in routinely collected medical samples. A fundamental difficulty in implementing such studies is extracting accurate information about disease outcomes and important clinical covariates from large numbers of EMRs. Recently, numerous algorithms have been developed to infer phenotypes by combining information from multiple structured and unstructured variables extracted from EMRs. Although these algorithms are quite accurate, they typically do not provide perfect classification due to the difficulty in inferring meaning from the text. Some algorithms can produce for each patient a probability that the patient is a disease case. This probability can be thresholded to define case-control status, and this estimated case-control status has been used to replicate known genetic associations in EMR-based studies. However, using the estimated disease status in place of true disease status results in outcome misclassification, which can diminish test power and bias odds ratio estimates. We propose to instead directly model the algorithm-derived probability of being a case. We demonstrate how our approach improves test power and effect estimation in simulation studies, and we describe its performance in a study of rheumatoid arthritis. Our work provides an easily implemented solution to a major practical challenge that arises in the use of EMR data, which can facilitate the use of EMR infrastructure for more powerful, cost-effective, and diverse genetic studies.

The problem of “approximating the crowd” is that of estimating the crowd’s majority opinion by querying only a subset of it. Algorithms that approximate the crowd can intelligently stretch a limited budget for a crowdsourcing task. We present an algorithm, “CrowdSense,” that works in an online fashion where items come one at a time. CrowdSense dynamically samples subsets of the crowd based on an exploration/exploitation criterion. The algorithm produces a weighted combination of the subset’s votes that approximates the crowd’s opinion. We then introduce two variations of CrowdSense that make various distributional approximations to handle distinct crowd characteristics. In particular, the first algorithm makes a statistical independence approximation of the labelers for large crowds, whereas the second algorithm finds a lower bound on how often the current subcrowd agrees with the crowd’s majority vote. Our experiments on CrowdSense and several baselines demonstrate that we can reliably approximate the entire crowd’s vote by collecting opinions from a representative subset of the crowd.

Advances in high-throughput sequencing are reshaping how we perceive microbial communities inhabiting the human body, with implications for therapeutic interventions. Several large-scale datasets derived from hundreds of human microbiome samples sourced from multiple studies are now publicly available. However, idiosyncratic data processing methods between studies introduce systematic differences that confound comparative analyses. To overcome these challenges, we developed GutCyc, a compendium of environmental pathway genome databases (ePGDBs) constructed from 418 assembled human microbiome datasets using MetaPathways, enabling reproducible functional metagenomic annotation. We also generated metabolic network reconstructions for each metagenome using the Pathway Tools software, empowering researchers and clinicians interested in visualizing and interpreting metabolic pathways encoded by the human gut microbiome. For the first time, GutCyc provides consistent annotations and metabolic pathway predictions, making possible comparative community analyses between health and disease states in inflammatory bowel disease, Crohn’s disease, and type 2 diabetes. GutCyc data products are searchable online, or may be downloaded and explored locally using MetaPathways and Pathway Tools., Alexander Graham Bell Canada (Graduate Scholarships-Doctoral Program (CGS D)), Tula Foundation, University of British Columbia. Faculty of Graduate and Postdoctoral Studies, Stanford University. School of Medicine (Dean's Funds), National Institutes of Health (U.S.) (Biotechnology Training Grant, grant number 5T32 GM008412), King Abdullah University of Science and Technology (research grant under the KAUST Stanford Academic Excellence Alliance program), National Institutes of Health (U.S.) (NIH/NIGMS 5R01GM099534), Thomas C. and Joan M. Merigan Endowment

Chromatin-state analysis is widely applied in the studies of development and diseases. However, existing methods operate at a single length scale, and therefore cannot distinguish large domains from isolated elements of the same type. To overcome this limitation, we present a hierarchical hidden Markov model, diHMM, to systematically annotate chromatin states at multiple length scales. We apply diHMM to analyse a public ChIP-seq data set. diHMM not only accurately captures nucleosome-level information, but identifies domain-level states that vary in nucleosome-level state composition, spatial distribution and functionality. The domain-level states recapitulate known patterns such as super-enhancers, bivalent promoters and Polycomb repressed regions, and identify additional patterns whose biological functions are not yet characterized. By integrating chromatin-state information with gene expression and Hi-C data, we identify context-dependent functions of nucleosome-level states. Thus, diHMM provides a powerful tool for investigating the role of higher-order chromatin structure in gene regulation., Claudia Barr Award, National Institutes of Health (U.S.) (Grant R21HG006778), National Institutes of Health (U.S.) (Grant R01HL119099), National Institutes of Health (U.S.) (Grant K25HL133599)

Background The combinatorial binding of trans-acting factors (TFs) to the DNA is critical to the spatial and temporal specificity of gene regulation. For certain regulatory regions, more than one regulatory module (set of TFs that bind together) are combined to achieve context-specific gene regulation. However, previous approaches are limited to either pairwise TF co-association analysis or assuming that only one module is used in each regulatory region. Results We present a new computational approach that models the modular organization of TF combinatorial binding. Our method learns compact and coherent regulatory modules from in vivo binding data using a topic model. We found that the binding of 115 TFs in K562 cells can be organized into 49 interpretable modules. Furthermore, we found that tens of thousands of regulatory regions use multiple modules, a structure that cannot be observed with previous hard clustering based methods. The modules discovered recapitulate many published protein-protein physical interactions, have consistent functional annotations of chromatin states, and uncover context specific co-binding such as gene proximal binding of NFY + FOS + SP and distal binding of NFY + FOS + USF. For certain TFs, the co-binding partners of direct binding (motif present) differs from those of indirect binding (motif absent); the distinct set of co-binding partners can predict whether the TF binds directly or indirectly with up to 95% accuracy. Joint analysis across two cell types reveals both cell-type-specific and shared regulatory modules. Conclusions Our results provide comprehensive cell-type-specific combinatorial binding maps and suggest a modular organization of combinatorial binding. Keywords Computational genomics Transcription factor Combinatorial binding Direct and indirect binding Topic model, National Institutes of Health (U.S.) (grant 1U01HG007037-01)

Consider laying out a fixed-topology binary tree of N nodes into external memory with block size B so as to minimize the worst-case number of block memory transfers required to traverse a path from the root to a node of depth D. We prove that the optimal number of memory transfers is Θ([D over lg(1+B))] when D = O(lgN), Θ([lgN over lg(1+[BlgN over D])]) when D=Ω(lgN) and D=O(BlgN), Θ([D over B]) ,when D=Ω(BlgN)., National Science Foundation (U.S.) (Grant CCF-0430849), National Science Foundation (U.S.) (Grant OISE-0334653)

Additive manufacturing of cellular structures has numerous applications ranging from fabrication of biological scaffolds and medical implants, to mechanical weight reduction and control over mechanical properties. Various additive manufacturing processes have been used to produce open regular cellular structures limited only by the resolution of the printer. These efforts have focused on printing explicitly designed cells or explicitly planning offsets between strands. Here we describe a technique for producing cellular structures implicitly by inducing viscous thread instability when extruding material. This process allows us to produce complex cellular structures at a scale that is finer than the native resolution of the printer. We demonstrate tunable effective elastic modulus and density that span two orders of magnitude. Fine grained cellular structures allow for fabrication of foams for use in a wide range of fields ranging from bioengineering, to robotics to food printing., United States. Department of Defense (Grant W81XWH-13-C-0081)

The central nervous system is a dense, layered, 3D interconnected network of populations of neurons and thus recapitulating that complexity for in vitro CNS models requires methods that can create defined topologically-complex neuronal networks. Several three-dimensional patterning approaches have been developed but none have demonstrated the ability to control the connections between populations of neurons. Here we report a method using AC electrokinetic forces that can guide, accelerate, slow down and push up neurites in un-modified collagen scaffolds. We present a means to create in vitro neural networks of arbitrary complexity by using such forces to create 3D intersections of primary neuronal populations that are plated in a 2D plane. We report for the first time in vitro basic brain motifs that have been previously observed in vivo and show that their functional network is highly decorrelated to their structure. This platform can provide building blocks to reproduce in vitro the complexity of neural circuits and provide a minimalistic environment to study the structure-function relationship of the brain circuitry.

The complex multi-stage architecture of cortical visual pathways provides the neural basis for efficient visual object recognition in humans. However, the stage-wise computations therein remain poorly understood. Here, we compared temporal (magnetoencephalography) and spatial (functional MRI) visual brain representations with representations in an artificial deep neural network (DNN) tuned to the statistics of real-world visual recognition. We showed that the DNN captured the stages of human visual processing in both time and space from early visual areas towards the dorsal and ventral streams. Further investigation of crucial DNN parameters revealed that while model architecture was important, training on real-world categorization was necessary to enforce spatio-temporal hierarchical relationships with the brain. Together our results provide an algorithmically informed view on the spatio-temporal dynamics of visual object recognition in the human visual brain., National Eye Institute (EY020484), Google (Firm) (Google Research Faculty Award), Alexander von Humboldt-Stiftung (Feodor Lynen Postdoctoral Fellowship), Deutsche Forschungsgemeinschaft (Emmy Noether Program, CI 241/1-1), McGovern Institute Neurotechnology (MINT) program, National Science Foundation (U.S.) (NSF Award 1532591)

Introduction The human genome-scale metabolic reconstruction details all known metabolic reactions occurring in humans, and thereby holds substantial promise for studying complex diseases and phenotypes. Capturing the whole human metabolic reconstruction is an on-going task and since the last community effort generated a consensus reconstruction, several updates have been developed. Objectives We report a new consensus version, Recon 2.2, which integrates various alternative versions with significant additional updates. In addition to re-establishing a consensus reconstruction, further key objectives included providing more comprehensive annotation of metabolites and genes, ensuring full mass and charge balance in all reactions, and developing a model that correctly predicts ATP production on a range of carbon sources. Methods Recon 2.2 has been developed through a combination of manual curation and automated error checking. Specific and significant manual updates include a respecification of fatty acid metabolism, oxidative phosphorylation and a coupling of the electron transport chain to ATP synthase activity. All metabolites have definitive chemical formulae and charges specified, and these are used to ensure full mass and charge reaction balancing through an automated linear programming approach. Additionally, improved integration with transcriptomics and proteomics data has been facilitated with the updated curation of relationships between genes, proteins and reactions. Results Recon 2.2 now represents the most predictive model of human metabolism to date as demonstrated here. Extensive manual curation has increased the reconstruction size to 5324 metabolites, 7785 reactions and 1675 associated genes, which now are mapped to a single standard. The focus upon mass and charge balancing of all reactions, along with better representation of energy generation, has produced a flux model that correctly predicts ATP yield on different carbon sources. Conclusion Through these updates we have achieved the most complete and best annotated consensus human metabolic reconstruction available, thereby increasing the ability of this resource to provide novel insights into normal and disease states in human. The model is freely available from the Biomodels database (http://identifiers.org/biomodels.db/MODEL1603150001). Electronic supplementary material The online version of this article (doi:10.1007/s11306-016-1051-4) contains supplementary material, which is available to authorized users.

The purpose of this paper is to conceptualize the hitherto separate domains of Cyberspace and International Relations into an integrated socio-technical system that we jointly call the cyber International Relations (Cyber-IR) system and to identify and analyze its emergent properties utilizing the methods common to science and engineering systems adapted here for the social sciences. Our work is an exploration in both theory and methodology. This paper (a) identifies the actors and functions in the core systems, Cyberspace, and IR, (b) disambiguates system boundary, (c) creates a design structure matrix (DSM), a matrix of the interdependencies among functions of actors, (d) analyzes DSM qualitatively to show multiple interdependent and heterogeneous Cyber-IR properties, and (e) analyzes quantitatively the differential importance of core functions as well as the impact of actor attributes on influence in Cyber-IR. This work forms a baseline for further understanding of the nature of the heterogeneous influences of the various actors and the various outcomes that could result from it., United States. Office of Naval Research (ONR award number N00014-09-1-0597)

An obfuscator is a compiler that transforms any program (which we will view in this work as a boolean circuit) into an obfuscated program (also a circuit) that has the same input-output functionality as the original program, but is “unintelligible”. Obfuscation has applications for cryptography and for software protection. Barak et al. (CRYPTO 2001, pp. 1–18, 2001) initiated a theoretical study of obfuscation, which focused on black-box obfuscation, where the obfuscated circuit should leak no information except for its (black-box) input-output functionality. A family of functionalities that cannot be obfuscated was demonstrated. Subsequent research has showed further negative results as well as positive results for obfuscating very specific families of circuits, all with respect to black box obfuscation. This work is a study of a new notion of obfuscation, which we call best-possible obfuscation. Best possible obfuscation makes the relaxed requirement that the obfuscated program leaks as little information as any other program with the same functionality (and of similar size). In particular, this definition allows the program to leak information that cannot be obtained from a black box. Best-possible obfuscation guarantees that any information that is not hidden by the obfuscated program is also not hidden by any other similar-size program computing the same functionality, and thus the obfuscation is (literally) the best possible. In this work we study best-possible obfuscation and its relationship to previously studied definitions. Our main results are: (1) A separation between black-box and best-possible obfuscation. We show a natural obfuscation task that can be achieved under the best-possible definition, but cannot be achieved under the black-box definition. (2) A hardness result for best-possible obfuscation, showing that strong (information-theoretic) best-possible obfuscation implies a collapse in the Polynomial-Time Hierarchy. (3) An impossibility result for efficient best-possible (and black-box) obfuscation in the presence of random oracles. This impossibility result uses a random oracle to construct hard-to-obfuscate circuits, and thus it does not imply impossibility in the standard model., National Science Foundation (U.S.) (NSF grant CFF-0635297), National Science Foundation (U.S.) (NSF grant CNS-0430450), Weitzmann Institute of Science (Cymerman-Jakubskind award)

This paper considers scheduling tasks while minimizing the power consumption of one or more processors, each of which can go to sleep at a fixed cost α . There are two natural versions of this problem, both considered extensively in recent work: minimize the total power consumption (including computation time), or minimize the number of “gaps” in execution. For both versions in a multiprocessor system, we develop a polynomial-time algorithm based on sophisticated dynamic programming. In a generalization of the power-saving problem, where each task can execute in any of a specified set of time intervals, we develop a (1+23α) -approximation, and show that dependence on α is necessary. In contrast, the analogous multi-interval gap scheduling problem is set-cover hard (and thus not o(lgn) -approximable), even in the special cases of just two intervals per job or just three unit intervals per job. We also prove several other hardness-of-approximation results. Finally, we give an O(n√) -approximation for maximizing throughput given a hard upper bound on the number of gaps., Institute for Research in Fundamental Sciences (Iran) (Grant Number CS1385-2-01), Institute for Research in Fundamental Sciences (Iran) (Grant Number CS1384-6-01)

We give subquadratic algorithms that, given two necklaces each with n beads at arbitrary positions, compute the optimal rotation of the necklaces to best align the beads. Here alignment is measured according to the ℓ [subscript p] norm of the vector of distances between pairs of beads from opposite necklaces in the best perfect matching. We show surprisingly different results for p=1, p even, and p=∞. For p even, we reduce the problem to standard convolution, while for p=∞ and p=1, we reduce the problem to (min,+) convolution and \((\operatorname {median},+)\) convolution. Then we solve the latter two convolution problems in subquadratic time, which are interesting results in their own right. These results shed some light on the classic sorting X+Y problem, because the convolutions can be viewed as computing order statistics on the antidiagonals of the X+Y matrix. All of our algorithms run in o(n [superscript 2]) time, whereas the obvious algorithms for these problems run in Θ(n [superscript 2]) time., National Science Foundation (U.S.) (Grant CCF-0430849), National Science Foundation (U.S.) (Grant OISE-0334653), Alfred P. Sloan Foundation (Fellowship)

Association studies provide genome-wide information about the genetic basis of complex disease, but medical research has focused primarily on protein-coding variants, owing to the difficulty of interpreting noncoding mutations. This picture has changed with advances in the systematic annotation of functional noncoding elements. Evolutionary conservation, functional genomics, chromatin state, sequence motifs and molecular quantitative trait loci all provide complementary information about the function of noncoding sequences. These functional maps can help with prioritizing variants on risk haplotypes, filtering mutations encountered in the clinic and performing systems-level analyses to reveal processes underlying disease associations. Advances in predictive modeling can enable data-set integration to reveal pathways shared across loci and alleles, and richer regulatory models can guide the search for epistatic interactions. Lastly, new massively parallel reporter experiments can systematically validate regulatory predictions. Ultimately, advances in regulatory and systems genomics can help unleash the value of whole-genome sequencing for personalized genomic risk assessment, diagnosis and treatment., National Institutes of Health (U.S.) (Grant R01HG004037), National Institutes of Health (U.S.) (Grant RC1HG005334), National Science Foundation (U.S.) (CAREER Grant 0644282)

We consider the problem of leader election (LE) in single-hop radio networks with synchronized time slots for transmitting and receiving messages. We assume that the actual number n of processes is unknown, while the size u of the ID space is known, but is possibly much larger. We consider two types of collision detection: strong (SCD), whereby all processes detect collisions, and weak (WCD), whereby only non-transmitting processes detect collisions. We introduce loneliness detection (LD) as a key subproblem for solving LE in WCD systems. LD informs all processes whether the system contains exactly one process or more than one. We show that LD captures the difference in power between SCD and WCD, by providing an implementation of SCD over WCD and LD. We present two algorithms that solve deterministic and probabilistic LD in WCD systems with time costs of O(log u/n and O(min(log u/n, log (1/ε)/n)), respectively, where ε is the error probability. We also provide matching lower bounds. Assuming LD is solved, we show that SCD systems can be emulated in WCD systems with factor-2 overhead in time. We present two algorithms that solve deterministic and probabilistic LE in SCD systems with time costs of O(log u) and O(min (log u/, log log + log(1/ε), respectively, where ε is the error probability. We provide matching lower bounds. Keywords: Collision Detection, Safety Property, Leader Election, Liveness Property, Virtual Process, National Science Foundation (U.S.) (CCF-0937274), National Science Foundation (U.S.) (CCF0939370), National Science Foundation (U.S.) (CCF-0726514), United States. Air Force. Office of Scientific Research (FA9550-08-1-0159)

This article is one of ten reviews selected from the Annual Update in Intensive Care and Emergency Medicine 2015 and co-published as a series in Critical Care. Other articles in the series can be found online at http://ccforum.com/series/annualupdate2015. Further information about the Annual Update in Intensive Care and Emergency Medicine is available from http://www.springer.com/series/8901, Philips Healthcare Nederland, SAP for Healthcare

Capturing color in water is challenging due to the heavy non-uniform attenuation of light in water across the visible spectrum, which results in dramatic hue shifts toward blue. Yet observing color in water is important for monitoring and surveillance as well as marine biology studies related to species identification, individual and group behavior, and ecosystem health and activity monitoring. Underwater robots are equipped with motor control for large scale transects but they lack sensors that enable capturing color-accurate underwater images. We present a method for color-accurate imaging in water called perceptual adaptive illumination. This method dynamically mixes the illumination of an object in a distance-dependent way using a controllable multi-color light source. The color mix compensates correctly for color loss and results in an image whose color composition is equivalent to rendering the object in air. Experiments were conducted with a color palette in the pool and at three different coral reefs sites, and with an underwater robot collecting image data with the new sensor., United States. Office of Naval Research (Project N000140911051)

This paper presents a decision-theoretic approach to problems that require accurate placement of a robot relative to an object of known shape, such as grasping for assembly or tool use. The decision process is applied to a robot hand with tactile sensors, to localize the object on a table and ultimately achieve a target placement by selecting among a parameterized set of grasping and information-gathering trajectories. The process is demonstrated in simulation and on a real robot. This work has been previously presented in Hsiao et al. (Workshop on Algorithmic Foundations of Robotics (WAFR), 2008; Robotics Science and Systems (RSS), 2010) and Hsiao (Relatively robust grasping, Ph.D. thesis, Massachusetts Institute of Technology, 2009)., National Science Foundation (U.S.) (Grant 0712012)

We describe a modeling framework and collection of foundational composition results for the study of probabilistic distributed algorithms in synchronous radio networks. Though the radio setting has been studied extensively by the distributed algorithms community, their results rely on informal descriptions of the channel behavior and therefore lack easy comparability and are prone to error caused by definition subtleties. Our framework rectifies these issues by providing: (1) a method to precisely describe a radio channel as a probabilistic automaton; (2) a mathematical notion of implementing one channel using another channel, allowing for direct comparisons of channel strengths and a natural decomposition of problems into implementing a more powerful channel and solving the problem on the powerful channel; (3) a mathematical definition of a problem and solving a problem; (4) a pair of composition results that simplify the tasks of proving properties about channel implementation algorithms and combining problems with channel implementations. Our goal is to produce a model streamlined for the needs of the radio network algorithms community.

Transcription of long noncoding RNAs (lncRNAs) within gene regulatory elements can modulate gene activity in response to external stimuli, but the scope and functions of such activity are not known. Here we use an ultrahigh-density array that tiles the promoters of 56 cell-cycle genes to interrogate 108 samples representing diverse perturbations. We identify 216 transcribed regions that encode putative lncRNAs, many with RT-PCR–validated periodic expression during the cell cycle, show altered expression in human cancers and are regulated in expression by specific oncogenic stimuli, stem cell differentiation or DNA damage. DNA damage induces five lncRNAs from the CDKN1A promoter, and one such lncRNA, named PANDA, is induced in a p53-dependent manner. PANDA interacts with the transcription factor NF-YA to limit expression of pro-apoptotic genes; PANDA depletion markedly sensitized human fibroblasts to apoptosis by doxorubicin. These findings suggest potentially widespread roles for promoter lncRNAs in cell-growth control., National Institutes of Health (U.S.), National Institute of Arthritis and Musculoskeletal and Skin Diseases (U.S.) (NIAMS) (K08-AR054615)), National Cancer Institute (U.S.) (NIH/(NCI) (R01-CA118750)), National Cancer Institute (U.S.) (NIH/(NCI) R01-CA130795)), Juvenile Diabetes Research Foundation International, American Cancer Society, Howard Hughes Medical Institute (Early career scientist), Stanford University (Graduate Fellowship), National Science Foundation (U.S.) (Graduate Research Fellowship), United States. Dept. of Defense (National Defense Science and Engineering Graduate Fellowship)

Chromatin is composed of DNA and a variety of modified histones and non-histone proteins, which have an impact on cell differentiation, gene regulation and other key cellular processes. Here we present a genome-wide chromatin landscape for Drosophila melanogaster based on eighteen histone modifications, summarized by nine prevalent combinatorial patterns. Integrative analysis with other data (non-histone chromatin proteins, DNase I hypersensitivity, GRO-Seq reads produced by engaged polymerase, short/long RNA products) reveals discrete characteristics of chromosomes, genes, regulatory elements and other functional domains. We find that active genes display distinct chromatin signatures that are correlated with disparate gene lengths, exon patterns, regulatory functions and genomic contexts. We also demonstrate a diversity of signatures among Polycomb targets that include a subset with paused polymerase. This systematic profiling and integrative analysis of chromatin signatures provides insights into how genomic elements are regulated, and will serve as a resource for future experimental investigations of genome structure and function., United States. Dept. of Energy (Contract DE-AC02-05CH11231), RC2 HG005639, U01 HG004279, R01 GM082798, R37 GM45744, R01 GM071923, U54 HG004592, National Science Foundation (U.S.) (NSF 0905968)

This paper describes the architecture and implementation of a distributed autonomous gardening system with applications in urban/indoor precision agriculture. The garden is a mesh network of robots and plants. The gardening robots are mobile manipulators with an eye-in-hand camera. They are capable of locating plants in the garden, watering them, and locating and grasping fruit. The plants are potted cherry tomatoes enhanced with sensors and computation to monitor their well-being (e.g. soil humidity, state of fruits) and with networking to communicate servicing requests to the robots. By embedding sensing, computation, and communication into the pots, task allocation in the system is de-centrally coordinated, which makes the system scalable and robust against the failure of a centralized agent. We describe the architecture of this system and present experimental results for navigation, object recognition, and manipulation as well as challenges that lie ahead toward autonomous precision agriculture with multi-robot teams., Swiss National Science Foundation (contract number PBEL2118737), United States. Army Research Office. Multidisciplinary University Research Initiative (MURI SWARMS project W911NF-05-1-0219), National Science Foundation (U.S.) (NSF IIS-0426838), Intel Corporation (EFRI 0735953 Intel), Massachusetts Institute of Technology (UROP program), Massachusetts Institute of Technology (MSRP program)

Continuous-state POMDPs provide a natural representation for a variety of tasks, including many in robotics. However, most existing parametric continuous-state POMDP approaches are limited by their reliance on a single linear model to represent the world dynamics. We introduce a new switching-state dynamics model that can represent multi-modal state-dependent dynamics. We present the Switching Mode POMDP (SM-POMDP) planning algorithm for solving continuous-state POMDPs using this dynamics model. We also consider several procedures to approximate the value function as a mixture of a bounded number of Gaussians. Unlike the majority of prior work on approximate continuous-state POMDP planners, we provide a formal analysis of our SM-POMDP algorithm, providing bounds, where possible, on the quality of the resulting solution. We also analyze the computational complexity of SM-POMDP. Empirical results on an unmanned aerial vehicle collisions avoidance simulation, and a robot navigation simulation where the robot has faulty actuators, demonstrate the benefit of SM-POMDP over a prior parametric approach., National Science Foundation (U.S.). Division of Information and Intelligent Systems (Grant 0546467)

Toward our comprehensive understanding of legged locomotion in animals and machines, the compass gait model has been intensively studied for a systematic investigation of complex biped locomotion dynamics. While most of the previous studies focused only on the locomotion on flat surfaces, in this article, we tackle with the problem of bipedal locomotion in rough terrains by using a minimalistic control architecture for the compass gait walking model. This controller utilizes an open-loop sinusoidal oscillation of hip motor, which induces basic walking stability without sensory feedback. A set of simulation analyses show that the underlying mechanism lies in the “phase locking” mechanism that compensates phase delays between mechanical dynamics and the open-loop motor oscillation resulting in a relatively large basin of attraction in dynamic bipedal walking. By exploiting this mechanism, we also explain how the basin of attraction can be controlled by manipulating the parameters of oscillator not only on a flat terrain but also in various inclined slopes. Based on the simulation analysis, the proposed controller is implemented in a real-world robotic platform to confirm the plausibility of the approach. In addition, by using these basic principles of self-stability and gait variability, we demonstrate how the proposed controller can be extended with a simple sensory feedback such that the robot is able to control gait patterns autonomously for traversing a rough terrain., National Science Foundation (U.S.) (grant 0746194), Swiss National Science Foundation (grant PBZH2-114461), Swiss National Science Foundation (grant PP00P2_123387/1)

The primary objective of the Human Genome Project was to produce high-quality sequences not just for the human genome but also for those of the chief model organisms: Escherichia coli, yeast (Saccharomyces cerevisiae), worm (Caenorhabditis elegans), fly (Drosophila melanogaster) and mouse (Mus musculus). Free access to the resultant data has prompted much biological research, including development of a map of common human genetic variants (the International HapMap Project)1, expression profiling of healthy and diseased cells2 and in-depth studies of many individual genes. These genome sequences have enabled researchers to carry out genetic and functional genomic studies not previously possible, revealing new biological insights with broad relevance across the animal kingdom 3, 4.

Applications of linear mixed models (LMMs) to problems in genomics include phenotype prediction, correction for confounding in genome-wide association studies, estimation of narrow sense heritability, and testing sets of variants (e.g., rare variants) for association. In each of these applications, the LMM uses a genetic similarity matrix, which encodes the pairwise similarity between every two individuals in a cohort. Although ideally these similarities would be estimated using strictly variants relevant to the given phenotype, the identity of such variants is typically unknown. Consequently, relevant variants are excluded and irrelevant variants are included, both having deleterious effects. For each application of the LMM, we review known effects and describe new effects showing how variable selection can be used to mitigate them., National Institute on Aging (Brain eQTL Study (dbGaP phs000249.v1.p1))

Background Mapping of orthologous genes among species serves an important role in functional genomics by allowing researchers to develop hypotheses about gene function in one species based on what is known about the functions of orthologs in other species. Several tools for predicting orthologous gene relationships are available. However, these tools can give different results and identification of predicted orthologs is not always straightforward. Results We report a simple but effective tool, the Drosophila RNAi Screening Center Integrative Ortholog Prediction Tool (DIOPT; http://www.flyrnai.org/diopt webcite), for rapid identification of orthologs. DIOPT integrates existing approaches, facilitating rapid identification of orthologs among human, mouse, zebrafish, C. elegans, Drosophila, and S. cerevisiae. As compared to individual tools, DIOPT shows increased sensitivity with only a modest decrease in specificity. Moreover, the flexibility built into the DIOPT graphical user interface allows researchers with different goals to appropriately 'cast a wide net' or limit results to highest confidence predictions. DIOPT also displays protein and domain alignments, including percent amino acid identity, for predicted ortholog pairs. This helps users identify the most appropriate matches among multiple possible orthologs. To facilitate using model organisms for functional analysis of human disease-associated genes, we used DIOPT to predict high-confidence orthologs of disease genes in Online Mendelian Inheritance in Man (OMIM) and genes in genome-wide association study (GWAS) data sets. The results are accessible through the DIOPT diseases and traits query tool (DIOPT-DIST; http://www.flyrnai.org/diopt-dist webcite). Conclusions DIOPT and DIOPT-DIST are useful resources for researchers working with model organisms, especially those who are interested in exploiting model organisms such as Drosophila to study the functions of human disease genes., Harvard Catalyst, National Institutes of Health (U.S.) (NIH R01 GM067761), National Institute of Diabetes and Digestive and Kidney Diseases (U.S.) (5K08DK78361), Dana-Farber/Harvard Cancer Center

Background: The advent of high-throughput sequencing has enabled sequencing based measurements of cellular function, with an individual measurement potentially consisting of more than 108 reads. While tools are available for aligning sets of reads to genomes and interpreting the results, fewer tools have been developed to address the storage and retrieval requirements of large collections of aligned datasets. We present ReadDB, a network accessible column store database system for aligned high-throughput read datasets. Results: ReadDB stores collections of aligned read positions and provides a client interface to support visualization and analysis. ReadDB is implemented as a network server that responds to queries on genomic intervals in an experiment with either the set of contained reads or a histogram based interval summary. Tests on datasets ranging from 105 to 108 reads demonstrate that ReadDB performance is generally within a factor of two of local-storage based methods and often three to five times better than other network-based methods. Conclusions: ReadDB is a high-performance foundation for ChIP-Seq and RNA-Seq analysis. The client-server model provides convenient access to compute cluster nodes or desktop visualization software without requiring a shared network filesystem or large amounts of local storage. The client code provides a simple interface for fast data access to visualization or analysis. ReadDB provides a new way to store genome-aligned reads for use in applications where read sequence and alignment mismatches are not needed., National Institutes of Health (U.S.) (grant 5TL1EB008540), National Institutes of Health (U.S.) (grant 5R01HG002668), National Institutes of Health (U.S.) (grant P01-NS055923-01), National Institutes of Health (U.S.) (grant 1-UL1-RR024920)

Background Proteins are dynamic molecules that exhibit a wide range of motions; often these conformational changes are important for protein function. Determining biologically relevant conformational changes, or true variability, efficiently is challenging due to the noise present in structure data. Results In this paper we present a novel approach to elucidate conformational variability in structures solved using X-ray crystallography. We first infer an ensemble to represent the experimental data and then formulate the identification of truly variable members of the ensemble (as opposed to those that vary only due to noise) as a sparse estimation problem. Our results indicate that the algorithm is able to accurately distinguish genuine conformational changes from variability due to noise. We validate our predictions for structures in the Protein Data Bank by comparing with NMR experiments, as well as on synthetic data. In addition to improved performance over existing methods, the algorithm is robust to the levels of noise present in real data. In the case of Human Ubiquitin-conjugating enzyme Ubc9, variability identified by the algorithm corresponds to functionally important residues implicated by mutagenesis experiments. Our algorithm is also general enough to be integrated into state-of-the-art software tools for structure-inference., National Institute of General Medical Sciences (U.S.) (Grant Number 1R01GM081871)

We propose a constructive control design for stabilization of non-periodic trajectories of underactuated mechanical systems. An important example of such a system is an underactuated "dynamic walking" biped robot walking over rough terrain. The proposed technique is to compute a transverse linearization about the desired motion: a linear impulsive system which locally represents dynamics about a target trajectory. This system is then exponentially stabilized using a modified receding-horizon control design. The proposed method is experimentally verified using a compass-gait walker: a two-degree-of-freedom biped with hip actuation but pointed stilt-like feet. The technique is, however, very general and can be applied to higher degree-of-freedom robots over arbitrary terrain and other impulsive mechanical systems. © 2011 Springer-Verlag.

Background Analyze an approach to distributing transperineal prostate biopsy cores that yields data on the volume of a tumor that might be present when the biopsy is negative, and also increases detection efficiency. Methods Basic principles of sampling and probability theory are employed to analyze a transperineal biopsy pattern that uses evenly-spaced parallel cores in order to extract quantitative data on the volume of a small spherical tumor that could potentially be present, even though the biopsy did not detect it, i.e., negative biopsy. Results This approach to distributing biopsy cores provides data for the upper limit on the volume of a small, spherical tumor that might be present, and the probability of smaller volumes, when biopsies are negative and provides a quantitative basis for evaluating the effectiveness of different core spacing distances. Conclusions Distributing transperineal biopsy cores so they are evenly spaced provides a means to calculate the probability that a tumor of given volume could be present when the biopsy is negative, and can improve detection efficiency.

Background: Capturing accurate and machine-interpretable primary data from clinical encounters is a challenging task, yet critical to the integrity of the practice of medicine. We explore the intriguing possibility that technology can help accurately capture structured data from the clinical encounter using a combination of automated speech recognition (ASR) systems and tools for extraction of clinical meaning from narrative medical text. Our goal is to produce a displayed evolving encounter note, visible and editable (using speech) during the encounter. Results: This is very ambitious, and so far we have taken only the most preliminary steps. We report a simple proof-of-concept system and the design of the more comprehensive one we are building, discussing both the engineering design and challenges encountered. Without a formal evaluation, we were encouraged by our initial results. The proof-of-concept, despite a few false positives, correctly recognized the proper category of single-and multi-word phrases in uncorrected ASR output. The more comprehensive system captures and transcribes speech and stores alternative phrase interpretations in an XML-based format used by a text-engineering framework. It does not yet use the framework to perform the language processing present in the proof-of-concept. Conclusion: The work here encouraged us that the goal is reachable, so we conclude with proposed next steps. Some challenging steps include acquiring a corpus of doctor-patient conversations, exploring a workable microphone setup, performing user interface research, and developing a multi-speaker version of our tools., National Library of Medicine (U.S.) (grant T15 LM07117), National Library of Medicine (U.S.) (grant R01 LM009723-01A1)

Background Image-based screens can produce hundreds of measured features for each of hundreds of millions of individual cells in a single experiment. Results Here, we describe CellProfiler Analyst, open-source software for the interactive exploration and analysis of multidimensional data, particularly data from high-throughput, image-based experiments. Conclusion The system enables interactive data exploration for image-based screens and automated scoring of complex phenotypes that require combinations of multiple measured features per cell.

Background Genomic sequencing of SNPs is increasingly prevalent, though the amount of familial information these data contain has not been quantified. Methods We provide a framework for measuring the risk to siblings of a patient's SNP genotype disclosure, and demonstrate that sibling SNP genotypes can be inferred with substantial accuracy. Results Extending this inference technique, we determine that a very low number of matches at commonly varying SNPs is sufficient to confirm sib-ship, demonstrating that published sequence data can reliably be used to derive sibling identities. Using HapMap trio data, at SNPs where one child is homozygotic major, with a minor allele frequency ≤ 0.20, (N = 452684, 65.1%) we achieve 91.9% inference accuracy for sibling genotypes. Conclusion These findings demonstrate that substantial discrimination and privacy risks arise from use of inferred familial genomic data., National Institutes of Health (grant R01-LM009375-01A1), National Library of Medicine

Background: Text-based patient medical records are a vital resource in medical research. In order to preserve patient confidentiality, however, the U.S. Health Insurance Portability and Accountability Act (HIPAA) requires that protected health information (PHI) be removed from medical records before they can be disseminated. Manual de-identification of large medical record databases is prohibitively expensive, time-consuming and prone to error, necessitating automatic methods for large-scale, automated de-identification. Methods: We describe an automated Perl-based de-identification software package that is generally usable on most free-text medical records, e.g., nursing notes, discharge summaries, X-ray reports, etc. The software uses lexical look-up tables, regular expressions, and simple heuristics to locate both HIPAA PHI, and an extended PHI set that includes doctors' names and years of dates. To develop the de-identification approach, we assembled a gold standard corpus of re-identified nursing notes with real PHI replaced by realistic surrogate information. This corpus consists of 2,434 nursing notes containing 334,000 words and a total of 1,779 instances of PHI taken from 163 randomly selected patient records. This gold standard corpus was used to refine the algorithm and measure its sensitivity. To test the algorithm on data not used in its development, we constructed a second test corpus of 1,836 nursing notes containing 296,400 words. The algorithm's false negative rate was evaluated using this test corpus. Results: Performance evaluation of the de-identification software on the development corpus yielded an overall recall of 0.967, precision value of 0.749, and fallout value of approximately 0.002. On the test corpus, a total of 90 instances of false negatives were found, or 27 per 100,000 word count, with an estimated recall of 0.943. Only one full date and one age over 89 were missed. No patient names were missed in either corpus. Conclusion We have developed a pattern-matching de-identification system based on dictionary look-ups, regular expressions, and heuristics. Evaluation based on two different sets of nursing notes collected from a U.S. hospital suggests that, in terms of recall, the software out-performs a single human de-identifier (0.81) and performs at least as well as a consensus of two human de-identifiers (0.94). The system is currently tuned to de-identify PHI in nursing notes and discharge summaries but is sufficiently generalized and can be customized to handle text files of any format. Although the accuracy of the algorithm is high, it is probably insufficient to be used to publicly disseminate medical data. The open-source de-identification software and the gold standard re-identified corpus of medical records have therefore been made available to researchers via the PhysioNet website to encourage improvements in the algorithm., National Institute of Biomedical Imaging and Bioengineering (U.S.), National Institutes of Health (U.S) ( Grant Number R01-EB001659 )

Background: The regulatory map of a genome consists of the binding sites for proteins that determine the transcription of nearby genes. An initial regulatory map for S. cerevisiae was recently published using six motif discovery programs to analyze genome-wide chromatin immunoprecipitation data for 203 transcription factors. The programs were used to identify sequence motifs that were likely to correspond to the DNA-binding specificity of the immunoprecipitated proteins. We report improved versions of two conservation-based motif discovery algorithms, PhyloCon and Converge. Using these programs, we create a refined regulatory map for S. cerevisiae by reanalyzing the same chromatin immunoprecipitation data. Results: Applying the same conservative criteria that were applied in the original study, we find that PhyloCon and Converge each separately discover more known specificities than the combination of all six programs in the previous study. Combining the results of PhyloCon and Converge, we discover significant sequence motifs for 36 transcription factors that were previously missed. The new set of motifs identifies 636 more regulatory interactions than the previous one. The new network contains 28% more regulatory interactions among transcription factors, evidence of greater cross-talk between regulators. Conclusion: Combining two complementary computational strategies for conservation-based motif discovery improves the ability to identify the specificity of transcriptional regulators from genome-wide chromatin immunoprecipitation data. The increased sensitivity of these methods significantly expands the map of yeast regulatory sites without the need to alter any of the thresholds for statistical significance. The new map of regulatory sites reveals a more elaborate and complex view of the yeast genetic regulatory network than was observed previously., Pfizer Inc., National Institute of General Medical Sciences (U.S.) (NRSA award), National Institutes of Health (U.S) ( grant 1R01 HG002668-01 ), National Institutes of Health (U.S) ( grant HG00249 ), National Institutes of Health (U.S) ( training grant in genomic science 2T32HG00045 ), Society of Kauffman Fellows

We have designed a zebrafish genomic microarray to identify DNA-protein interactions in the proximal promoter regions of over 11,000 zebrafish genes. Using these microarrays, together with chromatin immunoprecipitation with an antibody directed against tri-methylated lysine 4 of Histone H3, we demonstrate the feasibility of this method in zebrafish. This approach will allow investigators to determine the genomic binding locations of DNA interacting proteins during development and expedite the assembly of the genetic networks that regulate embryogenesis., Wellcome Trust, European Molecular Biology Organization, National Institutes of Health (Grant HG002668) (Grant DK070813) (Grant 2RO1 HD33472) (Grant 5RO1 MH59942)

Background Whole-genome sequencing is an important tool for understanding microbial evolution and identifying the emergence of functionally important variants over the course of epidemics. In October 2010, a severe cholera epidemic began in Haiti, with additional cases identified in the neighboring Dominican Republic. We used whole-genome approaches to sequence four Vibrio cholerae isolates from Haiti and the Dominican Republic and three additional V. cholerae isolates to a high depth of coverage (>2000x); four of the seven isolates were previously sequenced. Results Using these sequence data, we examined the effect of depth of coverage and sequencing platform on genome assembly and identification of sequence variants. We found that 50x coverage is sufficient to construct a whole-genome assembly and to accurately call most variants from 100 base pair paired-end sequencing reads. Phylogenetic analysis between the newly sequenced and thirty-three previously sequenced V. cholerae isolates indicates that the Haitian and Dominican Republic isolates are closest to strains from South Asia. The Haitian and Dominican Republic isolates form a tight cluster, with only four variants unique to individual isolates. These variants are located in the CTX region, the SXT region, and the core genome. Of the 126 mutations identified that separate the Haiti-Dominican Republic cluster from the V. cholerae reference strain (N16961), 73 are non-synonymous changes, and a number of these changes cluster in specific genes and pathways. Conclusions Sequence variant analyses of V. cholerae isolates, including multiple isolates from the Haitian outbreak, identify coverage-specific and technology-specific effects on variant detection, and provide insight into genomic change and functional evolution during an epidemic.

Background Among its many roles in development, retinoic acid determines the anterior-posterior identity of differentiating motor neurons by activating retinoic acid receptor (RAR)-mediated transcription. RAR is thought to bind the genome constitutively, and only induce transcription in the presence of the retinoid ligand. However, little is known about where RAR binds to the genome or how it selects target sites. Results We tested the constitutive RAR binding model using the retinoic acid-driven differentiation of mouse embryonic stem cells into differentiated motor neurons. We find that retinoic acid treatment results in widespread changes in RAR genomic binding, including novel binding to genes directly responsible for anterior-posterior specification, as well as the subsequent recruitment of the basal polymerase machinery. Finally, we discovered that the binding of transcription factors at the embryonic stem cell stage can accurately predict where in the genome RAR binds after initial differentiation. Conclusions We have characterized a ligand-dependent shift in RAR genomic occupancy at the initiation of neurogenesis. Our data also suggest that enhancers active in pluripotent embryonic stem cells may be preselecting regions that will be activated by RAR during neuronal differentiation., Damon Runyon Cancer Research Foundation (DRG-1937-07), National Institutes of Health (U.S.) (P01 NS055923)