More Like this

1. Improving RNA Branching Predictions: Advances and Limitations

   https://doi.org/10.3390/genes12040469  

   Poznanović, Svetlana; Wood, Carson; Cloer, Michael; Heitsch, Christine (April 2021, Genes)

   null (Ed.)

   Minimum free energy prediction of RNA secondary structures is based on the Nearest Neighbor Thermodynamics Model. While such predictions are typically good, the accuracy can vary widely even for short sequences, and the branching thermodynamics are an important factor in this variance. Recently, the simplest model for multiloop energetics—a linear function of the number of branches and unpaired nucleotides—was found to be the best. Subsequently, a parametric analysis demonstrated that per family accuracy can be improved by changing the weightings in this linear function. However, the extent of improvement was not known due to the ad hoc method used to find the new parameters. Here we develop a branch-and-bound algorithm that finds the set of optimal parameters with the highest average accuracy for a given set of sequences. Our analysis shows that the previous ad hoc parameters are nearly optimal for tRNA and 5S rRNA sequences on both training and testing sets. Moreover, cross-family improvement is possible but more difficult because competing parameter regions favor different families. The results also indicate that restricting the unpaired nucleotide penalty to small values is warranted. This reduction makes analyzing longer sequences using the present techniques more feasible. 

   more » « less
2. Markov Chain-Based Sampling for Exploring RNA Secondary Structure under the Nearest Neighbor Thermodynamic Model and Extended Applications

   https://doi.org/10.3390/mca25040067  

   Kirkpatrick, Anna; Patton, Kalen; Tetali, Prasad; Mitchell, Cassie (December 2020, Mathematical and Computational Applications)

   null (Ed.)

   Ribonucleic acid (RNA) secondary structures and branching properties are important for determining functional ramifications in biology. While energy minimization of the Nearest Neighbor Thermodynamic Model (NNTM) is commonly used to identify such properties (number of hairpins, maximum ladder distance, etc.), it is difficult to know whether the resultant values fall within expected dispersion thresholds for a given energy function. The goal of this study was to construct a Markov chain capable of examining the dispersion of RNA secondary structures and branching properties obtained from NNTM energy function minimization independent of a specific nucleotide sequence. Plane trees are studied as a model for RNA secondary structure, with energy assigned to each tree based on the NNTM, and a corresponding Gibbs distribution is defined on the trees. Through a bijection between plane trees and 2-Motzkin paths, a Markov chain converging to the Gibbs distribution is constructed, and fast mixing time is established by estimating the spectral gap of the chain. The spectral gap estimate is obtained through a series of decompositions of the chain and also by building on known mixing time results for other chains on Dyck paths. The resulting algorithm can be used as a tool for exploring the branching structure of RNA, especially for long sequences, and to examine branching structure dependence on energy model parameters. Full exposition is provided for the mathematical techniques used with the expectation that these techniques will prove useful in bioinformatics, computational biology, and additional extended applications. 

   more » « less
3. Space colonization by branching trachea explains the morphospace of a simple respiratory organ

   https://doi.org/10.1016/j.ydbio.2020.02.005  

   Ruiz-Sobrino, A.; Martín-Blanco, C.A.; Navarro, T.; Almudí, I.; Masiero, G.; Jiménez-Caballero, M.; Buchwalter, D.B.; Funk, D.H.; Gattolliat, J.L.; Lemos, M.C.; et al (June 2020, Developmental Biology)

   n/a (Ed.)

   Branching morphogenesis helps increase the efficiency of gas and liquid transport in many animal organs. Studies in several model organisms have highlighted the molecular and cellular complexity behind branching morphogenesis. To understand this complexity, computational models have been developed with the goal of identifying the “major rules” that globally explain the branching patterns. These models also guide further experimental exploration of the biological processes that execute and maintain these rules. In this paper we introduce the tracheal gills of mayfly (Ephemeroptera) larvae as a model system to study the generation of branched respiratory patterns. First, we describe the gills of the mayfly Cloeon dipterum, and quantitatively characterize the geometry of its branching trachea. We next extend this characterization to those of related species to generate the morphospace of branching patterns. Then, we show how an algorithm based on the “space colonization” concept (SCA) can generate this branching morphospace via growth towards a hypothetical attractor molecule (M). SCA differs from other branch-generating algorithms in that the geometry generated depends to a great extent on its perception of the “external” space available for branching, uses few rules and, importantly, can be easily translated into a realistic “biological patterning algorithm”. We identified a gene in the C. dipterum genome (Cd-bnl) that is orthologous to the fibroblast growth factor branchless (bnl), which stimulates growth and branching of embryonic trachea in Drosophila. In C. dipterum, this gene is expressed in the gill margins and areas of finer tracheolar branching from thicker trachea. Thus, Cd-bnl may perform the function of M in our model. Finally, we discuss this general mechanism in the context of other branching pattern-generating algorithms. 

   more » « less
4. Distributed-Memory Parallel Algorithms for Sparse Matrix and Sparse Tall-and-Skinny Matrix Multiplication

   https://doi.org/10.1109/SC41406.2024.00052  

   Ranawaka, Isuru; Hussain, Md Taufique; Block, Charles; Gerogiannis, Gerasimos; Torrellas, Josep; Azad, Ariful (November 2024, IEEE)

   We consider a sparse matrix-matrix multiplication (SpGEMM) setting where one matrix is square and the other is tall and skinny. This special variant, TS-SpGEMM, has important applications in multi-source breadth-first search, influence maximization, sparse graph embedding, and algebraic multigrid solvers. Unfortunately, popular distributed algorithms like sparse SUMMA deliver suboptimal performance for TS-SpGEMM. To address this limitation, we develop a novel distributed-memory algorithm tailored for TS SpGEMM. Our approach employs customized 1D partitioning for all matrices involved and leverages sparsity-aware tiling for efficient data transfers. In addition, it minimizes communication overhead by incorporating both local and remote computations. On average, our TSSpGEMM algorithm attains 5x performance gains over 2D and 3D SUMMA. Furthermore, we use our algorithm to implement multi-source breadth-first search and sparse graph embedding algorithms and demonstrate their scalability up to 512 Nodes (or 65,536 cores) on NERSC Perlmutter. 

   more » « less
5. Estimating atmospheric motion winds from satellite image data using space‐time drift models

   https://doi.org/10.1002/env.2818  

   Sahoo, Indranil; Guinness, Joseph; Reich, Brian J. (December 2023, Environmetrics)

   Abstract Geostationary weather satellites collect high‐resolution data comprising a series of images. The Derived Motion Winds (DMW) Algorithm is commonly used to process these data and estimate atmospheric winds by tracking features in the images. However, the wind estimates from the DMW Algorithm are often missing and do not come with uncertainty measures. Also, the DMW Algorithm estimates can only be half‐integers, since the algorithm requires the original and shifted data to be at the same locations, in order to calculate the displacement vector between them. This motivates us to statistically model wind motions as a spatial process drifting in time. Using a covariance function that depends on spatial and temporal lags and a drift parameter to capture the wind speed and wind direction, we estimate the parameters by local maximum likelihood. Our method allows us to compute standard errors of the local estimates, enabling spatial smoothing of the estimates using a Gaussian kernel weighted by the inverses of the estimated variances. We conduct extensive simulation studies to determine the situations where our method performs well. The proposed method is applied to the GOES‐15 brightness temperature data over Colorado and reduces prediction error of brightness temperature compared to the DMW Algorithm. 

   more » « less