More Like this

1. ESKEMAP: exact sketch-based read mapping

   https://doi.org/10.1186/s13015-024-00261-7  

   Schulz, Tizian; Medvedev, Paul (December 2024, Algorithms for Molecular Biology)

   Abstract BackgroundGiven a sequencing read, the broad goal of read mapping is to find the location(s) in the reference genome that have a “similar sequence”. Traditionally, “similar sequence” was defined as having a high alignment score and read mappers were viewed as heuristic solutions to this well-defined problem. For sketch-based mappers, however, there has not been a problem formulation to capture what problem an exact sketch-based mapping algorithm should solve. Moreover, there is no sketch-based method that can find all possible mapping positions for a read above a certain score threshold. ResultsIn this paper, we formulate the problem of read mapping at the level of sequence sketches. We give an exact dynamic programming algorithm that finds all hits above a given similarity threshold. It runs in$$\mathcal {O} (|t| + |p| + \ell ^2)$$ $O\left(\right|t|+|p|+{\ell }^2)$time and$$\mathcal {O} (\ell \log \ell )$$ $O(\ell log\ell )$space, where |t| is the number of$$k$$ $k$-mers inside the sketch of the reference, |p| is the number of$$k$$ $k$-mers inside the read’s sketch and$$\ell$$ $\ell$is the number of times that$$k$$ $k$-mers from the pattern sketch occur in the sketch of the text. We evaluate our algorithm’s performance in mapping long reads to the T2T assembly of human chromosome Y, where ampliconic regions make it desirable to find all good mapping positions. For an equivalent level of precision as minimap2, the recall of our algorithm is 0.88, compared to only 0.76 of minimap2. 

   more » « less
2. Connection probabilities of multiple FK-Ising interfaces

   https://doi.org/10.1007/s00440-024-01269-1  

   Feng, Yu; Peltola, Eveliina; Wu, Hao (June 2024, Probability Theory and Related Fields)

   Abstract We find the scaling limits of a general class of boundary-to-boundary connection probabilities and multiple interfaces in the critical planar FK-Ising model, thus verifying predictions from the physics literature. We also discuss conjectural formulas using Coulomb gas integrals for the corresponding quantities in general critical planar random-cluster models with cluster-weight$${q \in [1,4)}$$ $q\in [1,4)$. Thus far, proofs for convergence, including ours, rely on discrete complex analysis techniques and are beyond reach for other values ofqthan the FK-Ising model ($$q=2$$ $q=2$). Given the convergence of interfaces, the conjectural formulas for other values ofqcould be verified similarly with relatively minor technical work. The limit interfaces are variants of$$\text {SLE}_\kappa $$ ${\text{SLE}}_{\kappa }$curves (with$$\kappa = 16/3$$ $\kappa =16/3$for$$q=2$$ $q=2$). Their partition functions, that give the connection probabilities, also satisfy properties predicted for correlation functions in conformal field theory (CFT), expected to describe scaling limits of critical random-cluster models. We verify these properties for all$$q \in [1,4)$$ $q\in [1,4)$, thus providing further evidence of the expected CFT description of these models. 

   more » « less
3. Block mapping class groups and their finiteness properties

   https://doi.org/10.1007/s10711-025-00985-9  

   Aramayona, J; Aroca, J; Cumplido, M; Skipper, R; Wu, X (April 2025, Geometriae Dedicata)

   Abstract Given$$g \in \mathbb N \cup \{0, \infty \}$$ $g\in N\cup \{0,\infty \}$, let$$\Sigma _g$$ ${\Sigma }_g$denote the closed surface of genusgwith a Cantor set removed, if$$g<\infty $$ $g<\infty$; or the blooming Cantor tree, when$$g= \infty $$ $g=\infty$. We construct a family$$\mathfrak B(H)$$ $B\left(H\right)$of subgroups of$${{\,\textrm{Map}\,}}(\Sigma _g)$$ $\text{Map}\left({\Sigma }_g\right)$whose elements preserve ablock decompositionof$$\Sigma _g$$ ${\Sigma }_g$, andeventually like actlike an element ofH, whereHis a prescribed subgroup of the mapping class group of the block. The group$$\mathfrak B(H)$$ $B\left(H\right)$surjects onto an appropriate symmetric Thompson group of Farley–Hughes; in particular, it answers positively. Our main result asserts that$$\mathfrak B(H)$$ $B\left(H\right)$is of type$$F_n$$ $F_n$if and only ifHis. As a consequence, for every$$g\in \mathbb N \cup \{0, \infty \}$$ $g\in N\cup \{0,\infty \}$and every$$n\ge 1$$ $n\ge 1$, we construct a subgroup$$G <{{\,\textrm{Map}\,}}(\Sigma _g)$$ $G<\text{Map}\left({\Sigma }_g\right)$that is of type$$F_n$$ $F_n$but not of type$$F_{n+1}$$ $F_{n+1}$, and which contains the mapping class group of every compact surface of genus$$\le g$$ $\le g$and with non-empty boundary. 

   more » « less
