RESUMO
A mapping α:V(G)âV(H) from the vertex set of one graph G to another graph H is an isometric embedding if the shortest path distance between any two vertices in G equals the distance between their images in H. Here, we consider isometric embeddings of a weighted graph G into unweighted Hamming graphs, called Hamming embeddings, when G satisfies the property that every edge is a shortest path between its endpoints. Using a Cartesian product decomposition of G called its canonical isometric representation, we show that every Hamming embedding of G may be partitioned into a canonical partition, whose parts provide Hamming embeddings for each factor of the canonical isometric representation of G. This implies that G permits a Hamming embedding if and only if each factor of its canonical isometric representation is Hamming embeddable. This result extends prior work on unweighted graphs that showed that an unweighted graph permits a Hamming embedding if and only if each factor is a complete graph. When a graph G has nontrivial isometric representation, determining whether G has a Hamming embedding can be simplified to checking embeddability of two or more smaller graphs.
RESUMO
For unweighted graphs, finding isometric embeddings of a graph G is closely related to decompositions of G into Cartesian products of smaller graphs. When G is isomorphic to a Cartesian graph product, we call the factors of this product a factorization of G. When G is isomorphic to an isometric subgraph of a Cartesian graph product, we call those factors a pseudofactorization of G. Prior work has shown that an unweighted graph's pseudofactorization can be used to generate a canonical isometric embedding into a product of the smallest possible pseudofactors. However, for arbitrary weighted graphs, which represent a richer variety of metric spaces, methods for finding isometric embeddings or determining their existence remain elusive, and indeed pseudofactorization and factorization have not previously been extended to this context. In this work, we address the problem of finding the factorization and pseudofactorization of a weighted graph G, where G satisfies the property that every edge constitutes a shortest path between its endpoints. We term such graphs minimal graphs, noting that every graph can be made minimal by removing edges not affecting its path metric. We generalize pseudofactorization and factorization to minimal graphs and develop new proof techniques that extend the previously proposed algorithms due to Graham and Winkler [Graham and Winkler, '85] and Feder [Feder, '92] for pseudofactorization and factorization of unweighted graphs. We show that any n-vertex, m-edge graph with positive integer edge weights can be factored in O(m2) time, plus the time to find all pairs shortest paths (APSP) distances in a weighted graph, resulting in an overall running time of O(m2+n2 log log n) time. We also show that a pseudofactorization for such a graph can be computed in O(mn) time, plus the time to solve APSP, resulting in an O(mn+n2 log log n) running time.
RESUMO
DNA is an ultrahigh-density storage medium that could meet exponentially growing worldwide demand for archival data storage if DNA synthesis costs declined sufficiently and if random access of files within exabyte-to-yottabyte-scale DNA data pools were feasible. Here, we demonstrate a path to overcome the second barrier by encapsulating data-encoding DNA file sequences within impervious silica capsules that are surface labelled with single-stranded DNA barcodes. Barcodes are chosen to represent file metadata, enabling selection of sets of files with Boolean logic directly, without use of amplification. We demonstrate random access of image files from a prototypical 2-kilobyte image database using fluorescence sorting with selection sensitivity of one in 106 files, which thereby enables one in 106N selection capability using N optical channels. Our strategy thereby offers a scalable concept for random access of archival files in large-scale molecular datasets.
Assuntos
DNA/química , Armazenamento e Recuperação da Informação , Arquivos , Fluorescência , Plasmídeos , Reação em Cadeia da Polimerase , Dióxido de Silício/química , Biologia SintéticaRESUMO
MOTIVATION: The study of T cell receptor (TCR) repertoires has generated new insights into immune system recognition. However, the ability to robustly characterize these populations has been limited by technical barriers and an inability to reliably infer heterodimeric chain pairings for TCRs. RESULTS: Here, we describe a novel analytical approach to an emerging immune repertoire sequencing method, improving the resolving power of this low-cost technology. This method relies upon the distribution of a T cell population across a 96-well plate, followed by barcoding and sequencing of the relevant transcripts from each T cell. Multicell Analytical Deconvolution for High Yield Paired-chain Evaluation (MAD-HYPE) uses Bayesian inference to more accurately extract TCR information, improving our ability to study and characterize T cell populations for immunology and immunotherapy applications. AVAILABILITY AND IMPLEMENTATION: The MAD-HYPE algorithm is released as an open-source project under the Apache License and is available from https://github.com/birnbaumlab/MAD-HYPE. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.
Assuntos
Linfócitos T , Algoritmos , Teorema de Bayes , Imunoterapia , Receptores de Antígenos de Linfócitos TRESUMO
The surge in nucleic acid analytics requires scalable storage and retrieval systems akin to electronic databases used to organize digital data. Such a system could transform disease diagnosis, ecological preservation, and molecular surveillance of biothreats. Current storage systems use individual containers for nucleic acid samples, requiring single-sample retrieval that falls short compared with digital databases that allow complex and combinatorial data retrieval on aggregated data. Here, we leverage protective microcapsules with combinatorial DNA labeling that enables arbitrary retrieval on pooled biosamples analogous to Structured Query Languages. Ninety-six encapsulated pooled mock SARS-CoV-2 genomic samples barcoded with patient metadata are used to demonstrate queries with simultaneous matches to sample collection date ranges, locations, and patient health statuses, illustrating how such flexible queries can be used to yield immunological or epidemiological insights. The approach applies to any biosample database labeled with orthogonal barcodes, enabling complex post-hoc analysis, for example, to study global biothreat epidemiology.
RESUMO
It has been observed that the performing for high stakes can, paradoxically, lead to uncharacteristically poor performance. Here we investigate a novel approach to attenuating such 'choking under pressure' by instructing participants performing a demanding motor task that rewards successful performance with a monetary gain, to reappraise this incentive as a monetary loss for unsuccessful performance. We show that when participants applied this simple strategy, choking was significantly reduced. This strategy also influenced participants' neural and physiological activity. When participants reappraised the incentive as a potential monetary loss, the representation of the magnitude of the incentive in the ventral striatum Blood Oxygenation Level Dependent (BOLD) signal was attenuated. In addition, individual differences in the degree of attenuation of the neural response to incentive predicted the effectiveness of the reappraisal strategy in reducing choking. Furthermore, participants' skin conductance changed in proportion to the magnitude of the incentive being played for, and was exaggerated on high incentive trials on which participants failed. Reappraisal of the incentive abolished this exaggerated skin conductance response. This represents the first experimental association of sympathetic arousal with choking. Taken together, these results suggest that reappraisal of the incentive is indeed a promising intervention for attenuating choking under pressure.
Assuntos
Motivação/fisiologia , Desempenho Psicomotor/fisiologia , Adolescente , Adulto , Mapeamento Encefálico , Feminino , Resposta Galvânica da Pele , Jogo de Azar/psicologia , Humanos , Individualidade , Imageamento por Ressonância Magnética , Masculino , Pessoa de Meia-Idade , Destreza Motora/fisiologia , Oxigênio/sangue , Recompensa , Sistema Nervoso Simpático/fisiologia , Estriado Ventral/diagnóstico por imagem , Estriado Ventral/fisiologia , Adulto JovemRESUMO
As an engineering material, DNA is well suited for the construction of biochemical circuits and systems, because it is simple enough that its interactions can be rationally designed using Watson-Crick base pairing rules, yet the design space is remarkably rich. When designing DNA systems, this simplicity permits using functional sections of each strand, called domains, without considering particular nucleotide sequences. However, the actual sequences used may have interactions not predicted at the domain-level abstraction, and new rigorous analysis techniques are needed to determine the extent to which the chosen sequences conform to the system's domain-level description. We have developed a computational method for verifying sequence-level systems by identifying discrepancies between the domain-level and sequence-level behaviour. This method takes a DNA system, as specified using the domain-level tool Peppercorn, and analyses data from the stochastic sequence-level simulator Multistrand and sequence-level thermodynamic analysis tool NUPACK to estimate important aspects of the system, such as reaction rate constants and secondary structure formation. These techniques, implemented as the Python package KinDA, will allow researchers to predict the kinetic and thermodynamic behaviour of domain-level systems after sequence assignment, as well as to detect violations of the intended behaviour.
Assuntos
DNA/genética , Análise de Sequência de DNA , DNA/química , Cinética , TermodinâmicaRESUMO
Biochemical circuits made of rationally designed DNA molecules are proofs of concept for embedding control within complex molecular environments. They hold promise for transforming the current technologies in chemistry, biology, medicine and material science by introducing programmable and responsive behaviour to diverse molecular systems. As the transformative power of a technology depends on its accessibility, two main challenges are an automated design process and simple experimental procedures. Here we demonstrate the use of circuit design software, combined with the use of unpurified strands and simplified experimental procedures, for creating a complex DNA strand displacement circuit that consists of 78 distinct species. We develop a systematic procedure for overcoming the challenges involved in using unpurified DNA strands. We also develop a model that takes synthesis errors into consideration and semi-quantitatively reproduces the experimental data. Our methods now enable even novice researchers to successfully design and construct complex DNA strand displacement circuits.