Search

Suppose an oracle knows a string $S$ that is unknown to us and that we want to determine. The oracle can answer queries of the form "Is $s$ a substring of $S$?". In 1995, Skiena and Sundaram showed that, in the worst case, any algorithm needs to ask the oracle $\sigma n/4 -O(n)$ queries in order to be able to reconstruct the hidden string, where $\sigma$ is the size of the alphabet of $S$ and $n$ its length, and gave an algorithm that spends $(\sigma-1)n+O(\sigma \sqrt{n})$ queries to reconstruct $S$. The main contribution of our paper is to improve the above upper-bound in the context where the string is compressible. We first present a universal algorithm that, given a (computable) compressor that compresses the string to $\tau$ bits, performs $q=O(\tau)$ substring queries; this algorithm, however, runs in exponential time. For this reason, the second part of the paper focuses on more time-efficient algorithms whose number of queries is bounded by specific compressibility measures. We first show that any string of length $n$ over an integer alphabet of size $\sigma$ with $rle$ runs can be reconstructed with $q=O(rle (\sigma + \log \frac{n}{rle}))$ substring queries in linear time and space. We then present an algorithm that spends $q \in O(\sigma g\log n)$ substring queries and runs in $O(n(\log n + \log \sigma)+ q)$ time using linear space, where $g$ is the size of a smallest straight-line program generating the string., Comment: Accepted for publication in Theoretical Computer Science

Modelling of chromosomes with permutations has triggered the research of sorting permutations using global rearrangement operations in computational molecular biology. One such rearrangement is transposition which swaps two adjacent substrings. If one of the substrings is restricted to be the prefix of the permutation then that operation is called a prefix transposition. The symmetric prefix transposition distance between two permutations is defined to be the minimum number of prefix transpositions required to transform one into another. Group theory dictates that an upper bound for prefix transposition distance between any pair of permutations in the symmetric group S n is equivalent to the upper bound for sorting any permutation with prefix transpositions. In this paper, we improve the upper bound for sorting permutations with prefix transpositions to n − log 2 ⁡ n .

Sorting permutations with various operations has applications in macro rearrangement of genes in a genome and the design of computer interconnection networks. Block-interchange is a powerful operation that swaps two substrings that are called as blocks in literature, in a given permutation. When the blocks are restricted to be adjacent then one obtains a well studied operation: transposition. We call either a prefix or a suffix as an extreme. Restricting one of the swapped blocks to be an extreme in block-interchange operation yields a prefix or a suffix block-interchange respectively, the two types of extreme block-interchanges. For prefix block-interchange operation over permutations we design: (i) an optimum algorithm to sort reverse permutation, R n , in n/2 moves, (ii) a simple 2-approximation algorithm, and (iii) for permutations with O ( 1 ) cycles, a 4/3 approximation algorithm. Due to symmetry, these results apply to suffix block-interchange operation also.

