180,603 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
Jaap R. Bruijn, Zeegang. Zeevarend Nederland in de achttiende eeuw
No full textJaap R. Bruijn, Zeegang. Zeevarend Nederland in de achttiende eeuw (Zutphen: Walburg Pers, 2016, 320 pp., ISBN 978 946 249 098 7)
Individual differences in the acute effects of cannabis and cocaine on cognitive control
No full textContains fulltext :
155627.pdf (Publisher’s version ) (Open Access)Radboud Universiteit Nijmegen, 09 maart 2016Promotores : Cools, R., Raemakers, J. Co-promotores : Verkes, R.J., Bruijn, E.R.A. d
A meshing technique for De Bruijn tori
No full textAbstract. An (R, S; m, n)k-de Bruijn torus is a k-ary R × S toroidal array with the property that every k-ary m × n matrix appears exactly once contiguously on the torus. The torus is a generalization of de Bruijn cycles and has been extended to higher dimensions by many authors. The central question, asked by Chung, Diaconis, and Graham, is for which R, S, m, n, and k such tori exist. In this note we develop a notion of equivalence class de Bruijn cycles and we extend a technique of Iványi and Tóth. Combining these ideas we are able to construct the first examples in which R and S are not powers of k. We prove for all natural numbers s and t there is a (4st 2, 4s 3 t 2; 2, 2)2st-de Bruijn torus. 1
Inference of viral quasispecies with a paired de Bruijn graph
No full textMotivation: RNA viruses exhibit a high mutation rate and thus they exist in infected cells as a population of closely related strains called viral quasispecies. The viral quasispecies assembly problem asks to characterize the quasispecies present in a sample from high-throughput sequencing data. We study the de novo version of the problem, where reference sequences of the quasispecies are not available. Current methods for assembling viral quasispecies are either based on overlap graphs or on de Bruijn graphs. Overlap graph-based methods tend to be accurate but slow, whereas de Bruijn graph-based methods are fast but less accurate. Results: We present viaDBG, which is a fast and accurate de Bruijn graph-based tool for de novo assembly of viral quasispecies. We first iteratively correct sequencing errors in the reads, which allows us to use large k-mers in the de Bruijn graph. To incorporate the paired-end information in the graph, we also adapt the paired de Bruijn graph for viral quasispecies assembly. These features enable the use of long-range information in contig construction without compromising the speed of de Bruijn graph-based approaches. Our experimental results show that viaDBG is both accurate and fast, whereas previous methods are either fast or accurate but not both. In particular, viaDBG has comparable or better accuracy than SAVAGE, while being at least nine times faster. Furthermore, the speed of viaDBG is comparable to PEHaplo but viaDBG is able to retrieve also low abundance quasispecies, which are often missed by PEHaplo.Peer reviewe
Meta-colored Compacted de Bruijn Graphs
No full textThe colored compacted de Bruijn graph (c-dBG) has become a fundamental tool used across several areas of genomics and pangenomics. For example, it has been widely adopted by methods that perform read mapping or alignment, abundance estimation, and subsequent downstream analyses. These applications essentially regard the c-dBG as a map from k-mers to the set of references in which they appear. The c-dBG data structure should retrieve this set—the color of the k-mer—efficiently for any given k-mer, while using little memory. To aid retrieval, the colors are stored explicitly in the data structure and take considerable space for large reference collections, even when compressed. Reducing the space of the colors is therefore of utmost importance for large-scale sequence indexing. We describe the meta-colored compacted de Bruijn graph (Mac-dBG)—a new colored de Bruijn graph data structure where colors are represented holistically, i.e., taking into account their redundancy across the whole collection being indexed, rather than individually as atomic integer lists. This allows the factorization and compression of common sub-patterns across colors. While optimizing the space of our data structure is NP-hard, we propose a simple heuristic algorithm that yields practically good solutions. Results show that the Mac-dBG data structure improves substantially over the best previous space/time trade-off, by providing remarkably better compression effectiveness for the same (or better) query efficiency . This improved space/time trade-off is robust across different datasets and query workloads. Code availability. A C++17 implementation of the Mac-dBG is publicly available on GitHub at: https://github.com/jermp/fulgor
Succinct colored de Bruijn graphs
No full textAbstract
Motivation
In 2012, Iqbal et al. introduced the colored de Bruijn graph, a variant of the classic de Bruijn graph, which is aimed at ‘detecting and genotyping simple and complex genetic variants in an individual or population’. Because they are intended to be applied to massive population level data, it is essential that the graphs be represented efficiently. Unfortunately, current succinct de Bruijn graph representations are not directly applicable to the colored de Bruijn graph, which requires additional information to be succinctly encoded as well as support for non-standard traversal operations.
Results
Our data structure dramatically reduces the amount of memory required to store and use the colored de Bruijn graph, with some penalty to runtime, allowing it to be applied in much larger and more ambitious sequence projects than was previously possible.
Availability and Implementation
https://github.com/cosmo-team/cosmo/tree/VARI
Supplementary information
Supplementary data are available at Bioinformatics online.
</jats:sec
Efficient reconfiguration algorithms of de Bruijn and Kautz networks into linear arrays
No full textAbstractIn this paper, we prove the existence of ranking and unranking algorithms on d-ary de Bruijn and Kautz graphs. A ranking algorithm takes as input the label of a node and returns the rank r of that node in a hamiltonian path (0⩽r⩽N−1, where N is the order of the considered graph). An unranking algorithm takes as input an integer r (0⩽r⩽N−1) and returns the label of the rth ranked node in a hamiltonian path. Our results generalize results given by Annexstein for binary de Bruijn graphs. The key of our framework is based on a recursive construction of hamiltonian paths in de Bruijn and Kautz graphs. The construction uses suitable uniform homomorphisms of de Bruijn and Kautz graphs of diameter D on de Bruijn graphs of diameter D−1. Our ranking and unranking algorithms have sequential time complexity in O(D2), where D is the length of node labels
An efficient implementation of the D-homomorphism for generation of de Bruijn sequences
No full textIn this correspondence, an efficient implementation of the D-homomorphism for generating de Bruijn sequences is presented. The number of exclusive-or operations required to generate the next bit for de Bruijn sequences of order n from a de Bruijn function of order k is shown to be approximately k(2(W(n-k))- 1), where W(r) is the number of one's in the binary representation of r: therefore, the number of required operations can be reduced to k if the de Bruijn function is selected appropriately. As an application, the stream cipher is indicated.Ministry of Information and Communications
(MIC) under Grant from the University Basic Research Fun
De Bruijn covering codes with arbitrary alphabets
No full textAbstractLet Ω be a set of q symbols and Ωn={x1…xn|xi∈Ω}. We prove that for any fixed q and R, there is a de Bruijn covering code of radius R of length O(qn(nR)lnn), answering a question of Chung and Cooper
- …
