Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Constructive Tree”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 37 records · Page 2
All sourcesNASA NTRSDOE OSTI
DOE OSTI2024

Poplar

SAND2025-00683O Poplar is a software tool that generates a phylogenetic tree from input gene and genome sequences. It integrates established tools to identify genes within genomes, group sequences, construct gene trees, and infer a species tree. Poplar processes nucleotide sequences, identifies similar sequences using Nucleotide BLAST, groups them with DBSCAN, aligns sequences with MAFFT, constructs gene trees with RAxML-NG, and infers a species tree using ASTRAL-Pro3. This pipeline provides a structured approach to phylogenetic analysis, facilitating the study of evolutionary relationships among species. Sandia National Laboratories is a multimission laboratory managed and operated by National Technology & Engineering Solutions of Sandia, LLC, a wholly owned subsidiary of Honeywell International Inc., for the U.S. Department of Energy’s National Nuclear Security Administration under contract DE-NA0003525.

Krishnakumar, Raga↗
DOE OSTI2022

Constructing high-fidelity halo merger trees in abacussummit

ABSTRACT Tracking the formation and evolution of dark matter haloes is a critical aspect of any analysis of cosmological N-body simulations. In particular, the mass assembly of a halo and its progenitors, encapsulated in the form of its merger tree, serves as a fundamental input for constructing semi-analytic models of galaxy formation and, more generally, for building mock catalogues that emulate galaxy surveys. We present an algorithm for constructing halo merger trees from abacussummit, the largest suite of cosmological N-body simulations performed to date consisting of nearly 60 trillion particles, and which has been designed to meet the Cosmological Simulation Requirements of the Dark Energy Spectroscopic Instrument (DESI) survey. Our method tracks the cores of haloes to determine associations between objects across multiple time slices, yielding lists of halo progenitors and descendants for the several tens of billions of haloes identified across the entire suite. We present an application of these merger trees as a means to enhance the fidelity of abacussummit halo catalogues by flagging and ‘merging’ haloes deemed to exhibit non-monotonic past merger histories. We show that this cleaning technique identifies portions of the halo population that have been deblended due to choices made by the halo finder, but which could have feasibly been part of larger aggregate systems. We demonstrate that by cleaning halo catalogues in this post-processing step, we remove potentially unphysical features in the default halo catalogues, leaving behind a more robust halo population that can be used to create highly accurate mock galaxy realizations from abacussummit.

79 ASTRONOMY AND ASTROPHYSICS↗
DOE OSTI2014

Characterizing quasiconvex functions in terms of the Kronrod's tree of a function

As an application of Kronrod's construction of the tree of a function to convex analysis, a characterization of quasiconvex functions is obtained. Namely, a function is quasiconvex if and only if the associated function defined on the tree of the original function is quasiconvex. A new proof of one of the existence lemmas in Kronrod's construction of the tree of a function (the original proof of which turned out to be incorrect) is given. Bibliography: 4 titles. (paper)

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2018

The zinc-finger transcription factor BcMF20 and its orthologs in Cruciferae which are required for pollen development

