Graph neural networks (GNNs) are widely used in urban spatiotemporal forecasting, e.g., predicting infrastructure problems. In this setting, government officials aim to identify in which neighborhoods incidents like potholes or rodents occur. The true state of incidents is observed via government inspection ratings. However, these ratings are only conducted for a sparse set of neighborhoods and incident types. We also observe the state of incidents via crowdsourced reports, which are more densely observed but may be biased due to heterogeneous reporting. First, we propose a multiview, multioutput GNN-based model that uses both unbiased rating data and biased reporting data to predict the true latent state of incidents. Second, we investigate a case study of New York City urban incidents and collect a dataset of 9,615,863 crowdsourced reports and 1,041,415 government inspection ratings over 3 years and across 139 types of incidents. We show on both real and semi-synthetic data that our model can better predict the latent state compared to models that use only reporting data or only rating data. Finally, we quantify demographic biases in crowdsourced reporting, e.g., higher-income neighborhoods report problems at higher rates. Our analysis showcases a widely applicable approach for latent state prediction using heterogeneous, sparse, and biased data.

We show that if a language $\mathcal{L}$ admits a public-coin unambiguous interactive proof (UIP) with round complexity $\ell$, where a bits are communicated per round, then the batch language ${\mathcal{L}}^{\otimes k}$, i.e. the set of k-tuples of statements all belonging to $\mathcal{L}$, has an unambiguous interactive proof with round complexity $\ell \cdot$ polylog $(k)$, per-round communication of $a \cdot \ell \cdot$ polylog $(k)+$ poly $(\ell)$ bits, assuming the verifier in the UIP has depth bounded by polylog $(k)$. Prior to this work, the best known batch UIP for ${\mathcal{L}}^{\otimes k}$ required communication complexity at least ($\operatorname{poly}(a) \cdot k^{\epsilon}+k$) $\cdot \ell^{1 / \epsilon}$ for any arbitrarily small constant $\epsilon\gt 0$ (Reingold-Rothblum-Rothblum, STOC 2016). As a corollary of our result, we obtain a doubly efficient proof system, that is, a proof system whose proving overhead is polynomial in the time of the underlying computation, for any language computable in polynomial space and in time at most $n^{O\left(\sqrt{\frac{\log n}{\log \log n}}\right)}$. This expands the state of the art of doubly efficient proof systems: prior to our work, such systems were known for languages computable in polynomial space and in time $n^{(\log n)^{\delta}}$ for a small $\delta\gt 0$ significantly smaller than 1/2 (Reingold-Rothblum-Rothblum, STOC 2016).

It is difficult to evaluate machine learning classifiers without large labeled datasets, which are often unavailable. In contrast, unlabeled data is plentiful, but not easily used for evaluation. Here, we introduce Semi-Supervised Model Evaluation (SSME), a method that uses both labeled and unlabeled data to evaluate machine learning classifiers. The key idea is to estimate the joint distribution of ground truth labels and classifier scores using a semi-supervised mixture model. The semi-supervised mixture model allows SSME to learn from three sources of information: unlabeled data, multiple classifiers, and probabilistic classifier scores. Once fit, the mixture model enables estimation of any metric that is a function of classifier scores and ground truth labels (e.g., accuracy or AUC). We derive theoretical bounds on the error of these estimates, showing that estimation error decreases with the number of classifiers and the amount of unlabeled data. We present experiments in four domains where obtaining large labeled datasets is often impractical: healthcare, content moderation, molecular property prediction, and text classification. Our results demonstrate that SSME estimates performance more accurately than do competing methods, reducing error by 5.1x relative to using labeled data alone and 2.4x relative to the next best method.

SUMMARY: D-SCRIPT is a powerful tool for high-throughput inference of protein-protein interactions (PPIs), but it is expensive in time and memory to infer all PPIs for network-/proteome-level analyses. We introduce D-SCRIPT with blocked multi-GPU parallel inference, which substantially reduces memory usage across tasks and computational systems (13.8× for a representative large proteome) and enables multi-GPU parallelism. AVAILABILITY AND IMPLEMENTATION: Blocked multi-GPU parallel inference has been integrated into the main D-SCRIPT package, available at https://github.com/samsledje/D-SCRIPT. An archived version of the code at time of submission can be found at https://doi.org/10.5281/zenodo.16325182.

Molecular docking is critical to structure-based virtual screening, yet the throughput of such workflows is limited by the expensive optimization of scoring functions involved in most docking algorithms. We explore how machine learning can accelerate this process by learning a scoring function with a functional form that allows for more rapid optimization. Specifically, we define the scoring function to be the cross-correlation of multi-channel ligand and protein scalar fields parameterized by equivariant graph neural networks, enabling rapid optimization over rigid-body degrees of freedom with fast Fourier transforms. The runtime of our approach can be amortized at several levels of abstraction, and is particularly favorable for virtual screening settings with a common binding pocket. We benchmark our scoring functions on two simplified docking-related tasks: decoy pose scoring and rigid conformer docking. Our method attains similar but faster performance on crystal structures compared to the widely-used Vina and Gnina scoring functions, and is more robust on computationally predicted structures. Code is available at https://github.com/bjing2016/scalar-fields.

The biological functions of proteins often depend on dynamic structural ensembles. In this work, we develop a flow-based generative modeling approach for learning and sampling the conformational landscapes of proteins. We repurpose highly accurate single-state predictors such as AlphaFold and ESMFold and fine-tune them under a custom flow matching framework to obtain sequence-conditioned generative models of protein structure called AlphaFlow and ESMFlow. When trained and evaluated on the PDB, our method provides a superior combination of precision and diversity compared to AlphaFold with MSA subsampling. When further trained on ensembles from all-atom MD, our method accurately captures conformational flexibility, positional distributions, and higher-order ensemble observables for unseen proteins. Moreover, our method can diversify a static PDB structure with faster wall-clock convergence to certain equilibrium properties than replicate MD trajectories, demonstrating its potential as a proxy for expensive physics-based simulations. Code is available at https://github.com/bjing2016/alphaflow.

Discrete diffusion or flow models could enable faster and more controllable sequence generation than autoregressive models. We show that naive linear flow matching on the simplex is insufficient toward this goal since it suffers from discontinuities in the training target and further pathologies. To overcome this, we develop Dirichlet flow matching on the simplex based on mixtures of Dirichlet distributions as probability paths. In this framework, we derive a connection between the mixtures' scores and the flow's vector field that allows for classifier and classifier-free guidance. Further, we provide distilled Dirichlet flow matching, which enables one-step sequence generation with minimal performance hits, resulting in $O(L)$ speedups compared to autoregressive models. On complex DNA sequence generation tasks, we demonstrate superior performance compared to all baselines in distributional metrics and in achieving desired design targets for generated sequences. Finally, we show that our classifier-free guidance approach improves unconditional generation and is effective for generating DNA that satisfies design targets.

Molecular dynamics (MD) is a powerful technique for studying microscopic phenomena, but its computational cost has driven significant interest in the development of deep learning-based surrogate models. We introduce generative modeling of molecular trajectories as a paradigm for learning flexible multi-task surrogate models of MD from data. By conditioning on appropriately chosen frames of the trajectory, we show such generative models can be adapted to diverse tasks such as forward simulation, transition path sampling, and trajectory upsampling. By alternatively conditioning on part of the molecular system and inpainting the rest, we also demonstrate the first steps towards dynamics-conditioned molecular design. We validate the full set of these capabilities on tetrapeptide simulations and show preliminary results on scaling to protein monomers. Altogether, our work illustrates how generative modeling can unlock value from MD data towards diverse downstream tasks that are not straightforward to address with existing methods or even MD itself. Code is available at https://github.com/bjing2016/mdgen.

Domain-specific languages (DSLs) are able to provide intuitive high-level abstractions that are easy to work with while attaining better performance than general-purpose languages. Yet, implementing new DSLs is a burdensome task. As a result, new DSLs are usually embedded in general-purpose languages. While low-level languages like C or C++ often provide better performance as a host than high-level languages like Python, high-level languages are becoming more prevalent in many domains due to their ease and flexibility. Here, we present Codon, a domain-extensible compiler and DSL framework for high-performance DSLs with Python's syntax and semantics. Codon builds on previous work on ahead-of-time type checking and compilation of Python programs and leverages a novel intermediate representation to easily incorporate domain-specific optimizations and analyses. We showcase and evaluate several compiler extensions and DSLs for Codon targeting various domains, including bioinformatics, secure multi-party computation, block-based data compression and parallel programming, showing that Codon DSLs can provide benefits of familiar high-level languages and achieve performance typically only seen with low-level languages, thus bridging the gap between performance and usability.

Principal component analysis (PCA) is an essential algorithm for dimensionality reduction in many data science domains. We address the problem of performing a federated PCA on private data distributed among multiple data providers while ensuring data confidentiality. Our solution, SF-PCA, is an end-to-end secure system that preserves the confidentiality of both the original data and all intermediate results in a passive-adversary model with up to all-but-one colluding parties. SF-PCA jointly leverages multiparty homomorphic encryption, interactive protocols, and edge computing to efficiently interleave computations on local cleartext data with operations on collectively encrypted data. SF-PCA obtains results as accurate as non-secure centralized solutions, independently of the data distribution among the parties. It scales linearly or better with the dataset dimensions and with the number of data providers. SF-PCA is more precise than existing approaches that approximate the solution by combining local analysis results, and between 3x and 250x faster than privacy-preserving alternatives based solely on secure multiparty computation or homomorphic encryption. Our work demonstrates the practical applicability of secure and federated PCA on private distributed datasets.

MOTIVATION: High-quality computational structural models are now precomputed and available for nearly every protein in UniProt. However, the best way to leverage these models to predict which pairs of proteins interact in a high-throughput manner is not immediately clear. The recent Foldseek method of van Kempen et al. encodes the structural information of distances and angles along the protein backbone into a linear string of the same length as the protein string, using tokens from a 21-letter discretized structural alphabet (3Di). RESULTS: We show that using both the amino acid sequence and the 3Di sequence generated by Foldseek as inputs to our recent deep-learning method, Topsy-Turvy, substantially improves the performance of predicting protein-protein interactions cross-species. Thus TT3D (Topsy-Turvy 3D) presents a way to reuse all the computational effort going into producing high-quality structural models from sequence, while being sufficiently lightweight so that high-quality binary protein-protein interaction predictions across all protein pairs can be made genome-wide. AVAILABILITY AND IMPLEMENTATION: TT3D is available at https://github.com/samsledje/D-SCRIPT. An archived version of the code at time of submission can be found at https://zenodo.org/records/10037674.

SUMMARY: Computational methods to predict protein-protein interaction (PPI) typically segregate into sequence-based 'bottom-up' methods that infer properties from the characteristics of the individual protein sequences, or global 'top-down' methods that infer properties from the pattern of already known PPIs in the species of interest. However, a way to incorporate top-down insights into sequence-based bottom-up PPI prediction methods has been elusive. We thus introduce Topsy-Turvy, a method that newly synthesizes both views in a sequence-based, multi-scale, deep-learning model for PPI prediction. While Topsy-Turvy makes predictions using only sequence data, during the training phase it takes a transfer-learning approach by incorporating patterns from both global and molecular-level views of protein interaction. In a cross-species context, we show it achieves state-of-the-art performance, offering the ability to perform genome-scale, interpretable PPI prediction for non-model organisms with no existing experimental PPI data. In species with available experimental PPI data, we further present a Topsy-Turvy hybrid (TT-Hybrid) model which integrates Topsy-Turvy with a purely network-based model for link prediction that provides information about species-specific network rewiring. TT-Hybrid makes accurate predictions for both well- and sparsely-characterized proteins, outperforming both its constituent components as well as other state-of-the-art PPI prediction methods. Furthermore, running Topsy-Turvy and TT-Hybrid screens is feasible for whole genomes, and thus these methods scale to settings where other methods (e.g. AlphaFold-Multimer) might be infeasible. The generalizability, accuracy and genome-level scalability of Topsy-Turvy and TT-Hybrid unlocks a more comprehensive map of protein interaction and organization in both model and non-model organisms. AVAILABILITY AND IMPLEMENTATION: https://topsyturvy.csail.mit.edu. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Protein structure determination from cryo-EM data requires reconstructing a 3D volume (or distribution of volumes) from many noisy and randomly oriented 2D projection images. While the standard homogeneous reconstruction task aims to recover a single static structure, recently-proposed neural and non-neural methods can reconstruct distributions of structures, thereby enabling the study of protein complexes that possess intrinsic structural or conformational heterogeneity. These heterogeneous reconstruction methods, however, require fixed image poses, which are typically estimated from an upstream homogeneous reconstruction and are not guaranteed to be accurate under highly heterogeneous conditions.In this work we describe cryoDRGN2, an ab initio reconstruction algorithm, which can jointly estimate image poses and learn a neural model of a distribution of 3D structures on real heterogeneous cryo-EM data. To achieve this, we adapt search algorithms from the traditional cryo-EM literature, and describe the optimizations and design choices required to make such a search procedure computationally tractable in the neural model setting. We show that cryoDRGN2 is robust to the high noise levels of real cryo-EM images, trains faster than earlier neural methods, and achieves state-of-the-art performance on real cryo-EM datasets.

