Search results for "Strings"
showing 10 items of 28 documents
ParDRe: faster parallel duplicated reads removal tool for sequencing studies
2016
This is a pre-copyedited, author-produced version of an article accepted for publication in Bioinformatics following peer review. The version of record [insert complete citation information here] is available online at: https://doi.org/10.1093/bioinformatics/btw038 [Abstract] Summary: Current next generation sequencing technologies often generate duplicated or near-duplicated reads that (depending on the application scenario) do not provide any interesting biological information but can increase memory requirements and computational time of downstream analysis. In this work we present ParDRe , a de novo parallel tool to remove duplicated and near-duplicated reads through the clustering of S…
Region-dependent hamstrings activity in Nordic hamstring exercise and stiff-leg deadlift defined with high-density electromyography
2018
Recent studies suggest region-specific metabolic activity in hamstring muscles during injury prevention exercises, but the neural representation of this phenomenon is unknown. The aim of this study was to examine whether regional differences are evident in the activity of biceps femoris long head (BFlh) and semitendinosus (ST) muscles during two common injury prevention exercises. Twelve male participants without a history of hamstring injury performed the Nordic hamstring exercise (NHE) and stiff-leg deadlift (SDL) while BFlh and ST activities were recorded with high-density electromyography (HD-EMG). Normalized activity was calculated from the distal, middle, and proximal regions in the e…
Algebraic and logical characterizations of deterministic linear time classes
1997
In this paper an algebraic characterization of the class DLIN of functions that can be computed in linear time by a deterministic RAM using only numbers of linear size is given. This class was introduced by Grandjean, who showed that it is robust and contains most computational problems that are usually considered to be solvable in deterministic linear time.
On Combinatorial Generation of Prefix Normal Words
2014
A prefix normal word is a binary word with the property that no substring has more 1s than the prefix of the same length. This class of words is important in the context of binary jumbled pattern matching. In this paper we present an efficient algorithm for exhaustively listing the prefix normal words with a fixed length. The algorithm is based on the fact that the language of prefix normal words is a bubble language, a class of binary languages with the property that, for any word w in the language, exchanging the first occurrence of 01 by 10 in w results in another word in the language. We prove that each prefix normal word is produced in O(n) amortized time, and conjecture, based on expe…
A first search for coincident gravitational waves and high energy neutrinos using LIGO, Virgo and ANTARES data from 2007
2013
A search for high-energy neutrinos coming from the direction of the Sun has been performed using the data recorded by the ANTARES neutrino telescope during 2007 and 2008. The neutrino selection criteria have been chosen to maximize the selection of possible signals produced by the self-annihilation of weakly interacting massive particles accumulated in the centre of the Sun with respect to the atmospheric background. After data unblinding, the number of neutrinos observed towards the Sun was found to be compatible with background expectations. The 90% CL upper limits in terms of spin-dependent and spin-independent WIMP-proton cross-sections are derived and compared to predictions of two sup…
Combinatorial isomorphism between Fibonacci classes
2008
Abstract In 1985 Simion and Schmidt showed that the set S n (T 3) of length n permutations avoiding the set of patterns T 3={123, 132, 213} is counted by (the second order) Fibonacci numbers. They also presented a constructive bijection between the set F n–1 of length (n–1) binary strings with no two consecutive 1s and S n (T 3). In 2005, Egge and Mansour generalized the first Simion-Simion’s result and showed that S n (T p ), the set of permutations avoiding the patterns T p ={12…p, 132, 213}, is counted by the (p–1)th order Fibonacci numbers. In this paper we extend the second Simion-Schmidt’s result by giving a bijection between the set of length (n–1) binary strings with no (p–1) consec…
Periodicity and repetitions in parameterized strings
2008
AbstractOne of the most beautiful and useful notions in the Mathematical Theory of Strings is that of a Period, i.e., an initial piece of a given string that can generate that string by repeating itself at regular intervals. Periods have an elegant mathematical structure and a wealth of applications [F. Mignosi and A. Restivo, Periodicity, Algebraic Combinatorics on Words, in: M. Lothaire (Ed.), Cambridge University Press, Cambridge, pp. 237–274, 2002]. At the hearth of their theory, there are two Periodicity Lemmas: one due to Lyndon and Schutzenberger [The equation aM=bNcP in a free group, Michigan Math. J. 9 (1962) 289–298], referred to as the Weak Version, and the other due to Fine and …
Dyck paths with a first return decomposition constrained by height
2018
International audience; We study the enumeration of Dyck paths having a first return decomposition with special properties based on a height constraint. We exhibit new restricted sets of Dyck paths counted by the Motzkin numbers, and we give a constructive bijection between these objects and Motzkin paths. As a byproduct, we provide a generating function for the number of Motzkin paths of height k with a flat (resp. with no flats) at the maximal height. (C) 2018 Elsevier B.V. All rights reserved.KeywordsKeyWords Plus:STATISTICS; STRINGS
ALGORITHMS FOR JUMBLED PATTERN MATCHING IN STRINGS
2011
The Parikh vector p(s) of a string s is defined as the vector of multiplicities of the characters. Parikh vector q occurs in s if s has a substring t with p(t)=q. We present two novel algorithms for searching for a query q in a text s. One solves the decision problem over a binary text in constant time, using a linear size index of the text. The second algorithm, for a general finite alphabet, finds all occurrences of a given Parikh vector q and has sub-linear expected time complexity; we present two variants, which both use a linear size index of the text.
A trace partitioned Gray code forq-ary generalized Fibonacci strings
2015
AbstractWe provide a trace partitioned Gray code for the set of q-ary strings avoiding a pattern constituted by k consecutive equal symbols. The definition of this Gray code is based on two different constructions, according to the parity of q. This result generalizes, and is based on, a Gray code for binary strings avoiding k consecutive 0's.