Highlights: • BcMF20 was a three-fingered protein and close to the four-fingered proteins of petunia. • The inhibition of BcMF20 led to fewer and lower rate in pollen germination. • The inhibition of BcMF20 led to lower rate in fruit setting. • BcMF20 may work in genetic pathways to act on proliferation of tapetal cells. • BcMF20 helps keep the normal development of pollens. Brassica campestris Male Fertility 20 (BcMF20) is a typical zinc-finger transcription factor that was previously isolated from flower buds of Chinese cabbage (Brassica campestris ssp. chinensis). By applying expression pattern analysis, it can be known that BcMF20 was specifically and strongly expressed in tapetum and pollen, beginning from the uninucleate stage, and was maintained during the mature-pollen stage. As BcMF20 was highly conserved in Cruciferae, it can be indicated that this zinc-finger transcription factor is important during the growth of Cruciferae. In this study, 12 C2H2-type zinc-finger TFs which shared high homology with BcMF20 were found from NCBI via BLAST. A new molecular phylogenetic tree was constructed by the comparison between BcMF20 and these 12 C2H2-type zinc-finger TFs with NJ method. By analyzing this phylogenetic tree, the evolution of BcMF20 was discussed. Then, antisense RNA technology was applied in the transgenesis of Arabidopsis thaliana to get the deletion mutants of BcMF20, so that its function during the pollen development can be identified. The results showed: BcMF20 are in the same clade with three genes from Arabidopsis. The inhibition of BcMF20 expression led to smaller amounts of and lower rate in germination of pollen and lower rate in fruit setting in certain transgenetic plants. This also led to the complete collapse of pollen grains. By SEM and TEM, pollen morphology and anther development processes were observed. In the middle uninucleate microspore stage, a relatively thin or even no primexine was formed in microspores. This may result in the malformation of the pollen wall and finally cause the deformity of pollens. Above all, it can be indicated that BcMF20 may act as a part of regulation mechanisms of TAZ1 and MS1. Together they play a role in a genetic pathway in the tapetum to act on proliferation of tapetal cells and keep the normal development of pollens.

60 APPLIED LIFE SCIENCES↗
DOE OSTI2014

Optimizing Data Locality for Fork/Join Programs Using Constrained Work Stealing

We present an approach to improving data locality across different phases of fork/join programs scheduled using work stealing. The approach consists of: (1) user-specified and automated approaches to constructing a steal tree, the schedule of steal operations and (2) constrained work stealing algorithms that constrain the actions of the scheduler to mirror a given steal tree. These are combined to construct work stealing schedules that maximize data locality across computation phases while ensuring load balance within each phase. These algorithms are also used to demonstrate dynamic coarsening, an optimization to improve spatial locality and sequential overheads by combining many finer-grained tasks into coarser tasks while ensuring sufficient concurrency for locality-optimized load balance. Implementation and evaluation in Cilk demonstrate performance improvements of up to 2.5x on 80 cores. We also demonstrate that dynamic coarsening can combine the performance benefits of coarse task specification with the adaptability of finer tasks.

cilk↗
DOE OSTI2022

A Mountaintop View Requires Minimal Sorting: A Faster Contour Tree Algorithm

Consider a scalar field f : M → R, where M is a triangulated simplicial mesh in R d . A level set, or contour, at value v is a connected component of f –1 (v). As v is changed, these contours change topology, merge into each other, or split. Contour trees are concise representations of f that track this contour behavior. The vertices of these trees are the critical points of f, where the gradient is zero. The edges represent changes in the topology of contours. It is a fundamental data structure in data analysis and visualization, and there is significant previous work (both theoretical and practical) on algorithms for constructing contour trees. Suppose M has n vertices, N facets, and t critical points. A classic result of Carr, Snoeyink, and Axen (2000) gives an algorithm that takes O(n log n+Nα(N)) time (where α(·) is the inverse Ackermann function). A further improvement to O(t log t + N) time was given by Chiang et al. All these algorithms involve a global sort of the critical points, a significant computational bottleneck. Unfortunately, lower bounds of Ω(t log t) also exist. We present the first algorithm that can avoid the global sort and has a refined time complexity that depends on the contour tree structure. Intuitively, if the tree is short and fat, we get significant improvements in running time. For a partition of the contour tree into a set of descending paths, P, our algorithm runs in O($\Sigma$ pϵP |p| log |p| + tα(t) + N). This is at most O(t log D + N), where D is the diameter of the contour tree. Moreover, it is O(tα(t) + N) for balanced trees, a significant improvement over the previous complexity. Our algorithm requires numerous ideas: partitioning the contour tree into join and split trees, a local growing procedure to iteratively build contour trees, and the use of heavy path decompositions for the time complexity analysis. There is a crucial use of a family of binomial heaps to maintain priorities, ensuring that any comparison made is between comparable nodes of the contour tree. We also prove lower bounds showing that the $\Sigma$ pϵP |p| log |p| complexity is inherent to computing contour trees.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2017