MOTIVATION: Recent advances in single-cell RNA-sequencing (scRNA-seq) technologies promise to enable the study of gene regulatory associations at unprecedented resolution in diverse cellular contexts. However, identifying unique regulatory associations observed only in specific cell types or conditions remains a key challenge; this is particularly so for rare transcriptional states whose sample sizes are too small for existing gene regulatory network inference methods to be effective. RESULTS: We present ShareNet, a Bayesian framework for boosting the accuracy of cell type-specific gene regulatory networks by propagating information across related cell types via an information sharing structure that is adaptively optimized for a given single-cell dataset. The techniques we introduce can be used with a range of general network inference algorithms to enhance the output for each cell type. We demonstrate the enhanced accuracy of our approach on three benchmark scRNA-seq datasets. We find that our inferred cell type-specific networks also uncover key changes in gene associations that underpin the complex rewiring of regulatory networks across cell types, tissues and dynamic biological processes. Our work presents a path toward extracting deeper insights about cell type-specific gene regulation in the rapidly growing compendium of scRNA-seq datasets. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online. AVAILABILITY AND IMPLEMENTATION: The code for ShareNet is available at http://sharenet.csail.mit.edu and https://github.com/alexw16/sharenet.

Levenshtein edit distance has played a central role-both past and present-in sequence alignment in particular and biological database similarity search in general. We start our review with a history of dynamic programming algorithms for computing Levenshtein distance and sequence alignments. Following, we describe how those algorithms led to heuristics employed in the most widely used software in bioinformatics, BLAST, a program to search DNA and protein databases for evolutionarily relevant similarities. More recently, the advent of modern genomic sequencing and the volume of data it generates has resulted in a return to the problem of local alignment. We conclude with how the mathematical formulation of Levenshtein distance as a metric made possible additional optimizations to similarity search in biological contexts. These modern optimizations are built around the low metric entropy and fractional dimensionality of biological databases, enabling orders of magnitude acceleration of biological similarity search.

In many natural domains, changing a small part of an entity can transform its semantics; for example, a single word change can alter the meaning of a sentence, or a single amino acid change can mutate a viral protein to escape antiviral treatment or immunity. Although identifying such mutations can be desirable (for example, therapeutic design that anticipates avenues of viral escape), the rules governing semantic change are often hard to quantify. Here, we introduce the problem of identifying mutations with a large effect on semantics, but where valid mutations are under complex constraints (for example, English grammar or biological viability), which we refer to as constrained semantic change search (CSCS). We propose an unsupervised solution based on language models that simultaneously learn continuous latent representations. We report good empirical performance on CSCS of single-word mutations to news headlines, map a continuous semantic space of viral variation, and, notably, show unprecedented zero-shot prediction of single-residue escape mutations to key influenza and HIV proteins, suggesting a productive link between modeling natural language and pathogenic evolution.

MOTIVATION: Single-cell RNA-sequencing has grown massively in scale since its inception, presenting substantial analytic and computational challenges. Even simple downstream analyses, such as dimensionality reduction and clustering, require days of runtime and hundreds of gigabytes of memory for today's largest datasets. In addition, current methods often favor common cell types, and miss salient biological features captured by small cell populations. RESULTS: Here we present Hopper, a single-cell toolkit that both speeds up the analysis of single-cell datasets and highlights their transcriptional diversity by intelligent subsampling, or sketching. Hopper realizes the optimal polynomial-time approximation of the Hausdorff distance between the full and downsampled dataset, ensuring that each cell is well-represented by some cell in the sample. Unlike prior sketching methods, Hopper adds points iteratively and allows for additional sampling from regions of interest, enabling fast and targeted multi-resolution analyses. In a dataset of over 1.3 million mouse brain cells, Hopper detects a cluster of just 64 macrophages expressing inflammatory genes (0.004% of the full dataset) from a Hopper sketch containing just 5000 cells, and several other small but biologically interesting immune cell populations invisible to analysis of the full data. On an even larger dataset consisting of ∼2 million developing mouse organ cells, we show Hopper's even representation of important cell types in small sketches, in contrast with prior sketching methods. We also introduce Treehopper, which uses spatial partitioning to speed up Hopper by orders of magnitude with minimal loss in performance. By condensing transcriptional information encoded in large datasets, Hopper and Treehopper grant the individual user with a laptop the analytic capabilities of a large consortium. AVAILABILITY AND IMPLEMENTATION: The code for Hopper is available at https://github.com/bendemeo/hopper. In addition, we have provided sketches of many of the largest single-cell datasets, available at http://hopper.csail.mit.edu.

MOTIVATION: Models for analysing and making relevant biological inferences from massive amounts of complex single-cell transcriptomic data typically require several individual data-processing steps, each with their own set of hyperparameter choices. With deep generative models one can work directly with count data, make likelihood-based model comparison, learn a latent representation of the cells and capture more of the variability in different cell populations. RESULTS: We propose a novel method based on variational auto-encoders (VAEs) for analysis of single-cell RNA sequencing (scRNA-seq) data. It avoids data preprocessing by using raw count data as input and can robustly estimate the expected gene expression levels and a latent representation for each cell. We tested several count likelihood functions and a variant of the VAE that has a priori clustering in the latent space. We show for several scRNA-seq datasets that our method outperforms recently proposed scRNA-seq methods in clustering cells and that the resulting clusters reflect cell types. AVAILABILITY AND IMPLEMENTATION: Our method, called scVAE, is implemented in Python using the TensorFlow machine-learning library, and it is freely available at https://github.com/scvae/scvae. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: The advent of in vivo automated techniques for single-cell lineaging, sequencing and analysis of gene expression has begun to dramatically increase our understanding of organismal development. We applied novel meta-analysis and visualization techniques to the EPIC single-cell-resolution developmental gene expression dataset for Caenorhabditis elegans from Bao, Murray, Waterston et al. to gain insights into regulatory mechanisms governing the timing of development. RESULTS: Our meta-analysis of the EPIC dataset revealed that a simple linear combination of the expression levels of the developmental genes is strongly correlated with the developmental age of the organism, irrespective of the cell division rate of different cell lineages. We uncovered a pattern of collective sinusoidal oscillation in gene activation, in multiple dominant frequencies and in multiple orthogonal axes of gene expression, pointing to the existence of a coordinated, multi-frequency global timing mechanism. We developed a novel method based on Fisher's Discriminant Analysis to identify gene expression weightings that maximally separate traits of interest, and found that remarkably, simple linear gene expression weightings are capable of producing sinusoidal oscillations of any frequency and phase, adding to the growing body of evidence that oscillatory mechanisms likely play an important role in the timing of development. We cross-linked EPIC with gene ontology and anatomy ontology terms, employing Fisher's Discriminant Analysis methods to identify previously unknown positive and negative genetic contributions to developmental processes and cell phenotypes. This meta-analysis demonstrates new evidence for direct linear and/or sinusoidal mechanisms regulating the timing of development. We uncovered a number of previously unknown positive and negative correlations between developmental genes and developmental processes or cell phenotypes. Our results highlight both the continued relevance of the EPIC technique, and the value of meta-analysis of previously published results. The presented analysis and visualization techniques are broadly applicable across developmental and systems biology. AVAILABILITY AND IMPLEMENTATION: Analysis software available upon request. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Representing data in hyperbolic space can effectively capture latent hierarchical relationships. To enable accurate classification of points in hyperbolic space while respecting their hyperbolic geometry, we introduce hyperbolic SVM, a hyperbolic formulation of support vector machine classifiers, and describe its theoretical connection to the Euclidean counterpart. We also generalize Euclidean kernel SVM to hyperbolic space, allowing nonlinear hyperbolic decision boundaries and providing a geometric interpretation for a certain class of indefinite kernels. Hyperbolic SVM improves classification accuracy in simulation and in real-world problems involving complex networks and word embeddings. Our work enables end-to-end analyses based on the inherent hyperbolic geometry of the data without resorting to ill-fitting tools developed for Euclidean space.

Given an image dataset, we are often interested in finding data generative factors that encode semantic content independently from pose variables such as rotation and translation. However, current disentanglement approaches do not impose any specific structure on the learned latent representations. We propose a method for explicitly disentangling image rotation and translation from other unstructured latent factors in a variational autoencoder (VAE) framework. By formulating the generative model as a function of the spatial coordinate, we make the reconstruction error differentiable with respect to latent translation and rotation parameters. This formulation allows us to train a neural network to perform approximate inference on these latent variables while explicitly constraining them to only represent rotation and translation. We demonstrate that this framework, termed spatial-VAE, effectively learns latent representations that disentangle image rotation and translation from content and improves reconstruction over standard VAEs on several benchmark datasets, including applications to modeling continuous 2-D views of proteins from single particle electron microscopy and galaxies in astronomical images.

Motivation: Vastly greater quantities of microbial genome data are being generated where environmental samples mix together the DNA from many different species. Here, we present Opal for metagenomic binning, the task of identifying the origin species of DNA sequencing reads. We introduce 'low-density' locality sensitive hashing to bioinformatics, with the addition of Gallager codes for even coverage, enabling quick and accurate metagenomic binning. Results: On public benchmarks, Opal halves the error on precision/recall (F1-score) as compared with both alignment-based and alignment-free methods for species classification. We demonstrate even more marked improvement at higher taxonomic levels, allowing for the discovery of novel lineages. Furthermore, the innovation of low-density, even-coverage hashing should itself prove an essential methodological advance as it enables the application of machine learning to other bioinformatic challenges. Availability and implementation: Full source code and datasets are available at http://opal.csail.mit.edu and https://github.com/yunwilliamyu/opal. Supplementary information: Supplementary data are available at Bioinformatics online.

The scope and scale of biological data are increasing at an exponential rate, as technologies like next-generation sequencing are becoming radically cheaper and more prevalent. Over the last two decades, the cost of sequencing a genome has dropped from $100 million to nearly $100—a factor of over 10 6 —and the amount of data to be analyzed has increased proportionally. Yet, as Moore’s Law continues to slow, computational biologists can no longer rely on computing hardware to compensate for the ever-increasing size of biological datasets. In a field where many researchers are primarily focused on biological analysis over computational optimization, the unfortunate solution to this problem is often to simply buy larger and faster machines. Here, we introduce Seq , the first language tailored specifically to bioinformatics, which marries the ease and productivity of Python with C-like performance. Seq starts with a subset of Python—and is in many cases a drop-in replacement—yet also incorporates novel bioinformatics- and computational genomics-oriented data types, language constructs and optimizations. Seq enables users to write high-level, Pythonic code without having to worry about low-level or domain-specific optimizations, and allows for the seamless expression of the algorithms, idioms and patterns found in many genomics or bioinformatics applications. We evaluated Seq on several standard computational genomics tasks like reverse complementation, k -mer manipulation, sequence pattern matching and large genomic index queries. On equivalent CPython code, Seq attains a performance improvement of up to two orders of magnitude, and a 160× improvement once domain-specific language features and optimizations are used. With parallelism, we demonstrate up to a 650× improvement. Compared to optimized C++ code, which is already difficult for most biologists to produce, Seq frequently attains up to a 2× improvement, and with shorter, cleaner code. Thus, Seq opens the door to an age of democratization of highly-optimized bioinformatics software.

