In this work, we study periodicity in strings with wildcards. A string T with at most k wildcards is called strongly (p,k)-periodic if the wildcards in T can be replaced with alphabet symbols to obtain a string with period p, and weakly (p,k)-periodic if T[i] matches T[i+p] for all i. Intuitively, both generalize to (≤ g, k)-periodicity, which is the property of being (p,k)-periodic for some p ∈ [1..g]. An ε-tester for a property 𝒫 is an algorithm that distinguishes between strings that satisfy 𝒫 and strings where one needs to change at least an ε-fraction of the symbols to obtain a string that satisfies 𝒫. We study one-sided error testers, where strings satisfying 𝒫 must always be accepted, while strings that are ε-far must be rejected with probability at least 2/3. The complexity of a tester is the worst-case number of symbols of an input of length n it must read to make the decision. We design the following testers for p,g ≤ n/2: 1) An ε-tester for strong (p,k)-periodicity with complexity Õ_ε(1) . 2) An ε-tester for strong (≤ g,k)-periodicity with complexity Õ_ε(√g). 3) An ε-tester for weak (p,k)-periodicity with complexity Õ_ε(min(k, n /(k+p))). 4) An ε-tester for weak (≤ g,k)-periodicity with complexity Õ_ε(min(k+ √{gk}, n/√k)). Additionally, we show a lower bound on the complexity of ε-testers for weak (≤ g,k)-periodicity, implying that our tester for weak (≤ g,k)-periodicity is optimal up to a multiplicative (ε^{-1} ln(gk))^O(1) factor for a wide range of g and k. Finally, our tester for strong (≤ g,k)-periodicity generalizes the one of [Lachish and Newman; Algorithmica 2011] for strings without wildcards, matching (up to polylogarithmic factors) the unconditional lower bound of ̃Ω(√g) in said work for constant ε.

MOTIVATION: Combinatorial pooling schemes have enabled the measurement of thousands of experiments in a small number of reactions. This efficiency is achieved by distributing the items to be measured across multiple reaction units called pools. However, current methods for the design of pooling schemes do not adequately address the need for balanced item distribution across pools, a property particularly important for biological applications. RESULTS: Here, we introduce balanced constant-weight Gray codes for detecting consecutive positives (DCP-CWGCs) for the efficient construction of combinatorial pooling schemes. Balanced DCP-CWGCs ensure uniform item distribution across pools, allow for the identification of consecutive positive items such as overlapping biological sequences, and enable error detection by ensuring a constant number of tests on each item and pair of consecutive items. For the efficient construction of balanced DCP-CWGCs, we have released an open-source python package codePUB, with implementations of the two core algorithms: a branch-and-bound algorithm (BBA) and a recursive combination with BBA (rcBBA). Simulations using codePUB show that our algorithms can construct long, balanced DCP-CWGCs that allow for error detection in tractable runtime. AVAILABILITY AND IMPLEMENTATION: The source code of codePUB is available at https://github.com/meyer-lab-cshl/codepub, with detailed documentation at https://codepub.readthedocs.io/.

Pattern matching with wildcards is a string matching problem with the goal of finding all factors of a text t of length n that match a pattern x of length m, where wildcards (characters that match everything) may be present. In this paper we present a number of complexity results and fast average-case algorithms for pattern matching where wildcards are allowed in the pattern, however, the results are easily adapted to the case where wildcards are allowed in the text as well. We analyse the average-case complexity of these algorithms and derive non-trivial time bounds. These are the first results on the average-case complexity of pattern matching with wildcards which provide a provable separation in time complexity between exact pattern matching and pattern matching with wildcards. We introduce the wc-period of a string which is the period of the binary mask xb where xb[i]=a iff x[i]≠ϕ and b otherwise. We denote the length of the wc-period of a string x by . We show the following results for constant 0<ϵ<1 and a pattern x of length m and g wildcards with the prefix of length p contains gp wildcards: If limm→∞⁡gpp=0 there is an optimal algorithm running in O(nlogσ⁡mm)-time on average. If limm→∞⁡gpp=1−ϵ there is an algorithm running in O(nlogσ⁡mlog2⁡pm)-time on average. If limm→∞⁡gm=limm→∞⁡1−f(m)=1 any algorithm takes at least Ω(nlogσ⁡mf(m))-time on average.

The 3D structure of chromatin plays a key role in genome function, including gene expression, DNA replication, chromosome segregation, and DNA repair. Furthermore the location of genomic loci within the nucleus, especially relative to each other and nuclear structures such as the nuclear envelope and nuclear bodies strongly correlates with aspects of function such as gene expression. Therefore, determining the 3D position of the 6 billion DNA base pairs in each of the 23 chromosomes inside the nucleus of a human cell is a central challenge of biology. Recent advances of super-resolution microscopy in principle enable the mapping of specific molecular features with nanometer precision inside cells. Combined with highly specific, sensitive and multiplexed fluorescence labeling of DNA sequences this opens up the possibility of mapping the 3D path of the genome sequence in situ. Here we develop computational methodologies to reconstruct the sequence configuration of all human chromosomes in the nucleus from a super-resolution image of a set of fluorescent in situ probes hybridized to the genome in a cell. To test our approach, we develop a method for the simulation of DNA in an idealized human nucleus. Our reconstruction method, ChromoTrace, uses suffix trees to assign a known linear ordering of in situ probes on the genome to an unknown set of 3D in-situ probe positions in the nucleus from super-resolved images using the known genomic probe spacing as a set of physical distance constraints between probes. We find that ChromoTrace can assign the 3D positions of the majority of loci with high accuracy and reasonable sensitivity to specific genome sequences. By simulating appropriate spatial resolution, label multiplexing and noise scenarios we assess our algorithms performance. Our study shows that it is feasible to achieve genome-wide reconstruction of the 3D DNA path based on super-resolution microscopy images.