Tree tensor network approach to simulating Shor's algorithm

Constructively simulating quantum systems furthers our understanding of qualitative and quantitative features which may be analytically intractable. In this paper, we directly simulate and explore the entanglement structure present in the paradigmatic example for exponential quantum speedups: Shor's algorithm. To perform our simulation, we construct a dynamic tree tensor network which manifestly captures two salient circuit features for modular exponentiation. These are the natural two-register bipartition and the invariance of entanglement with respect to permutations of the top-register qubits. Our construction help identify the entanglement entropy properties, which we summarize by a scaling relation. Further, the tree network is efficiently projected onto a matrix product state from which we efficiently execute the quantum Fourier transform. In conclusion, future simulation of quantum information states with tensor networks exploiting circuit symmetries is discussed.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2014

Adaptive h -refinement for reduced-order models: ADAPTIVE h -refinement for reduced-order models

Our work presents a method to adaptively refine reduced-order models a posteriori without requiring additional full-order-model solves. The technique is analogous to mesh-adaptive h-refinement: it enriches the reduced-basis space online by ‘splitting’ a given basis vector into several vectors with disjoint support. The splitting scheme is defined by a tree structure constructed offline via recursive k-means clustering of the state variables using snapshot data. This method identifies the vectors to split online using a dual-weighted-residual approach that aims to reduce error in an output quantity of interest. The resulting method generates a hierarchy of subspaces online without requiring large-scale operations or full-order-model solves. Furthermore, it enables the reduced-order model to satisfy any prescribed error tolerance regardless of its original fidelity, as a completely refined reduced-order model is mathematically equivalent to the original full-order model. Experiments on a parameterized inviscid Burgers equation highlight the ability of the method to capture phenomena (e.g., moving shocks) not contained in the span of the original reduced basis.

42 ENGINEERING↗
DOE OSTI2014

Novel Human Radiation Exposure Biomarker Panel Applicable for Population Triage

Purpose: To identify a panel of radiation-responsive plasma proteins that could be used in a point-of-care biologic dosimeter to detect clinically significant levels of ionizing radiation exposure. Methods and Materials: Patients undergoing preparation for hematopoietic cell transplantation using radiation therapy (RT) with either total lymphoid irradiation or fractionated total body irradiation were eligible. Plasma was examined from patients with potentially confounding conditions and from normal individuals. Each plasma sample was analyzed for a panel of 17 proteins before RT was begun and at several time points after RT exposure. Paired and unpaired t tests between the dose and control groups were performed. Conditional inference trees were constructed based on panels of proteins to compare the non-RT group with the RT group. Results: A total of 151 patients (62 RT, 41 infection, 48 trauma) were enrolled on the study, and the plasma from an additional 24 healthy control individuals was analyzed. In comparison with to control individuals, tenascin-C was upregulated and clusterin was downregulated in patients receiving RT. Salivary amylase was strongly radiation responsive, with upregulation in total body irradiation patients and slight downregulation in total lymphoid irradiation patients compared with control individuals. A panel consisting of these 3 proteins accurately distinguished between irradiated patients and healthy control individuals within 3 days after exposure: 97% accuracy, 0.5% false negative rate, 2% false positive rate. The accuracy was diminished when patients with trauma, infection, or both were included (accuracy, 74%-84%; false positive rate, 14%-33%, false negative rate: 8%-40%). Conclusions: A panel of 3 proteins accurately distinguishes unirradiated healthy donors from those exposed to RT (0.8-9.6 Gy) within 3 days of exposure. These findings have significant implications in terms of triaging individuals in the case of nuclear or other radiologic events.

62 RADIOLOGY AND NUCLEAR MEDICINE↗
DOE OSTI2020

A quantum algorithm to efficiently sample from interfering binary trees