Elemental balance, the property of having the same number of each type of atom on both sides of the equation, is a fundamental feature of chemical reactions. In metabolic network models, this property is typically verified on a reaction-by-reaction basis. In this paper we show how violations of elemental balance can be efficiently detected in an entire network, without the need for specifying the chemical formula of each of the metabolites, which enhances a modeler's ability to automatically verify that their model satisfies elemental balance. Our method makes use of duality theory, linear programming, and mixed integer linear programming, and runs efficiently on genome-scale metabolic networks (GSMNs). We detect elemental balance violations in 40 out of 84 metabolic network models in the BiGG database. We also identify a short list of reactions that are candidates for being elementally imbalanced. Out of these candidates, nearly half turn out to be truly imbalanced reactions, and the rest can be seen as witnesses of elemental balance violations elsewhere in the network. The majority of these violations involve a proton imbalance, a known challenge of metabolic network reconstruction. Our approach is efficient, easy to use and powerful. It can be helpful to metabolic network modelers during model verification. Our methods are fully integrated into the MONGOOSE software suite and are available at https://github.com/WGS-TB/MongooseGUI3.

Motivation: Segmental duplications (SDs) or low-copy repeats, are segments of DNA > 1 Kbp with high sequence identity that are copied to other regions of the genome. SDs are among the most important sources of evolution, a common cause of genomic structural variation and several are associated with diseases of genomic origin including schizophrenia and autism. Despite their functional importance, SDs present one of the major hurdles for de novo genome assembly due to the ambiguity they cause in building and traversing both state-of-the-art overlap-layout-consensus and de Bruijn graphs. This causes SD regions to be misassembled, collapsed into a unique representation, or completely missing from assembled reference genomes for various organisms. In turn, this missing or incorrect information limits our ability to fully understand the evolution and the architecture of the genomes. Despite the essential need to accurately characterize SDs in assemblies, there has been only one tool that was developed for this purpose, called Whole-Genome Assembly Comparison (WGAC); its primary goal is SD detection. WGAC is comprised of several steps that employ different tools and custom scripts, which makes this strategy difficult and time consuming to use. Thus there is still a need for algorithms to characterize within-assembly SDs quickly, accurately, and in a user friendly manner. Results: Here we introduce SEgmental Duplication Evaluation Framework (SEDEF) to rapidly detect SDs through sophisticated filtering strategies based on Jaccard similarity and local chaining. We show that SEDEF accurately detects SDs while maintaining substantial speed up over WGAC that translates into practical run times of minutes instead of weeks. Notably, our algorithm captures up to 25% 'pairwise error' between segments, whereas previous studies focused on only 10%, allowing us to more deeply track the evolutionary history of the genome. Availability and implementation: SEDEF is available at https://github.com/vpc-ccg/sedef.

The recent editorial by Dr Longo and Dr Drazen in the New England Journal of Medicine (Longo and Drazen, 2016) has stirred up quite a bit of controversy. As Executive Officers of the International Society of Computational Biology, Inc. (ISCB), we express our deep concern about the restrictive and potentially damaging opinions voiced in this editorial, and while ISCB works to write a detailed response, we felt it necessary to promptly address the editorial with this reaction. Although some of the concerns voiced by the authors of the editorial are worth considering, large parts of the statement purport an obsolete view of hegemony over data that is neither in line with today’s spirit of open access nor furthering an atmosphere where the potential of data can be fully realized. ISCB acknowledges that the additional comment on the editorial (Drazen, 2016) eases some of the polemics unfortunately without addressing some of the core issues. We still feel, however, that we need to contrast the opinion voiced in the editorial with what we consider the axioms of our scientific society, statements that lead into a fruitful future of data-driven science: Data produced with public money should be public in benefit of the science and society Restrictions on the use of public data hamper science and slow progress Open data is the best way to combat fraud and misinterpretations Current large data collections proceed from many sources, are continually accumulated, and require a variety of analytical approaches. Data generation and data analysis overlap in time and are continually updated with new data sets produced by new techniques and new analysis methodologies. Furthermore, in many cases current science functions in consortia in which scientists collaborate toward common goals while preserving their own scientific objectives. Dividing scientists into data providers and data analysts is simplistic and gives a misleading impression of the actual state of biological and biomedical science. ISCB very much supports collaboration between disciplines, including experimental and clinical as well as bioinformatics, as the best way forward to address complex biological problems. But this collaboration cannot be based on imposed restrictions to data access and cannot be contained in professional silos. (The use of expressions such as ‘research parasites’ clearly does not help.) Many bio-communities have made significant progress by endorsing open data policies and, gratefully, public funding agencies have connected to the spirit that they are distributing taxpayers’ money to science and that, therefore, the data that are generated in the course belong to the public. It is, perhaps, natural that some areas of biomedical research are slow in adopting these policies. History and the confidential nature of the relevant data are surely among the reasons. However, in our opinion data hegemony is another, a reason that has to be overcome. The sooner these barriers to progress are removed the sooner the patients will benefit from the current flourishing of biomedical research. Conflict of Interest: none declared.

