120,490 research outputs found
A space efficient representation for sparse de Bruijn subgraphs
No full textQuitzau JAA, Stoye J. A space efficient representation for sparse de Bruijn subgraphs. Forschungsberichte der Technischen Fakultät, Abteilung Informationstechnik / Universität Bielefeld. Bielefeld: Technische Fakultät der Universität Bielefeld; 2008.De Bruijn graphs are structures that appear naturally in the study of strings. Therefore the rise of de Bruijn graph based sequence analysis approaches is not a surprise. The problem with de Bruijn graphs is that for most of their applications in Bioinformatics they are too large even for small genomes. A way to overcome this problem is the compression of branch-free paths to single nodes. Although this compression is a common first step in many of the de Bruijn graph based approaches, its direct construction from raw data does not seem to be documented before. Our experience shows that, though based on simple operations, implementing the construction of such graphs is a tricky and time consuming task. Therefore we shortly describe in this report our graph construction algorithm and hope that the given details are enough to help the reader skipping some pitfalls we found by doing this task
Cut-down de Bruijn sequences
No full textA cut-down de Bruijn sequence is a cyclic string of length L, where 1≤L≤kn, such that every substring of length n appears at most once. Etzion [Theor. Comp. Sci 44 (1986)] introduced an algorithm to construct binary cut-down de Bruijn sequences requiring o(n) simple n-bit operations per symbol generated. In this paper, we simplify the algorithm and improve the running time to O(n) time per symbol generated using O(n) space. Additionally, we develop the first successor-rule approach for constructing a binary cut-down de Bruijn sequence by leveraging recent ranking/unranking algorithms for fixed-density Lyndon words. Finally, we develop an algorithm to generate cut-down de Bruijn sequences for k>2 that runs in O(n) time per symbol using O(n) space after some initialization. © 2024 Elsevier B.V
Arbitrary-Length Analogs to de Bruijn Sequences
No full textLet α̃ be a length-L cyclic sequence of characters from a size-K alphabet such that for every positive integer m ≤ L, the number of occurrences of any length-m string on as a substring of α̃ is ⌊ L / K^m ⌋ or ⌈ L / K^m ⌉. When L = K^N for any positive integer N, α̃ is a de Bruijn sequence of order N, and when L ≠ K^N, α̃ shares many properties with de Bruijn sequences. We describe an algorithm that outputs some α̃ for any combination of K ≥ 2 and L ≥ 1 in O(L) time using O(L log K) space. This algorithm extends Lempel’s recursive construction of a binary de Bruijn sequence. An implementation written in Python is available at https://github.com/nelloreward/pkl
Stationary Distribution and Eigenvalues for a de Bruijn Process
No full textWe define a de Bruijn process with parameters n and L as a certain continuous-time
Markov chain on the de Bruijn graph with words of length L over an n-letter alphabet as
vertices. We determine explicitly its steady state distribution and its characteristic
polynomial, which turns out to decompose into linear factors. In addition, we examine the
stationary state of two specializations in detail. In the first one, the de
Bruijn-Bernoulli process, this is a product measure. In the second one, the Skin-deep de
Bruin process, the distribution has constant density but nontrivial correlation functions.
The two point correlation function is determined using generating function techniques
Two-Way Machines and de Bruijn Words
No full textWe consider de Bruijn words and their recognition by finite automata. While on one-way nondeterministic automata the recognition of de Bruijn words of order k requires exponentially many states in k, we show a family of de Bruijn words such that the word wk of order k, for k>0, can be recognized by a deterministic two-way finite automaton with O(k3) states. Using this result we are able to obtain an exponential-size separation from deterministic two-way finite automata to equivalent context-free grammars. We also show how wk can be generated by a 1-limited automaton with O(k3) states and a constant-size work alphabet. This allows to obtain small 1-limited automata for certain unary languages and to show an exponential-size separation from unary deterministic 1-limited automata to equivalent deterministic pushdown automata
Weight class distributions of de Bruijn sequences
No full textAbstractOrder n de Bruijn sequences are the period 2n binary sequences produced by an n stage feedback shift register. The de Bruijn sequences have good randomness and complexity properties. Theorems are given on the weight class distributions of the generator functions. Data that extend the work of Fredricksen are also presented
Characterizations of generators for modified de Bruijn sequences
No full textAbstractOrder n modified de Bruijn sequences are created by removing a single zero from the longest run of zeros in period 2n de Bruijn sequences. The M sequences are then the natural linear subset of modified de Bruijn sequences. Recursions which are the nonlinear duals to primitive polynomials over GF(2) are developed. Data is presented for 4 ≤ n ≤ 6
On the complexities of de Bruijn sequences
No full textAbstractThe shortest linear recursion which generates a de Bruijn sequence is defined to be the complexity of the sequence. It is shown that the complexity of a binary de Bruijn sequence of span n is bounded by 2n − 1 from above and 2n − 1 + n from below. Results on the distribution of the complexities are also presented
Further results on de Bruijn weight classes
No full textAbstractOrder n de Bruijn sequences are the period 2n binary sequences produced by an n stage feedback shift register. Additional information is given on the weight class distribution for the order n=7 generator functions
Extreme weight classes of de Bruijn sequences
No full textAbstractOrder n de Bruijn sequences are the period 2n binary sequences produced by an n stage feedback shift register. Properties of the number of sequences in the minimum and maximum weight classes of the generator functions are discussed
- …