Quantum computers provide an opportunity to efficiently sample from probability distributions that include non-trivial interference effects between amplitudes. Using a simple process wherein all possible state histories can be specified by a binary tree, we construct an explicit quantum algorithm that runs in polynomial time to sample from the process once. The corresponding naive Markov Chain algorithm does not produce the correct probability distribution and an explicit classical calculation of the full distribution requires exponentially many operations. Finally, the problem can be reduced to a system of two qubits with repeated measurements, shedding light on a quantum-inspired efficient classical algorithm.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2025

Decision-tree structures utilizing a phase-transition material

The rich internal physics due to competing electronic phases present in phase-transition materials such as VO2 offer the potential for compact building block design for emerging non-von Neumann computing technologies. Here, based on the relaxation dynamics of an insulator-metal phase transition, we demonstrate experimentally a decision-tree classifier embedded within a single volatile resistive switching device. The tree is constructed by the combination of the voltage pulse and relaxation time and can adapt to different tasks. We use machine learning to analyze the relaxation process, enabling a predictive voltage-relaxation time phase diagram for the electrical resistance state. Classification of the etiology of the chronic cough is presented as a proof-of-principle use case. Further, our approach can be generalized to broader classes of solid-state and solid-liquid interfacial systems that demonstrate a variety of phase relaxations.

36 MATERIALS SCIENCE↗
DOE OSTI2024

Momentum shift and on-shell constructible massive amplitudes

We construct tree-level amplitude for massive particles using on-shell recursion relations based on two classes of momentum shifts: an all-line transverse shift that deforms momentum by its transverse polarization vector, and a massive Britto-Cachazo-Feng-Witten-type shift. We illustrate that these shifts allow us to correctly calculate four-point and five-point amplitudes in massive QED, without an ambiguity associated with the contact terms that may arise from a simple “gluing” of lower-point on-shell amplitudes. We discuss various aspects and applicability of the two shifts, including the large-z behavior and complexity scaling. We show that there exists a “good” all-line transverse shift for all possible little group configurations of the external particles, which can be extended to a broader class of theories with massive particles such as massive QCD and theories with massive spin-1 particles. The massive Britto-Cachazo-Feng-Witten-type shift enjoys more simplicity, but a “good” shift does not exist for all the spin states due to the specific choice of spin axis.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗
DOE OSTI2015

Quasi-Optimal Elimination Trees for 2D Grids with Singularities

We construct quasi-optimal elimination trees for 2D finite element meshes with singularities. These trees minimize the complexity of the solution of the discrete system. The computational cost estimates of the elimination process model the execution of the multifrontal algorithms in serial and in parallel shared-memory executions. Since the meshes considered are a subspace of all possible mesh partitions, we call these minimizers quasi-optimal. We minimize the cost functionals using dynamic programming. Finding these minimizers is more computationally expensive than solving the original algebraic system. Nevertheless, from the insights provided by the analysis of the dynamic programming minima, we propose a heuristic construction of the elimination trees that has cost O N e log ⁡ N e , where N e is the number of elements in the mesh. We show that this heuristic ordering has similar computational cost to the quasi-optimal elimination trees found with dynamic programming and outperforms state-of-the-art alternatives in our numerical experiments.

Paszyńska, A.↗
DOE OSTI2021

Optimization and Augmentation for Data Parallel Contour Trees

Contour trees are used for topological data analysis in scientific visualization. While originally computed with serial algorithms, recent work has introduced a vector-parallel algorithm. Furthermore, this algorithm is relatively slow for fully augmented contour trees which are needed for many practical data analysis tasks. We therefore introduce a representation called the hyperstructure that enables efficient searches through the contour tree and use it to construct a fully augmented contour tree in data parallel, with performance on average 6 times faster than the state-of-the-art parallel algorithm in the TTK topological toolkit.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2016

Data catalog project—A browsable, searchable, metadata system