2017 marks the second year of the ISCB Innovator Award, which recognizes an ISCB scientist who is within two decades of having completed his or her graduate degree and has consistently made outstanding contributions to the field. The 2017 winner is Dr. Aviv Regev, Professor of Biology at the Massachusetts Institute of Technology (MIT), a Core Member and Chair of the Faculty of the Broad Institute of MIT and Harvard, and an HHMI Investigator. Regev will receive her award and deliver a keynote address during ISMB/ECCB 2017 in Prague, Czech Republic (July 21–July 25, 2017). Aviv Regev first pursued her studies in a unique interdisciplinary program at Tel Aviv University, where she planned to focus on math and computer science (https://www.hhmi.org/scientists/aviv-regev). But she discovered her interest in biology in the classroom of evolutionary biologist Eva Jablonka. Regev said, ‘I found biology because of her—in my first year as an undergrad, I took a genetics course with her in what is now called the ‘flipped classroom’ style. It was all abstract and inferential, and I was hooked’. Before starting her PhD thesis at Tel Aviv University, Regev began to really think about cells as computers, particularly how they are comprised of circuits. Regev’s deep interest in this concept started at a conference where new approaches for modeling concurrent computation were featured, and she immediately considered this as a way to model cell circuitry. She was able to develop her ideas into a PhD project under the mentorship of Udi Shapiro and Eva Jablonka, and she recalled, ‘No one was working on this type of project. I did, however, have the great fortune to find Udi, who listened to my idea. He thought it was important. He didn’t want to work on it himself—but he wanted me to be able to work on it’. Regev completed her PhD in 2002 and was selected to be a Bauer Fellow at the Center for Genomics Research at Harvard University, which gave her an intellectual community, as well as freedom and funding to build a small independent research group. She continued to pursue her interest in modeling cell circuits using gene expression and genomic data, and she developed with her colleagues several widely used algorithms and computational tools, including Module Networks and Synergy. She received early support from Andrew Murray at Harvard University, who shared Regev’s view that it was critical to deeply understand both theory and experiments. In 2006, Regev was given a joint faculty appointment at MIT and the Broad Institute, and she started applying her cell circuit modeling algorithms to understanding different cell types, particularly cells of the immune system. Once again, Regev struck out on an independent line of research. She recalled, ‘Many people were not focused on circuits. But that was OK. I wanted to build and be part of a community that would open a new direction’. Eric Lander at Broad—a longtime supporter of female and young scientists with leadership potential—stood behind and supported Regev’s independent scientific vision at this critical point in her career. Regev’s independent research program has blossomed since she founded her lab, and she has applied her interest in how cellular circuits function and rewire to a wide range of biological questions, including how immune cells rapidly respond and differentiate, how hematopoietic stem cells develop into different blood cells and how evolutionary changes occur over millions of years. She is both a computational biologist with keen instincts about how to extract insight from data, and an experimental biologist with the ability to create new methods and deploy cutting edge technology to address fundamental questions. Regev continues to be drawn to seemingly intractable problems, such as biological scenarios with a massive number of hypothetical combinations or interactions, and making them into manageable problems by using sampling approaches. Her work on cells of the immune system reflects this focus, and she recalls one of her most unexpected findings emerged in 2012 while working with collaborators on applying single-cell RNA-seq to the analysis of dendritic cells. In contrast to present day technology, which enables the profiling of thousands of cells quickly and cheaply, this study only looked at 18 cells and required a tremendous effort. Regev recalled, ‘What we found was surprising in two ways. First, we were examining just one cell type which we thought was well-defined, so we did not expect to find major differences in gene expression between the cells—yet we saw 1000-fold differences, from which we could recover regulatory molecules that accounted for this variation. Second, we discovered surprising patterns in alternative splicing—some cells preferentially used one isoform, others used another. We had been expecting the cells to use both. This added up to a bigger surprise: we weren’t really looking at one group of cells. We were looking at two subgroups, which we now know represent different developmental programs. A great deal of my work now focuses on understanding heterogeneity of this type—defining and understanding cells at a much higher resolution than we could before’. Regev has passed along her love of science through her mentorship of postdocs, graduate students, and undergraduates, and outside of the lab she has maintained an intense teaching load and worked to overhaul the undergraduate genetics course to include quantitative content. She is grateful to her mentors who gave her freedom to pursue her own scientific interests and this has guided her style of mentorship. She said, ‘Today, when I see a person with an idea, I don’t care about career stage—maybe they’re a grad student or an undergrad; maybe they are a seasoned staff scientist. I care about who they are. Do they show the seeds of independence, vision and leadership? And what is their idea? If it’s challenging in entirely new ways, and can transform the world, it should be grown. As I mentor my students and postdocs, I try to let them spread their own wings—to be their colleague and collaborator’. At Broad, Regev was recently appointed Chair of the Faculty, and in this role she has been focusing on initiatives to strengthen and build communities around computational biology and advance software engineering approaches to biological data analysis. She has served the greater computational biology community in many ways through work on numerous advisory boards, journal editorial boards and program committees for conferences. Regev has been a reviewing editor for eLife since its inception, and more recently a senior editor with a major responsibility for computational biology, genomics and theory papers. Regev is gratified by her selection for the 2017 ISCB Innovator Award, and she said, ‘Biology is such a data science now, and ISCB is the community that made that happen—so it is especially exciting and gratifying to be receiving such an honor from peers in this community’.

computational biology and bioinformatics through their research, service and education work.

The International Society for Computational Biology (ISCB) each year recognizes the achievements of an early to mid-career scientist with the Overton Prize. This prize honors the untimely death of Dr. G. Christian Overton, an admired computational biologist and founding ISCB Board member. Winners of the Overton Prize are independent investigators who are in the early to middle phases of their careers and are selected because of their significant contributions to computational biology through research, teaching and service. ISCB is pleased to recognize Dr. Christoph Bock, Principal Investigator at the CeMM Research Center for Molecular Medicine of the Austrian Academy of Sciences in Vienna, Austria, as the 2017 winner of the Overton Prize. Bock will be presenting a keynote presentation at the 2017 International Conference on Intelligent Systems for Molecular Biology/European Conference on Computational Biology (ISMB/ECCB) in Prague, Czech Republic, being held during July 21–25, 2017. Christoph Bock’s scientific curiosity was nurtured from a young age. His parents were math and science teachers, and while they did not push him to pursue these areas of study, he sees how this intellectually stimulating environment cultivated his natural curiosity and provided a critical foundation to his career as a scientist. Bock started exploring computer programming from the age of 12, and he realizes in retrospect how learning to code was a valuable tool for practicing problem solving and scientific thinking. During high school, Bock specialized in physics and math. His undergraduate studies at the University of Mannheim focused on computer science and business information systems, emphasizing machine learning and artificial intelligence. Toward the end of his studies, Bock yearned to tackle questions with broader relevance than the ‘toy problems’ he encountered in his course work. Bock recalled, ‘Human biology seemed the biggest challenge and also most societally relevant. I was lucky that Jürgen Hesser offered a bioinformatics lecture and agreed to supervise my Master’s thesis at the University of Mannheim’. His Master’s research work focused on protein structure prediction and homology modeling. Bock pursued his PhD studies in bioinformatics under the supervision of Thomas Lengauer at the Max Planck Institute for Informatics, studying epigenetic regulation of the genome. ‘Moving into bioinformatics and epigenetics, I had to catch up on a lot of important biological knowledge’, Bock recalled. ‘Reading papers and collaborating was key, but it also helped that my research focused on a field that was quite young, with ample opportunity to try out something new’. He attributes much of his bioinformatics training to the time spent in the research group of Thomas Lengauer, and he has been grateful for his mentor’s continued support and collaboration throughout his early career. Bock also acknowledges the important guidance and feedback on his research provided by Jörn Walter, who co-supervised his PhD dissertation and introduced Bock to the international epigenetics community. Bock’s first encounter with epigenetics data transformed his scientific career path, and he has been one of the first bioinformaticians that dedicated their work to epigenetic data. ‘When I started my PhD studies in 2004, the largest epigenetic dataset consisted of just over 100 data points, and one of my first papers established epigenome prediction as a means of inferring what was still very difficult and costly to measure experimentally’. In the following years, next-generation sequencing transformed the field, and it became possible to collect several billion data points in a single epigenome mapping experiment. This development created a strong demand for bioinformatic methods. ‘Working at the forefront of the epigenome revolution has been the highlight of my scientific research so far. But the most exciting times may still be ahead as epigenome research is starting to become broadly relevant for medicine, and I am looking forward to contributing to this development’. Bock developed several software tools as part of his PhD, including BiQ Analyzer for processing DNA methylation data and EpiGRAPH for analyzing and predicting epigenome profiles in their genomic context. Bock went on to pursue postdoctoral studies under Alexander Meissner at the Broad Institute. There, Bock was exposed to the world of wet-lab biology, and he discovered the thrill and power of jointly developing new laboratory techniques and computational methods, which he used to study the epigenome of pluripotent and hematopoietic stem cells. In 2012, Bock started his own research group at CeMM, an institute dedicated to advancing precision medicine through basic and translational research. He was hired by Giulio Superti-Furga, Scientific Director of CeMM, who, as Bock said, ‘Provided ample encouragement and let me try things that were initially quite far outside of my comfort zone, such as starting a wet lab and leading a next generation sequencing technology platform’. Bock has thrived at CeMM, where he has been able to work with many passionate researchers within the institute and at the neighboring Medical University of Vienna. At CeMM, Bock has also developed his personal style of being a PI and mentor, acting as a catalyst of ideas and projects for an interdisciplinary team. He explained, ‘Our lab combines computational and wet-lab biology on roughly equal terms, with a good dose of technology development – including single-cell sequencing, CRISPR, epigenome editing, machine learning, and more. There is also an extensive network of collaborations, ranging from fundamental biology to immediate clinical applications in the area of personalized and precision medicine. It is a great privilege to work with such an interdisciplinary and creative group of smart people’. Bock considers the success of his students and postdocs as a key measure of his achievement as a PI. He explained, ‘I work hard to maintain an environment in which every group member can build a great CV and learns what he or she needs to advance in their scientific career. So far, we have a 100% success rate of postdocs moving on to attractive PI jobs, which is great for young lab. But it is clear that helping others succeed in their career is not an easy task, and you need to create room for success and failure, and a safety net that encourages risk taking’. Bock is still excited about epigenetics and what it can teach us about a cell’s past, present and future. He hopes that epigenomic data can be used to understand the regulatory logic of cells and to determine what goes awry in diseases like cancer. Bock said, ‘We are pursuing an engineering-inspired "build it to understand it" approach to cancer biology, where we combine CRISPR epigenome editing and computationally designed drug combinations to rationally reprogram normal cells into cancer cells and vice versa. Building upon a breakthrough technology for pooled CRISPR screening with single-cell sequencing, We seek to decipher complex biological pathways and gene regulatory networks in high throughput, in order to overcome the classical "one gene, one postdoc" paradigm of functional (epi-)genomics’. Bock is deeply gratified to be honored with the Overton Prize, especially since he will receive his award this year in Prague. He said, ‘Ten years ago, I attended ISMB 2007 in Vienna – one of the first conferences where I presented my PhD project on epigenome prediction. That year, Eran Segal won the Overton Prize, and his keynote lecture about DNA’s regulatory code reinforced my interest in understanding the role of epigenome regulation in biology and medicine. ISMB 2007 was also my first time in Vienna, and the great impressions from that visit surely contributed to the fact that a job ad from Vienna caught my attention a few years later. This year, it will be my pleasure to give the Overton Prize lecture at ISMB 2017 in Prague, ten years and just a few hundred kilometers away from a truly career-defining ISMB 2007’.

The Outstanding Contributions to ISCB Award was launched in 2015 to recognize individuals who have made lasting and valuable contributions to the Society through their leadership, service, and educational work, or a combination of these areas. Fran Lewitter is the 2017 winner of the Outstanding Contributions to ISCB Award and will be recognized at the 2017 Intelligent Systems for Molecular Biology (ISMB)/European Conference on Computational Biology meeting in Prague, Czech Republic being held from July 21 to 25, 2017. Fran Lewitter completed her PhD in Human Genetics and Statistical Genetics at the University of Colorado Boulder. After completing postdoctoral work in Genetic Epidemiology at Harvard Medical School, she worked on the first 5 years of the GenBank project. Lewitter then worked in the Biology Department at Brandeis University in a number of capacities, including supporting molecular biology computing and being involved with their Genetic Counseling program. In 1994, she joined the Whitehead Institute for Biomedical Research in Cambridge, MA, to run a bioinformatics core facility. For 20 years, she worked with and trained basic biomedical researchers who were doing sequencing or were using bioinformatics to gain a deeper understanding of different biological questions. She was later named the Founding Director of Bioinformatics and Research Computing and was given a larger staff as the demand for bioinformatics information grew in the late 1990s and early 2000s. Lewitter’s first encounter with ISCB occurred when she attended ISMB 2001 in Copenhagen, Denmark, followed by a 1-day satellite meeting, Workshop on Education in Bioinformatics (WEB). At the time, Whitehead did not have a large bioinformatics community, and she was in search of peers who were running bioinformatics core facilities and teaching bioinformatics to biologists. ‘One thing that attracted me to go [to ISMB] was the one day workshop on education and bioinformatics, since I was so heavily involved in educating people. I went to every meeting since then’. At ISMB 2002 in Edmonton, Lewitter helped organize an informal gathering of bioinformatics core facility managers, and this unique gathering spurred the organization of a mailing list, which became an invaluable resource for Lewitter and her peers as they faced challenges and questions unique to running a core facility. Since her early encounters with ISCB, Lewitter has become a tireless advocate for bioinformatics education and training on behalf of ISCB. As a core facility director, she has offered her unique academic perspective and voice through her service on the ISCB Education Committee and as a member of the Board from 2008 to 2017. Lewitter recognized the growing demand for bioinformatics training early in her involvement with ISCB, and she worked to strengthen ISCB’s role in supporting bioinformatics education and training by promoting the inclusion of bioinformatics education content in the main conference programs. To this end, she has organized Workshops on Education in Bioinformatics (WEB) at ISMB meetings since 2009, and she has helped build ISCB community activities including the CoBE COSI (Computational Biology Education Community of Special Interest). Lewitter’s leadership of the ISCB Education Committee helped unite the global bioinformatics education community through shared objectives and brought greater awareness of the committee’s work through tutorials and training opportunities offered at ISCB conferences. Lewitter recognizes that one of the most critical aspects of training is ‘to introduce biologists to bioinformatics vocabulary whether or not they would be using the primary bioinformatics tools’. This fosters better collaborations between bioinformatics experts and bench scientists and is necessary to facilitate the ongoing integration of bioinformatics into all aspects of biology. Lewitter has been instrumental in bringing together ISCB and GOBLET (the Global Organization for Bioinformatics Learning, Education and Training) and coordinating activities by which these two organizations work together to further bioinformatics training on a global scale. She has advocated for the development and maintenance of bioinformatics education resources on ISCB webpages, and these electronic resources are valuable tools used by the global bioinformatics education community. Lewitter has valued her membership in ISCB for providing her opportunities to ‘get to know innovative people’. She has especially appreciated meeting other core facility directors and managers. Lewitter said, ‘It’s gratifying to hear I am doing the right thing, or other people have ideas that can help me or I can help them. It is good to talk to other people about issues of running a core facility, what courses to teach or what tools are the best to teach?’ Despite having retired from Whitehead Institute 3 years ago, she enjoys her continued involvement in ISCB activities. She is also heartened by the rising generation of ISCB members who are involved with the ISCB Student Council. Lewitter hopes ISCB will continue to grow and thrive and is grateful for being recognized for her steadfast efforts to promote and further bioinformatics education.

MOTIVATION: Protein complexes are one of the keys to studying the behavior of a cell system. Many biological functions are carried out by protein complexes. During the past decade, the main strategy used to identify protein complexes from high-throughput network data has been to extract near-cliques or highly dense subgraphs from a single protein-protein interaction (PPI) network. Although experimental PPI data have increased significantly over recent years, most PPI networks still have many false positive interactions and false negative edge loss due to the limitations of high-throughput experiments. In particular, the false negative errors restrict the search space of such conventional protein complex identification approaches. Thus, it has become one of the most challenging tasks in systems biology to automatically identify protein complexes. RESULTS: In this study, we propose a new algorithm, NEOComplex ( NE CC- and O rtholog-based Complex identification by multiple network alignment), which integrates functional orthology information that can be obtained from different types of multiple network alignment (MNA) approaches to expand the search space of protein complex detection. As part of our approach, we also define a new edge clustering coefficient (NECC) to assign weights to interaction edges in PPI networks so that protein complexes can be identified more accurately. The NECC is based on the intuition that there is functional information captured in the common neighbors of the common neighbors as well. Our results show that our algorithm outperforms well-known protein complex identification tools in a balance between precision and recall on three eukaryotic species: human, yeast, and fly. As a result of MNAs of the species, the proposed approach can tolerate edge loss in PPI networks and even discover sparse protein complexes which have traditionally been a challenge to predict. AVAILABILITY AND IMPLEMENTATION: http://acolab.ie.nthu.edu.tw/bionetwork/NEOComplex. CONTACT: [email protected] or [email protected]. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

selected Pevzner as the 2017 winner.Pevzner will receive his award and deliver a keynote address at the 2017 Intelligent Systems for Molecular Biology-European Conference on Computational Biology joint meeting (ISMB/ECCB 2017) held in Prague, Czech Republic, from July 21-25, 2017.ISMB/ECCB is a biennial joint meeting that brings together leading scientists in computational biology and bioinformatics from around the globe.

The Outstanding Contributions to ISCB Award was launched in 2015 to recognize individuals who have made lasting and valuable contributions to the society through their leadership, service, and educational work or a combination of these areas.Fran Lewitter is the 2017 winner of the Outstanding Contributions to ISCB Award and will be recognized at the 2017 Intelligent Systems for Molecular Biology (ISMB)/European Conference on Computational Biology meeting in Prague, Czech Republic, which will be held from July 21-25, 2017.Fran Lewitter (Fig 1) completed her PhD in human genetics and statistical genetics at the University of Colorado Boulder.After completing postdoctoral work in genetic epidemiology at Harvard Medical School, she worked on the first 5 years of the GenBank project.Lewitter then worked in the biology department at Brandeis University in a number of capacities, including supporting molecular biology computing and being involved with their genetic counseling program.In 1994, she joined the Whitehead Institute for Biomedical Research in Cambridge, Massachusetts, to run a bioinformatics core facility.For 20 years, she worked with and trained basic biomedical researchers who were doing sequencing or were using bioinformatics to gain a deeper understanding of different biological questions.She was later named the Founding Director of Bioinformatics and Research Computing and was given a larger staff as the demand for bioinformatics information grew in the late 1990s and early 2000s.Lewitter's first encounter with ISCB occurred when she attended ISMB 2001 in Copenhagen, Denmark, followed by a one-day satellite meeting, Workshop on Education in Bioinformatics (WEB).At the time, Whitehead did not have a large bioinformatics community, and she was in search of peers who were running bioinformatics core facilities and teaching bioinformatics to biologists."One thing that attracted me to go [to ISMB] was the one-day

The International Society for Computational Biology (ISCB) each year recognizes the achievements of an early-to mid-career scientist with the Overton Prize.This prize honors the untimely death of Dr. G. Christian Overton, an admired computational biologist and founding ISCB board member.Winners of the Overton Prize are independent investigators

Aviv Regev: Seeing cells as life's smallest circuitsAviv Regev (Fig 1) first pursued her studies in a unique interdisciplinary program at Tel Aviv University, where she planned to focus on math and computer science (https://www.hhmi. org/scientists/aviv-regev).However, she discovered her interest in biology in the classroom of evolutionary biologist Eva Jablonka.Regev said, "I found biology because of her-in my first year as an undergrad, I took a genetics course with her in what is now called the 'flipped classroom' style.It was all abstract and inferential, and I was hooked."Before starting her

This paper provides the specification and an initial validation of an evaluation framework for the comparison of lossy compressors of genome sequencing quality values. The goal is to define reference data, test sets, tools and metrics that shall be used to evaluate the impact of lossy compression of quality values on human genome variant calling. The functionality of the framework is validated referring to two state-of-the-art genomic compressors. This work has been spurred by the current activity within the ISO/IEC SC29/WG11 technical committee (a.k.a. MPEG), which is investigating the possibility of starting a standardization activity for genomic information representation.

MOTIVATION: Protein-RNA interactions, which play vital roles in many processes, are mediated through both RNA sequence and structure. CLIP-based methods, which measure protein-RNA binding in vivo, suffer from experimental noise and systematic biases, whereas in vitro experiments capture a clearer signal of protein RNA-binding. Among them, RNAcompete provides binding affinities of a specific protein to more than 240 000 unstructured RNA probes in one experiment. The computational challenge is to infer RNA structure- and sequence-based binding models from these data. The state-of-the-art in sequence models, Deepbind, does not model structural preferences. RNAcontext models both sequence and structure preferences, but is outperformed by GraphProt. Unfortunately, GraphProt cannot detect structural preferences from RNAcompete data due to the unstructured nature of the data, as noted by its developers, nor can it be tractably run on the full RNACompete dataset. RESULTS: We develop RCK, an efficient, scalable algorithm that infers both sequence and structure preferences based on a new k-mer based model. Remarkably, even though RNAcompete data is designed to be unstructured, RCK can still learn structural preferences from it. RCK significantly outperforms both RNAcontext and Deepbind in in vitro binding prediction for 244 RNAcompete experiments. Moreover, RCK is also faster and uses less memory, which enables scalability. While currently on par with existing methods in in vivo binding prediction on a small scale test, we demonstrate that RCK will increasingly benefit from experimentally measured RNA structure profiles as compared to computationally predicted ones. By running RCK on the entire RNAcompete dataset, we generate and provide as a resource a set of protein-RNA structure-based models on an unprecedented scale. AVAILABILITY AND IMPLEMENTATION: Software and models are freely available at http://rck.csail.mit.edu/ CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: As the volume of next-generation sequencing (NGS) data increases, faster algorithms become necessary. Although speeding up individual components of a sequence analysis pipeline (e.g. read mapping) can reduce the computational cost of analysis, such approaches do not take full advantage of the particulars of a given problem. One problem of great interest, genotyping a known set of variants (e.g. dbSNP or Affymetrix SNPs), is important for characterization of known genetic traits and causative disease variants within an individual, as well as the initial stage of many ancestral and population genomic pipelines (e.g. GWAS). RESULTS: We introduce lightweight assignment of variant alleles (LAVA), an NGS-based genotyping algorithm for a given set of SNP loci, which takes advantage of the fact that approximate matching of mid-size k-mers (with k = 32) can typically uniquely identify loci in the human genome without full read alignment. LAVA accurately calls the vast majority of SNPs in dbSNP and Affymetrix's Genome-Wide Human SNP Array 6.0 up to about an order of magnitude faster than standard NGS genotyping pipelines. For Affymetrix SNPs, LAVA has significantly higher SNP calling accuracy than existing pipelines while using as low as ∼5 GB of RAM. As such, LAVA represents a scalable computational method for population-level genotyping studies as well as a flexible NGS-based replacement for SNP arrays. AVAILABILITY AND IMPLEMENTATION: LAVA software is available at http://lava.csail.mit.edu CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: As genomics moves into the clinic, there has been much interest in using this medical data for research. At the same time the use of such data raises many privacy concerns. These circumstances have led to the development of various methods to perform genome-wide association studies (GWAS) on patient records while ensuring privacy. In particular, there has been growing interest in applying differentially private techniques to this challenge. Unfortunately, up until now all methods for finding high scoring SNPs in a differentially private manner have had major drawbacks in terms of either accuracy or computational efficiency. RESULTS: Here we overcome these limitations with a substantially modified version of the neighbor distance method for performing differentially private GWAS, and thus are able to produce a more viable mechanism. Specifically, we use input perturbation and an adaptive boundary method to overcome accuracy issues. We also design and implement a convex analysis based algorithm to calculate the neighbor distance for each SNP in constant time, overcoming the major computational bottleneck in the neighbor distance method. It is our hope that methods such as ours will pave the way for more widespread use of patient data in biomedical research. AVAILABILITY AND IMPLEMENTATION: A python implementation is available at http://groups.csail.mit.edu/cb/DiffPriv/ CONTACT: [email protected] SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

This message is a response from the ISCB in light of the recent the New England Journal of Medicine (NEJM) editorial around data sharing.

UNLABELLED: Speed is of the essence in combating Ebola; thus, computational approaches should form a significant component of Ebola research. As for the development of any modern drug, computational biology is uniquely positioned to contribute through comparative analysis of the genome sequences of Ebola strains and three-dimensional protein modeling. Other computational approaches to Ebola may include large-scale docking studies of Ebola proteins with human proteins and with small-molecule libraries, computational modeling of the spread of the virus, computational mining of the Ebola literature and creation of a curated Ebola database. Taken together, such computational efforts could significantly accelerate traditional scientific approaches. In recognition of the need for important and immediate solutions from the field of computational biology against Ebola, the International Society for Computational Biology (ISCB) announces a prize for an important computational advance in fighting the Ebola virus. ISCB will confer the ISCB Fight against Ebola Award, along with a prize of US$2000, at its July 2016 annual meeting (ISCB Intelligent Systems for Molecular Biology 2016, Orlando, FL). CONTACT: [email protected] or [email protected].

MOTIVATION: Systematically predicting gene (or protein) function based on molecular interaction networks has become an important tool in refining and enhancing the existing annotation catalogs, such as the Gene Ontology (GO) database. However, functional labels with only a few (<10) annotated genes, which constitute about half of the GO terms in yeast, mouse and human, pose a unique challenge in that any prediction algorithm that independently considers each label faces a paucity of information and thus is prone to capture non-generalizable patterns in the data, resulting in poor predictive performance. There exist a variety of algorithms for function prediction, but none properly address this 'overfitting' issue of sparsely annotated functions, or do so in a manner scalable to tens of thousands of functions in the human catalog. RESULTS: We propose a novel function prediction algorithm, clusDCA, which transfers information between similar functional labels to alleviate the overfitting problem for sparsely annotated functions. Our method is scalable to datasets with a large number of annotations. In a cross-validation experiment in yeast, mouse and human, our method greatly outperformed previous state-of-the-art function prediction algorithms in predicting sparsely annotated functions, without sacrificing the performance on labels with sufficient information. Furthermore, we show that our method can accurately predict genes that will be assigned a functional label that has no known annotations, based only on the ontology graph structure and genes associated with other labels, which further suggests that our method effectively utilizes the similarity between gene functions. AVAILABILITY AND IMPLEMENTATION: https://github.com/wangshenguiuc/clusDCA.

Speed is of the essence in combating Ebola; thus, computational approaches should form a significant component of Ebola research.As for the development of any modern drug, computational biology is uniquely positioned to contribute through comparative analysis of the genome sequences of Ebola strains as well as 3-D protein modeling.Other computational approaches to Ebola may include large-scale docking studies of Ebola proteins with human proteins and with small-molecule libraries, computational modeling of the spread of the virus, computational mining of the Ebola literature, and creation of a curated Ebola database.Taken together, such computational efforts could significantly accelerate traditional scientific approaches.In recognition of the need for important and immediate solutions from the field of computational biology against Ebola, the International Society for Computational Biology (ISCB) announces a prize for an important computational advance in fighting the Ebola virus.ISCB will confer the ISCB Fight against Ebola Award, along with a prize of US$2,000, at its July 2016 annual meeting (ISCB Intelligent Systems for Molecular Biology [ISMB] 2016, Orlando, Florida).

As the more recent next-generation sequencing (NGS) technologies provide longer read sequences, the use of sequencing datasets for complete haplotype phasing is fast becoming a reality, allowing haplotype reconstruction of a single sequenced genome. Nearly all previous haplotype reconstruction studies have focused on diploid genomes and are rarely scalable to genomes with higher ploidy. Yet computational investigations into polyploid genomes carry great importance, impacting plant, yeast and fish genomics, as well as the studies of the evolution of modern-day eukaryotes and (epi)genetic interactions between copies of genes. In this paper, we describe a novel maximum-likelihood estimation framework, HapTree, for polyploid haplotype assembly of an individual genome using NGS read datasets. We evaluate the performance of HapTree on simulated polyploid sequencing read data modeled after Illumina sequencing technologies. For triploid and higher ploidy genomes, we demonstrate that HapTree substantially improves haplotype assembly accuracy and efficiency over the state-of-the-art; moreover, HapTree is the first scalable polyplotyping method for higher ploidy. As a proof of concept, we also test our method on real sequencing data from NA12878 (1000 Genomes Project) and evaluate the quality of assembled haplotypes with respect to trio-based diplotype annotation as the ground truth. The results indicate that HapTree significantly improves the switch accuracy within phased haplotype blocks as compared to existing haplotype assembly methods, while producing comparable minimum error correction (MEC) values. A summary of this paper appears in the proceedings of the RECOMB 2014 conference, April 2-5.

MOTIVATION: The global alignment of protein interaction networks is a widely studied problem. It is an important first step in understanding the relationship between the proteins in different species and identifying functional orthologs. Furthermore, it can provide useful insights into the species' evolution. RESULTS: We propose a novel algorithm, PISwap, for optimizing global pairwise alignments of protein interaction networks, based on a local optimization heuristic that has previously demonstrated its effectiveness for a variety of other intractable problems. PISwap can begin with different types of network alignment approaches and then iteratively adjust the initial alignments by incorporating network topology information, trading it off for sequence information. In practice, our algorithm efficiently refines other well-studied alignment techniques with almost no additional time cost. We also show the robustness of the algorithm to noise in protein interaction data. In addition, the flexible nature of this algorithm makes it suitable for different applications of network alignment. This algorithm can yield interesting insights into the evolutionary dynamics of related species. AVAILABILITY: Our software is freely available for non-commercial purposes from our Web site, http://piswap.csail.mit.edu/. CONTACT: [email protected] or [email protected]. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: The exponential growth of protein sequence databases has increasingly made the fundamental question of searching for homologs a computational bottleneck. The amount of unique data, however, is not growing nearly as fast; we can exploit this fact to greatly accelerate homology search. Acceleration of programs in the popular PSI/DELTA-BLAST family of tools will not only speed-up homology search directly but also the huge collection of other current programs that primarily interact with large protein databases via precisely these tools. RESULTS: We introduce a suite of homology search tools, powered by compressively accelerated protein BLAST (CaBLASTP), which are significantly faster than and comparably accurate with all known state-of-the-art tools, including HHblits, DELTA-BLAST and PSI-BLAST. Further, our tools are implemented in a manner that allows direct substitution into existing analysis pipelines. The key idea is that we introduce a local similarity-based compression scheme that allows us to operate directly on the compressed data. Importantly, CaBLASTP's runtime scales almost linearly in the amount of unique data, as opposed to current BLASTP variants, which scale linearly in the size of the full protein database being searched. Our compressive algorithms will speed-up many tasks, such as protein structure prediction and orthology mapping, which rely heavily on homology search. AVAILABILITY: CaBLASTP is available under the GNU Public License at http://cablastp.csail.mit.edu/ CONTACT: [email protected].

BACKGROUND: In the last decade, a considerable amount of research has been devoted to investigating the phylogenetic properties of organisms from a systems-level perspective. Most studies have focused on the classification of organisms based on structural comparison and local alignment of metabolic pathways. In contrast, global alignment of multiple metabolic networks complements sequence-based phylogenetic analyses and provides more comprehensive information. RESULTS: We explored the phylogenetic relationships between microorganisms through global alignment of multiple metabolic networks. The proposed approach integrates sequence homology data with topological information of metabolic networks. In general, compared to recent studies, the resulting trees reflect the living style of organisms as well as classical taxa. Moreover, for phylogenetically closely related organisms, the classification results are consistent with specific metabolic characteristics, such as the light-harvesting systems, fermentation types, and sources of electrons in photosynthesis. CONCLUSIONS: We demonstrate the usefulness of global alignment of multiple metabolic networks to infer phylogenetic relationships between species. In addition, our exhaustive analysis of microbial metabolic pathways reveals differences in metabolic features between phylogenetically closely related organisms. With the ongoing increase in the number of genomic sequences and metabolic annotations, the proposed approach will help identify phenotypic variations that may not be apparent based solely on sequence-based classification.

BACKGROUND: Comprehensive protein-protein interaction (PPI) maps are a powerful resource for uncovering the molecular basis of genetic interactions and providing mechanistic insights. Over the past decade, high-throughput experimental techniques have been developed to generate PPI maps at proteome scale, first using yeast two-hybrid approaches and more recently via affinity purification combined with mass spectrometry (AP-MS). Unfortunately, data from both protocols are prone to both high false positive and false negative rates. To address these issues, many methods have been developed to post-process raw PPI data. However, with few exceptions, these methods only analyze binary experimental data (in which each potential interaction tested is deemed either observed or unobserved), neglecting quantitative information available from AP-MS such as spectral counts. RESULTS: We propose a novel method for incorporating quantitative information from AP-MS data into existing PPI inference methods that analyze binary interaction data. Our approach introduces a probabilistic framework that models the statistical noise inherent in observations of co-purifications. Using a sampling-based approach, we model the uncertainty of interactions with low spectral counts by generating an ensemble of possible alternative experimental outcomes. We then apply the existing method of choice to each alternative outcome and aggregate results over the ensemble. We validate our approach on three recent AP-MS data sets and demonstrate performance comparable to or better than state-of-the-art methods. Additionally, we provide an in-depth discussion comparing the theoretical bases of existing approaches and identify common aspects that may be key to their performance. CONCLUSIONS: Our sampling framework extends the existing body of work on PPI analysis using binary interaction data to apply to the richer quantitative data now commonly available through AP-MS assays. This framework is quite general, and many enhancements are likely possible. Fruitful future directions may include investigating more sophisticated schemes for converting spectral counts to probabilities and applying the framework to direct protein complex prediction methods.

This special issue comprises the papers accepted for presentation at the 20th Annual International Conference on Intelligent Systems for Molecular Biology, an official conference of the International Society for Computational Biology (ISCB; http://www.iscb.org). ISMB 2012 (http://www.iscb.org/ismb2012/) will take place in Long Beach, California, USA, from July 15–17, 2012; preceded during July 13–14 by eleven 1 or 2 day Special Interest Group (SIG) meetings, two satellite meetings and two half-day tutorials. The 35 papers in this volume were selected from 268 submitted papers. Submitted papers were assigned to 13 areas. Area Chairs led each topic area by selecting their area's program committee and overseeing the reviewing process. Many area chairs were new compared with 2011. Fourteen papers for which area chairs were in conflict were reviewed under a ‘Conflicts Management’ section headed by the Proceedings Chair; five such papers were accepted. Areas, co-chairs and acceptance information are listed in Table 1. Areas, co-chairs and acceptance information Areas, co-chairs and acceptance information Compared with prior years, five mature topic areas had steady submissions, ‘Evolution and Comparative Genomics’, ‘Gene Regulation and Transcriptomics’, ‘Protein Structure and Function’, ‘Protein Interactions and Networks’ and ‘Sequence Analysis’. The latter's rose by 30% with many strong submissions. Two areas newer to ISMB had a good showing this year, ‘Bioimaging’ and ‘Disease Models and Epidemiology’. One area more than doubled, ‘Disease Models’, partly as a result of taking some of ‘Population Genomics’ load; and one quadrupled, ‘Bioimaging’. ‘Databases and Ontologies’, ‘Massspec’ and ‘Text Mining’ each received roughly six submissions. Across the areas, 224 members of the bioinformatics community provided reviews. Most papers received three reviews and several received four or more. There was significant discussion of the merits of the papers first between referees and the area chairs, and then between area chairs and the proceedings chair. Initial decisions to accept papers were made during a comprehensive conference call with the area chairs, and several papers underwent a further evaluation by additional area chairs before acceptance decisions were finalized. We appreciate that in several cases reviewers' opinions might have changed with additional input or further clarifications from the authors; because the ISMB 2012 timeline did not allow for a second round of reviews, however, only papers where referees suggested minor revisions could be accepted. For several papers where referee comments might have been unclear to the authors, area chairs added additional comments and explanations. In total, 36 papers were conditionally accepted, pending revision. After acceptance notices were sent, the authors had two weeks to modify their papers according to the suggestions made by the reviewers and to respond to reviewersxa' comments. Modified papers and authors' responses were re-examined during the next week to ensure each paper was modified appropriately in response to the reviewers' comments. We were pleased that 35 conditionally accepted papers were finally accepted for the conference. The final acceptance rate was 13%, significantly lower than rates of 20 and 19% in the two prior years, based on the decision to accept fewer proceedings papers. Collectively, the 35 accepted papers had 133 authors from 12 countries across 5 continents, with 89 authors from North America, 25 from Europe, 7 from Asia, 2 from Israel and 10 from Australia. We thank the area chairs and reviewers for their hard work and dedication to maintaining a professional review process. We thank all authors of submitted papers and authors of accepted papers for their diligences in responding to reviewer comments within two weeks. We thank Steven Leard's team for extensive technical support with the EasyChair submission and reviewing system; Mona Singh, Joel S. Bader, Terry Gaasterland and Martin Vingron for sharing their experiences from prior years; the team at Oxford University Press for type-setting the papers; Conference Chairs, Terry Gaasterland, Richard H. Lathrop, Burkhard Rost and Sydney Brenner (Honorary Chair), as well as the ISMB 2012 Steering Committee, for their valuable input; and Steven Leard for helping us oversee the process.

MOTIVATION: One of the most successful methods to date for recognizing protein sequences that are evolutionarily related has been profile hidden Markov models (HMMs). However, these models do not capture pairwise statistical preferences of residues that are hydrogen bonded in beta sheets. These dependencies have been partially captured in the HMM setting by simulated evolution in the training phase and can be fully captured by Markov random fields (MRFs). However, the MRFs can be computationally prohibitive when beta strands are interleaved in complex topologies. We introduce SMURFLite, a method that combines both simplified MRFs and simulated evolution to substantially improve remote homology detection for beta structures. Unlike previous MRF-based methods, SMURFLite is computationally feasible on any beta-structural motif. RESULTS: We test SMURFLite on all propeller and barrel folds in the mainly-beta class of the SCOP hierarchy in stringent cross-validation experiments. We show a mean 26% (median 16%) improvement in area under curve (AUC) for beta-structural motif recognition as compared with HMMER (a well-known HMM method) and a mean 33% (median 19%) improvement as compared with RAPTOR (a well-known threading method) and even a mean 18% (median 10%) improvement in AUC over HHPred (a profile-profile HMM method), despite HHpred's use of extensive additional training data. We demonstrate SMURFLite's ability to scale to whole genomes by running a SMURFLite library of 207 beta-structural SCOP superfamilies against the entire genome of Thermotoga maritima, and make over a 100 new fold predictions. Availability and implementaion: A webserver that runs SMURFLite is available at: http://smurf.cs.tufts.edu/smurflite/

Abstract Background Causal graphs are an increasingly popular tool for the analysis of biological datasets. In particular, signed causal graphs--directed graphs whose edges additionally have a sign denoting upregulation or downregulation--can be used to model regulatory networks within a cell. Such models allow prediction of downstream effects of regulation of biological entities; conversely, they also enable inference of causative agents behind observed expression changes. However, due to their complex nature, signed causal graph models present special challenges with respect to assessing statistical significance. In this paper we frame and solve two fundamental computational problems that arise in practice when computing appropriate null distributions for hypothesis testing. Results First, we show how to compute a p-value for agreement between observed and model-predicted classifications of gene transcripts as upregulated, downregulated, or neither. Specifically, how likely are the classifications to agree to the same extent under the null distribution of the observed classification being randomized? This problem, which we call "Ternary Dot Product Distribution" owing to its mathematical form, can be viewed as a generalization of Fisher's exact test to ternary variables. We present two computationally efficient algorithms for computing the Ternary Dot Product Distribution and investigate its combinatorial structure analytically and numerically to establish computational complexity bounds. Second, we develop an algorithm for efficiently performing random sampling of causal graphs. This enables p-value computation under a different, equally important null distribution obtained by randomizing the graph topology but keeping fixed its basic structure: connectedness and the positive and negative in- and out-degrees of each vertex. We provide an algorithm for sampling a graph from this distribution uniformly at random. We also highlight theoretical challenges unique to signed causal graphs; previous work on graph randomization has studied undirected graphs and directed but unsigned graphs. Conclusion We present algorithmic solutions to two statistical significance questions necessary to apply the causal graph methodology, a powerful tool for biological network analysis. The algorithms we present are both fast and provably correct. Our work may be of independent interest in non-biological contexts as well, as it generalizes mathematical results that have been studied extensively in other fields.

MOTIVATION: Proteins of all kinds can self-assemble into highly ordered β-sheet aggregates known as amyloid fibrils, important both biologically and clinically. However, the specific molecular structure of a fibril can vary dramatically depending on sequence and environmental conditions, and mutations can drastically alter amyloid function and pathogenicity. Experimental structure determination has proven extremely difficult with only a handful of NMR-based models proposed, suggesting a need for computational methods. RESULTS: We present AmyloidMutants, a statistical mechanics approach for de novo prediction and analysis of wild-type and mutant amyloid structures. Based on the premise of protein mutational landscapes, AmyloidMutants energetically quantifies the effects of sequence mutation on fibril conformation and stability. Tested on non-mutant, full-length amyloid structures with known chemical shift data, AmyloidMutants offers roughly 2-fold improvement in prediction accuracy over existing tools. Moreover, AmyloidMutants is the only method to predict complete super-secondary structures, enabling accurate discrimination of topologically dissimilar amyloid conformations that correspond to the same sequence locations. Applied to mutant prediction, AmyloidMutants identifies a global conformational switch between Aβ and its highly-toxic 'Iowa' mutant in agreement with a recent experimental model based on partial chemical shift data. Predictions on mutant, yeast-toxic strains of HET-s suggest similar alternate folds. When applied to HET-s and a HET-s mutant with core asparagines replaced by glutamines (both highly amyloidogenic chemically similar residues abundant in many amyloids), AmyloidMutants surprisingly predicts a greatly reduced capacity of the glutamine mutant to form amyloid. We confirm this finding by conducting mutagenesis experiments. AVAILABILITY: Our tool is publically available on the web at http://amyloid.csail.mit.edu/. CONTACT: [email protected]; [email protected].

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), 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). 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.

