Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “human computers”

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 361 records · Page 20

Continual Learning for Pattern Recognizers using Neurogenesis Deep Learning

Deep neural networks have emerged as a leading set of algorithms to infer information from a variety of data sources such as images and time series data. In their most basic form, neural networks lack the ability to adapt to new classes of information. Continual learning is a field of study attempting to give previously trained deep learning models the ability to adapt to a changing environment. Previous work developed a CL method called Neurogenesis for Deep Learning (NDL). Here, we combine NDL with a specific neural network architecture (the Ladder Network) to produce a system capable of automatically adapting a classification neural network to new classes of data. The NDL Ladder Network was evaluated against other leading CL methods. While the NDL and Ladder Network system did not match the cutting edge performance achieved by other CL methods, in most cases it performed comparably and is the only system evaluated that can learn new classes of information with no human intervention.

97 MATHEMATICS AND COMPUTING↗

Shotgun Immunoproteomic Approach for the Discovery of Linear B-Cell Epitopes in Biothreat Agents Francisella tularensis and Burkholderia pseudomallei

Peptide-based subunit vaccines are coming to the forefront of current vaccine approaches, with safety and cost-effective production among their top advantages. Peptide vaccine formulations consist of multiple synthetic linear epitopes that together trigger desired immune responses that can result in robust immune memory. The advantages of linear compared to conformational epitopes are their simple structure, ease of synthesis, and ability to stimulate immune responses by means that do not require complex 3D conformation. Prediction of linear epitopes through use of computational tools is fast and cost-effective, but typically of low accuracy, necessitating extensive experimentation to verify results. On the other hand, identification of linear epitopes through experimental screening has been an inefficient process that requires thorough characterization of previously identified full-length protein antigens, or laborious techniques involving genetic manipulation of organisms. In this study, we apply a newly developed generalizable screening method that enables efficient identification of B-cell epitopes in the proteomes of pathogenic bacteria. As a test case, we used this method to identify epitopes in the proteome of Francisella tularensis (Ft), a Select Agent with a well-characterized immunoproteome. Our screen identified many peptides that map to known antigens, including verified and predicted outer membrane proteins and extracellular proteins, validating the utility of this approach. We then used the method to identify seroreactive peptides in the less characterized immunoproteome of Select Agent Burkholderia pseudomallei (Bp). This screen revealed known Bp antigens as well as proteins that have not been previously identified as antigens. Although B-cell epitope prediction tools Bepipred 2.0 and iBCE-EL classified many of our seroreactive peptides as epitopes, they did not score them significantly higher than the non-reactive tryptic peptides in our study, nor did they assign higher scores to seroreactive peptides from known Ft or Bp antigens, highlighting the need for experimental data instead of relying on computational epitope predictions alone. The present workflow is easily adaptable to detecting peptide targets relevant to the immune systems of other mammalian species, including humans (depending upon the availability of convalescent sera from patients), and could aid in accelerating the discovery of B-cell epitopes and development of vaccines to counter emerging biological threats.

60 APPLIED LIFE SCIENCES↗

Apparatus, system and method for highlighting activity-induced change in multi-pass synthetic aperture radar imagery

Described herein are various technologies relating to constructing a differenced change product (DCP) image. A plurality of synthetic aperture radar (SAR) images of a scene are generated based upon radar signals directed towards and reflected off of the scene, and a plurality of coherence change detection (CCD) images of the scene are generated based upon the SAR images. The CCD images are registered with one another, and their pixel values re-scaled according to a monotonic mapping function. The DCP image is generated based upon a computed pixel-wise difference between a pair of the re-scaled CCD images. The DCP image identifies locations in the scene where human activity-induced change is likely to have occurred between a pair of SAR passes of the scene.

42 ENGINEERING↗

Learning from learning machines: improving the predictive power of energy-water-land nexus models with insights from complex measured and simulated data

