Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “graph sequence”

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 109 records · Page 6
All sourcesNASA NTRSDOE OSTI
DOE OSTI2014

SWAP-Assembler: scalable and efficient genome assembly towards thousands of cores

Background: There is a widening gap between the throughput of massive parallel sequencing machines and the ability to analyze these sequencing data. Traditional assembly methods requiring long execution time and large amount of memory on a single workstation limit their use on these massive data. Results: This paper presents a highly scalable assembler named as SWAP-Assembler for processing massive sequencing data using thousands of cores, where SWAP is an acronym for Small World Asynchronous Parallel model. In the paper, a mathematical description of multi-step bi-directed graph (MSG) is provided to resolve the computational interdependence on merging edges, and a highly scalable computational framework for SWAP is developed to automatically preform the parallel computation of all operations. Graph cleaning and contig extension are also included for generating contigs with high quality. Experimental results show that SWAP-Assembler scales up to 2048 cores on Yanhuang dataset using only 26 minutes, which is better than several other parallel assemblers, such as ABySS, Ray, and PASHA. Results also show that SWAP-Assembler can generate high quality contigs with good N50 size and low error rate, especially it generated the longest N50 contig sizes for Fish and Yanhuang datasets. Conclusions: In this paper, we presented a highly scalable and efficient genome assembly software, SWAPAssembler. Compared with several other assemblers, it showed very good performance in terms of scalability and contig quality. This software is available at: https://sourceforge.net/projects/swapassembler

59 BASIC BIOLOGICAL SCIENCES↗
DOE OSTI2018

Weighted Distances in Scale-Free Configuration Models

In this paper we study first-passage percolation in the configuration model with empirical degree distribution that follows a power-law with exponent τ∈(2,3). We assign independent and identically distributed (i.i.d.) weights to the edges of the graph. We investigate the weighted distance (the length of the shortest weighted path) between two uniformly chosen vertices, called typical distances. When the underlying age-dependent branching process approximating the local neighborhoods of vertices is found to produce infinitely many individuals in finite time—called explosive branching process—Baroni, Hofstad and the second author showed in Baroni et al. (J Appl Probab 54(1):146–164, 2017) that typical distances converge in distribution to a bounded random variable. The order of magnitude of typical distances remained open for the τ∈(2,3) case when the underlying branching process is not explosive. We close this gap by determining the first order of magnitude of typical distances in this regime for arbitrary, not necessary continuous edge-weight distributions that produce a non-explosive age-dependent branching process with infinite mean power-law offspring distributions. This sequence tends to infinity with the amount of vertices, and, by choosing an appropriate weight distribution, can be tuned to be any growing function that is O(loglog n), where n is the number of vertices in the graph. We show that the result remains valid for the the erased configuration model as well, where we delete loops and any second and further edges between two vertices.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗
DOE OSTI2018

Beyond Hosting Capacity: Using Shortest Path Methods to Minimize Upgrade Cost Pathways: Preprint

We present in this paper a graph based forwardlooking algorithm applied to distribution planning in the context of distributed PV penetration. We study the target hosting capacity (THC) problem where the objective is to find the cheapest sequence of system upgrades to reach a predefined hosting capacity target value. We show in this paper that commonly used short-term cost minimization approaches lead most of the time to suboptimal solutions. By comparing our method against such myopic techniques on real distribution systems, we show that our algorithm is able to reduce the overall integration costs by looking at future decisions. Because hosting capacity is hard to compute, this problem requires efficient methods to search the space. We demonstrate here that heuristics using domain specific knowledge can be efficiently used to improve the algorithm performance such that real distribution systems can be studied.

14 SOLAR ENERGY↗
DOE OSTI2016

AiiDA: automated interactive infrastructure and database for computational science