MOTIVATION: With the increasing availability of large protein-protein interaction networks, the question of protein network alignment is becoming central to systems biology. Network alignment is further delineated into two sub-problems: local alignment, to find small conserved motifs across networks, and global alignment, which attempts to find a best mapping between all nodes of the two networks. In this article, our aim is to improve upon existing global alignment results. Better network alignment will enable, among other things, more accurate identification of functional orthologs across species. RESULTS: We introduce IsoRankN (IsoRank-Nibble) a global multiple-network alignment tool based on spectral clustering on the induced graph of pairwise alignment scores. IsoRankN outperforms existing algorithms for global network alignment in coverage and consistency on multiple alignments of the five available eukaryotic networks. Being based on spectral methods, IsoRankN is both error tolerant and computationally efficient. AVAILABILITY: Our software is available freely for non-commercial purposes on request from: http://isorank.csail.mit.edu/.

Amyloids and prion proteins are clinically and biologically important beta-structures, whose supersecondary structures are difficult to determine by standard experimental or computational means. In addition, significant conformational heterogeneity is known or suspected to exist in many amyloid fibrils. Recent work has indicated the utility of pairwise probabilistic statistics in beta-structure prediction. We develop here a new strategy for beta-structure prediction, emphasizing the determination of beta-strands and pairs of beta-strands as fundamental units of beta-structure. Our program, BETASCAN, calculates likelihood scores for potential beta-strands and strand-pairs based on correlations observed in parallel beta-sheets. The program then determines the strands and pairs with the greatest local likelihood for all of the sequence's potential beta-structures. BETASCAN suggests multiple alternate folding patterns and assigns relative a priori probabilities based solely on amino acid sequence, probability tables, and pre-chosen parameters. The algorithm compares favorably with the results of previous algorithms (BETAPRO, PASTA, SALSA, TANGO, and Zyggregator) in beta-structure prediction and amyloid propensity prediction. Accurate prediction is demonstrated for experimentally determined amyloid beta-structures, for a set of known beta-aggregates, and for the parallel beta-strands of beta-helices, amyloid-like globular proteins. BETASCAN is able both to detect beta-strands with higher sensitivity and to detect the edges of beta-strands in a richly beta-like sequence. For two proteins (Abeta and Het-s), there exist multiple sets of experimental data implying contradictory structures; BETASCAN is able to detect each competing structure as a potential structure variant. The ability to correlate multiple alternate beta-structures to experiment opens the possibility of computational investigation of prion strains and structural heterogeneity of amyloid. BETASCAN is publicly accessible on the Web at http://betascan.csail.mit.edu.

