We hypothesized that transcription factors (TFs) can recognize DNA shape without nucleotide sequence recognition. Motivating an independent role for shape, many TF binding sites lack a sequence-motif, DNA shape adds specificity to sequence-motifs, and different sequences can encode similar shapes. We therefore asked if binding sites of any TFs are enriched for a specific pattern of DNA shape features, such as minor groove width, propeller twist, helical twist, or roll. To discover these shape-motifs de novo, we developed ShapeMF, which performs Gibbs sampling directly on shape features rather than nucleotide sequences. Using ChIP-Seq data for 110 human ENCODE TFs, we find that most TFs have shape-motifs and strongly bind regulatory regions with shape-motifs in the absence of sequence-motifs. When shape- and sequence-recognition co-occur in a region, the two types of motifs can be overlapping, flanking, or separated by consistent spacing, with shape-motifs explaining low information content positions in and nearby sequence-motifs. Shape-motifs are prevalent in regions co-bound by multiple TFs. They also explain binding of the co-factors MYC-MAX and TBX5-NKX2-5, which cannot be accounted for with sequence-motifs. Finally, shape-motifs are strikingly different across TFs with nearly identical sequence motifs, providing an explanation for their distinct binding locations. These results establish shape-motifs as drivers of TF-DNA recognition complementary to sequence-motifs.

Protein networks have been shown to be instrumental in deciphering the molecular basis of disease. In this talk I will describe on-going work to harness physical interaction networks for the identification of cancer driver genes and the eluciation of neurodegenrative disease genes and modules.

Nucleotide variation in gene regulatory elements is a major determinant of phenotypes including morphological diversity between species, human variation and human disease. Despite continual progress in the cataloging of these elements, little is known about the code and grammatical rules that govern their function. Deciphering the code and their grammatical rules will enable high-resolution mapping of regulatory elements, accurate interpretation of nucleotide variation within them and the design of sequences that can deliver molecules for therapeutic purposes. To this end, we are using massively parallel reporter assays (MPRAs) to simultaneously test the activity of thousands of gene regulatory elements in parallel. By designing MPRAs to learn regulatory grammar or to carry out saturation mutagenesis of every possible nucleotide change in disease causing gene regulatory elements, we are increasing our understanding of the phenotypic consequences of gene regulatory mutations. Regulatory elements can also serve as therapeutic targets. To highlight this role, we used CRISPR/Cas9 activation (CRISPRa) of regulatory elements to rescue a haploinsufficient disease (having a 50% dosage reduction due to having only one functional allele) in vivo. By targeting the Sim1 promoter or its 270kb distant hypothalamic enhancer, we were able to rescue the haploinsufficient obesity phenotype in Sim1 heterozygous mice, both using a transgenic and adeno-associated virus approach. Our results highlight how regulatory elements could be used as therapeutic targets to treat numerous altered gene dosage diseases.

Most methods for construction of gene regulatory networks from expression data rely on the precision matrix, the inverse of the covariance matrix, as an indicator of which variables are directly associated. The precision matrix assumes Gaussian linear data and its entries are zero for pairs of variables that are conditionally independent given all other variables. In this talk, we propose the Distance Precision Matrix which builds on distance covariance,  a measure of possibly non-linear association due to Szekely and Rizzo. Computing networks using the Distance Precision Matrix allows to discard indirect associations even in the presence of non-linear interactions. The method can also be adopted to small-sample situations.

No abstract available.

This talk deals with finding self-similar trends in a long sequence presented as a stream. We focus on finding exact trends, as well as those that might have a small number of errors in the forms of bit flips while using a single pass and space polylogarithmic in the input size.

I have been exploring the hypothesis that the best integer programming solvers can largely be used as push-button black boxes for many significant problems in computational biology. If so, ILP would become a more accessible tool for biologists without a deeper background in computation and programming. The experimental results are generally positive, but with some exceptions. I will report on these results and outline future experiments.

Given an alphabet  and integers k and L, a universal hitting set is a set of k-mers so that every possible L-long string over the alphabet must contain as a substring a k-mer from the set. We provide complexity analysis and efficient algorithms to construct small universal hitting sets. We also explore the relationship of such sets to minimizers, which have been adopted in many deep-sequencing algorithms, and show the advantage of universal hitting sets.
Joint work with Yaron Orenstein, David Pellow, Guillaume Marcais and Carl Kingsford

Cancer is an evolutionary process driven by somatic mutations that accumulate in a population of cells that form a primary tumor.  In later stages of cancer progression, cells migrate from a primary tumor and seed metastases at distant anatomical sites.  I will describe algorithms to reconstruct this evolutionary process from DNA sequencing data of tumors.  These algorithms address challenges that distinguish the tumor phylogeny problem from classical phylogenetic tree reconstruction, including challenges due to mixed samples and complex migration patterns.