An official website of the United States government
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)$$ time and$$\mathcal {O} (\ell \log \ell )$$ space, where |t| is the number of$$k$$ -mers inside the sketch of the reference, |p| is the number of$$k$$ -mers inside the read’s sketch and$$\ell$$ is the number of times that$$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
This content will become publicly available on December 1, 2026
Rocket-crane algorithm for the Feedback Arc Set problem
Understanding information flow in the brain can be facilitated by arranging neurons in the fly connectome to form a maximally “feedforward” structure. This task is naturally formulated as the Minimum Feedback Arc Set (MFAS)—a well-known NP-hard problem, especially for large-scale graphs. To address this, we propose the Rocket-Crane algorithm, an efficient two-phase method for solving MFAS. In the first phase, we develop a continuous-space optimization method that rapidly generates excellent solutions. In the second phase, we refine these solutions through advanced exploration techniques that integrate randomized and heuristic strategies to effectively escape local minima. Extensive experiments demonstrate that Rocket-Crane outperforms state-of-the-art methods in terms of solution quality, scalability, and computational efficiency. On the primary benchmark—the fly connectom—our method achieved a feedforward arc set with a total forward weight of 35,459,266 (about 85$$\%$$ ), the highest among all competing methods. The algorithm is open-source and available on GitHub.
more »
« less
- PAR ID:
- 10655187
- Publisher / Repository:
- Springer
- Date Published:
- Journal Name:
- Social Network Analysis and Mining
- Volume:
- 15
- Issue:
- 1
- ISSN:
- 1869-5469
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract The Li-Stephens (LS) haplotype copying model forms the basis of a number of important statistical inference procedures in genetics. LS is a probabilistic generative model which supposes that a sampled chromosome is an imperfect mosaic of other chromosomes found in a population. In the frequentist setting which is the focus of this paper, the output of LS is a “copying path” through chromosome space. The behavior of LS depends crucially on two user-specified parameters,$$\theta $$ and$$\rho $$ , which are respectively interpreted as the rates of mutation and recombination. However, because LS is not based on a realistic model of ancestry, the precise connection between these parameters and the biological phenomena they represent is unclear. Here, we offer an alternative perspective, which considers$$\theta $$ and$$\rho $$ as tuning parameters, and seeks to understand their impact on the LS output. We derive an algorithm which, for a given dataset, efficiently partitions the$$(\theta ,\rho )$$ plane into regions where the output of the algorithm is constant, thereby enumerating all possible solutions to the LS model in one go. We extend this approach to the “diploid LS” model commonly used for phasing. We demonstrate the usefulness of our method by studying the effects of changing$$\theta $$ and$$\rho $$ when using LS for common bioinformatic tasks. Our findings indicate that using the conventional (i.e., population-scaled) values for$$\theta $$ and$$\rho $$ produces near optimal results for imputation, but may systematically inflate switch error in the case of phasing diploid genotypes.more » « less
-
Abstract We show that for any quadratic extension of number fields$$K/F$$ , there exists an abelian variety$$A/F$$ of positive rank whose rank does not grow upon base change to$$K$$ . This result implies that Hilbert’s tenth problem over the ring of integers of any number field has a negative solution. That is, for the ring$${\mathcal{O}}_{K}$$ of integers of any number field$$K$$ , there does not exist an algorithm that answers the question of whether a polynomial equation in several variables over $${\mathcal{O}}_{K}$$ has solutions in $${\mathcal{O}}_{K}$$ .more » « less
-
Agricola, Ilka; Bögelein, Verena (Ed.)Abstract Murphy and the second author showed that a generic closed Riemannian manifold has no totally geodesic submanifolds, provided the ambient space is at least four dimensional. Lytchak and Petrunin established a similar result in dimension 3. For the higher dimensional result, the “generic set” is open and dense in the$$C^{q}$$ –topology for any$$q\ge 2.$$ In Lytchak and Petrunin’s work, the “generic set” is a dense$$G_{\delta }$$ in the$$C^{q}$$ –topology for any$$q\ge 2.$$ Here we show that the set of such metrics on a compact 3–manifold actually contains a set that is that is open and dense set in the$$C^{q}$$ –topology, provided$$q\ge 3.$$more » « less
-
Abstract We establish a first general partial regularity theorem for area minimizing currents$${\mathrm{mod}}(p)$$ , for everyp, in any dimension and codimension. More precisely, we prove that the Hausdorff dimension of the interior singular set of anm-dimensional area minimizing current$${\mathrm{mod}}(p)$$ cannot be larger than$$m-1$$ . Additionally, we show that, whenpis odd, the interior singular set is$$(m-1)$$ -rectifiable with locally finite$$(m-1)$$ -dimensional measure.more » « less