Probabilistic grammatical formalisms such as hidden Markov models (HMMs) and stochastic context-free grammars (SCFGs) have been extensively studied and widely applied in a number of fields. Here, we introduce a new algorithmic problem on HMMs and SCFGs that arises naturally from protein and RNA design, and which has not been previously studied. The problem can be viewed as an inverse to the one solved by the Viterbi algorithm on HMMs or by the CKY algorithm on SCFGs. We study this problem theoretically and obtain the first algorithmic results. We prove that the problem is NP-complete, even for a 3-letter emission alphabet, via a reduction from 3-SAT, a result that has implications for the hardness of RNA secondary structure design. We then develop a number of approaches for making the problem tractable. In particular, for HMMs we develop a branch-and-bound algorithm, which can be shown to have fixed-parameter tractable worst-case running time, exponential in the number of states of the HMM but linear in the length of the structure. We also show how to cast the problem as a Mixed Integer Linear Program.

The long-standing problem of constructing protein structure alignments is of central importance in computational biology. The main goal is to provide an alignment of residue correspondences, in order to identify homologous residues across chains. A critical next step of this is the alignment of protein complexes and their interfaces. Here, we introduce the program CMAPi, a two-dimensional dynamic programming algorithm that, given a pair of protein complexes, optimally aligns the contact maps of their interfaces: it produces polynomial-time near-optimal alignments in the case of multiple complexes. We demonstrate the efficacy of our algorithm on complexes from PPI families listed in the SCOPPI database and from highly divergent cytokine families. In comparison to existing techniques, CMAPi generates more accurate alignments of interacting residues within families of interacting proteins, especially for sequences with low similarity. While previous methods that use an all-atom based representation of the interface have been successful, CMAPi's use of a contact map representation allows it to be more tolerant to conformational changes and thus to align more of the interaction surface. These improved interface alignments should enhance homology modeling and threading methods for predicting PPIs by providing a basis for generating template profiles for sequence-structure alignment.

