MOTIVATION: Biosynthetic gene clusters (BGCs) are responsible the biosynthesis of many natural products, including a multitude of effective therapeutics and their precursors. Advances in genomic data collection as well as computational techniques have made it possible to identify BGCs at scale. However, accurately determining the types of BGC-encoded products from genomic content remains elusive. RESULTS: Here, we introduce BGC annotation tool (BGCat), a machine learning method for fine-grained structural classification of BGC-encoded products, leveraging the NPClassifier natural product nomenclature. Our method leverages a pre-trained protein language model for creating meaningful gene representations and a deep neural network for class label prediction. We show the method outperforms state-of-the-art approaches in coarse-grained product classification and is effective for detailed classification. We implement a clustering-based augmentation strategy for BGC-product relationships, addressing a crucial gap in the available datasets. We then introduce the concept of product class profiles of gene cluster families (GCFs), associating each GCF with a probabilistic distribution of product types and offering a new perspective on GCF functions. Lastly, we use BGCat to provide new product class labels for over 100k BGCs in antiSMASH DB that presently have minimal information about their products. AVAILABILITY AND IMPLEMENTATION: The source code and trained model weights are freely available at https://github.com/HassounLab/BGCat.

The annotation (assigning structural chemical identities) of MS/MS spectra remains a significant challenge due to the enormous molecular diversity in biological samples and the limited scope of reference databases. Currently, the vast majority of spectral measurements remain in the "dark chemical space" without structural annotations. To improve annotation, we propose MADGEN (Mass-spec Attends to De Novo Molecular GENeration), a scaffold-based method for de novo molecular structure generation guided by mass spectrometry data. MADGEN operates in two stages: scaffold retrieval and spectra-conditioned molecular generation starting with the scaffold. In the first stage, given an MS/MS spectrum, we formulate scaffold retrieval as a ranking problem and employ contrastive learning to align mass spectra with candidate molecular scaffolds. In the second stage, starting from the retrieved scaffold, we employ the MS/MS spectrum to guide an attention-based generative model to generate the final molecule. Our approach constrains the molecular generation search space, reducing its complexity and improving generation accuracy. We evaluate MADGEN on three datasets (NIST23, CANOPUS, and MassSpecGym) and evaluate MADGEN's performance with a predictive scaffold retriever and with an oracle retriever. We demonstrate the effectiveness of using attention to integrate spectral information throughout the generation process to achieve strong results with the oracle retriever.

Graph generation is a critical task in numerous domains, including molecular design and social network analysis, due to its ability to model complex relationships and structured data. While most modern graph generative models utilize adjacency matrix representations, this work revisits an alternative approach that represents graphs as sequences of node set and edge set. We advocate for this approach due to its efficient encoding of graphs and propose a novel representation. Based on this representation, we introduce the Graph Generative Pre-trained Transformer (G2PT), an auto-regressive model that learns graph structures via next-token prediction. To further exploit G2PT’s capabilities as a general-purpose foundation model, we explore fine-tuning strategies for two downstream applications: goal-oriented generation and graph property prediction. We conduct extensive experiments across multiple datasets. Results indicate that G2PT achieves superior generative performance on both generic graph and molecule datasets. Furthermore, G2PT exhibits strong adaptability and versatility in downstream tasks from molecular design to property prediction.

MOTIVATION: A major challenge in metabolomics is annotation: assigning molecular structures to mass spectral fragmentation patterns. Despite recent advances in molecule-to-spectra and in spectra-to-molecular fingerprint (FP) prediction, annotation rates remain low. RESULTS: We introduce in this article a novel tool (JESTR) for annotation. Unlike prior approaches that "explicitly" construct molecular FPs or spectra, JESTR leverages the insight that molecules and their corresponding spectra are views of the same data and effectively embeds their representations in a joint space. Candidate structures are ranked based on cosine similarity between the embeddings of query spectrum and each candidate. We evaluate JESTR against mol-to-spec, spec-to-FP, and spec-mol matching annotation tools on four datasets. On average, for rank@[1-20], JESTR outperforms other tools by 55.5%-302.6%. We further demonstrate the strong value of regularization with candidate molecules during training, boosting rank@1 performance by 5.72% across all datasets and enhancing the model's ability to discern between target and candidate molecules. When comparing JESTR's performance against that of publicly available pretrained models of SIRIUS and CFM-ID on appropriate subsets of MassSpecGym dataset, JESTR outperforms these tools by 31% and 238%, respectively. Through JESTR, we offer a novel promising avenue toward accurate annotation, therefore unlocking valuable insights into the metabolome. AVAILABILITY AND IMPLEMENTATION: Code and dataset available at https://github.com/HassounLab/JESTR1/.

