More Like this

1. Maximum Subbarcode Matching and Subbarcode Distance

   Chubet, Oliver ( January 2022 , Canadian Conference in Computational Geometry)

   Bahoo, Yeganeh ; Georgiou, Konstantinos (Ed.)

   We investigate the maximum subbarcode matching problem which arises from the study of persistent homology and introduce the subbarcode distance on barcodes. A barcode is a set of intervals which correspond to topological features in data and is the output of a persistent homology computation. A barcode A has a subbarcode matching to B if each interval in A matches to an interval in B which contains it. We present an algorithm which takes two barcodes, A and B, and returns a maximum subbarcode matching. 

   more » « less
2. Composition closed premodel structures and the Kreweras lattice

   https://doi.org/10.1016/j.ejc.2023.103879  

   Balchin, Scott ; MacBrough, Ethan ; Ormsby, Kyle ( February 2024 , European Journal of Combinatorics)

   We investigate the rich combinatorial structure of premodel structures on finite lattices whose weak equivalences are closed under composition. We prove that there is a natural refinement of the inclusion order of weak factorization systems so that the intervals detect these composition closed premodel structures. In the case that the lattice in question is a finite total order, this natural order retrieves the Kreweras lattice of noncrossing partitions as a refinement of the Tamari lattice, and model structures can be identified with certain tricolored trees. 

   more » « less
3. Maximal Chains in Bond Lattices

   https://doi.org/10.37236/10983  

   Ahirwar, Shreya ; Fishel, Susanna ; Gya, Parikshita ; Harris, Pamela ; Pham, Nguyen ; Vindas Meléndez, Andrés ; Vo, Dan Khanh ( July 2022 , The Electronic Journal of Combinatorics)

   Let $G$ be a graph with vertex set $\{1,2,\ldots,n\}$. Its bond lattice, $BL(G)$, is a sublattice of the set partition lattice. The elements of $BL(G)$ are the set partitions whose blocks induce connected subgraphs of $G$. In this article, we consider graphs $G$ whose bond lattice consists only of noncrossing partitions. We define a family of graphs, called triangulation graphs, with this property and show that any two produce isomorphic bond lattices. We then look at the enumeration of the maximal chains in the bond lattices of triangulation graphs. Stanley's map from maximal chains in the noncrossing partition lattice to parking functions was our motivation. We find the restriction of his map to the bond lattice of certain subgraphs of triangulation graphs. Finally, we show the number of maximal chains in the bond lattice of a triangulation graph is the number of ordered cycle decompositions. 

   more » « less
4. Best Practices in Designing, Sequencing, and Identifying Random DNA Barcodes

   https://doi.org/10.1007/s00239-022-10083-z  

   Johnson, Milo S. ; Venkataram, Sandeep ; Kryazhimskiy, Sergey ( January 2023 , Journal of Molecular Evolution)

   Random DNA barcodes are a versatile tool for tracking cell lineages, with applications ranging from development to cancer to evolution. Here, we review and critically evaluate barcode designs as well as methods of barcode sequencing and initial processing of barcode data. We first demonstrate how various barcode design decisions affect data quality and propose a new design that balances all considerations that we are currently aware of. We then discuss various options for the preparation of barcode sequencing libraries, including inline indices and Unique Molecular Identifiers (UMIs). Finally, we test the performance of several established and new bioinformatic pipelines for the extraction of barcodes from raw sequencing reads and for error correction. We find that both alignment and regular expression-based approaches work well for barcode extraction, and that error-correction pipelines designed specifically for barcode data are superior to generic ones. Overall, this review will help researchers to approach their barcoding experiments in a deliberate and systematic way.

    

   more » « less
5. Affinely representable lattices, stable matchings, and choice functions

   https://doi.org/10.1007/978-3-030-73879-2_7  

   Faenza, Y. ; Zhang, X. ( June 2021 , Lecture notes in computer science)

   Singh, M. ; Williamson, D. (Ed.)

   Birkhoff’s representation theorem defines a bijection between elements of a distributive lattice L and the family of upper sets of an associated poset B. When elements of L are the stable matchings in an instance of Gale and Shapley’s marriage model, Irving et al. showed how to use B to devise a combinatorial algorithm for maximizing a linear function over the set of stable matchings. In this paper, we introduce a general property of distributive lattices, which we term as affine representability, and show its role in efficiently solving linear optimization problems over the elements of a distributive lattice, as well as describing the convex hull of the characteristic vectors of lattice elements. We apply this concept to the stable matching model with path-independent quotafilling choice functions, thus giving efficient algorithms and a compact polyhedral description for this model. To the best of our knowledge, this model generalizes all models from the literature for which similar results were known, and our paper is the first that proposes efficient algorithms for stable matchings with choice functions, beyond extension of the Deferred Acceptance algorithm. 

   more » « less