Even when there is agreement on what measure a protein multiple structure alignment should be optimizing, finding the optimal alignment is computationally prohibitive. One approach used by many previous methods is aligned fragment pair chaining, where short structural fragments from all the proteins are aligned against each other optimally, and the final alignment chains these together in geometrically consistent ways. Ye and Godzik have recently suggested that adding geometric flexibility may help better model protein structures in a variety of contexts. We introduce the program Matt (Multiple Alignment with Translations and Twists), an aligned fragment pair chaining algorithm that, in intermediate steps, allows local flexibility between fragments: small translations and rotations are temporarily allowed to bring sets of aligned fragments closer, even if they are physically impossible under rigid body transformations. After a dynamic programming assembly guided by these "bent" alignments, geometric consistency is restored in the final step before the alignment is output. Matt is tested against other recent multiple protein structure alignment programs on the popular Homstrad and SABmark benchmark datasets. Matt's global performance is competitive with the other programs on Homstrad, but outperforms the other programs on SABmark, a benchmark of multiple structure alignments of proteins with more distant homology. On both datasets, Matt demonstrates an ability to better align the ends of alpha-helices and beta-strands, an important characteristic of any structure alignment program intended to help construct a structural template library for threading approaches to the inverse protein-folding problem. The related question of whether Matt alignments can be used to distinguish distantly homologous structure pairs from pairs of proteins that are not homologous is also considered. For this purpose, a p-value score based on the length of the common core and average root mean squared deviation (RMSD) of Matt alignments is shown to largely separate decoys from homologous protein structures in the SABmark benchmark dataset. We postulate that Matt's strong performance comes from its ability to model proteins in different conformational states and, perhaps even more important, its ability to model backbone distortions in more distantly related proteins.

The diversity and importance of the role played by RNAs in the regulation and development of the cell are now well-known and well-documented. This broad range of functions is achieved through specific structures that have been (presumably) optimized through evolution. State-of-the-art methods, such as McCaskill's algorithm, use a statistical mechanics framework based on the computation of the partition function over the canonical ensemble of all possible secondary structures on a given sequence. Although secondary structure predictions from thermodynamics-based algorithms are not as accurate as methods employing comparative genomics, the former methods are the only available tools to investigate novel RNAs, such as the many RNAs of unknown function recently reported by the ENCODE consortium. In this paper, we generalize the McCaskill partition function algorithm to sum over the grand canonical ensemble of all secondary structures of all mutants of the given sequence. Specifically, our new program, RNAmutants, simultaneously computes for each integer k the minimum free energy structure MFE(k) and the partition function Z(k) over all secondary structures of all k-point mutants, even allowing the user to specify certain positions required not to mutate and certain positions required to base-pair or remain unpaired. This technically important extension allows us to study the resilience of an RNA molecule to pointwise mutations. By computing the mutation profile of a sequence, a novel graphical representation of the mutational tendency of nucleotide positions, we analyze the deleterious nature of mutating specific nucleotide positions or groups of positions. We have successfully applied RNAmutants to investigate deleterious mutations (mutations that radically modify the secondary structure) in the Hepatitis C virus cis-acting replication element and to evaluate the evolutionary pressure applied on different regions of the HIV trans-activation response element. In particular, we show qualitative agreement between published Hepatitis C and HIV experimental mutagenesis studies and our analysis of deleterious mutations using RNAmutants. Our work also predicts other deleterious mutations, which could be verified experimentally. Finally, we provide evidence that the 3' UTR of the GB RNA virus C has been optimized to preserve evolutionarily conserved stem regions from a deleterious effect of pointwise mutations. We hope that there will be long-term potential applications of RNAmutants in de novo RNA design and drug design against RNA viruses. This work also suggests potential applications for large-scale exploration of the RNA sequence-structure network. Binary distributions are available at http://RNAmutants.csail.mit.edu/.

Abstract Summary: We introduce Paircoil2, a new version of the Paircoil program, which uses pairwise residue probabilities to detect coiled–coil motifs in protein sequence data. Paircoil2 achieves 98% sensitivity and 97% specificity on known coiled coils in leave-family-out cross-validation. It also shows superior performance compared with published methods in tests on proteins of known structure. Availability: Paircoil2 is freely available as a web application and for download at Contact: [email protected]; [email protected] Supplementary information: Available at Bioinformatics online and at the Paircoil website.

This article studies the protein side-chain packing problem using the tree-decomposition of a protein structure. To obtain fast and accurate protein side-chain packing, protein structures are modeled using a geometric neighborhood graph, which can be easily decomposed into smaller blocks. Therefore, the side-chain assignment of the whole protein can be assembled from the assignment of the small blocks. Although we will show that the side-chain packing problem is stillNP-hard, we can achieve a tree-decomposition-based globally optimal algorithm with time complexity ofO(Nnrottw+ 1)and several polynomial-time approximation schemes (PTAS), whereNis the number of residues contained in the protein,nrotthe average number of rotamers for each residue, andtw=O(N2/3logN) the treewidth of the protein structure graph. Experimental results indicate that after Goldstein dead-end elimination is conducted,nrotis very small andtwis equal to 3 or 4 most of the time. Based on the globally optimal algorithm, we developed a protein side-chain assignment program TreePack, which runs up to 90 times faster than SCWRL 3.0, a widely-used side-chain packing program, on some large test proteins in the SCWRL benchmark database and an average of five times faster on all the test proteins in this database. There are also some real-world instances that TreePack can solve but that SCWRL 3.0 cannot. The TreePack program is available at http://ttic.uchicago.edu/~jinbo/TreePack.htm.

Many time-series experiments seek to estimate some signal as a continuous function of time. In this paper, we address the sampling problem for such experiments: determining which time-points ought to be sampled in order to minimize the cost of data collection. We restrict our attention to a growing class of experiments which measure multiple signals at each time-point and where raw materials/observations are archived initially, and selectively analyzed later, this analysis being the more expensive step. We present an active learning algorithm for iteratively choosing time-points to sample, using the uncertainty in the quality of the currently estimated time-dependent curve as the objective function. Using simulated data as well as gene expression data, we show that our algorithm performs well, and can significantly reduce experimental cost without loss of information.

A method is presented that uses β-strand interactions at both the sequence and the atomic level, to predict the beta-structural motifs in protein sequences. A program called Wrap-and-Pack implements this method, and is shown to recognize β-trefoils, an important class of globular β-structures, in the Protein Data Bank with 92% specificity and 92.3% sensitivity in cross-validation. It is demonstrated that Wrap-and-Pack learns each of the ten known SCOP β-trefoil families, when trained primarily on β-structures that are not β-trefoils, together with 3D structures of known β-trefoils from outside the family. Wrap-and-Pack also predicts many proteins of unknown structure to be β-trefoils. The computational method used here may generalize to other β-structures for which strand topology and profiles of residue accessibility are well conserved.

