1,720,977 research outputs found
Faster Approximate Elastic-Degenerate String Matching - Part A
Full text linkAn elastic-degenerate (ED) string is a sequence = [1] ⋯ [n] of n finite sets of strings. The cardinality m of is the total number of strings in [i], for all i ∈ [1..n]. The size N of is the total length of all m strings of . ED strings have been introduced to represent a set of closely-related DNA sequences. Let P = P[1..p] be a pattern of length p and k > 0 be an integer. We consider the problem of k-Approximate ED String Matching (EDSM): searching k-approximate occurrences of P in the language of . We call k-Approximate EDSM under the Hamming distance, k-Mismatch EDSM; and we call k-Approximate EDSM under edit distance, k-Edit EDSM.
Bernardini et al. (Theoretical Computer Science, 2020) showed a simple (k m p + kN)-time algorithm for k-Mismatch EDSM and an (k² m p + kN)-time algorithm for k-Edit EDSM. We improve the dependency on k in both results, obtaining an Õ(k^{2/3}mp+√kN)-time algorithm for k-Mismatch EDSM and an Õ(kmp+ kN)-time algorithm for k-Edit EDSM.
Bernardini et al. (Theory of Computing Systems, 2024) presented several algorithms for 1-Approximate EDSM working in Õ(np²+N) time. They have also left the possibility to generalize these solutions for k > 1 as an open problem. We improve the runtime of their solution for 1-Mismatch and 1-Edit EDSM from Õ(np²+N) to (np²+N). We further show algorithms for k-Approximate EDSM for the Hamming and edit distances working in Õ(np² + N) time, for any constant k > 0.
Finally, we show how our techniques can be applied to improve upon the complexity of the k-Approximate ED String Intersection and k-Approximate Doubly EDSM problems that were introduced very recently by Gabory et al. (Information and Computation, 2025)
Shortest Undirected Paths in de Bruijn Graphs
Full text linkComputing shortest directed paths in de Bruijn graphs is well studied and well understood. This is not the case for computing undirected paths, which is much more challenging algorithmically. In this paper, we present a general framework for computing shortest undirected paths in arbitrary de Bruijn graphs, that is, arbitrary subgraphs of the complete de Bruijn graph. We then present an application of our techniques for making any arbitrary order-k de Bruijn graph G(V,E) weakly connected by adding a set of edges of minimum total cost. This improves the running time of the recent (2-2/d)-approximation algorithm by Bernardini et al. [CPM 2024] from (k|V|²) to (k|V|log d) time, where d is the number of weakly connected components of graph G
Pangenome comparison via ED strings
Full text linkIntroduction: An elastic-degenerate (ED) string is a sequence of sets of strings. It can also be seen as a directed acyclic graph whose edges are labeled by strings. The notion of ED strings was introduced as a simple alternative to variation and sequence graphs for representing a pangenome, that is, a collection of genomic sequences to be analyzed jointly or to be used as a reference. Methods: In this study, we define notions of matching statistics of two ED strings as similarity measures between pangenomes and, consequently infer a corresponding distance measure. We then show that both measures can be computed efficiently, in both theory and practice, by employing the intersection graph of two ED strings. Results: We also implemented our methods as a software tool for pangenome comparison and evaluated their efficiency and effectiveness using both synthetic and real datasets. Discussion: As for efficiency, we compare the runtime of the intersection graph method against the classic product automaton construction showing that the intersection graph is faster by up to one order of magnitude. For showing effectiveness, we used real SARS-CoV-2 datasets and our matching statistics similarity measure to reproduce a well-established clade classification of SARS-CoV-2, thus demonstrating that the classification obtained by our method is in accordance with the existing one.</p
Linear-Time Computation of Shortest Covers of All Rotations of a String
Full text linkWe show that lengths of shortest covers of all rotations of a length-n string over an integer alphabet can be computed in (n) time in the word-RAM model, thus improving an (n log n)-time algorithm from Crochemore et al. (Theor. Comput. Sci., 2021). Similarly as Crochemore et al., we use a relation of covers of rotations of a string S to seeds and squares in S³. The crucial parameter of a string S is the number ξ(S) of primitive covers of all rotations of S. We show first that the time complexity of the algorithm from Crochemore et al. can be slightly improved which results in time complexity Θ(ξ(S)). However, we also show that in the worst case ξ(S) is Ω(|S|log |S|). This is the main difficulty in obtaining a linear time algorithm. We overcome it and obtain yet another application of runs in strings
Computing string covers in sublinear time
Full text linkIn the word RAM model, a string T of length n over an integer alphabet of size σ can be represented in O(n/logσn) space. We show that a representation of all covers of T can be computed in the optimal O(n/logσn) time; in particular, the shortest cover can be computed within this time. We also design an O(n(logσ+loglogn)/logn)-sized data structure that computes in O(1) time any element of the so-called (shortest) cover array of T, that is, the length of the shortest cover of any given prefix of T. As a by-product, we describe the structure of the cover array of Fibonacci strings. On the negative side, we show that the shortest cover of a length-n string cannot be computed using o(n/logn) operations in the PILLAR model of Charalampopoulos, Kociumaka, and Wellnitz (FOCS 2020)
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Full text link“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Full text linkWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
Minimizers in semi-dynamic strings
Full text linkMinimizers sampling is one of the most widely-used mechanisms for sampling strings. Let be a string over an alphabet . In addition, let and be two integers and be a total order on . The minimizer of window is the smallest position in where the smallest length- substring of based on starts. The set of minimizers for all is the set of the minimizers of . The set can be computed in time. The folklore algorithm for this computation computes the minimizer of every window in amortized time using working space. It is thus natural to pose the following two questions:
Question 1: Can we efficiently support other dynamic updates on the window?
Question 2: Can we improve on the working space?
We answer both questions in the affirmative:
1. We term a string semi-dynamic when one is allowed to insert or delete a letter at any of its ends. We show a data structure that maintains a semi-dynamic string and supports minimizer queries in in time with amortized time per update operation.
2. We show that this data structure can be modified to occupy strongly sublinear space without increasing the asymptotic complexity of its operations. To the best of our knowledge, this yields the first algorithm for computing in time using working space.
We complement our theoretical results with a concrete application and an experimental evaluation
- …
