More Like this

1. Systematic Enumeration and Identification of Unique Spatial Topologies of 3D Systems Using Spatial Graph Representations

   https://doi.org/10.1115/DETC2021-66900  

   Peddada, Satya R.; Dunfield, Nathan M.; Zeidner, Lawrence E.; James, Kai A.; Allison, James T. (August 2021, 47th Design Automation Conference (DAC))

   Systematic enumeration and identification of unique 3D spatial topologies of complex engineering systems such as automotive cooling layouts, hybrid-electric power trains, and aero-engines are essential to search their exhaustive design spaces to identify spatial topologies that can satisfy challenging system requirements. However, efficient navigation through discrete 3D spatial topology options is a very challenging problem due to its combinatorial nature and can quickly exceed human cognitive abilities at even moderate complexity levels. Here we present a new, efficient, and generic design framework that utilizes mathematical spatial graph theory to represent, enumerate, and identify distinctive 3D topological classes for an abstract engineering system, given its system architecture (SA) — its components and interconnections. Spatial graph diagrams (SGDs) are generated for a given SA from zero to a specified maximum crossing number. Corresponding Yamada polynomials for all the planar SGDs are then generated. SGDs are categorized into topological classes, each of which shares a unique Yamada polynomial. Finally, for each topological class, one 3D geometric model is generated for an SGD with the fewest interconnect crossings. Several case studies are shown to illustrate the different features of our proposed framework. Design guidelines are also provided for practicing engineers to aid the utilization of this framework for application to different types of real-world problems. 

   more » « less
2. ST-FiT: Inductive Spatial-Temporal Forecasting with Limited Training Data

   https://doi.org/10.1609/aaai.v39i11.33310  

   Lei, Zhenyu; Dong, Yushun; Li, Jundong; Chen, Chen (April 2025, Proceedings of the AAAI Conference on Artificial Intelligence)

   Spatial-temporal graphs are widely used in a variety of real-world applications. Spatial-Temporal Graph Neural Networks (STGNNs) have emerged as a powerful tool to extract meaningful insights from this data. However, in real-world applications, most nodes may not possess any available temporal data during training. For example, the pandemic dynamics of most cities on a geographical graph may not be available due to the asynchronous nature of outbreaks. Such a phenomenon disagrees with the training requirements of most existing spatial-temporal forecasting methods, which jeopardizes their effectiveness and thus blocks broader deployment. In this paper, we propose to formulate a novel problem of inductive forecasting with limited training data. In particular, given a spatial-temporal graph, we aim to learn a spatial-temporal forecasting model that can be easily generalized onto those nodes without any available temporal training data. To handle this problem, we propose a principled framework named ST-FiT. ST-FiT consists of two key learning components: temporal data augmentation and spatial graph topology learning. With such a design, ST-FiT can be used on top of any existing STGNNs to achieve superior performance on the nodes without training data. Extensive experiments verify the effectiveness of ST-FiT in multiple key perspectives. 

   more » « less
3. A geometric framework for reaction enumeration in computational nucleic acid devices

   https://doi.org/10.1098/rsif.2023.0259  

   Kumar, Sarika; Lakin, Matthew R (November 2023, Journal of The Royal Society Interface)

   Cascades of DNA strand displacement reactions enable the design of potentially large circuits with complex behaviour. Computational modelling of such systems is desirable to enable rapid design and analysis. In previous work, the expressive power of graph theory was used to enumerate reactions implementing strand displacement across a wide range of complex structures. However, coping with the rich variety of possible graph-based structures required enumeration rules with complicated side-conditions. This paper presents an alternative approach to tackle the problem of enumerating reactions at domain level involving complex structures by integrating with a geometric constraint solving algorithm. The rule sets from previous work are simplified by replacing side-conditions with a general check on the geometric plausibility of structures generated by the enumeration algorithm. This produces a highly general geometric framework for reaction enumeration. Here, we instantiate this framework to solve geometric constraints by a structure sampling approach in which we randomly generate sets of coordinates and check whether they satisfy all the constraints. We demonstrate this system by applying it to examples from the literature where molecular geometry plays an important role, including DNA hairpin and remote toehold reactions. This work therefore enables integration of reaction enumeration and structural modelling. 

   more » « less
4. Deciphering high-order structures in spatial transcriptomes with graph-guided Tucker decomposition

   https://doi.org/10.1093/bioinformatics/btae245  

   Broadbent, Charles; Song, Tianci; Kuang, Rui (June 2024, Bioinformatics)

   Abstract  Spatial transcripome (ST) profiling can reveal cells’ structural organizations and functional roles in tissues. However, deciphering the spatial context of gene expressions in ST data is a challenge—the high-order structure hiding in whole transcriptome space over 2D/3D spatial coordinates requires modeling and detection of interpretable high-order elements and components for further functional analysis and interpretation. This paper presents a new method GraphTucker—graph-regularized Tucker tensor decomposition for learning high-order factorization in ST data. GraphTucker is based on a nonnegative Tucker decomposition algorithm regularized by a high-order graph that captures spatial relation among spots and functional relation among genes. In the experiments on several Visium and Stereo-seq datasets, the novelty and advantage of modeling multiway multilinear relationships among the components in Tucker decomposition are demonstrated as opposed to the Canonical Polyadic Decomposition and conventional matrix factorization models by evaluation of detecting spatial components of gene modules, clustering spatial coefficients for tissue segmentation and imputing complete spatial transcriptomes. The results of visualization show strong evidence that GraphTucker detect more interpretable spatial components in the context of the spatial domains in the tissues. Availability and implementationhttps://github.com/kuanglab/GraphTucker. 

   more » « less
5. STalign: Alignment of spatial transcriptomics data using diffeomorphic metric mapping

   https://doi.org/10.1038/s41467-023-43915-7  

   Clifton, Kalen; Anant, Manjari; Aihara, Gohta; Atta, Lyla; Aimiuwu, Osagie K.; Kebschull, Justus M.; Miller, Michael I.; Tward, Daniel; Fan, Jean (December 2023, Nature Communications)

   Abstract Spatial transcriptomics (ST) technologies enable high throughput gene expression characterization within thin tissue sections. However, comparing spatial observations across sections, samples, and technologies remains challenging. To address this challenge, we develop STalign to align ST datasets in a manner that accounts for partially matched tissue sections and other local non-linear distortions using diffeomorphic metric mapping. We apply STalign to align ST datasets within and across technologies as well as to align ST datasets to a 3D common coordinate framework. We show that STalign achieves high gene expression and cell-type correspondence across matched spatial locations that is significantly improved over landmark-based affine alignments. Applying STalign to align ST datasets of the mouse brain to the 3D common coordinate framework from the Allen Brain Atlas, we highlight how STalign can be used to lift over brain region annotations and enable the interrogation of compositional heterogeneity across anatomical structures. STalign is available as an open-source Python toolkit athttps://github.com/JEFworks-Lab/STalignand as Supplementary Software with additional documentation and tutorials available athttps://jef.works/STalign. 

   more » « less