Search results for "Subsequence"
showing 10 items of 12 documents
Selecting one of two regular sound sequences : Perceptual and motor effects of tempo
2008
This study assessed the influence of tempo on selecting a sound sequence. In Exp. 1, synchronization with one of the two regular subsequences in a complex sequence was measured. 30 participants indicated a preference for the fastest subsequence when subsequences were in a slow tempo range (≥ 500 msec. IOI), and with the slower subsequence when they were in the fast tempo range (≤ 300 msec. IOI). These results were replicated using a perceptual task (Exp. 2 and 3) in which the 30 listeners had to detect a temporal irregularity in one of the two subsequences. Detection was better when the temporal irregularity was in the fastest subsequence than in the slowest one when the complex sequence w…
A Fly-Inspired Mushroom Bodies Model for Sensory-Motor Control Through Sequence and Subsequence Learning
2016
Classification and sequence learning are relevant capabilities used by living beings to extract complex information from the environment for behavioral control. The insect world is full of examples where the presentation time of specific stimuli shapes the behavioral response. On the basis of previously developed neural models, inspired by Drosophila melanogaster, a new architecture for classification and sequence learning is here presented under the perspective of the Neural Reuse theory. Classification of relevant input stimuli is performed through resonant neurons, activated by the complex dynamics generated in a lattice of recurrent spiking neurons modeling the insect Mushroom Bodies n…
Restricted 123-avoiding Baxter permutations and the Padovan numbers
2007
AbstractBaxter studied a particular class of permutations by considering fixed points of the composite of commuting functions. This class is called Baxter permutations. In this paper we investigate the number of 123-avoiding Baxter permutations of length n that also avoid (or contain a prescribed number of occurrences of) another certain pattern of length k. In several interesting cases the generating function depends only on k and is expressed via the generating function for the Padovan numbers.
Complemented Subspaces and Interpolation Properties in Spaces of Polynomials
1997
LetXbe a Banach space whose dualX* has typep ∈ (1, 2]. Ifmis an integer greater thanp/(p − 1) and (xn) is a seminormalized sequence weakly convergent to zero, there is a subsequence (yn) of (xn) such that, for each element (an) ofl∞, there is anm-homogeneous continuous polynomialPonXwithP(yn) = an,n = 1, 2,… . Some interpolation and complementation properties are also given in P(mlp), form < p, as well as in other spaces of polynomials and multilinear functionals.
Longest Common Subsequence from Fragments via Sparse Dynamic Programming
1998
Sparse Dynamic Programming has emerged as an essential tool for the design of efficient algorithms for optimization problems coming from such diverse areas as Computer Science, Computational Biology and Speech Recognition [7,11,15]. We provide a new Sparse Dynamic Programming technique that extends the Hunt-Szymanski [2,9,8] paradigm for the computation of the Longest Common Subsequence (LCS) and apply it to solve the LCS from Fragments problem: given a pair of strings X and Y (of length n and m, resp.) and a set M of matching substrings of X and Y, find the longest common subsequence based only on the symbol correspondences induced by the substrings. This problem arises in an application t…
Analysis and design of sequencing rules for car sequencing
2009
Abstract This paper presents novel approaches for generating sequencing rules for the car sequencing (CS) problem in cases of two and multiple processing times per station. The CS problem decides on the succession of different car models launched down a mixed-model assembly line. It aims to avoid work overloads at the stations of the line by applying so-called sequencing rules, which restrict the maximum occurrence of labor-intensive options in a subsequence of a certain length. Thus to successfully avoid work overloads, suitable sequencing rules are essential. The paper shows that the only existing rule generation approach leads to sequencing rules which misclassify feasible sequences. We …
Sparse Dynamic Programming for Longest Common Subsequence from Fragments
2002
Sparse Dynamic Programming has emerged as an essential tool for the design of efficient algorithms for optimization problems coming from such diverse areas as computer science, computational biology, and speech recognition. We provide a new sparse dynamic programming technique that extends the Hunt?Szymanski paradigm for the computation of the longest common subsequence (LCS) and apply it to solve the LCS from Fragments problem: given a pair of strings X and Y (of length n and m, respectively) and a set M of matching substrings of X and Y, find the longest common subsequence based only on the symbol correspondences induced by the substrings. This problem arises in an application to analysis…
XLCS: A New Bit-Parallel Longest Common Subsequence Algorithm on Xeon Phi Clusters
2019
Finding the longest common subsequence (LCS) of two strings is a classical problem in bioinformatics. A basic approach to solve this problem is based on dynamic programming. As the biological sequence databases are growing continuously, bit-parallel sequence comparison algorithms are becoming increasingly important. In this paper, we present XLCS, a new parallel implementation to accelerate the LCS algorithm on Xeon Phi clusters by performing bit-wise operations. We have designed an asynchronous IO framework to improve the data transfer efficiency. To make full use of the computing resources of Xeon Phi clusters, we use three levels of parallelism: node-level, thread-level and vector-level.…
A pointwise selection principle for metric semigroup valued functions
2008
Abstract Let ∅ ≠ T ⊂ R , ( X , d , + ) be an additive commutative semigroup with metric d satisfying d ( x + z , y + z ) = d ( x , y ) for all x , y , z ∈ X , and X T the set of all functions from T into X . If n ∈ N and f , g ∈ X T , we set ν ( n , f , g , T ) = sup ∑ i = 1 n d ( f ( t i ) + g ( s i ) , g ( t i ) + f ( s i ) ) , where the supremum is taken over all numbers s 1 , … , s n , t 1 , … , t n from T such that s 1 ⩽ t 1 ⩽ s 2 ⩽ t 2 ⩽ ⋯ ⩽ s n ⩽ t n . We prove the following pointwise selection theorem: If a sequence of functions { f j } j ∈ N ⊂ X T is such that the closure in X of the set { f j ( t ) } j ∈ N is compact for each t ∈ T , and lim n → ∞ ( 1 n lim N → ∞ sup j , k ⩾ N , j…
A basic analysis toolkit for biological sequences
2007
This paper presents a software library, nicknamed BATS, for some basic sequence analysis tasks. Namely, local alignments, via approximate string matching, and global alignments, via longest common subsequence and alignments with affine and concave gap cost functions. Moreover, it also supports filtering operations to select strings from a set and establish their statistical significance, via z-score computation. None of the algorithms is new, but although they are generally regarded as fundamental for sequence analysis, they have not been implemented in a single and consistent software package, as we do here. Therefore, our main contribution is to fill this gap between algorithmic theory an…