Search for: All records

Candecomp / PARAFAC (CP) decomposition, a generalization of the matrix singular value decomposition to higher-dimensional tensors, is a popular tool for analyzing multidimensional sparse data. On tensors with billions of nonzero entries, computing a CP decomposition is a computationally intensive task. We propose the first distributed-memory implementations of two randomized CP decomposition algorithms,CP-ARLS-LEV and STS-CP, that offer nearly an order-of-magnitude speedup at high decomposition ranks over well-tuned non-randomized decomposition packages. Both algorithms rely on leverage score sampling and enjoy strong theoretical guarantees, each with varying time and accuracy tradeoffs. We tailor the communication schedule for our random sampling algorithms, eliminating expensive reduction collectives and forcing communication costs to scale with the random sample count. Finally, we optimize the local storage format for our methods, switching between analogues of compressed sparse column and compressed sparse row formats. Experiments show that our methods are fast and scalable,producing 11x speedup over SPLATT by decomposing the billion-scale Reddit tensor on 512 CPU cores in under two minutes. 

We present a data structure to randomly sample rows from the Khatri-Rao product of several matrices according to the exact distribution of its leverage scores. Our proposed sampler draws each row in time logarithmic in the height of the Khatri-Rao product and quadratic in its column count, with persistent space overhead at most the size of the input matrices. As a result, it tractably draws samples even when the matrices forming the Khatri-Rao product have tens of millions of rows each. When used to sketch the linear least squares problems arising in CANDECOMP / PARAFAC tensor decomposition, our method achieves lower asymptotic complexity per solve than recent state-of-the-art methods. Experiments on billion-scale sparse tensors validate our claims, with our algorithm achieving higher accuracy than competing methods as the decomposition rank grows. 

Making cells magnetic is a long‐standing goal of chemical biology, aiming to enable the separation of cells from complex biological samples and their visualization in vivo using magnetic resonance imaging (MRI). Previous efforts towards this goal, focused on engineering cells to biomineralize superparamagnetic or ferromagnetic iron oxides, have been largely unsuccessful due to the stringent required chemical conditions. Here, we introduce an alternative approach to making cells magnetic, focused on biochemically maximizing cellular paramagnetism. We show that a novel genetic construct combining the functions of ferroxidation and iron chelation enables engineered bacterial cells to accumulate iron in “ultraparamagnetic” macromolecular complexes, allowing these cells to be trapped with magnetic fields and imaged with MRI in vitro and in vivo. We characterize the properties of these cells and complexes using magnetometry, nuclear magnetic resonance, biochemical assays, and computational modeling to elucidate the unique mechanisms and capabilities of this paramagnetic concept.

 

Making cells magnetic is a long‐standing goal of chemical biology, aiming to enable the separation of cells from complex biological samples and their visualization in vivo using magnetic resonance imaging (MRI). Previous efforts towards this goal, focused on engineering cells to biomineralize superparamagnetic or ferromagnetic iron oxides, have been largely unsuccessful due to the stringent required chemical conditions. Here, we introduce an alternative approach to making cells magnetic, focused on biochemically maximizing cellular paramagnetism. We show that a novel genetic construct combining the functions of ferroxidation and iron chelation enables engineered bacterial cells to accumulate iron in “ultraparamagnetic” macromolecular complexes, allowing these cells to be trapped with magnetic fields and imaged with MRI in vitro and in vivo. We characterize the properties of these cells and complexes using magnetometry, nuclear magnetic resonance, biochemical assays, and computational modeling to elucidate the unique mechanisms and capabilities of this paramagnetic concept.

 

The mechanistic underpinnings of the complex process of plant polysaccharide biosynthesis are poorly understood, largely because of the resistance of glycosyltransferase (GT) enzymes to structural characterization. InArabidopsis thaliana,a glycosyl transferase family 37 (GT37) fucosyltransferase 1 (AtFUT1) catalyzes the regiospecific transfer of terminal 1,2‐fucosyl residues to xyloglucan side chains – a key step in the biosynthesis of fucosylated sidechains of galactoxyloglucan. We unravel the mechanistic basis for fucosylation byAtFUT1 with a multipronged approach involving protein expression, X‐ray crystallography, mutagenesis experiments and molecular simulations. Mammalian cell culture expressions enable the sufficient production of the enzyme for X‐ray crystallography, which reveals the structural architecture ofAtFUT1 in complex with bound donor and acceptor substrate analogs. The lack of an appropriately positioned active site residue as a catalytic base leads us to propose an atypical water‐mediated fucosylation mechanism facilitated by an H‐bonded network, which is corroborated by mutagenesis experiments as well as detailed atomistic simulations.