A substring u of a string T is called a minimal unique substring (MUS) of T if u occurs exactly once in T and any proper substring of u occurs at least twice in T. In this paper, we study the problem of computing MUSs for a sliding window over a given string T. We first show how the set of MUSs can change when the window slides over T. We then present an $$O(n\log \sigma ')$$ O ( n log σ ′ ) -time and O(d)-space algorithm to compute MUSs for a sliding window of size d over the input string T of length n, where $$\sigma '\le d$$ σ ′ ≤ d is the maximum number of distinct characters in every window.

Given a text T and a set of r patterns P 1 , P 2 , … , P r , the exact multiple pattern matching problem reports the ending positions of all occurrences of P i in T for 1 ≤ i ≤ r . By transforming all substrings with a fixed length of T into a reference tree such that each internal node stores a reference string, the exact multiple pattern matching problem can be efficiently solved by searching patterns in the tree via the guidance of the reference strings. We design elegant algorithms to construct the reference tree (the preprocessing phase) and to search patterns in the tree (the searching phase) using bitwise operations. The experiments involving problem instances from the DNA sequence and the English language are conducted to compare the performance of our approach against those of the suffix tree and suffix array algorithms. The computational results demonstrate the advantage of our approach over these algorithms. In spite of the simplicity, our approach is quite efficient, flexible and robust.

V-order is a total order on strings that determines an instance of Unique Maximal Factorization Families (UMFFs), a generalization of Lyndon words. The fundamental V-comparison of strings can be done in linear time and constant space. V-order has been proposed as an alternative to lexicographic order (lexorder) in the computation of suffix arrays and in the suffix-sorting induced by the Burrows-Wheeler transform (BWT). In line with the recent interest in the connection between suffix arrays and Lyndon factorization, in this paper we obtain similar results for the V-order factorization. Indeed, we show that the results describing the connection between suffix arrays and Lyndon factorization are matched by analogous V-order processing. We also describe a methodology for efficiently computing the FM-Index in V-order, as well as V-order substring pattern matching using backward search.

This work aims to evaluate and propose matheuristics for the Distinguishing String Selection Problem (DSSP) and the Distinguishing Substring Selection Problems (DSSSP). Heuristics based on mathematical programming have already been proposed for String Selection problems in the literature and we are interested in adopting and testing different approaches for those problems. We proposed two matheuristics for both the DSSP and DSSSP by combining the Variable Neighbourhood Search (VNS) metaheuristic and mathematical programming. We compare the linear relaxation, lower bounds found through the branch-and-bound technique, and the matheuristics in three different groups of instances. Computational experiments show that the Basic Core Problem Algorithm (BCPA) finds overall better results for the DSSP. However, it was unable to provide any solutions for some hard DSSSP instances in a reasonable time limit. The two matheuristics based on the VNS have their own niche related to the different groups of instances. They found good solutions for the DSSSP while the BCPA failed. All the obtained data are available in our repository.

We introduce the concept of a prime band in a string algebra $\Lambda$ and use it to associate to $\Lambda$ its finite bridge quiver. Then we introduce a new technique of `recursive systems' for showing that a graph map between finite dimensional string modules lies in its stable radical. Further we study two classes of non-domestic string algebras in terms of some connectedness properties of its bridge quiver. `Meta-$\bigcup$-cyclic' string algebras constitute the first class that is essentially characterized by the statement that each finite string is a substring of a band. Extending this class we have `meta-torsion-free' string algebras that are characterized by a dichotomy statement for ranks of graph maps between string modules--such maps either have finite rank or are in the stable radical. Their stable ranks can only take values from $\{\omega,\omega+1,\omega+2\}$., Comment: 23 pages, minor changes in Corollary 4.3.3, added funding details for one author

This article investigates the lossless event compression problem of discrete event systems which is, given a discrete event system and a source string generated by it, to find a minimal recoverable compressed string by removing as many events as possible. In order for the problem to be well post, two compression protocols are introduced. One requires that the last event is always kept. The other requires that, for any loop substring, at least one event is kept. We say a compressed string is recoverable if we can uniquely determine the source string based on the knowledge of the given discrete event system. We first construct an automaton to present all the possible source strings for a given compressed string. Based on the automaton, an algorithm is proposed to check whether the given compressed string is recoverable or not. We then propose an algorithm to calculate a minimal recoverable compressed string for a source string. The compressed string satisfies monotonicity which can significantly reduce the computational complexity of the algorithm. Finally, we use a practical example to illustrate these results.

Effective biomarkers aid in the early diagnosis and monitoring of breast cancer and thus play an important role in the treatment of patients suffering from the disease. Growing evidence indicates that alteration of expression levels of miRNA is one of the principal causes of cancer. We analyze breast cancer miRNA data to discover a list of biclusters as well as breast cancer miRNA biomarkers which can help to understand better this critical disease and take important clinical decisions for treatment and diagnosis. In this paper, we propose a pattern-based parallel biclustering algorithm termed Rank-Preserving Biclustering (RPBic). The key strategy is to identify rank-preserved rows under a subset of columns based on a modified version of all substrings common subsequence (ALCS) framework. To illustrate the effectiveness of the RPBic algorithm, we consider synthetic datasets and show that RPBic outperforms relevant biclustering algorithms in terms of relevance and recovery. For breast cancer data, we identify 68 biclusters and establish that they have strong clinical characteristics among the samples. The differentially co-expressed miRNAs are found to be involved in KEGG cancer related pathways. Moreover, we identify frequency-based biomarkers (hsa-miR-410, hsa-miR-483-5p) and network-based biomarkers (hsa-miR-454, hsa-miR-137) which we validate to have strong connectivity with breast cancer. The source code and the datasets used can be found at http://agnigarh.tezu.ernet.in/~rosy8/Bioinformatics_RPBic_Data.rar . Graphical Abstract.

Palindromes are important objects in strings which have been extensively studied from combinatorial, algorithmic, and bioinformatics points of views. It is known that the length of the longest palindromic substrings (LPSs) of a given string T of length n can be computed in O ( n ) time by Manacher's algorithm [12] . In this paper, we consider the problem of finding the LPS after the string is edited. We present an algorithm that uses O ( n ) time and space for preprocessing, and answers the length of the LPSs in O ( log ⁡ ( min ⁡ { σ , log ⁡ n } ) ) time after a single character substitution, insertion, or deletion, where σ denotes the number of distinct characters appearing in T. We also propose an algorithm that uses O ( n ) time and space for preprocessing, and answers the length of the LPSs in O ( l + log ⁡ log ⁡ n ) time, after an existing substring in T is replaced by a string of arbitrary length l.

The Closest Substring problem asks whether there exists a consensus string w of given length l such that each string in a set of strings L has a substring whose edit distance is at most r (called the radius) from w. The Closest Substring problem has been studied for finite sets of strings and is known to be NP -hard. We show that the Closest Substring problem for regular languages represented by nondeterministic finite automata (NFA) is PSPACE -complete. The problem remains PSPACE -hard even when the input is a deterministic finite automaton and the length l and radius r are given in unary. Also we show that the Closest Substring problem for acyclic NFAs lies in the second level of the polynomial-time hierarchy and is both NP -hard and coNP -hard.

In this paper, we discuss an efficient and effective index mechanism for the string matching with k differences, by which we will find all the substrings of a target string y of length n that align with a pattern string x of length m with not more than k insertions, deletions, and mismatches. A typical application is the searching of a DNA database, where the size of a genome sequence in the database is much larger than that of a pattern. For example, n is often on the order of millions or billions while m is just a hundred or a thousand. The main idea of our method is to transform y to a BWT-array as an index, denoted as BWT ( y ), and search x against it. The time complexity of our method is bounded by O( k · | T |), where T is a tree structure dynamically generated during a search of BWT ( y ). The average value of | T | is bounded by O(|Σ| 2 k ), where Σ is an alphabet from which we take symbols to make up target and pattern strings. This time complexity is better than previous strategies when k ≤ O(log |Σ| n ). The general working process consists of two steps. In the first step, x is decomposed into a series of l small subpatterns, and BWT ( y ) is utilized to speedup the process to figure out all the occurrences of such subpatterns with ⌊ k/l ⌋ differences. In the second step, all the found occurrences in the first step will be rechecked to see whether they really match x , but with k differences. Extensive experiments have been conducted, which show that our method for this problem is promising.

Let P be a collection of d patterns { P 1 , P 2 , … , P d } of total length n characters, which are chosen from an alphabet Σ of size σ. Given a text T (over Σ), the dictionary indexing problem is to create a data structure using which we can report all positions j (called occurrences) where at least one of the patterns P i ∈ P is a match with the same-length substring of T that starts at j. We consider this problem under the following definitions of matching. • Parameterized Matching: The characters of Σ are partitioned into static characters and parameterized characters. Two equal length strings S and S ′ are a parameterized match iff the static characters match exactly, and there exists a one-to-one function which renames the parameterized characters in S to those in S ′ . • Order-Preserving Matching: The alphabet Σ is ordered. Two equal length strings S and S ′ are an order-preserving match iff for any two integers i , j ∈ [ 1 , | S | ] , S [ i ] ≺ S [ j ] ⇔ S ′ [ i ] ≺ S ′ [ j ] , where ≺ denotes the precedence order in Σ. Let e > 0 be an arbitrarily small constant. For parameterized matching, we first present a compact O ( n log ⁡ σ + d log ⁡ n ) -bit index that reports all occ occurrences in O ( | T | ( log ⁡ σ + log σ ⁡ n ) + o c c ) time, and then a succinct n log ⁡ σ + o ( n log ⁡ σ ) + O ( d log ⁡ n ) -bit index that reports all occ occurrences in O ( | T | ( log ⁡ σ + log e ⁡ n log σ ⁡ n ) + o c c ) time. For order-preserving matching, we present indexes of the same sizes, but with slightly increased query time.

Given a string T of length n, a substring u = T [ i . . j ] of T is called a shortest unique substring (SUS) for an interval [ s , t ] if (a) u occurs exactly once in T, (b) u contains the interval [ s , t ] (i.e. i ≤ s ≤ t ≤ j ), and (c) every substring v of T with | v | | u | containing [ s , t ] occurs at least twice in T. Given a query interval [ s , t ] ⊂ [ 1 , n ] , the interval SUS problem is to output all the SUSs for the interval [ s , t ] . In this article, we propose a 4 n + o ( n ) bits data structure answering an interval SUS query in output-sensitive O ( o c c ) time, where occ is the number of returned SUSs. Additionally, we focus on the point SUS problem, which is the interval SUS problem for s = t . Here, we propose a ⌈ ( log 2 ⁡ 3 + 1 ) n ⌉ + o ( n ) bits data structure answering a point SUS query in the same output-sensitive time. We also propose space-efficient algorithms for computing the minimal unique substrings of T.

Background Insects play a central role in the functioning of terrestrial and freshwater ecosystems and contribute to a multitude of ecosystem services in managed and unmanaged systems Even local declines of insect abundance and richness can have enormous ecological and economic consequences. Evidence-informed conservation actions are essential to prevent potential cascading consequences of insect declines, and to help declining populations recover. Policy-makers rely on syntheses of primary research, such as reviews and meta-analyses, when making decisions about which conservation actions to implement. These evidence reviews vary in their quality, and do not necessarily synthesise the full range of scientific evidence found in the primary literature, which hampers decision-making. This evidence review map will identify, catalogue, and describe evidence reviews that investigate actions and policies to conserve insect biodiversity. This will help policy makers identify relevant reviews and researchers to identify synthesis gaps. It will also generate a list of conservation actions which can feed into future synthesis projects. We will produce an interactive database of evidence reviews, acting as a bibliography for policy-makers, curate a list of insect conservation actions that have been reviewed, and identify synthesis gaps for conservation actions that have not been reviewed. Methods We will search for evidence reviews across seven large, generic bibliographic databases, a database of environmental reviews, and five grey literature resources using a search string consisting of an insect substring, a biodiversity or population response substring, an evidence synthesis substring, and a conservation substring. The results will be deduplicated and then screened at title and abstract (concurrently) and full text levels against predefined inclusion criteria. We will initially perform consistency checking on a subset of records at each level to ensure the inclusion criteria are sufficiently clear and understood by multiple reviewers. We will extract a suite of descriptive meta-data from relevant reviews, including a description of the action and information on each review’s focal taxa, biomes, and locations. If resources allow, we will apply the CEESAT critical appraisal tool for evidence reviews to assess validity of individual records and the evidence base as a whole. We will summarise our findings in an interactive database of reviews and other visualisations, including evidence atlases and heat maps (cross tabulations of the volume of evidence across two categorical variables). The findings of the evidence review map will support the identification of synthesis gaps and clusters that may warrant further attention through secondary research.

Detecting and fending off attacks on computer systems is an enduring problem in computer security. In light of a plethora of different threats and the growing automation used by attackers, we are in urgent need of more advanced methods for attack detection. In this thesis, we address the necessity of advanced attack detection and develop methods to detect attacks using machine learning to establish a higher degree of automation for reactive security. Machine learning is data-driven and not void of bias. For the effective application of machine learning for attack detection, thus, a periodic retraining over time is crucial. However, the training complexity of many learning-based approaches is substantial. We show that with the right data representation, efficient algorithms for mining substring statistics, and implementations based on probabilistic data structures, training the underlying model can be achieved in linear time. In two different scenarios, we demonstrate the effectiveness of so-called language models that allow to generically portray the content and structure of attacks: On the one hand, we are learning malicious behavior of Flash-based malware using classification, and on the other hand, we detect intrusions by learning normality in industrial control networks using anomaly detection. With a data throughput of up to 580 Mbit/s during training, we do not only meet our expectations with respect to runtime but also outperform related approaches by up to an order of magnitude in detection performance. The same techniques that facilitate learning in the previous scenarios can also be used for revealing malicious content, embedded in passive file formats, such as Microsoft Office documents. As a further showcase, we additionally develop a method based on the efficient mining of substring statistics that is able to break obfuscations irrespective of the used key length, with up to 25 Mbit/s and thus, succeeds where related approaches fail. These methods significantly improve detection performance and enable operation in linear time. In doing so, we counteract the trend of compensating increasing runtime requirements with resources. While the results are promising and the approaches provide urgently needed automation, they cannot and are not intended to replace human experts or traditional approaches, but are designed to assist and complement them.

A prefix normal word is a binary word with the property that no substring has more $1$s than the prefix of the same length. By proving that the set of prefix normal words is a bubble language, we can exhaustively list all prefix normal words of length $n$ as a combinatorial Gray code, where successive strings differ by at most two swaps or bit flips. This Gray code can be generated in $\Oh(\log^2 n)$ amortized time per word, while the best generation algorithm hitherto has $\Oh(n)$ running time per word. We also present a membership tester for prefix normal words, as well as a novel characterization of bubble languages., To appear in Theoretical Computer Science. arXiv admin note: text overlap with arXiv:1401.6346

Background Alignment-free methods for sequence comparisons have become popular in many bioinformatics applications, specifically in the estimation of sequence similarity measures to construct phylogenetic trees. Recently, the average common substring measure, ACS, and its k-mismatch counterpart, ACSk, have been shown to produce results as effective as multiple-sequence alignment based methods for reconstruction of phylogeny trees. Since computing ACSk takes O(n logkn) time and hence impractical for large datasets, multiple heuristics that can approximate ACSk have been introduced. Results In this paper, we present a novel linear-time heuristic to approximate ACSk, which is faster than computing the exact ACSk while being closer to the exact ACSk values compared to previously published linear-time greedy heuristics. Using four real datasets, containing both DNA and protein sequences, we evaluate our algorithm in terms of accuracy, runtime and demonstrate its applicability for phylogeny reconstruction. Our algorithm provides better accuracy than previously published heuristic methods, while being comparable in its applications to phylogeny reconstruction. Conclusions Our method produces a better approximation for ACSk and is applicable for the alignment-free comparison of biological sequences at highly competitive speed. The algorithm is implemented in Rust programming language and the source code is available at https://github.com/srirampc/adyar-rs.

Identifying long pairwise maximal common substrings among a large set of sequences is a frequently used construct in computational biology, with applications in DNA sequence clustering and assembly. Due to errors made by sequencers, algorithms that can accommodate a small number of differences are of particular interest. Formally, let D be a collection of n sequences of total length N , ϕ be a length threshold, and k be a mismatch threshold. The goal is to identify and report all k -mismatch maximal common substrings of length at least ϕ over all pairs of strings in D . Heuristics based on seed-and-extend style filtering techniques are often employed in such applications. However, such methods cannot provide any provably efficient run time guarantees. To this end, we present a sequential algorithm with an expected run time of O ( N log k N + occ ) , where occ is the output size. We then present a distributed memory parallel algorithm with an expected run time of O N p log N + occ log k N using O log k + 1 N expected rounds of global communications, under some realistic assumptions, where p is the number of processors. Finally, we demonstrate the performance and scalability of our algorithms using experiments on large high throughput sequencing data.

Models of sequence evolution typically assume that all sequences are possible. However, restriction enzymes that cut DNA at specific recognition sites provide an example where carrying a recognition site can be lethal. Motivated by this observation, we studied the set of strings over a finite alphabet with taboos, that is, with prohibited substrings. The taboo-set is referred to as $$\mathbb {T}$$ T and any allowed string as a taboo-free string. We consider the so-called Hamming graph $$\varGamma _n(\mathbb {T})$$ Γ n ( T ) , whose vertices are taboo-free strings of length n and whose edges connect two taboo-free strings if their Hamming distance equals one. Any (random) walk on this graph describes the evolution of a DNA sequence that avoids taboos. We describe the construction of the vertex set of $$\varGamma _n(\mathbb {T})$$ Γ n ( T ) . Then we state conditions under which $$\varGamma _n(\mathbb {T})$$ Γ n ( T ) and its suffix subgraphs are connected. Moreover, we provide an algorithm that determines if all these graphs are connected for an arbitrary $$\mathbb {T}$$ T . As an application of the algorithm, we show that about $$87\%$$ 87 % of bacteria listed in REBASE have a taboo-set that induces connected taboo-free Hamming graphs, because they have less than four type II restriction enzymes. On the other hand, four properly chosen taboos are enough to disconnect one suffix subgraph, and consequently connectivity of taboo-free Hamming graphs could change depending on the composition of restriction sites.

Secure two-party pattern matching involves two parties, where a server owns the long text and a client has the pattern. The goal is for the client to learn the positions in which his pattern appears in the text, while leaking nothing to the server. In secure wildcard pattern matching (WPM), wildcards that can match any character arbitrarily are allowed in the pattern of the client. In this study, we first propose an extended variant of the standard WPM functionality, which we termed extended wildcard pattern matching (EWPM). The EWPM functionality allows the client to acquire the entire set of substrings that match his pattern, rather than the corresponding locations. We constructed a secure protocol of the EWPM functionality using cut-and-choose oblivious transfer (CCOT) in a semi-honest model. The efficiency of the proposed protocol approximates that of the state-of-the-art scheme. Furthermore, we implemented our protocol to demonstrate its actual practicality. The experimental result shows that when the pattern length is 210 and the text length is less than 220, the total execution time is less than 2 s.

We investigate the problem of building a suffix array substring index for inputs significantly larger than main memory. This problem is especially important in the context of biological sequence analysis, where biological polymers can be thought of as very large contiguous strings. The objective is to index every substring of these long strings to facilitate efficient queries. We propose a new simple, scalable, and inherently parallelizable algorithm for building a suffix array for out-of-core strings. Our new algorithm, Suffix Rank , scales to arbitrarily large inputs, using disk as a memory extension. It solves the problem in just O (log n ) scans over the disk-resident data. We evaluate the practical performance of our new algorithm, and show that for inputs significantly larger than the available amount of RAM, it scales better than other state-of-the-art solutions, such as eSAIS, SAscan , and eGSA.

Dictionary-based entity extraction is an important task in many data analysis applications, such as academic search, document classification, and code auto-debugging. To improve the effectiveness of extraction, many previous studies focused on the problem of approximate dictionary-based entity extraction, which aims at finding all substrings in documents that are similar to pre-defined entities in the reference entity dictionary. However, these studies only consider syntactical similarity metrics, such as Jaccard and edit distance. In real-world scenarios, there are many cases where syntactically different strings can express the same meaning. Existing approximate entity extraction work fails to identify such kind of semantic similarity and will definitely suffer from low recall. In this paper, we come up with the new problem of an approximate dictionary-based entity extraction with synonyms and propose an end-to-end framework Aeetes to solve it. We propose a new similarity measure Asymmetric Rule-based Jaccard ( JaccAR ) to combine the synonym rules with syntactic similarity metrics and capture the semantic similarity expressed in the synonyms. We devise and implement a filter-and-verification based strategy to improve the overall efficiency. To this end, we propose several pruning techniques to reduce the filter cost and develop novel strategies to improve verification performance. Experimental results on three real-world datasets demonstrate the superior effectiveness and efficiency of Aeetes .

Resistor string is one of the classic digital-to-analog converter (DAC) architectures and has dominant applications where guaranteed monotonicity is important. For high-resolution string DACs, gradient errors limit the linearity performance by causing mismatch in the resistor arrays. In this paper, a low-cost practical string DAC structure with gradient error suppression is proposed. It achieves high linearity by dividing a string into multiple smaller substrings and placing them in a pattern where up to $2^{nd}$ order gradients are suppressed. The derivation is provided to explain how the $2^{nd}$ order gradient is mitigated. Averaging and interpolation are implemented at the substrings’ outputs to recover the bits of resolution without sacrificing the linearity improvement. An 8-bit prototype is fabricated in a $0.13~\mu \text{m}$ CMOS technology and occupies 2.6 mm2. It achieves 16-bit linearity performance without trimming and calibration.

Nearest neighbor search is a basic and recurring proximity problem that has been studied for several decades. The goal is to preprocess a dataset of points so that we can quickly report the closet point(s) to any query point. Many recent applications of NNS involve datasets that are very large and dynamic, that is items of data items become available gradually. In this study, we propose a data structure for solving NNS for dynamic binary data where both query and dataset items are represented as binary strings. The proposed tree data structure, called the Hamming Weight Tree, is simple and as the names suggests, is based on partitioning the feature space of binary strings by exploiting the Hamming weights of the binary codes and their substrings. Given a Hamming Weight Tree of binary codes, we propose two search algorithms that accommodate nearest neighbor search for two different distance functions, the Hamming distance and the angular distance. Our empirical results show significant speedup in comparison with the best known large-scale solutions.

This paper proposes two variants of improved Compression by Substring Enumeration (CSE) with a finite alphabet. In previous studies on CSE, an encoder utilizes inequalities which evaluate the number of occurrences of a substring or a minimal forbidden word (MFW) to be encoded. The inequalities are derived from a contingency table including the number of occurrences of a substring or an MFW. Moreover, codeword length of a substring and an MFW grows with the difference between the upper and lower bounds deduced from the inequalities, however the lower bound is not tight. Therefore, we derive a new tight lower bound based on the contingency table and consequently propose a new CSE algorithm using the new inequality. We also propose a new encoding order of substrings and MFWs based on a sorted contingency table such that both its row and column marginal total are sorted in descending order instead of a lexicographical order used in previous studies. We then propose a new CSE algorithm which is the first proposed CSE algorithm using the new encoding order. Experimental results show that compression ratios of all files of the Calgary corpus in the proposed algorithms are better than those of a previous study on CSE with a finite alphabet. Moreover, compression ratios under the second proposed CSE get better than or equal to that under a well-known compressor for 11 files amongst 14 files in the corpus.

For a string S, a palindromic substring S[i..j] is said to be a shortest unique palindromic substring (SUPS) for an interval [s,t] in S, if S[i..j] occurs exactly once in S, the interval [i,j] contains [s,t], and every palindromic substring containing [s,t] which is shorter than S[i..j] occurs at least twice in S. In this paper, we study the problem of answering SUPS queries on run-length encoded strings. We show how to preprocess a given run-length encoded string RLES of size m in O(m) space and $O(m \log \sigma _{\mathit {RLE}_{S}} + m \sqrt {\log m / \log \log m})$ time so that all SUPSs for any subsequent query interval can be answered in $O(\sqrt {\log m / \log \log m} + \alpha )$ time, where α is the number of outputs, and $\sigma _{\mathit {RLE}_{S}}$ is the number of distinct runs of RLES. Additionaly, we consider a variant of the SUPS problem where a query interval is also given in a run-length encoded form. For this variant of the problem, we present two alternative algorithms with faster queries. The first one answers queries in $O(\sqrt {\log \log m /\log \log \log m} + \alpha )$ time and can be built in $O(m \log \sigma _{\mathit {RLE}_{S}} + m \sqrt {\log m / \log \log m})$ time, and the second one answers queries in $O(\log \log m + \alpha )$ time and can be built in $O(m \log \sigma _{\mathit {RLE}_{S}})$ time. Both of these data structures require O(m) space.

Data provenance is an effective method to evaluate data reliability and has become a research hotspot in recent years. However, the size of the data provenance will increase rapidly as the number of hops experienced increases, which conflicts with the limitations of energy, storage, and resources of IoT devices. The existing DP provenance compression algorithm has a high error rate when decompressing. To solve this problem, we propose an index-based provenance compression algorithm, which adopts the idea of common substring matching, combined with path identifier and path index to represent the path information in the data provenance, thereby achieving the purpose of reducing the size of data provenance. In addition, we extend the data provenance scheme to attack detection and propose a malicious node identification method based on data provenance. The simulation results show that the proposed scheme has a high compression ratio and higher decoding accuracy and has high accuracy in malicious node identification.

Discovering Transcription Factor Binding Sites (TFBS) has immense significance in terms of developing techniques and evaluating regulatory processes in biological systems. The DNA gene sequence encompasses large volume of datasets so a new methodology is needed to analyze them in the quickest possible time. Over the past decades, the planted (l, d) motif discovery methodology has been used for locating TFBS in the genetic region. This paper focuses on developing a new approach for motif identification using planted (l, d) motif discovery algorithm. The proposed algorithm is named ESMD (Emerging Substring based Motif Detection), which is based on two processes: Mining and Combining Emerging Substrings. In the mining step, an array is initially created, based on the suffix array (SA) and the longest common prefix array (LCP). A MapReduce programming model handles the mining of emerging substring process since DNA gene sequences constitute huge data. The next step combines the emerging substrings of different lengths. The resulting models have been evaluated using two different metrics, the Pearson Correlation Coefficient (PCC) and the Area Under Curve (AUC). Both have produced much better results than existing methods.

We propose new frequent substring pattern mining which can enumerate all substrings with statistically significant frequencies of their locally optimal occurrences from a given single sequence. Our target application is genome sequences, around a half being said to be covered by interspersed and consecutive (tandem) repeats, and detecting these repeats is an important task in molecular life sciences. We evaluate the statistical significance of frequent substrings by using a string generation model with a memoryless stationary information source. We combine this idea with an existing algorithm, ESFLOO-0G.C (Nakamura et al. 2016), to enumerate all statistically significant substrings with locally optimal occurrences. We further develop a parallelized version of our algorithm. Experimental results using synthetic datasets showed the proposed algorithm achieved far higher F-measure in extracting substrings (with various lengths and frequencies) embedded in a randomly generated string with noise, than conventional algorithms. The large-scale experiment using the whole human genome sequence with 3,095,677,412 bases (letters) showed that our parallel algorithm covers 75% of the whole positions analyzed, around 4% and 24% higher than the recent report and the current cutting-edge knowledge, implying a biologically unique finding.

Many properties of a string can be viewed as sets of dependencies between substrings of the string expressed in terms of substring equality. We design a linear-time algorithm which finds a solution to an arbitrary system of such constraints: a generic string satisfying a system of substring equations. This provides a general tool for reconstructing a string from different kinds of repetitions or symmetries present in the string, in particular, from runs or from maximal palindromes. The recursive structure of our algorithm in some aspects resembles the suffix array construction by Karkkainen et al. (2006) [23] . This is a full version of a paper presented at WADS 2015 [18] .

The k-NN algorithm is an instance-based learning algorithm which is widely used in the data mining applications. The core engine of the k-NN algorithm is the distance/similarity function. The performance of the k-NN algorithm varies with the selection of distance function. The traditional distance/similarity functions in k-NN do not perfectly handle the mix-mode words such as when one string has multiple substrings/words. For example, a two-word string of 'Employee Name', a one-word string of 'Name' or more than one word such as, 'Name of Employee'. This ambiguity is faced by different distance/similarity functions causing difficulties in finding the perfect match of words. To improve the perfect-match calculation functionality in the traditional k-NN algorithm, a new similarity distance metric is developed and named as word-distance (w-distance). The perfect match will help us to identify the exact required value. The proposed w-distance is a hybrid of distance and similarity in nature because it is to handle dissimilarity and similarity features of strings at the same time. The simulation results showed that w-distance has a better impact on the performance of the k-NN algorithm as compared to the Euclidean distance and the cosine similarity. © 2020-IOS Press and the authors. All rights reserved.

Given a pattern x of length m and a text y of length n , both over a totally ordered alphabet, the order-preserving pattern matching (OPPM) problem consists in finding all substrings of the text with the same relative order as the pattern. The OPPM problem, which might be viewed as an approximate variant of the well-known exact pattern matching problem, has gained attention in recent years. This interesting problem finds applications in such diverse fields as time series analysis (as share prices on stock markets or weather data analysis) and musical melody matching, just to mention a few. In this paper we present two new filtering approaches which turn out to be much more effective in practice than the previously presented methods, reducing the number of false positives up to 99%. We also present a new efficient approach inspired by the well-known Skip Search algorithm for the exact string matching problem. It makes use of efficient SIMD SSE instructions for speeding up the searching phase. Experimental results show that our proposed algorithms are up to twice faster than previous solutions.

Delta encoding represents a target file making use of a source file by replacing common substrings by pointer references. Two similar, yet different, models are introduced and investigated in this paper: the Compressed Transitive Delta Encoding (CTDE) and the Compressed Source Delta Encoding (CSDE) paradigms. In these models we are given two delta files and the goal is to construct a third delta file working directly on the given compressed forms. Formally, given a source file S and two differencing files Δ ( S , T ) and Δ ( T , R ) , where Δ ( X , Y ) is used to denote the delta file of the target file Y with respect to the source file X , the objective of the CTDE problem is to be able to attain R . Unlike the traditional way which uses S to decompress Δ ( S , T ) , in order to attain T , and then applies Δ ( T , R ) on T to obtain R , CTDE constructs a delta file Δ ( S , R ) working directly on the two given delta files Δ ( S , T ) and Δ ( T , R ) , without any decompression or the use of the base file S . Thus, avoiding the storage of the redundant intermediate file T . An algorithm for solving CTDE is proposed and its compression performance is compared to the traditional “double delta decompression”. Not only does it use constant space, as opposed to linear memory storage used by the traditional method, experiments show that the compression efficiency of the constructed delta file Δ ( S , R ) is usually better than both Δ ( S , T ) and Δ ( T , R ) . The CSDE problem deals with a source file S and two differencing files Δ ( S , T ) and Δ ( S , R ) , and the goal is still to be able to attain R . Although it is not always possible to construct the target file R by processing only the two input delta files, empirical experiments show that on typical real life data, usually about 99% of the file can be constructed using the proposed algorithm for the CSDE problem.

The paper contains a new text searching method representing modification of the Boyer-Moore algorithm and enabling a user to find the places in the text where the given substring occurs maybe with possible errors, that is the string in text and a query may not coincide but nevertheless are identical. The idea consists in division of the searching process in two phases: at the first phase a fuzzy variant of the Boyer–Moore algorithm is performed; at the second phase the Dice metrics is used. The advantage of suggested technique in comparison with the known methods using the fixed value of the mistakes number is that it 1) does not perform precomputation of the auxiliary table of the sizes comparable to the original text sizes and 2) it more flexibly catches the semantics of the erroneous text substrings even for a big number of mistakes. This circumstance extends possibilities of the Boyer–Moore method by addmitting a bigger amount of possible mistakes in text and preserving text semantics. The suggested method provides also more accurate regulation of the upper boundary for the text mistakes which differs it from the known methods with fixed value of the maximum number of mistakes not depending on the text sizes. Moreover, this upper boundary is defined as Levenshtein distance not suitable for evaluating a relevance of the founded text and a query, while the Dice metrics provides such a relevance. In fact, if maximum Levenshtein distanse is 3 then how one can judge if this value is big or small to provide relevance of the search results. Consequently, the suggested method is more flexible, enables one to find relevant answers even in case of a big number of mistakes in text. The efficiency of the suggested method in the worst case is O(nc) with constant c defining the biggest allowable number of mistakes.