Focal Area(s): Insights gleaned from complex data (observed and simulated) using AI; Predictive modeling through the use of AI techniques and AI-derived model components, including physics- and knowledge-informed models; Energy-water-land nexus and integrated energy systems – models of MultiSector dynamics. Science Challenge: Scientific communities are in need of tools for the computational integration of physics-based models, experimental data, and empirical/observational studies across a broad range of temporal and spatial scales to explore and meet EESSD grand challenges. We require AI algorithms for the discovery of process-drivers in the Earth-energy-human system and to link them with complex measured and simulated data. We aim to understand the energy-water-land nexus, particularly under extreme forcing scenarios and rare events, leveraging scale-aware AI process models, including probabilistic uncertainties, and benefiting from the emerging 5G-enabled landscape-scale sensing and edge computing capabilities. These models are needed to identify instabilities and tipping points that manifest extreme system behaviors with consequences for integrated energy systems and the environment. This work requires fundamental advances in uncertainty quantification, in particular, to identify and model unlikely but catastrophic outliers. Specifically, we need models that are interpretable to domain scientists and, essentially, explainable to public and private stake holders.

54 ENVIRONMENTAL SCIENCES↗

Resilience-based Recovery Scheduling of Transportation Network in Mixed Traffic Environment: A Deep-Ensemble-Assisted Active Learning Approach

Devising effective post-hazard recovery strategies is critical in enhancing the resilience of transportation networks (TNs). However, existing work does not consider the multiclass users’ travel behavior in network functionality quantification and the metaheuristic solution procedures often suffer from extensive computational burden due to the exploration need in large solution space and the expensive functionality quantification. Here, this study develops a bilevel decision-making framework for the resilience-based recovery scheduling of the TN in a mixed traffic environment with connected and autonomous vehicles (CAVs) and human-driven vehicles (HDVs). The lower level quantifies the TN's functionality over time considering different travel behavior of CAV and HDV users arisen from their different levels of information perception. The upper level presents a novel deep-ensemble-assisted active learning approach to balance optimization performance and computational cost. This framework can help decision makers better quantify the TN's functionality to support effective recovery scheduling of TN with different mixed traffic scenarios ranging from HDV-only to future CAV-dominant traffic. The optimization approach bears the potential to be extended to solving general large-scale network recovery scheduling problems effectively and efficiently. The proposed methodology is demonstrated using a real-world traffic network in Southern California under earthquake considering deterministic and stochastic repair durations.

42 ENGINEERING↗

Matrix Metalloproteinases as Candidate Antigenic Determinants for Anti‐Tumor Autoantibodies in Human Ovarian Cancer: A Post Hoc Analysis

Circulating antibodies in patients with cancer can facilitate the identification of accessible epitopes on autoantigens expressed by tumors. To identify previously unrecognized protein targets in ovarian cancer, we computationally assessed a heptapeptide consensus motif (VPELGHE, flanked by two cysteine residues yielding a cyclic nonapeptide under oxidizing conditions) previously discovered via phage display-based epitope mapping of autoantibodies in patients. Eight proteins associated with ovarian cancer encompass amino acid sequences similar to the consensus motif and were, therefore, considered as candidate native autoantigens. Among these candidate targets, however, matrix metalloproteinase 14 (MMP14) demonstrates gene expression that is both high and negatively correlated with survival in ovarian cancer patient cohorts. MMP14 protein levels are also stable in tumor versus non-tumor tissues. Moreover, the corresponding heptapeptide mimic in MMP14 occurs within an α-helical secondary structural element observed in its catalytic domain. These findings demonstrate that a subset of patient-derived autoantibodies may interact with a previously unknown antigenic epitope found in MMP14 and other MMPs, thereby providing opportunities for the development of new targeted agents.

Biochemistry & Molecular Biology↗

Two MCNP Models for Computational Performance Benchmarking

The purpose of this report is to describe two non-trivial MCNP models and execution configurations that are suitable to characterizing computational performance. To that end, this report uses a constructive solid geometry (CSG) representation of the Oak Ridge National Laboratory (ORNL) Pool Critical Assembly (PCA) [1–3] to perform a k-eigenvalue calculation and an unstructured mesh (UM) representation of the International Commission on Radiological Protection (ICRP) publication 145 (ICRP145) male human phantom [4, 5] to perform a fixed-source calculation assuming that a 1 MeV photon source is distributed throughout the phantom’s liver.

97 MATHEMATICS AND COMPUTING↗

Benchmarking CO₂ storage simulations: Results from the 11 th Society of Petroleum Engineers Comparative Solution Project