In [13] we reported the genome sequences of S. paradoxus, S. mikatae and S. bayanus and compared these three yeast species to their close relative, S. cerevisiae. Genome-wide comparative analysis allowed the identification of functionally important sequences, both coding and non-coding. In this companion paper we describe the mathematical and algorithmic results underpinning the analysis of these genomes.We developed statistical methods for the systematic de-novo identification of regulatory motifs. Without making use of co-regulated gene sets, we discovered virtually all previously known DNA regulatory motifs as well as several noteworthy novel motifs. With the additional use of gene ontology information, expression clusters and transcription factor binding profiles, we assigned candidate functions to the novel motifs discovered.Our results demonstrate that entirely automatic genome-wide annotation, gene validation, and discovery of regulatory motifs is possible. Our findings are validated by the extensive experimental knowledge in yeast, confirming their applicability to other genomes.

We describe a new computer program, Trilogy, for the automated discovery of sequence-structure patterns in proteins. Trilogy implements a pattern discovery algorithm that begins with an exhaustive analysis of flexible three-residue patterns; a subset of these patterns are selected as seeds for an extension process in which longer patterns are identified. A key feature of the method is explicit treatment of both the sequence and structure components of these motifs: each Trilogy pattern is a pair consisting of a sequence pattern and a structure pattern. Matches to both these component patterns are identified independently, allowing the program to assign a significance score to each sequence-structure pattern that assesses the degree of correlation between the corresponding sequence and structure motifs. Trilogy identifies several thousand high-scoring patterns that occur across protein families. These include both previously identified and novel motifs. We expect that these sequence-structure patterns will be useful in predicting protein structure from sequence, annotating newly determined protein structures, and identifying novel motifs of potential functional or structural significance.

A method is presented that uses β-strand interactions to predict the right-handed β-helix super-secondary structural motif in protein sequences. A program called BetaWrap implements this method, and is shown to score known β-helices above non-β-helices in the Protein Data Bank in cross-validation. It is demonstrated that BetaWrap learns each of the seven known SCOP β-helix families, when trained on the the known β-helices from outside the family. BetaWrap also predicts many bacterial proteins of unknown structure that play a role in human infectious disease to β-helices; in particular, these proteins serve as virulence factors, adhesins and toxins in bacterial pathogenesis, and include cell surface proteins from Chlamydia and the intestinal bacterium Helicobacter pylori. The computational method used here may generalize to other β structures for which strand topology and profiles of residue accessibility are well conserved.

One important approach to sequencing a large genome is (i) to sequence a collection of non-overlapping `seed' chosen from a genomic library of large-insert clones (such as bacterial artificial chromosome (BACs)) and then (ii) to take successive `walking' steps by selecting and sequencing minimally overlapping clones, using information such as clone-end sequences to identify the overlaps. We analyze the strategic issues involved in using this approach. We derive formulas showing how two key factors, the initial density of seed clones and the depth of the genomic library used for walking, affect the cost and time of a sequencing project—that is, the amount of redundant sequencing and the number of steps to cover the vast majority of the genome. We also discuss a variant strategy in which a second genomic library with clones having a somewhat smaller insert size is used to close gaps. This approach can dramatically decrease the amount of redundant sequencing, without affecting the rate at which the genome is covered.

We describe a novel analytical approach to gene recognition based on cross-species comparison We first undertook a comparison of orthologous genomic look from human and mouse, studying the extent of similarity in the number, size and sequence of exons and introns We then developed an approach for recognizing genes within such orthologous regions, by first aligning the regions using an iterative global alignment system and then identifying genes based on conservation of exonic features at aligned positions in both species The alignment and gene recognition are performed by new programs called GLASS and ROSETTA, respectively ROSETTA performed well at exact identification of coding exons in 117 orthologous pairs tested.

This paper describes a fast and fully automated dictionary based approach to gene annotation and exon prediction. Two dictionaries are constructed, one from the nonredundant protein OWL database and the other from the dbEST database. These dictionaries are used to obtain O(1) time lookups of tuples in the dictionaries (4 tuples for the OWL database and 11 tuples for the \ndbEST database). These tuples can be used to rapidly find the longest matches at every position in an input sequence to the database sequences. Such matches provide very useful information pertaining to locating common segments between exons, alternative splice sites, and frequency data of long tuples for statistical purposes. These dictionaries also provide the basis for both homology determination, and statistical approaches to exon prediction. For instance, using the OWL protein database on a benchmark test set of 130 genes, and after removing sequences from the database with exact amino acid homology to genes in our test set, we find 88% of coding nucleotides, and 99% of our predictions of coding nucleotides are correct. Also, 81% of coding exons are predicted exactly, while 82% of our predictions of exons agree exactly with the published annotation of their genes.

A number of current technologies allow for the determination of interatomic distance information in structures such as proteins and RNA. Thus, the reconstruction of a three-dimensional set of points using information about its interpoint distances has become a task of basic importance in determining molecular structure. The distance measurements one obtains from techniques such as NMR are typically sparse and error-prone, greatly complicating the reconstruction task. Many of these errors result in distance measurements that can be safely assumed to lie within certain fixed tolerances. But a number of sources of systematic error in these experiments lead to inaccuracies in the data that are very hard to quantify; in effect, one must treat certain entries of the measured distance matrix as being arbitrarily “corrupted.” The existence of arbitrary errors leads to an interesting sort of error-correction problem—how many corrupted entries in a distance matrix can be efficiently corrected to produce a consistent three-dimensional structure? For the case of an n × n matrix in which every entry is specified, we provide a randomized algorithm running in time O(n log n) that enumerates all structures consistent with at most (1/2-ε)n errors per row, with high probability. In the case of randomly located errors, we can correct errors of the same density in a sparse matrix-one in which only a β fraction of the entries in each row are given, for any constant βgt;0.

Article Free Access Share on Protein folding in the hydrophobic-hydrophilic (HP) is NP-complete Authors: Bonnie Berger 2-389, Mathematics Dept. and Lab. for Computer Science, MIT, Cambridge, MA 2-389, Mathematics Dept. and Lab. for Computer Science, MIT, Cambridge, MAView Profile , Tom Leighton 2-377, Mathematics Dept. and Lab. for Computer Science, MIT, Cambridge, MA 2-377, Mathematics Dept. and Lab. for Computer Science, MIT, Cambridge, MAView Profile Authors Info & Claims RECOMB '98: Proceedings of the second annual international conference on Computational molecular biologyMarch 1998 Pages 30–39https://doi.org/10.1145/279069.279080Published:01 March 1998Publication History 51citation1,897DownloadsMetricsTotal Citations51Total Downloads1,897Last 12 Months157Last 6 weeks14 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

This paper introduces a near-linear time sequential algorithm for constructing a sparse neighborhood cover. This implies analogous improvements (from quadratic to near-linear time) for any problem whose solution relies on network decompositions, including small edge cuts in planar graphs, approximate shortest paths, and weight- and distance-preserving graph spanners. In particular, an O(log n) approximation to the k-shortest paths problem on an n-vertex, E-edge graph is obtained that runs in $\soh{n + E + k}$ time.

Article An iterative method for improved protein structural motif recognition Share on Authors: Bonnie Berger Math Dept. and Lab. for Computer Science (LCS), MIT Math Dept. and Lab. for Computer Science (LCS), MITView Profile , Mona Singh DIMACS and Princeton University DIMACS and Princeton UniversityView Profile Authors Info & Claims RECOMB '97: Proceedings of the first annual international conference on Computational molecular biologyJanuary 1997 Pages 37–46https://doi.org/10.1145/267521.267527Online:19 January 1997Publication History 2citation412DownloadsMetricsTotal Citations2Total Downloads412Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Higher moment analysis has typically been used to upper bound certain functions. In this paper, we introduce a new combinatorial method to lower bound the expectation of the absolute value of a random variable X by the expectation of a quartic in X. In the special case where we are looking at the absolute value of a (weighted) sum of {-1,+1} unbiased random variables, we achieve tight bounds, using only a fourth moment, for the total discrepancy of a set system. Because the fourth moment depends only on 4-wise independence, our bounds will hold over polynomially sized distributions, and so these bounds will be directly applicable in removing randomness to obtain NC algorithms. We obtain the first NC algorithms for the problems of total discrepancy, maximum acyclic subgraph, tournament ranking, the Gale--Berlekamp switching game, and edge discrepancy. We show that for most of these applications it is truly necessary to consider a fourth moment by exhibiting a 3-wise independent distribution which does not achieve the required bounds. Our method is strong enough to give a new combinatorial bound on tournament ranking.

A number of current technologies allow for the determination of inter-atomic distance information three-dimensional structure?For the case of an n x n matrix in which every entry is specified, we provide a randomized algorithm running in time O(n log n) that enumerates all structures consistent wit h at most (~-s) n errors per row, with high probability y.In the case of randomly located errors, we can correct errors of the same density in a sparse matrix -one in which only a ,6 fraction of the entries in each row are given, for any constant ~>0.

This paper presents deterministic sublinear-time distributed algorithms for network decomposition and for constructing a sparse neighborhood cover of a network. The latter construction leads to improved distributed preprocessing time for a number of distributed algorithms, including all-pairs shortest paths computation, load balancing, broadcast, and bandwidth management.

This paper presents algorithms for routing channels with L ≥2 layers. For the unit vertical overlap model, we describe a two-layer channel routing algorithm that uses at most d + O(√d) tracks to route two-terminal net problems and 2d + O(√d) tracks to route multiterminal nets. We also show that d + Ω(log d) tracks are required to route two-terminal net problems in the worst case even if arbitrary vertical overlap is allowed. We generalize the algorithm to unrestricted multilayer routing and use only d/(L -1) + O(√d/L + 1)> tracks for two-terminal net problems (within O(√d/L + 1) tracks of optimal) and d/(L-2) +O(√d/L + 1) tracks for multiterminal net problems (within a factor of(L-1)/(L-2) times optimal). We demonstrate the generality of our routing strategy by showing that it can be used to duplicate some of the best previous upper bounds for other models (two-layer Manhattan routing and two and three-layer knock-knee routing of two-terminal, two-sided nets), and gives a new upper bound for rotuing with 45-degree diagonal wires.

This paper introduces the first near-linear (specifically, O(Elog n+nlog/sup 2/ n)) time algorithm for constructing a sparse neighborhood cover in sequential and distributed environments. This automatically implies analogous improvements (from quadratic to near-linear) to all the results in the literature that rely on network decompositions, both in sequential and distributed domains, including adaptive routing schemes with O/spl tilde/(1) stretch and memory, small edge cuts in planar graphs, sequential algorithms for dynamic approximate shortest paths with O/spl tilde/(E) cost for edge insertion/deletion and O/spl tilde/(1) time to answer shortest-path queries, weight and distance-preserving graph spanners with O/spl tilde/(E) running time and space, and distributed asynchronous "from-scratch" breadth-first-search and network synchronizer constructions with O/spl tilde/(1) message and space overhead (down from O(n)).>

This paper obtains the first deterministic sublinear-time algorithm ~1992

A general framework for removing randomness from randomized NC algorithms whose analysls uses only pol ylogarlthmic independence is developed.Previously, no techniques were known to remove the randomness from those randomized NC algorithms depending on more than constant independence.One application of our techniques is an NC algorithm for the set discrepancy y problem.which can be used to obtain many other NC algorithms, mcludmg a better NC edge coloring algorithm.As another application of the techniques in this paper.an NC algorlthm for the h ypergraph coloring problem M provided.

A general framework is developed for removing randomness from randomized NC algorithms whose analysis uses only polylogarithmic independence. Previously, no techniques were known to determinize those RNC algorithms depending on more than constant independence. One application of the techniques is an NC algorithm for the set discrepancy problem, which can be used to obtain many other NC algorithms, including a better NC edge-coloring algorithm. As another application an NC algorithm for the hypergraph coloring problem is provided.>

NC approximation algorithms are given for the unweighted and weighted set cover problems. The algorithms use a linear number of processors and give a cover that has at most log n times the optimal size/weight, thus matching the performance of the best sequential algorithms. The set cover algorithm is applied to learning theory, providing an NC algorithm for learning the concept class obtained by taking the closure under finite union or finite intersection of any concept class of finite VC dimension which has an NC hypothesis finder. In addition, a linear-processor NC algorithm is given for a variant of the set cover problem and used to obtain NC algorithms for several problems in computational geometry.>