The discovery and identification of molecules in biological and environmental samples is crucial for advancing biomedical and chemical sciences. Tandem mass spectrometry (MS/MS) is the leading technique for high-throughput elucidation of molecular structures. However, decoding a molecular structure from its mass spectrum is exceptionally challenging, even when performed by human experts. As a result, the vast majority of acquired MS/MS spectra remain uninterpreted, thereby limiting our understanding of the underlying (bio)chemical processes. Despite decades of progress in machine learning applications for predicting molecular structures from MS/MS spectra, the development of new methods is severely hindered by the lack of standard datasets and evaluation protocols. To address this problem, we propose MassSpecGym -- the first comprehensive benchmark for the discovery and identification of molecules from MS/MS data. Our benchmark comprises the largest publicly available collection of high-quality MS/MS spectra and defines three MS/MS annotation challenges: \textit{de novo} molecular structure generation, molecule retrieval, and spectrum simulation. It includes new evaluation metrics and a generalization-demanding data split, therefore standardizing the MS/MS annotation tasks and rendering the problem accessible to the broad machine learning community. MassSpecGym is publicly available at \url{https://github.com/pluskal-lab/MassSpecGym}.

MOTIVATION: A key challenge in metabolomics is annotating measured spectra from a biological sample with chemical identities. Currently, only a small fraction of measurements can be assigned identities. Two complementary computational approaches have emerged to address the annotation problem: mapping candidate molecules to spectra, and mapping query spectra to molecular candidates. In essence, the candidate molecule with the spectrum that best explains the query spectrum is recommended as the target molecule. Despite candidate ranking being fundamental in both approaches, limited prior works incorporated rank learning tasks in determining the target molecule. RESULTS: We propose a novel machine learning model, Ensemble Spectral Prediction (ESP), for metabolite annotation. ESP takes advantage of prior neural network-based annotation models that utilize multilayer perceptron (MLP) networks and Graph Neural Networks (GNNs). Based on the ranking results of the MLP- and GNN-based models, ESP learns a weighting for the outputs of MLP and GNN spectral predictors to generate a spectral prediction for a query molecule. Importantly, training data is stratified by molecular formula to provide candidate sets during model training. Further, baseline MLP and GNN models are enhanced by considering peak dependencies through label mixing and multi-tasking on spectral topic distributions. When trained on the NIST 2020 dataset and evaluated on the relevant candidate sets from PubChem, ESP improves average rank by 23.7% and 37.2% over the MLP and GNN baselines, respectively, demonstrating performance gain over state-of-the-art neural network approaches. However, MLP approaches remain strong contenders when considering top five ranks. Importantly, we show that annotation performance is dependent on the training dataset, the number of molecules in the candidate set and candidate similarity to the target molecule. AVAILABILITY AND IMPLEMENTATION: The ESP code, a trained model, and a Jupyter notebook that guide users on using the ESP tool is available at https://github.com/HassounLab/ESP.

Self-supervised training methods for transformers have demonstrated remarkable performance across various domains. Previous transformer-based models, such as masked autoencoders (MAE), typically utilize a single normalization layer for both the [CLS] symbol and the tokens. We propose in this paper a simple modification that employs separate normalization layers for the tokens and the [CLS] symbol to better capture their distinct characteristics and enhance downstream task performance. Our method aims to alleviate the potential negative effects of using the same normalization statistics for both token types, which may not be optimally aligned with their individual roles. We empirically show that by utilizing a separate normalization layer, the [CLS] embeddings can better encode the global contextual information and are distributed more uniformly in its anisotropic space. When replacing the conventional normalization layer with the two separate layers, we observe an average 2.7% performance improvement over the image, natural language, and graph domains.

MOTIVATION: Accurately predicting the likelihood of interaction between two objects (compound-protein sequence, user-item, author-paper, etc.) is a fundamental problem in Computer Science. Current deep-learning models rely on learning accurate representations of the interacting objects. Importantly, relationships between the interacting objects, or features of the interaction, offer an opportunity to partition the data to create multi-views of the interacting objects. The resulting congruent and non-congruent views can then be exploited via contrastive learning techniques to learn enhanced representations of the objects. RESULTS: We present a novel method, Contrastive Stratification for Interaction Prediction (CSI), to stratify (partition) a dataset in a manner that can be exploited via Contrastive Multiview Coding to learn embeddings that maximize the mutual information across congruent data views. CSI assigns a key and multiple views to each data point, where data partitions under a particular key form congruent views of the data. We showcase the effectiveness of CSI by applying it to the compound-protein sequence interaction prediction problem, a pressing problem whose solution promises to expedite drug delivery (drug-protein interaction prediction), metabolic engineering, and synthetic biology (compound-enzyme interaction prediction) applications. Comparing CSI with a baseline model that does not utilize data stratification and contrastive learning, and show gains in average precision ranging from 13.7% to 39% using compounds and sequences as keys across multiple drug-target and enzymatic datasets, and gains ranging from 16.9% to 63% using reaction features as keys across enzymatic datasets. AVAILABILITY AND IMPLEMENTATION: Code and dataset available at https://github.com/HassounLab/CSI.

MOTIVATION: While traditionally utilized for identifying site-specific metabolic activity within a compound to alter its interaction with a metabolizing enzyme, predicting the site-of-metabolism (SOM) is essential in analyzing the promiscuity of enzymes on substrates. The successful prediction of SOMs and the relevant promiscuous products has a wide range of applications that include creating extended metabolic models (EMMs) that account for enzyme promiscuity and the construction of novel heterologous synthesis pathways. There is therefore a need to develop generalized methods that can predict molecular SOMs for a wide range of metabolizing enzymes. RESULTS: This article develops a Graph Neural Network (GNN) model for the classification of an atom (or a bond) being an SOM. Our model, GNN-SOM, is trained on enzymatic interactions, available in the KEGG database, that span all enzyme commission numbers. We demonstrate that GNN-SOM consistently outperforms baseline machine learning models, when trained on all enzymes, on Cytochrome P450 (CYP) enzymes, or on non-CYP enzymes. We showcase the utility of GNN-SOM in prioritizing predicted enzymatic products due to enzyme promiscuity for two biological applications: the construction of EMMs and the construction of synthesis pathways. AVAILABILITY AND IMPLEMENTATION: A python implementation of the trained SOM predictor model can be found at https://github.com/HassounLab/GNN-SOM. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Real-world link prediction problems often deal with data from multiple domains, where data may be highly skewed and imbalanced. Computer vision research has studied similar issues under the Few-Shot Learning (FSL) umbrella. However, this problem has rarely been addressed and explored in the graph domain, specifically for link prediction. In this work, we propose an adversarial training-based framework that aims at improving link prediction for highly skewed and imbalanced graphs from different domains by generating domain agnostic embedding. We introduce a domain discriminator on pairs of graph-level embedding. We then use the discriminator to improve the model in an adversarial way, such that the graph embedding generated by the model are domain agnostic. We test our ideas on one large real-world user-business-review dataset and three benchmark datasets. Our results demonstrate that when domain differences exist, our method creates better graph embedding that are more evenly distributed across domains and generate better prediction outcomes. In the absence of domain differences, our method is on par with state-of-the-art.

MOTIVATION: Despite experimental and curation efforts, the extent of enzyme promiscuity on substrates continues to be largely unexplored and under documented. Providing computational tools for the exploration of the enzyme-substrate interaction space can expedite experimentation and benefit applications such as constructing synthesis pathways for novel biomolecules, identifying products of metabolism on ingested compounds, and elucidating xenobiotic metabolism. Recommender systems (RS), which are currently unexplored for the enzyme-substrate interaction prediction problem, can be utilized to provide enzyme recommendations for substrates, and vice versa. The performance of Collaborative-Filtering (CF) RSs; however, hinges on the quality of embedding vectors of users and items (enzymes and substrates in our case). Importantly, enhancing CF embeddings with heterogeneous auxiliary data, specially relational data (e.g. hierarchical, pairwise or groupings), remains a challenge. RESULTS: We propose an innovative general RS framework, termed Boost-RS that enhances RS performance by 'boosting' embedding vectors through auxiliary data. Specifically, Boost-RS is trained and dynamically tuned on multiple relevant auxiliary learning tasks Boost-RS utilizes contrastive learning tasks to exploit relational data. To show the efficacy of Boost-RS for the enzyme-substrate prediction interaction problem, we apply the Boost-RS framework to several baseline CF models. We show that each of our auxiliary tasks boosts learning of the embedding vectors, and that contrastive learning using Boost-RS outperforms attribute concatenation and multi-label learning. We also show that Boost-RS outperforms similarity-based models. Ablation studies and visualization of learned representations highlight the importance of using contrastive learning on some of the auxiliary data in boosting the embedding vectors. AVAILABILITY AND IMPLEMENTATION: A Python implementation for Boost-RS is provided at https://github.com/HassounLab/Boost-RS. The enzyme-substrate interaction data is available from the KEGG database (https://www.genome.jp/kegg/).

Recent works apply Graph Neural Networks (GNNs) to graph matching tasks and show promising results. Considering that model outputs are complex matchings, we devise several techniques to improve the learning of GNNs and obtain a new model, Stochastic Iterative Graph MAtching (SIGMA). Our model predicts a distribution of matchings, instead of a single matching, for a graph pair so the model can explore several probable matchings. We further introduce a novel multi-step matching procedure, which learns how to refine a graph pair’s matching results incrementally. The model also includes dummy nodes so that the model does not have to find matchings for nodes without correspondence. We fit this model to data via scalable stochastic optimization. We conduct extensive experiments across synthetic graph datasets as well as biochemistry and computer vision applications. Across all tasks, our results show that SIGMA can produce significantly improved graph matching results compared to state-of-the-art models. Ablation studies verify that each of our components (stochastic training, iterative matching, and dummy nodes) offers noticeable improvement.

MOTIVATION: The complete characterization of enzymatic activities between molecules remains incomplete, hindering biological engineering and limiting biological discovery. We develop in this work a technique, enzymatic link prediction (ELP), for predicting the likelihood of an enzymatic transformation between two molecules. ELP models enzymatic reactions cataloged in the KEGG database as a graph. ELP is innovative over prior works in using graph embedding to learn molecular representations that capture not only molecular and enzymatic attributes but also graph connectivity. RESULTS: We explore transductive (test nodes included in the training graph) and inductive (test nodes not part of the training graph) learning models. We show that ELP achieves high AUC when learning node embeddings using both graph connectivity and node attributes. Further, we show that graph embedding improves link prediction by 30% in area under curve over fingerprint-based similarity approaches and by 8% over support vector machines. We compare ELP against rule-based methods. We also evaluate ELP for predicting links in pathway maps and for reconstruction of edges in reaction networks of four common gut microbiota phyla: actinobacteria, bacteroidetes, firmicutes and proteobacteria. To emphasize the importance of graph embedding in the context of biochemical networks, we illustrate how graph embedding can guide visualization. AVAILABILITY AND IMPLEMENTATION: The code and datasets are available through https://github.com/HassounLab/ELP.

MOTIVATION: As experimental efforts are costly and time consuming, computational characterization of enzyme capabilities is an attractive alternative. We present and evaluate several machine-learning models to predict which of 983 distinct enzymes, as defined via the Enzyme Commission (EC) numbers, are likely to interact with a given query molecule. Our data consists of enzyme-substrate interactions from the BRENDA database. Some interactions are attributed to natural selection and involve the enzyme's natural substrates. The majority of the interactions however involve non-natural substrates, thus reflecting promiscuous enzymatic activities. RESULTS: We frame this "enzyme promiscuity prediction" problem as a multi-label classification task. We maximally utilize inhibitor and unlabelled data to train prediction models that can take advantage of known hierarchical relationships between enzyme classes. We report that a hierarchical multi-label neural network, EPP-HMCNF, is the best model for solving this problem, outperforming k-nearest neighbours similarity-based and other machine learning models. We show that inhibitor information during training consistently improves predictive power, particularly for EPP-HMCNF. We also show that all promiscuity prediction models perform worse under a realistic data split when compared to a random data split, and when evaluating performance on non-natural substrates compared to natural substrates. AVAILABILITY AND IMPLEMENTATION: We provide Python code for EPP-HMCNF and other models in a repository termed EPP (Enzyme Promiscuity Prediction) at https://github.com/hassounlab/EPP. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

While elementary flux mode (EFM) analysis is now recognized as a cornerstone computational technique for cellular pathway analysis and engineering, EFM application to genome-scale models remains computationally prohibitive. This article provides a review of aspects of EFM computation that elucidates bottlenecks in scaling EFM computation. First, algorithms for computing EFMs are reviewed. Next, the impact of redundant constraints, sensitivity to constraint ordering and network compression are evaluated. Then, the advantages and limitations of recent parallelization and GPU-based efforts are highlighted. The article then reviews alternative pathway analysis approaches that aim to reduce the EFM solution space. Despite advances in EFM computation, our review concludes that continued scaling of EFM computation is necessary to apply EFM to genome-scale models. Further, our review concludes that pathway analysis methods that target specific pathway properties can provide powerful alternatives to EFM analysis.

Antibodies are capable of potently and specifically binding individual antigens and, in some cases, disrupting their functions. The key challenge in generating antibody-based inhibitors is the lack of fundamental information relating sequences of antibodies to their unique properties as inhibitors. We develop a pipeline, Antibody Sequence Analysis Pipeline using Statistical testing and Machine Learning (ASAP-SML), to identify features that distinguish one set of antibody sequences from antibody sequences in a reference set. The pipeline extracts feature fingerprints from sequences. The fingerprints represent germline, CDR canonical structure, isoelectric point and frequent positional motifs. Machine learning and statistical significance testing techniques are applied to antibody sequences and extracted feature fingerprints to identify distinguishing feature values and combinations thereof. To demonstrate how it works, we applied the pipeline on sets of antibody sequences known to bind or inhibit the activities of matrix metalloproteinases (MMPs), a family of zinc-dependent enzymes that promote cancer progression and undesired inflammation under pathological conditions, against reference datasets that do not bind or inhibit MMPs. ASAP-SML identifies features and combinations of feature values found in the MMP-targeting sets that are distinct from those in the reference sets.

Computational methods to engineer cellular metabolism promise to play a critical role in producing pharmaceutical, repairing defective genes, destroying cancer cells, and generating biofuels. Elementary Flux Mode (EFM) analysis is one such powerful technique that has elucidated cell growth and regulation, predicted product yield, and analyzed network robustness. EFM analysis, however, is a computationally daunting task because it requires the enumeration of all independent and stoichiometrically balanced pathways within a cellular network. We present in this paper an EFM enumeration algorithm, termed graphical EFM or gEFM. The algorithm is based on graph traversal, an approach previously assumed unsuitable for enumerating EFMs. The approach is derived from a pathway synthesis method proposed by Mavrovouniotis et al. The algorithm is described and proved correct. We apply gEFM to several networks and report runtimes in comparison with other EFM computation tools. We show how gEFM benefits from network compression. Like other EFM computational techniques, gEFM is sensitive to constraint ordering; however, we are able to demonstrate that knowledge of the underlying network structure leads to better constraint ordering. gEFM is shown to be competitive with state-of-the-art EFM computational techniques for several networks, but less so for networks with a larger number of EFMs.

Pathway analysis is a powerful approach to enable rational design or redesign of biochemical networks for optimizing metabolic engineering and synthetic biology objectives such as production of desired chemicals or biomolecules from specific nutrients. While experimental methods can be quite successful, computational approaches can enhance discovery and guide experimentation by efficiently exploring very large design spaces. We present a computational algorithm, Predictably Profitable Path (PreProPath), to identify target pathways best suited for engineering modifications. The algorithm utilizes uncertainties about the metabolic networks operating state inherent in the underdetermined linear equations representing the stoichiometric model. Flux Variability Analysis is used to determine the operational flux range. PreProPath identifies a path that is predictable in behavior, exhibiting small flux ranges, and profitable, containing the least restrictive flux-limiting reaction in the network. The algorithm is computationally efficient because it does not require enumeration of pathways. The results of case studies show that PreProPath can efficiently analyze variances in metabolic states and model uncertainties to suggest pathway engineering strategies that have been previously supported by experimental data.

Bulk FinFETs have emerged as the solution to short-channel effects at the 22-nm technology node and beyond. The capability of 3-D stacking of dies from various technologies will eventually enable stacking FinFET dies within 3-D integrated circuits. Within 3-D circuits, through silicon vias (TSVs) are a known source of substrate noise in planar bulk technologies. While FinFETs are expected to demonstrate superior noise immunity relative to planar devices due to superior gate control over and volume inversion of the active fin, the impact of TSV noise on FinFETs has not been previously quantified. To evaluate TSV-FinFET noise coupling, we develop in this paper a simulation methodology that extends the state of the art by accurately modeling substrate noise due to digital signals on nearby TSVs and improving the extraction of substrate circuit models from full-wave electromagnetic simulations. To overcome the lack of high-fidelity FinFET SPICE models that accurately capture the effects of substrate noise, we use high-fidelity technology computer-aided design (TCAD) FinFET models. Our results show that FinFETs exhibit an order of magnitude less leakage current noise transients, and two orders of magnitude less saturation current noise transients, relative to comparable planar technologies. Our findings are generalizable, showing that FinFETs are significantly more robust to substrate noise than equivalent planar devices.

Re-engineering cellular behavior promises to advance the production of commercially significant biomolecules and to enhance cellular function for many applications. To achieve a desired cellular objective, it is necessary to identify within a metabolic network a set of reactions whose fluxes should be changed using gene modifications. We develop a computational method, CCOpt, to optimize the selection of an intervention set that consists of gene up/down-regulation using uncertainty-aware chance-constrained optimization. In contrast to deterministic approaches where constraints are met with 100% certainty, constraints in CCOpt are probabilistically met at a user-specified confidence level. We investigate the application of CCOpt to two case studies that utilize the Chinese Hamster Ovary (CHO) cell metabolism. Our results demonstrate that CCOpt is capable of identifying optimal intervention sets without the run-time cost of a sampling based (Monte Carlo) approach.

Consider a re-spin of an existing complex SoC, with a partial schematic and an incomplete specification, with limited abilities to test and observe I/O behavior. Additionally, the underlying technology used is only partially understood. Can disciplined engineering approaches yield the re-spin? What are fundamental challenges? How will automation tools enable such designs? This talk will showcase how analysis and synthesis concepts can be applied in the context of biological discovery and design. Various optimization and analysis techniques can be applied to maximize the production of ethanol within an E. Coli cell without kill it. Pathway synthesis techniques can help uncover the fate of environmental chemicals within the human gut, which is colonized by ∼1014 bacteria belonging to ∼1000 species. No biology pre-requisites are needed to attend this talk.

Increased power density and package asymmetry pose challenges in designing power delivery networks for 3-D Integrated Circuits (ICs). The increased resistivity of Cu wires due to scaling has shifted attention to alternate interconnect technologies. Continued and significant innovations in CNT manufacturing at CMOS-compatible temperatures with quality low-resistive contacts promise to enable the use of CNT as a replacement. We investigate in this paper the feasibility of using CNTs for power delivery in 3-D ICs. We evaluate the use of CNTs as Through-Silicon Vias (TSVs) and as wiring for global power delivery grids, fabricated on interposer dies. We assume the CNT interconnect has a mix of single- and multi-walled CNTs with 30% metallic nanotubes. We design a 3-D system-level comparative framework that utilizes select traces from SPEC benchmarks to evaluate improvements of CNTs over Cu. Our results emphasize how CNTs can significantly improve power delivery for 3-D integrated circuits. Using CNTs for on-chip power grid and for TSVs reduces the number of TSVs by 71% when compared to a Cu implementation. For the same substrate area dedicated to power-TSVs, CNTs improve the maximum and average IR drop by 98% and 40%, respectively. Improvements in the Ldi/dt drop are 47% and 18%, respectively.

Constructing biological circuits in a bottom-up modular fashion using design methodologies similar to those used in electronics has gained tremendous attention in the past decade. The end goal, however, is engineering biological systems and not only individual components in the context of pursuing applications useful in improving human health or enhancing the environment. This article reviews the basics of biological system design rooted in Metabolic Engineering and Systems Biology and outlines current system-level modeling, analysis, optimization, and synthesis with emphasis on some current bottlenecks in establishing more rigorous design tools and methodologies for engineering biological systems.

Modularity analysis offers a route to better understand the organization of cellular biochemical networks as well as to derive practically useful, simplified models of these complex systems. While there is general agreement regarding the qualitative properties of a biochemical module, there is no clear consensus on the quantitative criteria that may be used to systematically derive these modules. In this work, we investigate cyclical interactions as the defining characteristic of a biochemical module. We utilize a round trip distance metric, termed Shortest Retroactive Distance (ShReD), to characterize the retroactive connectivity between any two reactions in a biochemical network and to group together network components that mutually influence each other. We evaluate the metric on two types of networks that feature feedback interactions: (i) epidermal growth factor receptor (EGFR) signaling and (ii) liver metabolism supporting drug transformation. For both networks, the ShReD partitions found hierarchically arranged modules that confirm biological intuition. In addition, the partitions also revealed modules that are less intuitive. In particular, ShReD-based partition of the metabolic network identified a 'redox' module that couples reactions of glucose, pyruvate, lipid and drug metabolism through shared production and consumption of NADPH. Our results suggest that retroactive interactions arising from feedback loops and metabolic cycles significantly contribute to the modularity of biochemical networks. For metabolic networks, cofactors play an important role as allosteric effectors that mediate the retroactive interactions.

3-D integrated circuits promise high bandwidth, low latency, low device power, and a small form factor. Increased device density and asymmetrical packaging, however, renders the design of 3-D power delivery a challenge. We investigate in this paper various methods to improve 3-D power delivery. We analyze the impact of through-silicon via (TSV) size and spacing, of controlled collapse chip connection (C4) spacing, and of dedicated power delivery TSVs. In addition to considering typical cylindrical or square metal-filled TSVs (core TSVs), we also investigate using coaxial TSVs for power delivery resulting in reduced routing blockages and added coupling capacitance. Our 3-D evaluation system is composed of a quad-core chip multiprocessor, a memory die, and an accelerator engine, and it is evaluated using representative SPEC benchmark traces. This is the first detailed architectural-level analysis for 3-D power delivery. Our findings provide clear guidelines for 3-D power delivery design. More importantly, we show that it is possible to achieve 2-D-like, or even better, power quality by increasing C4 granularity and by selecting suitable TSV size and spacing.

In the nascent field of synthetic biology, researchers are striving to create biological systems with functionality not seen in nature. This special session features talks that emphasize the fundamental engineering principles underlying this endeavor, highlighting possible synergies with electronic design automation (EDA). Pamela Silver will describe designing and constructing proteins and cells with predictable biological properties. These serve as potential therapeutics, cell-based sensors, factories for generating bio-energy, and bio-remediation. J. Christopher Anderson will demonstrate how complex biological functions can be decomposed into modular devices. He will describe the construction of therapeutic organisms and new tools for building complex systems. Richard Murray will discuss the use of concepts from control and dynamical systems in the analysis and design of biological feedback circuits at the molecular level.

As device dimensions shrink into the nanometer range, power and performance constraints prohibit the longevity of traditional MOS devices in circuit design. FinFETs, a quasi-planar double-gated device, has emerged as a replacement. While flnFETs provide promising electrostatic characteristics, they have the potential to suffer from significant self heating. We study in this paper self heating in multi-fin devices. We first develop thermal models for an individual fin with flared channel extensions and for multi-fin devices. We analyze several fin geometric parameters (fin width, and (gate) length) and investigate how fin spacing, fin height, gate oxide thickness and gate height affect the maximum fin temperatures in rectangular and flared channel extensions. Our data derived from numerical simulation validates our findings. We develop a novel metric, metric for electro-thermal sensitivity (METS), for measuring device thermal robustness. We use the metric to investigate electro-thermal device sensitivities. The metric, while applied to finFETs in this paper, is general and can be applied to any type of device for which coupled electrical and thermal models exist. Our work is the first to address thermal issues within multi-fin devices and to develop a widely-applicable electro-thermal metric.

FinFET devices promise to replace traditional MOSFETs because of superior ability in controlling leakage and minimizing short channel effects while delivering a strong drive current. We investigate in this paper gate sizing of finFET devices, and we provide a comparison with 32nm bulk CMOS. Wider finFET devices are built utilizing multiple parallel fins between the source and drain. Independent gating of the finFET's double gates allows significant reduction in leakage current. We perform temperature-aware circuit optimization by modeling delay using temperature-dependent parameters, and by imposing constraints that limit the maximum allowable number of parallel fins. We show that finFET circuits are superior in performance and produce less static power when compared to 32nm circuits.

The availability of millions of transistors on a single chip has allowed the creation of complex on-chip systems. The functional verification of such systems has become a challenge. Simulation run times are increasing, and emulation is now a necessity. Creating separate verification environments for simulation and emulation slows the design cycle and it requires additional human efforts. This paper describes a layered architecture suitable for both simulation and emulation. The architecture uses transactions for communication and synchronization between the driving environment (DE) and the device under test (DUT). Transactions provide synchronization only as needed and cycle and event-based synchronization common in emulators. The result is more efficient development of the DE and 100% portability when moving from simulation to emulation. We give an overview of our layered architecture and describe its implementation. Our results show that, by using emulation, the register-transfer level (RTL) implementation of an industrial design can be verified in the same amount of time it takes to run a C-based simulation. We also show two orders of magnitude speeds up over simulations of C and RTL through a programming language interface

Shrinking process geometries and the increasing use of intellectual property components in system-on-chip designs give rise to new problems in routing and buffer insertion. A particular concern is that cross-chip routing will require multiple clock cycles. Another is the integration of independently clocked components. This paper explores simultaneous routing and buffer insertion in the context of single- and multiple-clock domains. We present two optimal and efficient polynomial algorithms that build upon the dynamic programming fast path framework. The first algorithm solves the problem of finding the minimum latency path for a single-clock domain system. The second considers routing between two components that are locally synchronous yet globally asynchronous to each other. Both algorithms can be used for interconnect planning. Experimental results verify the correctness and practicality of our approach.

Static timing analysis is instrumental in efficiently verifying a design's temporal behavior to ensure correct functionality at the required frequency. This paper addresses static timing analysis in the presence of crosstalk for circuits containing level-sensitive latches, typical in high-performance designs. The paper focuses on two problems. First, coupling in a sequential circuit can occur because of the proximity of a victim's switching input to any periodic occurrence of the aggressor's input switching window. This paper shows that only three consecutive periodic occurrences of the aggressor's input switching window must be considered. Second, an arrival time in a sequential circuit is typically computed relative to a specific clock phase. The paper proposes a new phase shift operator to align the aggressor's three relevant switching windows with the victim's input signals. This paper solves the static analysis problem for level-clocked circuits iteratively in polynomial time, and it shows an upper bound on the number of iterations equal to the number of capacitors in the circuit. The contributions of this paper hold for any discrete overlapping coupling model. The experimental results demonstrate that eliminating false coupling allows finding a smaller clock period at which a circuit will run.

This paper addresses verifying the timing of circuits containing level-sensitive latches in the presence of crosstalk We show that three consecutive periodic occurrences of the aggressor's input switching window must be compared with the victim's input switching window. We propose a new phase shift operator to allow aligning the aggressor's three relevant switching windows with the victim's input signals. We solve the problem iteratively in polynomial time, and show an upper bound on the number of iterations equal to the number of capacitors in the circuit. Our experiments demonstrate that eliminating false coupling results in finding a smaller clock period at which a circuit will run.

Shrinking process geometries and the increasing use of IP components in SoC designs give rise to new problems in routing and buffer insertion. A particular concern is that cross-chip routing will require multiple clock cycles. Another is the integration of independently clocked components. This paper explores simultaneous routing and buffer insertion in the context of single and multiple clock domains. We present optimal and efficient polynomial algorithms that can be used to estimate communication overhead for interconnect and resource planning in single and multi-clock domain systems. Experimental results verify the correctness and practicality of our approach.

A transaction-based layered architecture providing for 100% portability of a C-based testbench between simulation and emulation is proposed. Transaction-based communication results in performance which is commensurate with emulation without a hardware target. Testbench portability eliminates duplicated effort when combining system level simulation and emulation. An implementation based on the IKOS VStation emulator validates these architectural claims on real designs.

This paper focuses on static timing analysis in the presence of capacitive coupling. We propose a novel gate delay model, the dynamically bounded delay model. In contrast to the min-max or bounded delay model which assumes a fixed delay range, [dmin, dmax], for each circuit component, our new model allows for the specification of delay variations and the conditions upon which the variations will hold. Novel static timing analysis algorithms can thus dynamically bound the delays. To demonstrate the effectiveness of this model and approach, we use our model to perform critical path analysis in the presence of capacitive coupling. Our experiments show that our approach avoids pessimism when compared to PERT analysis assuming worst case capacitive coupling.

Identifying repeating structural regularities in circuits allows the minimization of synthesis, optimization, and layout efforts. We introduce in this paper a novel method for identifying a set of repeating circuit structures, referred to as templates, and we report on using an efficient binate cover solver to select an appropriate subset of templates with which to cover the circuit. Our approach is comprised of three steps. First, the circuit graph is decomposed in a hierarchical inclusion parse tree using a clan-based decomposition algorithm. This algorithm discovers clans, grouping of nodes in the circuit graph that have a natural affinity towards each other. Second, the parse tree nodes are classified into equivalence classes. Such classes represent templates suitable for circuit covering. The final step consists of using a binate cover solver to find an appropriate cover. The cover will consist of instantiated templates and gates that cannot be covered by any templates. We describe the results of applying this algorithm to several circuits, and show that the algorithm is effective in extracting structural regularity.

Abstract { Although tremendous advances have been accom-plished in logic synthesis in the past two decades, in some cases logic synthesis still cannot attain the improvements possible by clever designers. This, in part, is a result of logic synthesis not optimizing across register boundaries. In this paper we focus on precomputation as a resynthesis technique capable of resyn-thesizing across register boundaries. By using precomputation, a critical signal is computed earlier in time, thus allowing it to be combinationally optimized with logic from previous pipeline stages. Precomputation automatically discovers some standard circuit transformations like bypassing and lookahead. In addi-tion, precomputation can be used in conjunction with combina-tional logic synthesis to resynthesize a circuit to obtain better performance. This paper contributes to the understanding and development of precomputation. First, it provides a synthesis algorithm for precomputation. Second, it demonstrates how precomputation can be used to improve sequential logic resynthesis and reports the results of applyinga heuristic to a subset of theMCNC bench-marks. Third, it illustrates how precomputation generalizes and uni es bypassing and lookahead { two important and practical architectural transformations often used in processor design and high-level synthesis of DSP processors. Finally, it claries the relationships among precomputation, retiming, and implicit re-timing. 1

This paper presents a new optimization technique called architectural retiming which is able to improve the performance of many latency-constrained circuits.Architectural retiming achieves this by increasing the number of registers on the latency-constrained path while preserving the functionality and latency of the circuit.This is done using the concept of a negative register, which can be implemented using precomputation and prediction.We use the name architectural retiming since it both reschedules operations in time and modi es the structure of the circuit to preserve its functionality.We illustrate the use of architectural retiming on two realistic examples and present performance improvement results for a number of sample circuits.

We propose a machine architecture for a high-performance processing node for a message-passing, MIMD concurrent computer. The principal mechanisms for attaining this goal are the direct execution and buffering of messages and a memory-based architecture that permits very fast context switches. Our architecture also includes a novel memory organization that permits both indexed and associative accesses and that incorporates an instruction buffer and message queue. Simulation results suggest that this architecture reduces message reception overhead by more than an order of magnitude.