The 11 th Society of Petroleum Engineers Comparative Solution Project (shortened SPE11 herein) benchmarked simulation tools for geological carbon dioxide (CO 2 ) storage. A total of 45 groups from leading research institutions and industry across the globe signed up to participate, with 18 ultimately contributing valid results that were included in the comparative study reported here. This paper summarizes the SPE11 results. A comprehensive introduction and qualitative discussion of the submitted data are provided, together with an overview of online resources for accessing the full depth of data. A global metric for analyzing the relative distance between submissions is proposed and used to conduct a quantitative analysis of the submissions. This analysis attempts to statistically resolve the key aspects influencing the variability between submissions. The study shows that the major qualitative variation between the submitted results is related to thermal effects, dissolution-driven convective mixing, and resolution of facies discontinuities. Moreover, a strong dependence on grid resolution is observed across all three versions of the SPE11. However, our quantitative analysis suggests that the observed variations are predominantly influenced by factors not documented in the technical responses provided by the participants. We therefore identify that unreported variations due to human choices within the process of setting up, conducting, and reporting on the simulations underlying each SPE11 submission are at least as impactful as the computational choices reported.

Nordbotten, Jan M. [Univ. of Bergen (Norway); Norw↗

Bigpicc: a graph-based approach to identifying carcinogenic gene combinations from mutation data

Abstract Genome data from cancer patients represents relationships between the presence of a gene mutation and cancer occurrence in a patient. Different types of cancer in human are thought to be caused by combinations of two to nine gene mutations. Identifying these combinations through traditional exhaustive search requires the amount of computation that scales exponentially with the combination size and in most cases is intractable even for cutting-edge supercomputers. We propose a parameter-free heuristic approach that leverages the intrinsic topology of gene-patient mutations to identify carcinogenic combinations. The biological relevance of the identified combinations is measured by using them to predict the presence of tumor in previously unseen samples. The resulting classifiers for 16 cancer types perform on par with exhaustive search results, and score the average of 80.1% sensitivity and 91.6% specificity for the best choice of hit range per cancer type. Our approach is able to find higher-hit carcinogenic combinations targeting which would take years of computations using exhaustive search.

Biochemistry & Molecular Biology↗

Mysteries of Nuclear Fusion: How can we build a star on Earth? [Slides]

This presentation given at the Women's Physics Summer Camp focuses on nuclear fusion as an alternative to fossil fuels, renewable energy sources and nuclear fission energy. The presentation explains plasma physics and how it might be used to generate power. Current attempts and potential applications are outlined. An appeal is made for people trained in mathematics, physics, chemistry, engineering, computer science to solve these problems. If technical problems can be overcome, fusion technology will play a part in a clean, prosperous Earth and expand humanity’s reach to the stars.

70 PLASMA PHYSICS AND FUSION TECHNOLOGY↗

Beneficial Use of Harvested Ponded Fly Ash and Landfilled FGD Materials for High-Volume Surface Mine Reclamation

The overall motivation of this project was to demonstrate at laboratory, bench-scale, and full-scale demonstration levels that (a) coal ash surface impoundments can go through closure by removal as per USEPA and state regulations so that the material can be used as is (other than draining free water using CCRs piles) in high-volume beneficial applications, (b) FGD material from closed out FGD facilities can be excavated and recompacted for coal mine reclamation, and (c) harvested CCRs can be beneficially utilized (providing a net environmental gain) in large-volumes for reclamation at abandoned coal mine sites across the US, especially in the Eastern and Midwest coal mining regions. The objectives of this project were to: 1) promote the safe and cost-effective closure by removal of coal ash impoundments, 2) harvest landfilled FGD, and 3) promote the high-volume beneficial use of these harvested CCRs in the reclamation of abandoned surface coal mine sites across the eastern and midwestern coal mining regions of the United States. The major tasks carried out for this project are summarized below: 1) Conesville Full-Scale Demonstration Project: About 2 million tons of harvested CCR materials from the closure by removal of an inactive fly ash pond and an adjacent old FGD landfill were used for the full-scale demonstration project to fully reclaim a nearby partially completed abandoned surface coal mine. Site monitoring for the project duration was carried out and results are discussed. 2) Laboratory Testing: Geotechnical and environmental testing of harvested ponded fly ash and landfilled FGD material at the former Conesville power plant were carried out. Completing the laboratory testing allowed for QA/QC for the full-scale site construction and informed the formulation of the risk analysis. 3) Risk Analysis: We developed a reliable computational model for fate and transport. We used these models and the rich set of monitored data for the Conesville site to analyze risks to human health and ecological risks associated with high-volume surface mine reclamation using harvested CCRs. 4) GIS Siting Study: A Geographic Information System (GIS) study was carried out for three states in the Eastern coal mining region and two states in the Midwest coal region. This effort provided site specific GIS information for five states and allowed us to establish protocols that other states can follow in implementing their own state specific GIS study.