The design of a sustainable photovoltaic (PV) module with advantages of high power output during faulty and hot-spot conditions is presented. This PV module is designed by incorporating a small modification in the existing PV modules. The cost involved in modification is negligible during the initial fabrication process. In a commercial market, all PV modules have only one junction box that contains terminals from various strings. Bypass diodes and output cables are connected with these terminals in the junction box. In the existing PV module, two substrings are connected in series, and its output terminals are given to the junction box. The proposed PV module has two junction boxes: one at the top and another at the bottom. The top box has top-end terminals of each substring, whereas the bottom box has bottom-end terminals of each substring. By having two junction boxes, the proposed PV module provides an opportunity to remodify the string connections during fault conditions. This research work analyzed the performance of existing and proposed PV modules under faulty and hot-spot conditions. This analysis verifies the sustainable nature of the proposed PV module.

Introduction: The parameters chosen for complex coded signals used in active radar systems of aircraft for detecting objects largelydetermines their qualitative characteristics and the possibility of covert operation. An important task in the design of such on-boardsystems is the formation of ensembles of pseudorandom-noise binary code sequences of a fixed length with predefined characteristics.Purpose: Search for PRN binary code sequences of a given length, optimal by the criterion of the minimum level of the sidelobes of theaperiodic autocorrelation function. Results: A procedure of search for binary code sequences with specified parameters based on theevolutionary approach is proposed. The minimum level of positive sidelobes of the autocorrelation function is used as a criterion forthe selection of code sequences. An additional restriction is imposed on the length of a substring of codes of the same character. Thepossibility of forming a representative array of sequences with the best ratio of the main peak of the aperiodic autocorrelation functionto its maximum positive sidelobe is shown on the example of 31-bit code sequences. An algorithm is proposed for generating a PRNseries of signals using the code sequences found. The Hamming distance is used as a measure of the difference between two binary codesequences in the series. The proposed approach is advantageous as compared to the well-known method of generating PRN signals basedon pseudorandom m-sequences. Practical relevance: The results obtained can be used in algorithms of airborne radar systems with ahigh range resolution to detect physical objects on the background of an underlying surface, for example, objects on the water surface.