Computational science has seen in the last decades a spectacular rise in the scope, breadth, and depth of its efforts. Notwithstanding this prevalence and impact, it is often still performed using the renaissance model of individual artisans gathered in a workshop, under the guidance of an established practitioner. Great benefits could follow instead from adopting concepts and tools coming from computer science to manage, preserve, and share these computational efforts. We illustrate here our paradigm sustaining such vision, based around the four pillars of Automation, Data, Environment, and Sharing. We then discuss its implementation in the open-source AiiDA platform (http://www.aiida.net), that has been tuned first to the demands of computational materials science. AiiDA’s design is based on directed acyclic graphs to track the provenance of data and calculations, and ensure preservation and searchability. Remote computational resources are managed transparently, and automation is coupled with data storage to ensure reproducibility. Last, complex sequences of calculations can be encoded into scientific workflows. We believe that AiiDA’s design and its sharing capabilities will encourage the creation of social ecosystems to disseminate codes, data, and scientific workflows.

Materials Science↗
DOE OSTI2019

Beyond Hosting Capacity: Using Shortest-Path Methods to Minimize Upgrade Cost Pathways

This paper presents a graph-based forward looking algorithm applied to distribution planning in the context of distributed photovoltaic penetration. We study the target hosting capacity problem where the objective is to find the least-cost sequence of system upgrades to reach a predefined hosting capacity target value. We show that commonly used short-term cost minimization approaches often lead to suboptimal long-term solutions. By comparing our method against such myopic techniques on real distribution systems, we show that our algorithm is able to reduce the overall integration costs by looking at future decisions. Because hosting capacity is hard to compute, this problem requires efficient methods to search the space. We demonstrate that heuristics using domain-specific knowledge can be efficiently used to improve the algorithm performance, such that real distribution systems can be studied.

24 POWER TRANSMISSION AND DISTRIBUTION↗
DOE OSTI2019

Review, Evaluation, and Directions for Gene-Targeted Assembly for Ecological Analyses of Metagenomes

Shotgun metagenomics has greatly advanced our understanding of microbial communities over the last decade. Metagenomic analyses often include assembly and genome binning, computationally daunting tasks especially for big data from complex environments such as soil and sediments. In many studies, however, only a subset of genes and pathways involved in specific functions are of interest; thus, it is not necessary to attempt global assembly. In addition, methods that target genes can be computationally more efficient and produce more accurate assembly by leveraging rich databases, especially for those genes that are of broad interest such as those involved in biogeochemical cycles, biodegradation, and antibiotic resistance or used as phylogenetic markers. Here, we review six gene-targeted assemblers with unique algorithms for extracting and/or assembling targeted genes: Xander, MegaGTA, SAT-Assembler, HMM-GRASPx, GenSeed-HMM, and MEGAN. We tested these tools using two datasets with known genomes, a synthetic community of artificial reads derived from the genomes of 17 bacteria, shotgun sequence data from a mock community with 48 bacteria and 16 archaea genomes, and a large soil shotgun metagenomic dataset. We compared assemblies of a universal single copy gene (rplB) and two N cycle genes (nifH and nirK). We measured their computational efficiency, sensitivity, specificity, and chimera rate and found Xander and MegaGTA, which both use a probabilistic graph structure to model the genes, have the best overall performance with all three datasets, although MEGAN, a reference matching assembler, had better sensitivity with synthetic and mock community members chosen from its reference collection. Also, Xander and MegaGTA are the only tools that include post-assembly scripts tuned for common molecular ecology and diversity analyses. Additionally, we provide a mathematical model for estimating the probability of assembling targeted genes in a metagenome for estimating required sequencing depth.

59 BASIC BIOLOGICAL SCIENCES↗
DOE OSTI2024

Efficient Hybrid Attack Graph Generation for Cyber-Physical System Resilience Experimentation (Final Project Report)

HAGEN project has developed theory, algorithms, and capabilities to assist cyber physical system modelers and operators to perform system and device-level vulnerability assessment, risk assessment, impact assessment, and mitigation planning. The project generates hybrid attack graphs for Cyber-Physical System (CPS) resilience experimentation at desired scale and speed. The project will produce composite attack datasets, algorithms, and demonstrable prototypical tools, and a library of high-impact attack sequences for a given CPS of interest. This report provided overall summary of research and development performed between FY22-24.

45 MILITARY TECHNOLOGY, WEAPONRY, AND NATIONAL DEF↗
DOE OSTI2020

A sorghum practical haplotype graph facilitates genome‐wide imputation and cost‐effective genomic prediction

Abstract Successful management and utilization of increasingly large genomic datasets is essential for breeding programs to accelerate cultivar development. To help with this, we developed a Sorghum bicolor Practical Haplotype Graph (PHG) pangenome database that stores haplotypes and variant information. We developed two PHGs in sorghum that were used to identify genome‐wide variants for 24 founders of the Chibas sorghum breeding program from 0.01x sequence coverage. The PHG called single nucleotide polymorphisms (SNPs) with 5.9% error at 0.01x coverage—only 3% higher than PHG error when calling SNPs from 8x coverage sequence. Additionally, 207 progenies from the Chibas genomic selection (GS) training population were sequenced and processed through the PHG. Missing genotypes were imputed from PHG parental haplotypes and used for genomic prediction. Mean prediction accuracies with PHG SNP calls range from .57–.73 and are similar to prediction accuracies obtained with genotyping‐by‐sequencing or targeted amplicon sequencing (rhAmpSeq) markers. This study demonstrates the use of a sorghum PHG to impute SNPs from low‐coverage sequence data and shows that the PHG can unify genotype calls across multiple sequencing platforms. By reducing input sequence requirements, the PHG can decrease the cost of genotyping, make GS more feasible, and facilitate larger breeding populations. Our results demonstrate that the PHG is a useful research and breeding tool that maintains variant information from a diverse group of taxa, stores sequence data in a condensed but readily accessible format, unifies genotypes across genotyping platforms, and provides a cost‐effective option for genomic selection.

Jensen, Sarah E.↗
DOE OSTI2025

Randomized Algorithms for Symmetric Nonnegative Matrix Factorization

Symmetric Nonnegative Matrix Factorization (SymNMF) is a technique in data analysis and machine learning that approximates a matrix with a product of a nonnegative, low-rank matrix and it transpose. To design faster and more scalable algorithms for SymNMF we develop two randomized algorithms for its computation. The first method uses randomized matrix sketching to compute an initial low-rank approximation to the input matrix and proceeds to uses this as a low-rank input to rapidly compute a SymNMF. The second methods uses randomized leverage score sampling to approximately solve constrained least squares problems. Many successful methods for SymNMF rely on (approximately) solving sequences of constrained least squares problems. Here, we prove theoretically that leverage score sampling can approximately solve constrained least squares problems to e-accuracy. Finally we demonstrate both methods work in practice by applying them to graph clustering tasks on large real world data sets. These experiments show that our methods approximately maintain solution quality and achieve significant speed ups for both large dense and large sparse problems.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Genomic Metrics Applied to Rhizobiales ( Hyphomicrobiales ): Species Reclassification, Identification of Unauthentic Genomes and False Type Strains

Taxonomic decisions within the order Rhizobiales have relied heavily on the interpretations of highly conserved 16S rRNA sequences and DNA–DNA hybridizations (DDH). Currently, bacterial species are defined as including strains that present 95–96% of average nucleotide identity (ANI) and 70% of digital DDH (dDDH). Thus, ANI values from 520 genome sequences of type strains from species of Rhizobiales order were computed. From the resulting 270,400 comparisons, a ≥95% cut-off was used to extract high identity genome clusters through enumerating maximal cliques. Coupling this graph-based approach with dDDH from clusters of interest, it was found that: (i) there are synonymy between Aminobacter lissarensis and Aminobacter carboxidus, Aurantimonas manganoxydans and Aurantimonas coralicida, “Bartonella mastomydis,” and Bartonella elizabethae, Chelativorans oligotrophicus, and Chelativorans multitrophicus, Rhizobium azibense, and Rhizobium gallicum, Rhizobium fabae, and Rhizobium pisi, and Rhodoplanes piscinae and Rhodoplanes serenus; (ii) Chelatobacter heintzii is not a synonym of Aminobacter aminovorans; (iii) “Bartonella vinsonii” subsp. arupensis and “B. vinsonii” subsp. berkhoffii represent members of different species; (iv) the genome accessions GCF_003024615.1 (“Mesorhizobium loti LMG 6125T”), GCF_003024595.1 (“Mesorhizobium plurifarium LMG 11892T”), GCF_003096615.1 (“Methylobacterium organophilum DSM 760T”), and GCF_000373025.1 (“R. gallicum R-602 spT”) are not from the genuine type strains used for the respective species descriptions; and v) “Xanthobacter autotrophicus” Py2 and “Aminobacter aminovorans” KCTC 2477T represent cases of misuse of the term “type strain”. Aminobacter heintzii comb. nov. and the reclassification of Aminobacter ciceronei as A. heintzii is also proposed. To facilitate the downstream analysis of large ANI matrices, we introduce here ProKlust (“Prokaryotic Clusters”), an R package that uses a graph-based approach to obtain, filter, and visualize clusters on identity/similarity matrices, with settable cut-off points and the possibility of multiple matrices entries.