01 COAL, LIGNITE, AND PEAT↗

An Approach to Dynamic Human Reliability Analysis and Its Data Collection Framework

Human reliability analysis (HRA) is a method for evaluating human errors in a variety of complex systems such as nuclear power plants, military systems, aircraft, and chemical plants. Most HRA methods currently used by regulatory institutes or utilities are called static HRA and are carried out by simple worksheets or simple calculators. To date, there are many unsolved or intrinsic challenges in static HRA. For example, existing static HRA does not realistically model and evaluate human actions as they would be performed at actual systems. There is no method with HRA to objectively estimate the time required for human actions despite being essential to HRA processes. In addition, many HRA methods still rely on a dataset generated prior to the 1980s, from unrelated industry experience or simply from expert judgment. Accordingly, this study attempted to research how to overcome the challenges of existing HRA via dynamic risk assessment (a.k.a., simulation-based or computation-based risk assessment) techniques. First, this study developed a dynamic HRA method, named as PRocedure-based Investigation Method of EMRALD Risk Assessment – HRA (PRIMERA-HRA). The PRIMERA-HRA mainly concentrates on providing HRA analysts with specific guidelines on how to reasonably model human actions, assign human reliability data and evaluate output of simulation within a dynamic probabilistic risk assessment tool, called as Event Modeling Risk Assessment using Linked Diagrams (EMRALD). Second, this study also developed a module for performance shaping factors (i.e., the key concept in HRA quantification) applicable to dynamic HRA, then implemented it based on PRIMERA-HRA within the EMRALD tool. Third, this study developed an HRA data collection framework to support dynamic HRA, called as Simplified Human Error Experimental Program (SHEEP). Originally, the SHEEP study aimed to support static HRA and its data collection, but recently extended the scope to the new technologies such as dynamic HRA or HRA for advanced reactors. SHEEP focuses on the use of data collected from simplified simulators to complement—but not replace—data collection studies using full-scope simulators and actual operators. To date, many experiments were conducted under the SHEEP framework. Multiple analyses, such as human performance analysis, human error analysis, task complexity analysis, learning effect analysis and time distribution analysis, were also carried out using the collected data. Then, based on the major insights, an approach to inferring full-scope data based on simplified simulator data was proposed. The PRIMERA-HRA and SHEEP research are expected to evaluate human actions more realistically than existing static HRA, provide an opportunity to collect more HRA data with reasonable cost and labor, then contribute to enhance the quality of HRA.

99 - GENERAL AND MISCELLANEOUS↗

An Approach to Dynamic Human Reliability Analysis and Its Data Collection Framework

Human reliability analysis (HRA) is a method for evaluating human errors in a variety of complex systems such as nuclear power plants, military systems, aircraft, and chemical plants. Most HRA methods currently used by regulatory institutes or utilities are called static HRA and are carried out by simple worksheets or simple calculators. To date, there are many unsolved or intrinsic challenges in static HRA. For example, existing static HRA does not realistically model and evaluate human actions as they would be performed at actual systems. There is no method with HRA to objectively estimate the time required for human actions despite being essential to HRA processes. In addition, many HRA methods still rely on a dataset generated prior to the 1980s, from unrelated industry experience or simply from expert judgment. Accordingly, this study attempted to research how to overcome the challenges of existing HRA via dynamic risk assessment (a.k.a., simulation-based or computation-based risk assessment) techniques. First, this study developed a dynamic HRA method, named as PRocedure-based Investigation Method of EMRALD Risk Assessment – HRA (PRIMERA-HRA). The PRIMERA-HRA mainly concentrates on providing HRA analysts with specific guidelines on how to reasonably model human actions, assign human reliability data and evaluate output of simulation within a dynamic probabilistic risk assessment tool, called as Event Modeling Risk Assessment using Linked Diagrams (EMRALD). Second, this study also developed a module for performance shaping factors (i.e., the key concept in HRA quantification) applicable to dynamic HRA, then implemented it based on PRIMERA-HRA within the EMRALD tool. Third, this study developed an HRA data collection framework to support dynamic HRA, called as Simplified Human Error Experimental Program (SHEEP). Originally, the SHEEP study aimed to support static HRA and its data collection, but recently extended the scope to the new technologies such as dynamic HRA or HRA for advanced reactors. SHEEP focuses on the use of data collected from simplified simulators to complement—but not replace—data collection studies using full-scope simulators and actual operators. To date, many experiments were conducted under the SHEEP framework. Multiple analyses, such as human performance analysis, human error analysis, task complexity analysis, learning effect analysis and time distribution analysis, were also carried out using the collected data. Then, based on the major insights, an approach to inferring full-scope data based on simplified simulator data was proposed. The PRIMERA-HRA and SHEEP research are expected to evaluate human actions more realistically than existing static HRA, provide an opportunity to collect more HRA data with reasonable cost and labor, then contribute to enhance the quality of HRA.

