We define a new filtration called the Steinhaus filtration built from a single cover based on a generalized Steinhaus distance, a generalization of Jaccard distance. The homology persistence module of a Steinhaus filtration with infinitely many cover elements may not be $q$-tame, even when the covers are in a totally bounded space. While this may pose a challenge to derive stability results, we show that the Steinhaus filtration is stable when the cover is finite. We show that while the Čech and Steinhaus filtrations are not isomorphic in general, they are isomorphic for a finite point set in dimension one. Furthermore, the VR filtration completely determines the $1$-skeleton of the Steinhaus filtration in arbitrary dimension. We then develop a language and theory for stable paths within the Steinhaus filtration. We demonstrate how the framework can be applied to several applications where a standard metric may not be defined but a cover is readily available. We introduce a new perspective for modeling recommendation system datasets. As an example, we look at a movies dataset and we find the stable paths identified in our framework represent a sequence of movies constituting a gentle transition and ordering from one genre to another. For explainable machine learning, we apply the Mapper algorithm for model induction by building a filtration from a single Mapper complex, and provide explanations in the form of stable paths between subpopulations. For illustration, we build a Mapper complex from a supervised machine learning model trained on the FashionMNIST dataset. Stable paths in the Steinhaus filtration provide improved explanations of relationships between subpopulations of images.

We design and implement two single-pass semi-streaming algorithms for the maximum weight $k$-disjoint matching ($k$-DM) problem. Given an integer $k$, the $k$-DM problem is to find $k$ pairwise edge-disjoint matchings such that the sum of the weights of the matchings is maximized. For $k \geq 2$, this problem is NP-hard. Our first algorithm is based on the primal-dual framework of a linear programming relaxation of the problem and is $\frac{1}{3+\varepsilon}$-approximate. We also develop an approximation preserving reduction from $k$-DM to the maximum weight $b$-matching problem. Leveraging this reduction and an existing semi-streaming $b$-matching algorithm, we design a $(\frac{1}{2+\varepsilon})(1 - \frac{1}{k+1})$-approximate semi-streaming algorithm for $k$-DM. For any constant $\varepsilon > 0$, both of these algorithms require $O(nk \log_{1+\varepsilon}^2 n)$ bits of space. To the best of our knowledge, this is the first study of semi-streaming algorithms for the $k$-DM problem. We compare our two algorithms to state-of-the-art offline algorithms on 95 real-world and synthetic test problems, including thirteen graphs generated from data center network traces. On these instances, our streaming algorithms used significantly less memory (ranging from 6$\times$ to 512$\times$ less) and were faster in runtime than the offline algorithms. Our solutions were often within 5% of the best weights from the offline algorithms. We highlight that the existing offline algorithms run out of 1 TB memory for most of the large instances ($>1$ billion edges), whereas our streaming algorithms can solve these problems using only 100 GB memory for $k=8$.

Phenomics is an emerging branch of modern biology that uses high throughput phenotyping tools to capture multiple environmental and phenotypic traits, often at massive spatial and temporal scales. The resulting high dimensional data represent a treasure trove of information for providing an in-depth understanding of how multiple factors interact and contribute to the overall growth and behavior of different genotypes. However, computational tools that can parse through such complex data and aid in extracting plausible hypotheses are currently lacking. In this article, we present Hyppo-X, a new algorithmic approach to visually explore complex phenomics data and in the process characterize the role of environment on phenotypic traits. We model the problem as one of unsupervised structure discovery, and use emerging principles from algebraic topology and graph theory for discovering higher-order structures of complex phenomics data. We present an open source software which has interactive visualization capabilities to facilitate data navigation and hypothesis formulation. We test and evaluate Hyppo-X on two real-world plant (maize) data sets. Our results demonstrate the ability of our approach to delineate divergent subpopulation-level behavior. Notably, our approach shows how environmental factors could influence phenotypic behavior, and how that effect varies across different genotypes and different time scales. To the best of our knowledge, this effort provides one of the first approaches to systematically formalize the problem of hypothesis extraction for phenomics data. Considering the infancy of the phenomics field, tools that help users explore complex data and extract plausible hypotheses in a data-guided manner will be critical to future advancements in the use of such data.

