42,014 research outputs found
The open-closed mod-minimizer algorithm
No full textSampling algorithms that deterministically select a subset of k-mers are an important building block in bioinformat-ics applications. For example, they are used to index large textual collections, like DNA, and to compare sequences quickly. In such applications, a sampling algorithm is required to select one k-mer out of every window of w consecu-tive k-mers. The folklore and most used scheme is the random minimizer that selects the smallest k-mer in the win-dow according to some random order. This scheme is remarkably simple and versatile, and has a density (expected fraction of selected k-mers) of 2/(w+1) . In practice, lower density leads to faster methods and smaller indexes, and it turns out that the random minimizer is not the best one can do. Indeed, some schemes are known to approach optimal density 1/w when k ->infinity , like the recently introduced mod-minimizer (Groot Koerkamp and Pibiri, WABI 2024). In this work, we study methods that achieve low density when k <= w . In this small-k regime, a practical method with provably better density than the random minimizer is the miniception (Zheng et al., Bioinformatics 2021). This method can be elegantly described as sampling the smallest closed sycnmer (Edgar, PeerJ 2021) in the window according to some random order. We show that extending the miniception to prefer sampling open syncmers yields much better density. This new method-the open-closed minimizer-offers improved density for small k <= w while being as fast to compute as the random minimizer. Compared to methods based on decycling sets, that achieve very low density in the small-k regime, our method has comparable density while being computation-ally simpler and intuitive. Furthermore, we extend the mod-minimizer to improve density of any scheme that works well for small k to also work well when k>w is large. We hence obtain the open-closed mod-minimizer, a practical method that improves over the mod-minimizer for all
The mod-minimizer: A Simple and Efficient Sampling Algorithm for Long k-mers
No full textGiven a string S, a minimizer scheme is an algorithm defined by a triple (k,w,O) that samples a subset of k-mers (k-long substrings) from a string S. Specifically, it samples the smallest k-mer according to the order O from each window of w consecutive k-mers in S. Because consecutive windows can sample the same k-mer, the set of the sampled k-mers is typically much smaller than S. More generally, we consider substring sampling algorithms that respect a window guarantee: at least one k-mer must be sampled from every window of w consecutive k-mers. As a sampled k-mer is uniquely identified by its absolute position in S, we can define the density of a sampling algorithm as the fraction of distinct sampled positions. Good methods have low density which, by respecting the window guarantee, is lower bounded by 1/w. It is however difficult to design a sequence-agnostic algorithm with provably optimal density. In practice, the order O is usually implemented using a pseudo-random hash function to obtain the so-called random minimizer. This scheme is simple to implement, very fast to compute even in streaming fashion, and easy to analyze. However, its density is almost a factor of 2 away from the lower bound for large windows.
In this work we introduce mod-sampling, a two-step sampling algorithm to obtain new minimizer schemes. Given a (small) parameter t, the mod-sampling algorithm finds the position p of the smallest t-mer in a window. It then samples the k-mer at position pod w. The lr-minimizer uses t = k-w and the mod-minimizer uses t≡ k (mod w).
These new schemes have provably lower density than random minimizers and other schemes when k is large compared to w, while being as fast to compute. Importantly, the mod-minimizer achieves optimal density when k → ∞. Although the mod-minimizer is not the first method to achieve optimal density for large k, its proof of optimality is simpler than previous work. We provide pseudocode for a number of other methods and compare to them. In practice, the mod-minimizer has considerably lower density than the random minimizer and other state-of-the-art methods, like closed syncmers and miniception, when k > w. We plugged the mod-minimizer into SSHash, a k-mer dictionary based on minimizers. For default parameters (w,k) = (11,21), space usage decreases by 15% when indexing the whole human genome (GRCh38), while maintaining its fast query time
U-Index: A Universal Indexing Framework for Matching Long Patterns
No full textMotivation. Text indexing is a fundamental and well-studied problem. Classic solutions to this problem either replace the original text with a compressed representation, e.g., the FM-index and its variants, or keep it uncompressed but attach some redundancy - an index - to accelerate matching, e.g., the suffix array. The former solutions thus retain excellent compressed space, but are practically slow to construct and query. The latter approaches, instead, sacrifice space efficiency but are typically faster; for example, the suffix array takes much more space than the text itself for commonly used alphabets, like ASCII or DNA, but it is very fast to construct and query. Methods. In this paper, we show that efficient text indexing can be achieved using just a small extra space on top of the original text, provided that the query patterns are sufficiently long. More specifically, we develop a new indexing paradigm in which a sketch of a query pattern is first matched against a sketch of the text. Once candidate matches are retrieved, they are verified using the original text. This paradigm is thus universal in the sense that it allows us to use any solution to index the sketched text, like a suffix array, FM-index, or r-index. Results. We explore both the theory and the practice of this universal framework. With an extensive experimental analysis, we show that, surprisingly, universal indexes can be constructed much faster than their unsketched counterparts and take a fraction of the space, as a direct consequence of (i) having a lower bound on the length of patterns and (ii) working in sketch space. Furthermore, these data structures have the potential of retaining or even improving query time, because matching against the sketched text is faster and verifying candidates can be theoretically done in constant time per occurrence (or, in practice, by short and cache-friendly scans of the text). Finally, we discuss some important applications of this novel indexing paradigm to computational biology. We hypothesize that such indexes will be particularly effective when the queries are sufficiently long, and so we demonstrate applications in long-read mapping
U-Index: A Universal Indexing Framework for Matching Long Patterns
No full textA related version of this article is available at arXiv:2502.14488v3 [cs.DS] (https://arxiv.org/abs/2502.14488). Comments: SEA-2025 version. 18 pages, 6 figures, code available at https://github.com/u-index/u-index-rs . ACM classes: F.2.2; J.3. Submission history: From: Ragnar Groot Koerkamp: [v1] Thu, 20 Feb 2025 12:09:34 UTC (383 KB); [v2] Fri, 21 Feb 2025 13:35:43 UTC (383 KB); [v3] Tue, 27 May 2025 12:05:04 UTC (459 KB).Motivation. Text indexing is a fundamental and well-studied problem. Classic solutions to this problem either replace the original text with a compressed representation, e.g., the FM-index and its variants, or keep it uncompressed but attach some redundancy - an index - to accelerate matching, e.g., the suffix array. The former solutions thus retain excellent compressed space, but are practically slow to construct and query. The latter approaches, instead, sacrifice space efficiency but are typically faster; for example, the suffix array takes much more space than the text itself for commonly used alphabets, like ASCII or DNA, but it is very fast to construct and query.
Methods. In this paper, we show that efficient text indexing can be achieved using just a small extra space on top of the original text, provided that the query patterns are sufficiently long. More specifically, we develop a new indexing paradigm in which a sketch of a query pattern is first matched against a sketch of the text. Once candidate matches are retrieved, they are verified using the original text. This paradigm is thus universal in the sense that it allows us to use any solution to index the sketched text, like a suffix array, FM-index, or r-index.
Results. We explore both the theory and the practice of this universal framework. With an extensive experimental analysis, we show that, surprisingly, universal indexes can be constructed much faster than their unsketched counterparts and take a fraction of the space, as a direct consequence of (i) having a lower bound on the length of patterns and (ii) working in sketch space. Furthermore, these data structures have the potential of retaining or even improving query time, because matching against the sketched text is faster and verifying candidates can be theoretically done in constant time per occurrence (or, in practice, by short and cache-friendly scans of the text).
Finally, we discuss some important applications of this novel indexing paradigm to computational biology. We hypothesize that such indexes will be particularly effective when the queries are sufficiently long, and so we demonstrate applications in long-read mapping.Gabriele Fici: Supported by MUR project PRIN 2022 APML – 20229BCXNW, funded
by the European Union -– Mission 4 “Education and Research” C2 - Investment 1.1. CUP
Master_B53D23012910006.
Ragnar Groot Koerkamp: ETH Research Grant ETH-1721-1 to Gunnar Rätsch.
Rob Patro: NIH grant award number R01HG009937, NSF award CNS-1763680 and grants 252586 and
2024342821 from the Chan Zuckerberg Initiative DAF, an advised fund of Silicon Valley Community
Foundation. RP is a co-founder of Ocean Genomics, Inc.
Giulio Ermanno Pibiri: European Union’s Horizon Europe research and innovation programme
(EFRA project, Grant Agreement Number 101093026). This work was also partially supported by
DAIS – Ca’ Foscari University of Venice within the IRIDE program.
Solon P. Pissis: Supported by the PANGAIA and ALPACA projects that have received funding
from the European Union’s Horizon 2020 research and innovation programme under the Marie
Skłodowska-Curie grant agreements No 872539 and 956229, respectively
The dialogue between the author and the hero in the “Notes” of G. R. Derzhavin
No full textВ центре внимания автора статьи «Записки» Г. Р. Державина, представляющие по своей сути его автобиографию. Труд этот был создан на закате жизни, он включает все важнейшие события жизни Г. Р. Державина, поэта и государственного деятеля. Рассказ ведется от третьего лица, что придает особую атмосферу повествованию, выстраивается своеобразный диалог между автором и героем, все это и является предметом исследования автора статьи.The focus of the author of the article “Notes” G. R. Derzhavin, representing in essence his autobiography. This work was created at the end of his life; it includes all the most important events in the life of G. R. Derzhavin, poet and statesman. The story is told in a third person, which gives a special atmosphere to the story, a certain dialogue emerges between the author and the hero, all this is the subject of the author's research
Gravastars in f(R, G) gravity
No full textThis paper is focused on the study of gravitational vacuum stars or, briefly, gravastars in f(R, G) gravity, where R and G stand for the Ricci scalar and Gauss–Bonnet invariant term, respectively. Due to the involvement of highly non-linear differential equations, solutions are found by using some appropriate numerical techniques. The main structure of gravastars has been discussed according to core, shell, and exterior regions for a well-known f(R, G) gravity cosmological model. Mass–radius evolution is described graphically for the considered gravastar, and it is shown that the mass is directly proportional to the radius.The presentation of the authors' names and (or) special characters in the title of the pdf file of the accepted manuscript may differ slightly from what is displayed on the item page. The information in the pdf file of the accepted manuscript reflects the original submission by the author
Introduction: Starring the Author
No full textLiterary celebrity is by now a familiar feat of contemporary literary culture, but it continues to raise complex questions about the history and development of fame, the interplay between the cultural marketplace and the official culture of critics and the canon, and the relation between authorial agency and public appropriation. This introduction addresses these questions by approaching literary celebrity as a merging of two discursive constructions: the celebrity-function and the author-function. By combining insights from celebrity studies, literary history and cultural memory studies, the introduction conceptualizes literary celebrity as a discursive construction with several variables, such as the author’s self-presentation, the circulation of his public identity, changing opinions on literature and writership, and the public afterlife of the author’s image
Spherically symmetric solution of f(R,G) gravity at low energy
No full textThe weak-field and slow-motion limit of f(R,G) gravity is developed up to (v/c)(4) order in a spherically symmetric background. Considering the Taylor expansion of a general function f around vanishing values of R and G, we present general vacuum solutions up to (v/c)(4) order for the gravitational field generated by a ball-like source. The spatial behaviors at (v/c)(2) order are the same for f(R,G) gravity and f(R) gravity, and their corresponding real valued static behaviors are presented and compared with the one in general relativity. The static Yukawa-like behavior is proved to be compatible with the previous result of the most general fourth-order theory. At (v/c)(4) order, the static corrections to the Yukawa-like behavior for f(R,G) gravity, f(R) gravity, and the Starobinsky gravity are presented and compared with the one in general relativity.National Natural Science Foundation of China [11120101004, 11475006]SCI(E)[email protected]; [email protected]
Real Estate Development: An overview
No full textGreen Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.Urban Development Managemen
ASO Author Reflections: Liver Failure Dominates the Risk of Failure to Rescue After Surgery for Perihilar Cholangiocarcinoma
No full text- …
