skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


This content will become publicly available on December 1, 2025

Title: Pfp-fm: an accelerated FM-index
Abstract FM-indexes are crucial data structures in DNA alignment, but searching with them usually takes at least one random access per character in the query pattern. Ferragina and Fischer [1] observed in 2007 that word-based indexes often use fewer random accesses than character-based indexes, and thus support faster searches. Since DNA lacks natural word-boundaries, however, it is necessary to parse it somehow before applying word-based FM-indexing. In 2022, Deng et al. [2] proposed parsing genomic data by induced suffix sorting, and showed that the resulting word-based FM-indexes support faster counting queries than standard FM-indexes when patterns are a few thousand characters or longer. In this paper we show that using prefix-free parsing—which takes parameters that let us tune the average length of the phrases—instead of induced suffix sorting, gives a significant speedup for patterns of only a few hundred characters. We implement our method and demonstrate it is between 3 and 18 times faster than competing methods on queries to GRCh38, and is consistently faster on queries made to 25,000, 50,000 and 100,000 SARS-CoV-2 genomes. Hence, it seems our method accelerates the performance of count over all state-of-the-art methods with a moderate increase in the memory. The source code for$$\texttt {PFP-FM}$$ PFP - FM is available athttps://github.com/AaronHong1024/afm.  more » « less
Award ID(s):
2013998
PAR ID:
10549030
Author(s) / Creator(s):
; ; ; ; ;
Publisher / Repository:
SPIRE
Date Published:
Journal Name:
Algorithms for Molecular Biology
Volume:
19
Issue:
1
ISSN:
1748-7188
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract Given a suitable solutionV(t, x) to the Korteweg–de Vries equation on the real line, we prove global well-posedness for initial data$$u(0,x) \in V(0,x) + H^{-1}(\mathbb {R})$$ u ( 0 , x ) V ( 0 , x ) + H - 1 ( R ) . Our conditions onVdo include regularity but do not impose any assumptions on spatial asymptotics. We show that periodic profiles$$V(0,x)\in H^5(\mathbb {R}/\mathbb {Z})$$ V ( 0 , x ) H 5 ( R / Z ) satisfy our hypotheses. In particular, we can treat localized perturbations of the much-studied periodic traveling wave solutions (cnoidal waves) of KdV. In the companion paper Laurens (Nonlinearity. 35(1):343–387, 2022.https://doi.org/10.1088/1361-6544/ac37f5) we show that smooth step-like initial data also satisfy our hypotheses. We employ the method of commuting flows introduced in Killip and Vişan (Ann. Math. (2) 190(1):249–305, 2019.https://doi.org/10.4007/annals.2019.190.1.4) where$$V\equiv 0$$ V 0 . In that setting, it is known that$$H^{-1}(\mathbb {R})$$ H - 1 ( R ) is sharp in the class of$$H^s(\mathbb {R})$$ H s ( R ) spaces. 
    more » « less
  2. Abstract By means of a unifying measure-theoretic approach, we establish lower bounds on the Hausdorff dimension of the space-time set which can support anomalous dissipation for weak solutions of fluid equations, both in the presence or absence of a physical boundary. Boundary dissipation, which can occur at both the time and the spatial boundary, is analyzed by suitably modifying the Duchon & Robert interior distributional approach. One implication of our results is that any bounded Euler solution (compressible or incompressible) arising as a zero viscosity limit of Navier–Stokes solutions cannot have anomalous dissipation supported on a set of dimension smaller than that of the space. This result is sharp, as demonstrated by entropy-producing shock solutions of compressible Euler (Drivas and Eyink in Commun Math Phys 359(2):733–763, 2018.https://doi.org/10.1007/s00220-017-3078-4; Majda in Am Math Soc 43(281):93, 1983.https://doi.org/10.1090/memo/0281) and by recent constructions of dissipative incompressible Euler solutions (Brue and De Lellis in Commun Math Phys 400(3):1507–1533, 2023.https://doi.org/10.1007/s00220-022-04626-0 624; Brue et al. in Commun Pure App Anal, 2023), as well as passive scalars (Colombo et al. in Ann PDE 9(2):21–48, 2023.https://doi.org/10.1007/s40818-023-00162-9; Drivas et al. in Arch Ration Mech Anal 243(3):1151–1180, 2022.https://doi.org/10.1007/s00205-021-01736-2). For$$L^q_tL^r_x$$ L t q L x r suitable Leray–Hopf solutions of the$$d-$$ d - dimensional Navier–Stokes equation we prove a bound of the dissipation in terms of the Parabolic Hausdorff measure$$\mathcal {P}^{s}$$ P s , which gives$$s=d-2$$ s = d - 2 as soon as the solution lies in the Prodi–Serrin class. In the three-dimensional case, this matches with the Caffarelli–Kohn–Nirenberg partial regularity. 
    more » « less
  3. Abstract Deep Neural Networks (DNNs) are increasingly deployed in critical applications, where ensuring their safety and robustness is paramount. We present$$_\text {CAV25}$$ CAV 25 , a high-performance DNN verification tool that uses the DPLL(T) framework and supports a wide-range of network architectures and activation functions. Since its debut in VNN-COMP’23, in which it achieved the New Participant Award and ranked 4th overall,$$_\text {CAV25}$$ CAV 25 has advanced significantly, achieving second place in VNN-COMP’24. This paper presents and evaluates the latest development of$$_\text {CAV25}$$ CAV 25 , focusing on the versatility, ease of use, and competitive performance of the tool.$$_\text {CAV25}$$ CAV 25 is available at:https://github.com/dynaroars/neuralsat. 
    more » « less
  4. Abstract This article revisits the problem of global well-posedness for the generalized parabolic Anderson model on$$\mathbb {R}^+\times \mathbb {T}^2$$ R + × T 2 within the framework of paracontrolled calculus (Gubinelli et al. in Forum Math, 2015). The model is given by the equation:$$\begin{aligned} (\partial _t-\Delta ) u=F(u)\eta \end{aligned}$$ ( t - Δ ) u = F ( u ) η where$$\eta \in C^{-1-\kappa }$$ η C - 1 - κ with$$1/6>\kappa >0$$ 1 / 6 > κ > 0 , and$$F\in C_b^2(\mathbb {R})$$ F C b 2 ( R ) . Assume that$$\eta \in C^{-1-\kappa }$$ η C - 1 - κ and can be lifted to enhanced noise, we derive new a priori bounds. The key idea follows from the recent work by Chandra et al. (A priori bounds for 2-d generalised Parabolic Anderson Model,,2024), to represent the leading error term as a transport type term, and our techniques encompass the paracontrolled calculus, the maximum principle, and the localization approach (i.e. high-low frequency argument). 
    more » « less
  5. Abstract The anomalous Hall effect (AHE), typically observed in ferromagnetic (FM) metals with broken time-reversal symmetry, depends on electronic and magnetic properties. In Co3Sn2-xInxS2, a giant AHE has been attributed to Berry curvature associated with the FM Weyl semimetal phase, yet recent studies report complicated magnetism. We use neutron scattering to determine the spin dynamics and structures as a function ofxand provide a microscopic understanding of the AHE and magnetism interplay. Spin gap and stiffness indicate a contribution from Weyl fermions consistent with the AHE. The magnetic structure evolves fromc-axis ferromagnetism at$$x = 0$$ x = 0 to a canted antiferromagnetic (AFM) structure with reducedc-axis moment and in-plane AFM order at$$x = 0.12$$ x = 0.12 and further reducedc-axis FM moment at$$x = 0.3$$ x = 0.3 . Since noncollinear spins can induce non-zero Berry curvature in real space acting as a fictitious magnetic field, our results revealed another AHE contribution, establishing the impact of magnetism on transport. 
    more » « less