Modern experiments are typically conducted by large, extended groups, where researchers rely on other team members to produce much of the data they use. The experiments record very large numbers of measurements that can be difficult for users to find, access and understand. Here. we are developing a system for users to annotate their data products with structured metadata, providing data consumers with a discoverable, browsable data index. Machine understandable metadata captures the underlying semantics of the recorded data, which can then be consumed by both programs, and interactively by users. Collaborators can use these metadata to select and understand recorded measurements. The data catalog project is a data dictionary and index which enables users to record general descriptive metadata, use cases and rendering information as well as providing them a transparent data access mechanism (URI). Users describe their diagnostic including references, text descriptions, units, labels, example data instances, author contact information and data access URIs. The list of possible attribute labels is extensible, but limiting the vocabulary of names increases the utility of the system. The data catalog is focused on the data products and complements process-based systems like the Metadata Ontology Provenance project [Greenwald, 2012; Schissel, 2015]. This system can be coupled with MDSplus to provide a simple platform for data driven display and analysis programs. Sites which use MDSplus can describe tree branches, and if desired create ‘processed data trees’ with homogeneous node structures for measurements. Sites not currently using MDSplus can either use the database to reference local data stores, or construct an MDSplus tree whose leaves reference the local data store. A data catalog system can provide a useful roadmap of data acquired from experiments or simulations making it easier for researchers to find and access important data and understand the meaning of the data and how it was obtained. This is particularly useful in research facilities that study the results of many different experiments or simulations and may not know the intricacies of the data organization in use where the data was generated. It is also possible to store a local copy of key data items in local MDSplus trees and then add processed data to the local catalog.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗
DOE OSTI2018

Classification of Complete Proteomes of Different Organisms and Protein Sets Based on Their Protein Distributions in Terms of Some Key Attributes of Proteins

The existence of complete genome sequences makes it important to develop different approaches for classification of large-scale data sets and to make extraction of biological insights easier. Here, we propose an approach for classification of complete proteomes/protein sets based on protein distributions on some basic attributes. We demonstrate the usefulness of this approach by determining protein distributions in terms of two attributes: protein lengths and protein intrinsic disorder contents (ID). The protein distributions based on L and ID are surveyed for representative proteome organisms and protein sets from the three domains of life. The two-dimensional maps (designated as fingerprints here) from the protein distribution densities in the LD space defined by ln( L ) and ID are then constructed. The fingerprints for different organisms and protein sets are found to be distinct with each other, and they can therefore be used for comparative studies. As a test case, phylogenetic trees have been constructed based on the protein distribution densities in the fingerprints of proteomes of organisms without performing any protein sequence comparison and alignments. The phylogenetic trees generated are biologically meaningful, demonstrating that the protein distributions in the LD space may serve as unique phylogenetic signals of the organisms at the proteome level.

59 BASIC BIOLOGICAL SCIENCES↗
DOE OSTI2025

Poplar: a phylogenomics pipeline

Motivation Generating phylogenomic trees from the genomic data is essential in understanding biological systems. Each step of this complex process has received extensive attention and has been significantly streamlined over the years. Given the public availability of data, obtaining genomes for a wide selection of species is straightforward. However, analyzing that data to generate a phylogenomic tree is a multistep process with legitimate scientific and technical challenges, often requiring a significant input from a domain-area scientist. Results We present Poplar, a new, streamlined computational pipeline, to address the computational logistical issues that arise when constructing the phylogenomic trees. It provides a framework that runs state-of-the-art software for essential steps in the phylogenomic pipeline, beginning from a genome with or without an annotation, and resulting in a species tree. Running Poplar requires no external databases. In the execution, it enables parallelism for execution for clusters and cloud computing. The trees generated by Poplar match closely with state-of-the-art published trees. The usage and performance of Poplar is far simpler and quicker than manually running a phylogenomic pipeline. Availability and implementation Freely available on GitHub at https://github.com/sandialabs/poplar. Implemented using Python and supported on Linux.

Koning, Elizabeth [Sandia National Laboratories (S↗