Search for: All records

Abstract Primary sclerosing cholangitis (PSC) is a complex bile duct disorder. Its etiology is incompletely understood, but environmental chemicals likely contribute to risk. Patients with PSC have an altered bile metabolome, which may be influenced by environmental chemicals. This novel study utilized state-of-the-art high-resolution mass spectrometry (HRMS) with bile samples to provide the first characterization of environmental chemicals and metabolomics (collectively, the exposome) in PSC patients located in the United States of America (USA) (n = 24) and Norway (n = 30). First, environmental chemical- and metabolome-wide association studies were conducted to assess geographic-based similarities and differences in the bile of PSC patients. Nine environmental chemicals (false discovery rate, FDR < 0.20) and 3143 metabolic features (FDR < 0.05) differed by site. Next, pathway analysis was performed to identify metabolomic pathways that were similarly and differentially enriched by the site. Fifteen pathways were differentially enriched (P < .05) in the categories of amino acid, glycan, carbohydrate, energy, and vitamin/cofactor metabolism. Finally, chemicals and pathways were integrated to derive exposure–effect correlation networks by site. These networks demonstrate the shared and differential chemical–metabolome associations by site and highlight important pathways that are likely relevant to PSC. The USA patients demonstrated higher environmental chemical bile content and increased associations between chemicals and metabolic pathways than those in Norway. Polychlorinated biphenyl (PCB)-118 and PCB-101 were identified as chemicals of interest for additional investigation in PSC given broad associations with metabolomic pathways in both the USA and Norway patients. Associated pathways include glycan degradation pathways, which play a key role in microbiome regulation and thus may be implicated in PSC pathophysiology. 

DOI: 10.1137/1.9781611975994.25 

Motivated by the study of matrix elimination orderings in combinatorial scientific computing, we utilize graph sketching and local sampling to give a data structure that provides access to approximate fill degrees of a matrix undergoing elimination in O(polylog(n)) time per elimination and query. We then study the problem of using this data structure in the minimum degree algorithm, which is a widely-used heuristic for producing elimination orderings for sparse matrices by repeatedly eliminating the vertex with (approximate) minimum fill degree. This leads to a nearly-linear time algorithm for generating approximate greedy minimum degree orderings. Despite extensive studies of algorithms for elimination orderings in combinatorial scientific computing, our result is the first rigorous incorporation of randomized tools in this setting, as well as the first nearly-linear time algorithm for producing elimination orderings with provable approximation guarantees. While our sketching data structure readily works in the oblivious adversary model, by repeatedly querying and greedily updating itself, it enters the adaptive adversarial model where the underlying sketches become prone to failure due to dependency issues with their internal randomness. We show how to use an additional sampling procedure to circumvent this problem and to create an independent access sequence. Our technique for decorrelating the interleaved queries and updates to this randomized data structure may be of independent interest. 

Abstract—Motivated by the study of matrix elimination orderings in combinatorial scientific computing, we utilize graph sketching and local sampling to give a data structure that provides access to approximate fill degrees of a matrix undergoing elimination in polylogarithmic time per elimination and query. We then study the problem of using this data structure in the minimum degree algorithm, which is a widely- used heuristic for producing elimination orderings for sparse matrices by repeatedly eliminating the vertex with (approx- imate) minimum fill degree. This leads to a nearly-linear time algorithm for generating approximate greedy minimum degree orderings. Despite extensive studies of algorithms for elimination orderings in combinatorial scientific computing, our result is the first rigorous incorporation of randomized tools in this setting, as well as the first nearly-linear time algorithm for producing elimination orderings with provable approximation guarantees. While our sketching data structure readily works in the oblivious adversary model, by repeatedly querying and greed- ily updating itself, it enters the adaptive adversarial model where the underlying sketches become prone to failure due to dependency issues with their internal randomness. We show how to use an additional sampling procedure to circumvent this problem and to create an independent access sequence. Our technique for decorrelating interleaved queries and updates to this randomized data structure may be of independent interest. 

We study the performance of linear solvers for graph Laplacians based on the combinatorial cycle adjustment methodology proposed by [Kelner-Orecchia-Sidford-Zhu STOC-13]. The approach finds a dual flow solution to this linear system through a sequence of flow adjustments along cycles. We study both data structure oriented and recursive methods for handling these adjustments. The primary difficulty faced by this approach, updating and querying long cycles, motivated us to study an important special case: instances where all cycles are formed by fundamental cycles on a length n path. Our methods demonstrate significant speedups over previous implementations, and are competitive with standard numerical routines.