99 - GENERAL AND MISCELLANEOUS↗

A non-cooperative meta-modeling game for automated third-party calibrating, validating and falsifying constitutive laws with parallelized adversarial attacks

The evaluation of constitutive models, especially for high-risk and high-regret engineering applications, requires efficient and rigorous third-party calibration, validation and falsification. While there are numerous efforts to develop paradigms and standard procedures to validate models, difficulties may arise due to the sequential, manual, and often biased nature of the commonly adopted calibration and validation processes, thus slowing down data collections, hampering the progress towards discovering new physics, increasing expenses and possibly leading to misinterpretations of the credibility and application ranges of proposed models. This work attempts to introduce concepts from game theory and machine learning techniques to overcome many of these existing difficulties. Here, we introduce an automated meta-modeling game where two competing AI agents systematically generate experimental data to calibrate a given constitutive model and to explore its weakness such that the experiment design and model robustness can be improved through competitions. The two agents automatically search for the Nash equilibrium of the meta-modeling game in an adversarial reinforcement learning framework without human intervention. In particular, a protagonist agent seeks to find the more effective ways to generate data for model calibrations, while an adversary agent tries to find the most devastating test scenarios that expose the weaknesses of the constitutive model calibrated by the protagonist. By capturing all possible design options of the laboratory experiments into a single decision tree, we recast the design of experiments as a game of combinatorial moves that can be resolved through deep reinforcement learning by the two competing players. Our adversarial framework emulates idealized scientific collaborations and competitions among researchers to achieve a better understanding of the application range of the learned material laws and prevent misinterpretations caused by conventional AI-based third-party validation. Numerical examples are given to demonstrate the wide applicability of the proposed meta-modeling game with adversarial attacks on both human-crafted constitutive models and machine learning models.

97 MATHEMATICS AND COMPUTING↗

Functional Data Analysis in Wearable Body Sensor Networks

Improving response time of indirect room-size calorimeters is still an outstanding problem in metabolic research. Accurate estimates of instantaneous rates of gaseous exchange require numerical differentiation of measured gaseousgas concentrations. We propose a new method to estimate the instantaneous gaseousgas exchange rates in indirect calorimetry. In contrast to the previously developed techniques, the method addresses the problem of differentiation of gaseous concentrations as an ill-posed problem. By applying the method of regularization, the problem of differentiation is converted into a well-posed problem resulting in smooth and consistent gaseous exchange rates. The validity of the method is tested on a large dataset of calorimeter experiments which included 313 human experiments along with 231 alcohol combustion experiments. It is demonstrated that the method is able to reliably differentiate between the “unphysiological” process of alcohol combustion and physiological variations produced by human metabolism. The method also allowed unraveling the previously unreported relative kinetics of O2 consumption and Respiratory Quotient (RQ) in humans. It was found that the kinetics of oxidative fuel selection lags behind the energy expenditure in humans exhibiting some sort of oxidative inertia. The time lag varies from 2-3 min up to 30 min, depending on particular individual. No such lag was found in alcohol combustion experiments. In addition to the relative kinetics of substrate oxidation, two statistical indexes reflecting variability of minute-by-minute RQ were estimated. The indexes were the RQ’s standard deviation and RQ’s first-order derivative. Both indexes showed statistically significant difference between human experiments and alcohol combustion experiments. We conclude that the proposed method can consistently extract physiologically-relevant information from noisy calorimetry data and the aforesaid information can provide additional insights into the mechanism of metabolic fuel selection in humans.

60 - APPLIED LIFE SCIENCES↗

Predicting drug-metagenome interactions: Variation in the microbial β-glucuronidase level in the human gut metagenomes