Given a simplicial complex with weights on its simplices, and a nontrivial cycle on it, we are interested in finding the cycle with minimal weight which is homologous to the given one. Assuming that the homology is defined with integer ($\mathbb{Z}$) coefficients, we show the following (Theorem 5.2): For a finite simplicial complex K of dimension greater than p, the boundary matrix $[\partial_{p+1}]$ is totally unimodular if and only if $H_p(L, L_0)$ is torsion-free for all pure subcomplexes $L_0, L$ in K of dimensions p and $p+1$, respectively, where $L_0 \subsetL$. Because of the total unimodularity of the boundary matrix, we can solve the optimization problem, which is inherently an integer programming problem, as a linear program and obtain an integer solution. Thus, the problem of finding optimal cycles in a given homology class can be solved in polynomial time. This result is surprising in the backdrop of a recent result which says that the problem is NP-hard under $\mathbb{Z}_2$ coefficients which, being a field, is in general easier to deal with. Our result implies, among other things, that one can compute in polynomial time an optimal $(d-1)$-cycle in a given homology class for any triangulation of an orientable compact d-manifold or for any finite simplicial complex embedded in $\mathbb{R}^d$. Our optimization approach can also be used for various related problems, such as finding an optimal chain homologous to a given one when these are not cycles. Our result can also be viewed as providing a topological characterization of total unimodularity.

Given a simplicial complex with weights on its simplices, and a nontrivial cycle on it, we are interested in finding the cycle with minimal weight which is homologous to the given one. Assuming that the homology is defined with integer (Z) coefficients, we show the following: For a finite simplicial complex K of dimension greater than p, the boundary matrix [partialp+1] is totally unimodular if and only if Hp(L, L0) is torsion-free, for all pure subcomplexes L0, L in K of dimensions p and p+1 respectively, where L0 ⊂ L.

MOTIVATION: There is a need for an efficient and accurate computational method to identify the effects of single- and multiple-residue mutations on the stability and reactivity of proteins. Such a method should ideally be consistent and yet applicable in a widespread manner, i.e. it should be applied to various proteins under the same parameter settings, and have good predictive power for all of them. RESULTS: We develop a Delaunay tessellation-based four-body scoring function to predict the effects of single- and multiple-residue mutations on the stability and reactivity of proteins. We test our scoring function on sets of single-point mutations used by several previous studies. We also assemble a new, diverse set of 237 single- and multiple-residue mutations, from over 24 different publications. The four-body scoring function correctly predicted the changes to the stability of 169 out of 210 mutants (80.5%), and the changes to the reactivity of 17 out of 27 mutants (63%). For the mutants that had the changes in stability/reactivity quantified (using reaction rates, temperatures, etc.), an average Spearman rank correlation coefficient of 0.67 was achieved with the four-body scores. We also develop an efficient method for screening huge numbers of mutants of a protein, called combinatorial mutagenesis. In one study, 64 million mutants of a cold-shock nucleus binding domain protein 1CSQ, with six of its residues being changed to all possible (20) amino acids, were screened within a few hours on a PC, and all five stabilizing mutants reported were correctly identified as stabilizing by combinatorial mutagenesis.

MOTIVATION: Most scoring functions used in protein fold recognition employ two-body (pseudo) potential energies. The use of higher-order terms may improve the performance of current algorithms. METHODS: Proteins are represented by the side chain centroids of amino acids. Delaunay tessellation of this representation defines all sets of nearest neighbor quadruplets of amino acids. Four-body contact scoring function (log likelihoods of residue quadruplet compositions) is derived by the analysis of a diverse set of proteins with known structures. A test protein is characterized by the total score calculated as the sum of the individual log likelihoods of composing amino acid quadruplets. RESULTS: The scoring function distinguishes native from partially unfolded or deliberately misfolded structures. It also discriminates between pre- and post-transition state and native structures in the folding simulations trajectory of Chymotrypsin Inhibitor 2 (CI2).