59 BASIC BIOLOGICAL SCIENCES↗
DOE OSTI2023

Causal interaction in high frequency turbulence at the biosphere–atmosphere interface: Structure–function coupling

At the biosphere–atmosphere interface, nonlinear interdependencies among components of an ecohydrological complex system can be inferred using multivariate high frequency time series observations. Information flow among these interacting variables allows us to represent the causal dependencies in the form of a directed acyclic graph (DAG). Here, we use high frequency multivariate data at 10 Hz from an eddy covariance instrument located at 25 m above agricultural land in the Midwestern US to quantify the evolutionary dynamics of this complex system using a sequence of DAGs by examining the structural dependency of information flow and the associated functional response. We investigate whether functional differences correspond to structural differences or if there are no functional variations despite the structural differences. We base our analysis on the hypothesis that causal dependencies are instigated through information flow, and the resulting interactions sustain the dynamics and its functionality. To test our hypothesis, we build upon causal structure analysis in the companion paper to characterize the information flow in similarly clustered DAGs from 3-min non-overlapping contiguous windows in the observational data. We characterize functionality as the nature of interactions as discerned through redundant, unique, and synergistic components of information flow. Through this analysis, we find that in turbulence at the biosphere–atmosphere interface, the variables that control the dynamic character of the atmosphere as well as the thermodynamics are driven by non-local conditions, while the scalar transport associated with CO and H 2 O is mainly driven by short-term local conditions.