4. Better Hardness Results for the Minimum Spanning Tree Congestion Problem

   https://doi.org/10.1007/s00453-024-01278-5  

   Luu, Huong; Chrobak, Marek (January 2025, Algorithmica)

   Abstract In the spanning tree congestion problem, given a connected graphG, the objective is to compute a spanning treeTinGthat minimizes its maximum edge congestion, where the congestion of an edgeeofTis the number of edges inGfor which the unique path inTbetween their endpoints traversese. The problem is known to be$$\mathbb{N}\mathbb{P}$$ $NP$-hard, but its approximability is still poorly understood, and it is not even known whether the optimum solution can be efficiently approximated with ratioo(n). In the decision version of this problem, denoted$${\varvec{K}-\textsf {STC}}$$ $K-\mathrm{STC}$, we need to determine ifGhas a spanning tree with congestion at mostK. It is known that$${\varvec{K}-\textsf {STC}}$$ $K-\mathrm{STC}$is$$\mathbb{N}\mathbb{P}$$ $NP$-complete for$$K\ge 8$$ $K\ge 8$, and this implies a lower bound of 1.125 on the approximation ratio of minimizing congestion. On the other hand,$${\varvec{3}-\textsf {STC}}$$ $3-\mathrm{STC}$can be solved in polynomial time, with the complexity status of this problem for$$K\in { \left\{ 4,5,6,7 \right\} }$$ $K\in \left(4,,,5,,,6,,,7\right)$remaining an open problem. We substantially improve the earlier hardness results by proving that$${\varvec{K}-\textsf {STC}}$$ $K-\mathrm{STC}$is$$\mathbb{N}\mathbb{P}$$ $NP$-complete for$$K\ge 5$$ $K\ge 5$. This leaves only the case$$K=4$$ $K=4$open, and improves the lower bound on the approximation ratio to 1.2. Motivated by evidence that minimizing congestion is hard even for graphs of small constant radius, we also consider$${\varvec{K}-\textsf {STC}}$$ $K-\mathrm{STC}$restricted to graphs of radius 2, and we prove that this variant is$$\mathbb{N}\mathbb{P}$$ $NP$-complete for all$$K\ge 6$$ $K\ge 6$. 

   more » « less
5. Surface Houghton groups

   https://doi.org/10.1007/s00208-023-02751-2  

   Aramayona, Javier; Bux, Kai-Uwe; Kim, Heejoung; Leininger, Christopher J. (November 2023, Mathematische Annalen)

   Abstract For every$$n\ge 2$$ $n\ge 2$, thesurface Houghton group$${\mathcal {B}}_n$$ $B_n$is defined as the asymptotically rigid mapping class group of a surface with exactlynends, all of them non-planar. The groups$${\mathcal {B}}_n$$ $B_n$are analogous to, and in fact contain, the braided Houghton groups. These groups also arise naturally in topology: every monodromy homeomorphism of a fibered component of a depth-1 foliation of closed 3-manifold is conjugate into some$${\mathcal {B}}_n$$ $B_n$. As countable mapping class groups of infinite type surfaces, the groups$$\mathcal {B}_n$$ $B_n$lie somewhere between classical mapping class groups and big mapping class groups. We initiate the study of surface Houghton groups proving, among other things, that$$\mathcal {B}_n$$ $B_n$is of type$$\text {F}_{n-1}$$ ${\text{F}}_{n-1}$, but not of type$$\text {FP}_{n}$$ ${\text{FP}}_n$, analogous to the braided Houghton groups. 

   more » « less