Circular string matching is a problem which naturally arises in many contexts. It consists in finding all occurrences of the rotations of a pattern of lengthmin a text of lengthn. There exist optimal worst- and average-case algorithms for circular string matching. Here, we present a suboptimal average-case algorithm for circular string matching requiring time $\mathcal{O}$ (n) and space $\mathcal{O}$ (m). The importance of our contribution is underlined by the fact that the proposed algorithm can be easily adapted to deal with circular dictionary matching. In particular, we show how the circular dictionary-matching problem can be solved in average-case time $\mathcal{O}$ (n+M) and space $\mathcal{O}$ (M), whereMis the total length of the dictionary patterns, assuming that the shortest pattern is sufficiently long. Moreover, the presented average-case algorithms and other worst-case approaches were also implemented. Experimental results, using real and synthetic data, demonstrate that the implementation of the presented algorithms can accelerate the computations by more than a factor of two compared to the corresponding implementation of other approaches.

Sequence comparison is the core computation of many applications involving textual representations of data. Edit distance is the most widely used measure to quantify the similarity of two sequences. Edit distance can be defined as the minimal total cost of a sequence of edit operations to transform one sequence into the other; for a sequence x of length m and a sequence y of length n, it can be computed in time O(mn). In many applications, it is common to consider sequences with circular structure: for instance, the orientation of two images or the leftmost position of two linearised circular DNA sequences may be irrelevant. To this end, an algorithm to compute the cyclic edit distance in time O(mnlogm) was proposed (Maes, 2003 [18]) and several heuristics have been proposed to speed up this computation. Recently, a new algorithm based on q-grams was proposed for circular sequence comparison (Grossi et al., 2016 [13]). We extend this algorithm for cyclic edit distance computation and show that this new heuristic is faster and more accurate than the state of the art. The aim of this letter is to give visibility to this idea in the pattern recognition community.

The problem of finding factors of a text string which are identical or similar to a given pattern string is a central problem in computer science. A generalised version of this problem consists in implementing an index over the text to support efficient on-line pattern queries. We study this problem in the case where the text is weighted: for every position of the text and every letter of the alphabet a probability of occurrence of this letter at this position is given. Sequences of this type, also called position weight matrices, are commonly used to represent imprecise or uncertain data. A weighted sequence may represent many different strings, each with probability of occurrence equal to the product of probabilities of its letters at subsequent positions. Given a probability threshold $1/z$, we say that a pattern string $P$ matches a weighted text at position $i$ if the product of probabilities of the letters of $P$ at positions $i,\ldots,i+|P|-1$ in the text is at least $1/z$. In this article, we present an $O(nz)$-time construction of an $O(nz)$-sized index that can answer pattern matching queries in a weighted text in optimal time improving upon the state of the art by a factor of $z \log z$. Other applications of this data structure include an $O(nz)$-time construction of the weighted prefix table and an $O(nz)$-time computation of all covers of a weighted sequence, which improve upon the state of the art by the same factor.

BACKGROUND: An absent word of a word y of length n is a word that does not occur in y. It is a minimal absent word if all its proper factors occur in y. Minimal absent words have been computed in genomes of organisms from all domains of life; their computation also provides a fast alternative for measuring approximation in sequence comparison. There exists an [Formula: see text]-time and [Formula: see text]-space algorithm for computing all minimal absent words on a fixed-sized alphabet based on the construction of suffix automata (Crochemore et al., 1998). No implementation of this algorithm is publicly available. There also exists an [Formula: see text]-time and [Formula: see text]-space algorithm for the same problem based on the construction of suffix arrays (Pinho et al., 2009). An implementation of this algorithm was also provided by the authors and is currently the fastest available. RESULTS: Our contribution in this article is twofold: first, we bridge this unpleasant gap by presenting an [Formula: see text]-time and [Formula: see text]-space algorithm for computing all minimal absent words based on the construction of suffix arrays; and second, we provide the respective implementation of this algorithm. Experimental results, using real and synthetic data, show that this implementation outperforms the one by Pinho et al. The open-source code of our implementation is freely available at http://github.com/solonas13/maw . CONCLUSIONS: Classical notions for sequence comparison are increasingly being replaced by other similarity measures that refer to the composition of sequences in terms of their constituent patterns. One such measure is the minimal absent words. In this article, we present a new linear-time and linear-space algorithm for the computation of minimal absent words based on the suffix array.