58 GEOSCIENCES↗
DOE OSTI2017

Hyperspectral Image Classification Using Graph Clustering Methods

Hyperspectral imagery is a challenging modality due to the dimension of the pixels which can range from hundreds to over a thousand frequencies depending on the sensor. Most methods in the literature reduce the dimension of the data using a method such as principal component analysis, however this procedure can lose information. More recently methods have been developed to address classification of large datasets in high dimensions. This paper presents two classes of graph-based classification methods for hyperspectral imagery. Using the full dimensionality of the data, we consider a similarity graph based on pairwise comparisons of pixels. The graph is segmented using a pseudospectral algorithm for graph clustering that requires information about the eigenfunctions of the graph Laplacian but does not require computation of the full graph. We develop a parallel version of the Nyström extension method to randomly sample the graph to construct a low rank approximation of the graph Laplacian. With at most a few hundred eigenfunctions, we can implement the clustering method designed to solve a variational problem for a graph-cut-based semi-supervised or unsupervised classification problem. We implement OpenMP directive-based parallelism in our algorithms and show performance improvement and strong, almost ideal, scaling behavior. The method can handle very large datasets including a video sequence with over a million pixels, and the problem of segmenting a data set into a pre-determined number of classes.

47 OTHER INSTRUMENTATION↗
DOE OSTI2020

