13 research outputs found
String Covering: A Survey
No full textThe study of strings is an important combinatorial field that precedes the
digital computer. Strings can be very long, trillions of letters, so it is
important to find compact representations. Here we first survey various forms
of one potential compaction methodology, the cover of a given string x,
initially proposed in a simple form in 1990, but increasingly of interest as
more sophisticated variants have been discovered. We then consider covering by
a seed; that is, a cover of a superstring of x. We conclude with many proposals
for research directions that could make significant contributions to string
processing in future
PATTERN MATCHING ON INDETERMINATE STRINGS WITH PREFIX ARRAYS
No full textUncertainty is prevalent in diverse datasets. This uncertainty is modelled by a string generalization termed as indeterminate string – a string containing one or more sub- sets of the alphabet as letters (known as indeterminate letters). In this thesis we revisit the pattern matching problem on indeterminate strings. We introduce innovative algorithms leveraging established techniques like KMP and BM, coupled with an exhaustive experimental evaluation focusing on both time complexity and runtime performance. Additionally, the thesis explores a novel encoding methodology for indeterminate strings, assessing its impact on runtime efficiency. Through rigorous analysis and experimentation, this study not only expands the theoretical framework of indeterminate pattern matching but also provides practical insights that will impact data processing in real-world applications.ThesisMaster of Science (MSc)In my thesis, I proposed novel algorithms for pattern matching on indeterminate strings — special strings that allow character uncertainties at specific positions. By addressing uncertainties in character positions, my work has implications in computa- tional biology, data mining, and various applications, with more precise and efficient pattern recognition in real-world scenarios
Algorithms to Compute K-Approximate Periodicities
No full textA cover of a string w is a string u such that each letter of w occurs in some occurrences
of u. In this thesis, we present the k-approximate maximal cover, where we allow for
at most k mismatches at each occurrence of u in w, u is not required to cover the
entire string and to compute the coverage we consider only the exact matches. Our
ultimate objective is to find an approximate cover that encompasses the maximum
number of exact positions covered while allowing for k mismatches. For this problem,
we present an efficient algorithm that executes in O(n2kLave)-time, where n is the
length of the given string and Lave is the average length of the longest common prefix
between every substring and the original string with up to k mismatches allowed.
To further broaden the scope of string analysis, we address two novel problems: the
k-frequency cover and the k-border. The k-frequency cover problem seeks to identify
the longest substring u of x, that has the maximum number of its k-approximate
occurrences over all the other substrings in x. We propose an algorithm with a
computational complexity of O(n2) to resolve this challenge efficiently. The longest
k-border problem focuses on determining the longest prefix of string x that matches
a suffix of x of the same length while allowing at most k mismatches. We propose an
O(n2)-time algorithm to compute the longest k-border of every substring of x.ThesisMaster of Science (MSc)Regularities in strings have been studied for many years and play a crucial role in
various fields, including biology, language theory, and compression theory. Periodicity
has been one of the major problems studied in the field of string algorithms spanning
several decades. Despite the advancements, accurately identifying various periodici-
ties and quasi-periodicities within a string presents a notable challenge, particularly
when the analysis must account for errors or inconsistencies. To address these com-
plexities the notion of k-approximate periodicities has been introduced. This concept
allows up to k mismatches between each occurrence of the periodicity in the original
string, providing a more flexible approach to understanding string regularities. In
this context, our work introduces innovative algorithms designed to efficiently com-
pute the k-approximate maximal cover, k-frequency cover and longest k-border under
the Hamming distance measure
A Generalization of Square-free Strings
No full textOur research is in the general area of String Algorithms and Combinatorics on Words. Specifically, we study a generalization of square-free strings, shuffle properties of strings, and formalizing the reasoning about finite strings.
The existence of infinitely long square-free strings (strings with no adjacent repeating word blocks) over a three (or more) letter finite set (referred to as Alphabet) is a well-established result. A natural generalization of this problem is that only subsets of the alphabet with predefined cardinality are available, while selecting symbols of the square-free string. This problem has been studied by several authors, and the lowest possible bound on the cardinality of the subset given is four. The problem remains open for subset size three and we investigate this question. We show that square-free strings exist in several specialized cases of the problem and propose approaches to solve the problem, ranging from patterns in strings to Proof Complexity. We also study the shuffle property (analogous to shuffling a deck of cards labeled with symbols) of strings, and explore the relationship between string shuffle and graphs, and show that large classes of graphs can be represented with special type of strings.
Finally, we propose a theory of strings, that formalizes the reasoning about finite strings. By engaging in this line of research, we hope to bring the richness of the advanced field of Proof Complexity to Stringology.ThesisDoctor of Philosophy (PhD
MAXIMAL COVER ALGORITHM IMPLEMENTATION
No full textThis thesis describes the development and application of the new software MAXCOVER that computes maximal covers and non-extendible repeats (a.k.a. “maximal repeats”).
A string is a finite array x[1..n] of elements chosen from a set of totally ordered symbols called an alphabet. A repeat is a substring that occurs at least twice in x. A repeat is left/right extendible if every occurrence is preceded/followed by the same symbol; otherwise, it is non-left/non-right extendible (NLE/NRE). A non-extendible (NE) repeat is both NLE and NRE. A repeat covers a position i if x[i] lies within the repeat. A maximal cover (a.k.a. “optimal cover”) is a repeat that covers the most positions in x.
For simplicity, we first describe a quadratic O(n2) implementation of MAXCOVER to compute all maximal covers of a given string based on the pseudocode given in [1]. Then, we consider the logarithmic O(n log n) pseudocode in [1], in which we identify several errors. We leave a complete correction and implementation for future work. Instead, we propose two improved quadratic algorithms that, shown through experiments, will execute in linear time for the average case.
We perform a benchmark evaluation of MAXCOVER’s performance and demonstrate its value to biologists in the protein context [2]. To do so, we develop an extension of MAXCOVER for the closely related task of computing NE repeats. Then, we compare MAXCOVER to the repeat-match feature of the well-known MUMmer software [3] (600+ citations). We determine that MAXCOVER is an order-of-magnitude faster than MUMmer with much lower space requirements. We also show that MAXCOVER produces a more compact, exact, and user-friendly output that specifies the repeats.
Availability: Open source code, binaries, and test data are available on Github at https://github.com/hollykoponen/MAXCOVER. Currently runs on Linux, untested on other OS.ThesisMaster of Science (MSc)This thesis deals with a simple yet essential data structure called a string, a sequence of symbols drawn from an alphabet. For example, a DNA sequence is a string comprised of four letters.
We describe a new software called MAXCOVER that identifies maximal covers of a given string x (a repeating substring that ‘covers’ the most positions in x). This software is based on the algorithms in [1]. We propose two new algorithms that perform faster in practice.
We also extended MAXCOVER for the closely related task of computing non-extendible repeats. We compare this extension to the well-known MUMmer software (600+ citations). We find that MAXCOVER is many times faster than MUMmer with much lower space requirements and produces a more compact, exact and user-friendly output
Practical KMP/BM Style Pattern-Matching on Indeterminate Strings
No full textIn this paper we describe two simple, fast, space-efficient algorithms for
finding all matches of an indeterminate pattern in an
indeterminate string , where both and are defined on a
"small" ordered alphabet say, . Both
algorithms depend on a preprocessing phase that replaces by an integer
alphabet of size which (reversibly, in time
linear in string length) maps both and into equivalent regular strings
and , respectively, on , whose maximum (indeterminate) letter
can be expressed in a 32-bit word (for , thus for DNA sequences,
an 8-bit representation suffices). We first describe an efficient version KMP
Indet of the venerable Knuth-Morris-Pratt algorithm to find all occurrences of
in (that is, of in ), but, whenever necessary, using the prefix
array, rather than the border array, to control shifts of the transformed
pattern along the transformed string . We go on to describe a similar
efficient version BM Indet of the Boyer- Moore algorithm that turns out to
execute significantly faster than KMP Indet over a wide range of test cases. A
noteworthy feature is that both algorithms require very little additional
space: words. We conjecture that a similar approach may yield
practical and efficient indeterminate equivalents to other well-known
pattern-matching algorithms, in particular the several variants of Boyer-Moore
V-Words, Lyndon Words and Galois Words
No full textWe say that a family of strings over forms a Unique Maximal Factorization Family (UMFF) if and only if every has a unique maximal factorization. Further, an UMFF is called a circ-UMFF whenever it contains exactly one rotation of every primitive string . -order is a non-lexicographical total ordering on strings that determines a circ-UMFF. In this paper we propose a generalization of circ-UMFF called the substring circ-UMFF and extend combinatorial research on -order by investigating connections to Lyndon words. Then we extend these concepts to any total order. Applications of this research arise in efficient text indexing, compression, and search problems.30 page