Characterizing the gut microbiota in terms of their capacity to interfere with drug metabolism is necessary to achieve drug efficacy and safety. Although examples of drug-microbiome interactions are well-documented, little has been reported about a computational pipeline for systematically identifying and characterizing bacterial enzymes that process particular classes of drugs. The goal of our study is to develop a computational approach that compiles drugs whose metabolism may be influenced by a particular class of microbial enzymes and that quantifies the variability in the collective level of those enzymes among individuals. The present paper describes this approach, with microbial β-glucuronidases as an example, which break down drug-glucuronide conjugates and reactivate the drugs or their metabolites. We identified 100 medications that may be metabolized by β-glucuronidases from the gut microbiome. These medications included morphine, estrogen, ibuprofen, midazolam, and their structural analogues. The analysis of metagenomic data available through the Sequence Read Archive (SRA) showed that the level of β-glucuronidase in the gut metagenomes was higher in males than in females, which provides a potential explanation for the sex-based differences in efficacy and toxicity for several drugs, reported in previous studies. Our analysis also showed that infant gut metagenomes at birth and 12 months of age have higher levels of β-glucuronidase than the metagenomes of their mothers and the implication of this observed variability was discussed in the context of breastfeeding as well as infant hyperbilirubinemia. Overall, despite important limitations discussed in this paper, our analysis provided useful insights on the role of the human gut metagenome in the variability in drug response among individuals. Importantly, this approach exploits drug and metagenome data available in public databases as well as open-source cheminformatics and bioinformatics tools to predict drug-metagenome interactions.

59 BASIC BIOLOGICAL SCIENCES↗

Granger causal inference for climate change attribution

Abstract Climate change detection and attribution (D&A) is concerned with determining the extent to which anthropogenic activities have influenced specific aspects of the global climate system. D&A fits within the broader field of causal inference, the collection of statistical methods that identify cause and effect relationships. There are a wide variety of methods for making attribution statements, each of which require different types of input data and focus on different types of weather and climate events and each of which are conditional to varying extents. Some methods are based on Pearl causality (direct experimental interference) while others leverage Granger (predictive) causality, and the causal framing provides important context for how the resulting attribution conclusion should be interpreted. However, while Granger-causal attribution analyses have become more common, there is no clear statement of their strengths and weaknesses relative to Pearl-causal attribution and no clear consensus on where and when Granger-causal perspectives are appropriate. In this prospective paper, we provide a formal definition for Granger-based approaches to trend and event attribution and a clear comparison with more traditional methods for assessing the human influence on extreme weather and climate events. Broadly speaking, Granger-causal attribution statements can be constructed quickly from observations and do not require computationally-intesive dynamical experiments. These analyses also enable rapid attribution, which is useful in the aftermath of a severe weather event, and provide multiple lines of evidence for anthropogenic climate change when paired with Pearl-causal attribution. Confidence in attribution statements is increased when different methodologies arrive at similar conclusions. Moving forward, we encourage the D&A community to embrace hybrid approaches to climate change attribution that leverage the strengths of both Granger and Pearl causality.

Risser, Mark D. (ORCID:0000000319561783)↗

A variant selection framework for genome graphs

Abstract Motivation Variation graph representations are projected to either replace or supplement conventional single genome references due to their ability to capture population genetic diversity and reduce reference bias. Vast catalogues of genetic variants for many species now exist, and it is natural to ask which among these are crucial to circumvent reference bias during read mapping. Results In this work, we propose a novel mathematical framework for variant selection, by casting it in terms of minimizing variation graph size subject to preserving paths of length α with at most δ differences. This framework leads to a rich set of problems based on the types of variants [e.g. single nucleotide polymorphisms (SNPs), indels or structural variants (SVs)], and whether the goal is to minimize the number of positions at which variants are listed or to minimize the total number of variants listed. We classify the computational complexity of these problems and provide efficient algorithms along with their software implementation when feasible. We empirically evaluate the magnitude of graph reduction achieved in human chromosome variation graphs using multiple α and δ parameter values corresponding to short and long-read resequencing characteristics. When our algorithm is run with parameter settings amenable to long-read mapping (α = 10 kbp, δ = 1000), 99.99% SNPs and 73% SVs can be safely excluded from human chromosome 1 variation graph. The graph size reduction can benefit downstream pan-genome analysis. Availability and implementation https://github.com/AT-CG/VF. Supplementary information Supplementary data are available at Bioinformatics online.

59 BASIC BIOLOGICAL SCIENCES↗