PersGNN: Applying Topological Data Analysis and Geometric Deep Learning to Structure-Based Protein Function Prediction

Understanding protein structure-function relationships is a key challenge in computational biology, with applications across the biotechnology and pharmaceutical industries. While it is known that protein structure directly impacts protein function, many functional prediction tasks use only protein sequence. In this work, we isolate protein structure to make functional annotations for proteins in the Protein Data Bank in order to study the expressiveness of different structure-based prediction schemes. We present PersGNN - an end-to-end trainable deep learning model that combines graph representation learning with topological data analysis to capture a complex set of both local and global structural features. While variations of these techniques have been successfully applied to proteins before, we demonstrate that our hybridized approach, PersGNN, outperforms either method on its own as well as a baseline neural network that learns from the same information. PersGNN achieves a 9.3% boost in area under the precision recall curve (AUPR) compared to the best individual model, as well as high F1 scores across different gene ontology categories, indicating the transferability of this approach.

Swenson, Nicolas↗
DOE OSTI2019

Ordering of Trotterization: Impact on Errors in Quantum Simulation of Electronic Structure

Trotter–Suzuki decompositions are frequently used in the quantum simulation of quantum chemistry. They transform the evolution operator into a form implementable on a quantum device, while incurring an error—the Trotter error. The Trotter error can be made arbitrarily small by increasing the Trotter number. However, this increases the length of the quantum circuits required, which may be impractical. It is therefore desirable to find methods of reducing the Trotter error through alternate means. The Trotter error is dependent on the order in which individual term unitaries are applied. Due to the factorial growth in the number of possible orderings with respect to the number of terms, finding an optimal strategy for ordering Trotter sequences is difficult. In this paper, we propose three ordering strategies, and assess their impact on the Trotter error incurred. Initially, we exhaustively examine the possible orderings for molecular hydrogen in a STO-3G basis. We demonstrate how the optimal ordering scheme depends on the compatibility graph of the Hamiltonian, and show how it varies with increasing bond length. We then use 44 molecular Hamiltonians to evaluate two strategies based on coloring their incompatibility graphs, while considering the properties of the obtained colorings. We find that the Trotter error for most systems involving heavy atoms, using a reference magnitude ordering, is less than 1 kcal/mol. Relative to this, the difference between ordering schemes can be substantial, being approximately on the order of millihartrees. The coloring-based ordering schemes are reasonably promising—particularly for systems involving heavy atoms—however further work is required to increase dependence on the magnitude of terms. Finally, we consider ordering strategies based on the norm of the Trotter error operator, including an iterative method for generating the new error operator terms added upon insertion of a term into an ordered Hamiltonian.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2021

Multilevel Spectral Coarsening for Graph Laplacian Problems with Application to Reservoir Simulation

We extend previously developed two-level coarsening procedures for graph Laplacian problems written in a mixed saddle point form to the fully recursive multilevel case. The resulting hierarchy of discretizations gives rise to a hierarchy of upscaled models, in the sense that they provide approximation in the natural norms (in the mixed setting). This property enables us to utilize them in three applications: (i) as an accurate reduced model, (ii) as a tool in multilevel Monte Carlo simulations (in application to finite volume discretizations), and (iii) for providing a sequence of nonlinear operators in a full approximation scheme for solving nonlinear pressure equations discretized by the conservative two-point flux approximation. Finally, we illustrate the potential of the proposed multilevel technique in all three applications on a number of popular benchmark problems used in reservoir simulation.

multilevel Monte Carlo↗
DOE OSTI2016

RAY-UI: A powerful and extensible user interface for RAY