Substring searching on gene sequence data is widely used for analyzing the association between a list of gene mutations and a specific disease. As substring search usually has a high computational cost, deploying it in the cloud has become a popular solution. Moreover, the cloud allows easier data sharing among medical organizations. Since the gene data contains private information, medical organizations usually outsource encrypted gene data to the cloud and selectively share with others. Most existing solutions for the privacy-preserving substring search problem are based on searchable encryption. However, they mainly focus on single-source gene data, not suitable for handling multi-source gene data because of some practical weaknesses. In this paper, we propose a cryptographic scheme that supports privacy-preserving substring search on multi-source encrypted gene data. The cloud can authorize queriers with access control and perform substring searches over the multi-source encrypted gene data for them. Despite the outsourced gene data is encrypted with different keys, but the authorized querier can issue a substring search only uses its own key. We adopt the composite order bilinear map as the primary underlying cryptographic primitive of our scheme. We mainly focus on protecting the privacy of the outsourced gene data and the substring queries, and we provide a security analysis under the honest-but-curious model. We also perform experiments on different datasets and analyze the experimental results in terms of computation cost and communication cost. The analyses show that our scheme is secure and efficient for substring search on multi-source encrypted gene data.

The theory of formal languages and, particularly, context-free grammars has been extensively studied and applied in different areas. For example, several approaches to the recognition and classification problems in bioinformatics are based on searching the genomic subsequences possessing some specific features which can be described by a context-free grammar. Therefore, the string-matching problem can be reduced to parsing – verification if some subsequence can be derived in this grammar. Such field of application as bioinformatics requires working with a large amount of data, so it is necessary to improve the existing parsing techniques. The most asymptotically efficient parsing algorithm that can be applied to any context-free grammar is a matrix-based algorithm proposed by Valiant. This paper aims to present Valiant’s algorithm modification, which main advantage is the possibility to divide the parsing table into successively computed layers of disjoint submatrices where each submatrix of the layer can be processed independently. Moreover, our approach is easily adapted for the string-matching problem. Our evaluation shows that the proposed modification retains all benefits of Valiant’s algorithm, especially its high performance achieved by using fast matrix multiplication methods. Also, the modified version decreases a large amount of excessive computations and accelerates the substrings searching.

