Search results for "Array"
showing 10 items of 1264 documents
Inducing the Lyndon Array
2019
In this paper we propose a variant of the induced suffix sorting algorithm by Nong (TOIS, 2013) that computes simultaneously the Lyndon array and the suffix array of a text in $O(n)$ time using $\sigma + O(1)$ words of working space, where $n$ is the length of the text and $\sigma$ is the alphabet size. Our result improves the previous best space requirement for linear time computation of the Lyndon array. In fact, all the known linear algorithms for Lyndon array computation use suffix sorting as a preprocessing step and use $O(n)$ words of working space in addition to the Lyndon array and suffix array. Experimental results with real and synthetic datasets show that our algorithm is not onl…
Sorting suffixes of a text via its Lyndon Factorization
2013
The process of sorting the suffixes of a text plays a fundamental role in Text Algorithms. They are used for instance in the constructions of the Burrows-Wheeler transform and the suffix array, widely used in several fields of Computer Science. For this reason, several recent researches have been devoted to finding new strategies to obtain effective methods for such a sorting. In this paper we introduce a new methodology in which an important role is played by the Lyndon factorization, so that the local suffixes inside factors detected by this factorization keep their mutual order when extended to the suffixes of the whole word. This property suggests a versatile technique that easily can b…
Uncommon Suffix Tries
2011
Common assumptions on the source producing the words inserted in a suffix trie with $n$ leaves lead to a $\log n$ height and saturation level. We provide an example of a suffix trie whose height increases faster than a power of $n$ and another one whose saturation level is negligible with respect to $\log n$. Both are built from VLMC (Variable Length Markov Chain) probabilistic sources; they are easily extended to families of sources having the same properties. The first example corresponds to a ''logarithmic infinite comb'' and enjoys a non uniform polynomial mixing. The second one corresponds to a ''factorial infinite comb'' for which mixing is uniform and exponential.
Lightweight LCP construction for very large collections of strings
2016
The longest common prefix array is a very advantageous data structure that, combined with the suffix array and the Burrows-Wheeler transform, allows to efficiently compute some combinatorial properties of a string useful in several applications, especially in biological contexts. Nowadays, the input data for many problems are big collections of strings, for instance the data coming from "next-generation" DNA sequencing (NGS) technologies. In this paper we present the first lightweight algorithm (called extLCP) for the simultaneous computation of the longest common prefix array and the Burrows-Wheeler transform of a very large collection of strings having any length. The computation is reali…
Adversary Lower Bound for the k-sum Problem
2013
We prove a tight quantum query lower bound $\Omega(n^{k/(k+1)})$ for the problem of deciding whether there exist $k$ numbers among $n$ that sum up to a prescribed number, provided that the alphabet size is sufficiently large. This is an extended and simplified version of an earlier preprint of one of the authors arXiv:1204.5074.
A Unified SVM Framework for Signal Estimation
2013
This paper presents a unified framework to tackle estimation problems in Digital Signal Processing (DSP) using Support Vector Machines (SVMs). The use of SVMs in estimation problems has been traditionally limited to its mere use as a black-box model. Noting such limitations in the literature, we take advantage of several properties of Mercer's kernels and functional analysis to develop a family of SVM methods for estimation in DSP. Three types of signal model equations are analyzed. First, when a specific time-signal structure is assumed to model the underlying system that generated the data, the linear signal model (so called Primal Signal Model formulation) is first stated and analyzed. T…
Compact 20-pass thin-disk amplifier insensitive to thermal lensing
2019
We present a multi-pass amplifier which passively compensates for distortions of the spherical phase front occurring in the active medium. The design is based on the Fourier transform propagation which makes the output beam parameters insensitive to variation of thermal lens effects in the active medium. The realized system allows for 20 reflections on the active medium and delivers a small signal gain of 30 with M$^2$ = 1.16. Its novel geometry combining Fourier transform propagations with 4f-imaging stages as well as a compact array of adjustable mirrors allows for a layout with a footprint of 400 mm x 1000 mm.
Carbon Monoxide in the Cold Debris of Supernova 1987A
2013
We report spectroscopic and imaging observations of rotational transitions of cold CO and SiO in the ejecta of SN1987A, the first such emission detected in a supernova remnant. In addition to line luminosities for the CO J=1-0, 2-1, 6-5, and 7-6 transitions, we present upper limits for all other transitions up to J=13-12, collectively measured from the Atacama Large Millimeter Array (ALMA), the Atacama Pathfinder EXperiment (APEX), and the Herschel Spectral and Photometric Imaging REceiver (SPIRE). Simple models show the lines are emitted from at least 0.01 solar masses of CO at a temperature > 14 K, confined within at most 35% of a spherical volume expanding at ~ 2000 km/s. Moreover, we…
Configurable low-cost plotter device for fabrication of multi-color sub-cellular scale microarrays.
2014
We report on the construction and operation of a low-cost plotter for fabrication of microarrays for multiplexed single-cell analyses. The printing head consists of polymeric pyramidal pens mounted on a rotation stage installed on an aluminium frame. This construction enables printing of microarrays onto glass substrates mounted on a tilt stage, controlled by a Lab-View operated user interface. The plotter can be assembled by typical academic workshops from components of less than 15 000 Euro. The functionality of the instrument is demonstrated by printing DNA microarrays on the area of 0.5 squared centimeters using up to three different oligonucleotides. Typical feature sizes are 5 μm diam…
A Genome-Wide Detection of Copy Number Variations Using SNP Genotyping Arrays in Braque Français Type Pyrénées Dogs
2019
Simple Summary Copy number variations (CNVs) are important sources of variation in mammalian species. In this study, we used a single nucleotide polymorphisms (SNP) array to detect CNVs in Braque Français, type Pyrénées dogs (BRA). Results overlapped moderately in comparison with previous studies on CNVs in dogs, leading to the identification of 16 novel CNVRs. Several genes were annotated in the CNV regions (CNVRs) detected, some of which related to muscle structure development. This breed is known to be excellent upland game birds dogs. The selection for such hunting behavior could have driven the presence of these genes into the CNVRs. Copy number variations may be of interest to study a…