The RAY-UI project started as a proof-of-concept for an interactive and graphical user interface (UI) for the well-known ray tracing software RAY [1]. In the meantime, it has evolved into a powerful enhanced version of RAY that will serve as the platform for future development and improvement of associated tools. The software as of today supports nearly all sophisticated simulation features of RAY. Furthermore, it delivers very significant usability and work efficiency improvements. Beamline elements can be quickly added or removed in the interactive sequence view. Parameters of any selected element can be accessed directly and in arbitrary order. With a single click, parameter changes can be tested and new simulation results can be obtained. All analysis results can be explored interactively right after ray tracing by means of powerful integrated image viewing and graphing tools. Unlimited image planes can be positioned anywhere in the beamline, and bundles of image planes can be created for moving the plane along the beam to identify the focus position with live updates of the simulated results. In addition to showing the features and workflow of RAY-UI, we will give an overview of the underlying software architecture as well as examples for use and an outlook for future developments.

46 INSTRUMENTATION RELATED TO NUCLEAR SCIENCE AND ↗
DOE OSTI2019

Detecting Data-Races in High-Performance Computing

High-performance computing is susceptible to data-race bugs. Data races occur when sequences of computed events do not happen in the intended order, a significant barrier to the integrity of parallel programs using shared-memory architectures. Many approaches to data-race detection are based on traditional static-analysis techniques that typically execute on a program’s source code or control-flow graph (the graphical representation of all possible orders of events in the execution of a program). Similar to classical data-flow analyses, such tools can produce false alarms that report spurious race conditions on error free programs. We have developed a software verification technique that requires as input only a program’s source code and can automatically detect a data-race bug which definitely exists, determine that a program is definitely data-race free, or report that it cannot determine either of the two cases.

97 MATHEMATICS AND COMPUTING↗
DOE OSTI2020

Temporal Analysis and Scene Change Detection in Multispectral Overhead Imagery

Scene change detection can be a tedious and time consuming process especially when concerning large geographical areas, and the process can be even more cumbersome when analyzing changes in an area over large spans of time. Developing a useful way to help analysts recognize at what points in time significant changes to a scene have occurred can allow them to better focus their efforts in characterizing events. Applications include: Facility monitoring, Construction chronology, Monitoring of vehicle/aircraft activity, Characterization of larger sequences of events. In large areas exceeding hundreds to thousands of square kilometers in size, it can be difficult localizing when scene changes have occurred. Analysts can spend hours going through imagery to try to identify new construction, monitor facility activities, monitor vehicle movement, etc. where the object of interest may only be a few square meters. Our goal is to help cut down this time by giving analysts change maps with hot spots of change, allowing them to focus on regions that have experienced actual change in time frames they're interested in. Additionally, by combining these change maps into layers within a data cube, analysts can examine the change maps from a temporal perspective, allowing events to be characterized over spans of time. By opening the data cube in an imaging software capable of separating the layers, we can analyze the change maps sequentially, allowing us to examine scene changes occurring over time. As an example, we examined overhead imagery from Planet Labs of what appears to be a parking lot on Fort Irwin over the course of a year using ENVI, a geospatial satellite imagery analysis software. Using ENVI, we generate a graph of changes over time, and notice a particular segment near the end of our analysis window where no changes are detected. Examination of the actual satellite imagery reveals that during this time span, the parking lot was empty. This could be due to facility shutdown for maintenance or upgrades, or possibly even total workforce/vehicle fleet movement. Information like this could help analysts better characterize events, as well as to help create clearer timelines in larger sequences of events. Workflow steps: - Collect multiple maps of the same AOI (Area of Interest) during a time span of interest; - Generate change maps from AOI maps; - Generate data cube from change maps. An analyst can use the data cube to help inspect an AOI for activities within a time span of interest. If an event of interest is discovered, the analyst can then refer to the maps corresponding to the appropriate dates and times in the data cube to see precisely what is transpiring. The biggest objective being worked on is improving the change detection methodology employed. We currently use PCA-EM (Principal Component Analysis with Expectation Maximization), but we are currently focusing on implementing IR-MAD (Iteratively Reweighted Multivariate Alteration Detection) to be used in conjunction with PCA-EM in an effort to decrease false positivity and noise in the change maps we generate.

42 ENGINEERING↗