Humans, by nature, have always been fascinated by the possibility of being able to acquire more information in minimum possible time and space. The effective lossless compression method, effective data structure, and DNA (Deoxyribonucleic Acid) data searching are quite essential as they provide a stimulus to easy accessibility and communication. The proposed algorithm is a new Lossless Compression algorithm, which compresses data, based on two tiers. Firstly, it searches for the exact Genetic Palindrome(GP), Palindrome(P) and Reverse(R)[GP2R] and the substring is reported, which is replaced by the corresponding ASCII character creating a Library file. By using the ASCII code, the Library file acts as a signature as well as provides the security of data. Secondly, modified RSA technique is proposed for the selection encryption purpose. This selection encryption of the modified RSA technique is an approach to lessen computational resources for greatly sized DNA facts. The experimental work shows 44% to 45% original sequence is encrypted where above 95% of the original file is damaged by using this method. This technique can find out the 3.851273 bits per base of the compression rate. The O(n) is the complexity of this algorithm. The running time is a few seconds of this algorithm. This is a hybrid approach to the compression & encryption process. For reducing the compression rate, the first pass output is again compressed by the second pass but it is lossy, This experiment is performed on benchmark DNA order.

In order to define a DNF version of first-order sentences over strings in which atomic sentences represent substring properties of strings, we use results of the Ehrenfeucht–Fraisse game over strings. Then, given a sample of strings and the number of disjunctive clauses, we investigate the problem of finding a DNF formula that is consistent with the sample. We show that this problem is NP-complete, and we solve it by a translation into Boolean satisfiability. We also present an extension of this problem that is robust concerning noisy samples. We solve the generalized version by a codification into the maximum satisfiability problem. As first-order logic over strings defines exactly the class of locally threshold testable (LTT) languages, our results can be useful in the grammatical inference framework when the goal is to find a model of a LTT language from a sample of strings.