Search

Two strings of the same length are order isomorphic if their relative orders are the same. The order-preserving pattern matching problem is to find all substrings of text T that are order isomorphic to pattern P when T (| T | = n) and P (| P | = m) are given. An O (m n + n q log q + q !) -time algorithm using the O (m + q !) space for the order-preserving pattern matching problem has been proposed utilizing fingerprints of q-grams based on the factorial number system and the bad character heuristic. In this paper, we propose an O (m n + 2 q) -time algorithm using the O (m + 2 q) space for the order-preserving pattern matching problem, but utilizing fingerprints of q-grams converted to binary numbers. A comparative experiment using three types of time series data demonstrates that the proposed algorithm is faster than existing algorithms because it reduces the number of order isomorphism tests. [ABSTRACT FROM AUTHOR]

With the growing dependence on smartphones for everyday activities, a large number of pedestrians nowadays are constantly fixated on their smartphone screens, and hence are susceptible to walking off pavements or colliding with other pedestrians. Reduced attention and situational awareness can render smartphone-occupied users, or smombies, oblivious to potential risks when using their smartphones while walking or driving. In this paper, we introduce a smartphone application, called Smombie Guardian, that detects obstacles and alerts smombies as they walk while viewing their smartphone screens to prevent potential collisions. Based on a user study with 74 participants who used Smombie Guardian in a real-life scenario, we highlight the effectiveness, usefulness, and unobtrusiveness of the algorithm and Smombie Guardian in helping users to avoid potential obstacles. [ABSTRACT FROM AUTHOR]

Solubilitiesof octahydro-1,3,5,7-tetranitro-1,3,5,7-tetrazocinein γ-butyrolactone + water, dimethyl sulfoxide + water, and N-methyl pyrrolidone + water were measured in the temperaturerange from 273.15 K to 363.15 K and mass fraction of water from 0to 1.0. Activity coefficient and heat of dissolution were obtainedfrom the solubility data. [ABSTRACT FROM AUTHOR]

Given two strings X ( | X | = m ) and Y ( | Y | = n ) over an alphabet Σ, the edit distance between X and Y can be computed in O ( m n / t ) time with the help of the Four-Russians' lookup table whose block size is t . The Four-Russians' lookup table can be constructed in O ( ( 3 | Σ | ) 2 t t 2 ) time using O ( ( 3 | Σ | ) 2 t t ) space. However, the construction time and space requirement of the lookup table grow very fast as the alphabet size increases and thus it has been used only when | Σ | is very small. For example, when a string is a protein sequence, | Σ | = 20 and thus it is almost impossible to use the Four-Russians' lookup table on typical workstations. In this paper, we present an efficient alphabet-independent Four-Russians' lookup table. It requires O ( 3 2 t ( 2 t ) ! t ) space and can be constructed in O ( 3 2 t ( 2 t ) ! t 2 ) time. Thus, the Four-Russians' lookup table can be constructed and used irrespective of the alphabet size. The time and space complexity were achieved by compacting the lookup table using a clever encoding of the preprocessed strings. Experimental results show that the space requirement of the lookup table is reduced to about 1/5,172,030 of its original size when | Σ | = 26 and t = 4 . Furthermore, we present efficient multithreaded parallel algorithms for edit distance computation using the Four-Russians' lookup table. The parallel algorithm for lookup table construction runs in O ( t ) time and the parallel algorithm for edit distance computation between X and Y runs in O ( m + n ) time. Experiments performed on CUDA-supported GPU show that our algorithm runs about 942 times faster than the sequential version of the original Four-Russians' algorithm for 100 pairs of random strings of length approximately 1,000 when | Σ | = 4 and t = 4 . [ABSTRACT FROM AUTHOR]

Abstract: Circular strings are different from linear strings in that the last symbol is considered to precede the first symbol. Even though circular strings are biologically important, only a few efforts have been made to solve computational problems on circular strings. In this paper, we introduce consensus problems for circular strings of length and present the first non-trivial algorithms to find a consensus and an optimal alignment for circular strings by the Hamming distance. They are -time algorithms for three circular strings and an -time algorithm for four circular strings. Our algorithms are times faster than the naïve algorithms directly using the solutions for the linear consensus problems, which take time for three circular strings and time for four circular strings. This speedup was achieved by reducing the problems into correlations and by formulating and solving systems of linear equations. Moreover, our algorithms use only space. [Copyright &y& Elsevier]

Abstract: The consensus (string) problem is finding a representative string, called a consensus, of a given set of strings. In this paper we deal with consensus problems considering both distance sum and radius, where the distance sum is the sum of (Hamming) distances from the strings in to the consensus and the radius is the longest (Hamming) distance from the strings in to the consensus. Although there have been results considering either distance sum or radius, there have been no results considering both, to the best of our knowledge. We present the first algorithms for two consensus problems considering both distance sum and radius for three strings: one problem is to find an optimal consensus minimizing both distance sum and radius. The other problem is to find a bounded consensus such that the distance sum is at most and the radius is at most for given constants and . Our algorithms are based on characterization of the lower bounds of distance sum and radius, and thus they solve the problems efficiently. Both algorithms run in linear time. [Copyright &y& Elsevier]

Abstract: In this paper, we study approximate regularities of strings, that is, approximate periods, approximate covers, and approximate seeds. We explore their similarities and differences and we implement algorithms for solving the smallest distance approximate period/cover/seed problem and the restricted smallest approximate period/cover/seed/ problem in polynomial time, under a variety of distance rules (the Hamming distance, the edit distance, and the weighted edit distance). Then, we analyse our experimental results to find out the time complexity of the algorithms in practice. [Copyright &y& Elsevier]