Narrow Results

We prove that the cutwidth of the n-dimensional shuffle-exchange graph is at most ⌈2ⁿ⁺¹/n⌉, for n≥10. This essentially improves on the previous best constant factors. As a consequence we obtain an improved upper bound for the cutwidth of the de Bruijn graph.

We present an embedding of the mesh of d-ary trees, a graph we introduce here, into de Bruijn graphs, which are good topologies for parallel architectures, with an optimal expansion and constant dilation and congestion. We show how to embed several disjoint meshes of d-ary trees in the same de Bruijn graph. It gives some results about emulation of the meshes of d-ary trees by the de Bruijn network.

The computation of upper bounds of the bandwidth of graphs is mainly based on the giving of a numbering which achieves these bounds. In [9], Harper proposed such a numbering for the binary hypercube, based on the Hamming weights and binary values of the hypercube vertices.

By defining an extended Hamming weight, this numbering can lead to an equivalent proof for the d-ary de Bruijn graph. We present in this paper an approach, based on the use of the continuous domain and Laplace’s theorem for asymptotically evaluating integrals, which leads to the enumeration of the vertices of the same extended Hamming weight in the non-binary case. This result allows the computation of an upper bound of the bandwidth of the unoriented de Bruijn graph, as well as an upper bound of its vertex-bisection when both the diameter and the degree are even.

We present a comprehensive study of utility function of the minority game in its efficient regime. We develop an effective description of state of the game. For the payoff function g(x) = sgn (x), we explicitly represent the game as the Markov process and prove the finiteness of number of states. We also demonstrate boundedness of the utility function. Using these facts we can explain all interesting observable features of the aggregated demand: appearance of strong fluctuations, their periodicity, and existence of preferred levels. For another payoff, g(x) = x, the number of states is still finite and utility remains bounded but the number of states cannot be reduced and probabilities of states are not calculated. However, using properties of the utility and analyzing the game in terms of de Bruijn graphs, we can also explain distinct peaks of demand and their frequencies.

The ability to detect the genetic variations between two individuals is an essential component for genetic studies. In these studies, obtaining the genome sequence of both individuals is the first step toward variation detection problem. The emergence of high-throughput sequencing (HTS) technology has made DNA sequencing practical, and is widely used by diagnosticians to increase their knowledge about the casual factor in genetic related diseases. As HTS advances, more data are generated every day than the amount that scientists can process. Genome assembly is one of the existing methods to tackle the variation detection problem. The de Bruijn graph formulation of the assembly problem is widely used in the field. Furthermore, it is the only method which can assemble any genome in linear time. However, it requires an enormous amount of memory in order to assemble any mammalian size genome. The high demands of sequencing more individuals and the urge to assemble them are the driving forces for a memory efficient assembler. In this work, we propose a novel method which builds the de Bruijn graph while consuming lower memory. Moreover, our proposed method can reduce the memory usage by 37% compared to the existing methods. In addition, we used a real data set (chromosome 17 of A/J strain) to illustrate the performance of our method.

The de Bruijn Graph algorithm (DBG) as one of the cornerstones algorithms in short read assembly has extended with the rapid advancement of the Next Generation Sequencing (NGS) technologies and low-cost production of millions of high-quality short reads. Erroneous reads, non-uniform coverage, and genomic repeats are three major problems that influence the performance of short read assemblers. To encounter these problems, the iterative DBG algorithm applies multiple $k$-mers instead of a single $k$-mer, by iterating the DBG graph over a range of $k$-mer sizes from the minimum to the maximum. However, the iteration paradigm of iterative DBG deals with complex graphs from the beginning of the algorithm and therefore, causes more potential errors and computational time for resolving various unreal branches. In this research, we propose the Reverse Modified Iterative DBG graph (named RMI-DBG) for short read assembly. RMI-DBG utilizes the DBG algorithm and String graph to achieve the advantages of both algorithms. We present that RMI-DBG performs faster with comparable results in comparison to iterative DBG. Additionally, the quality of the proposed algorithm in terms of continuity and accuracy is evaluated with some commonly-used assemblers via several real datasets of the GAGE-B benchmark.

The authors obtain a new property of the n dimensional binary undirected de Bruijn graph UB(n) for n≥4, namely, there is a vertex x such that for any other vertex y there exist at least two internally disjoint paths of length at most n-1 between x and y in UB(n). The result means that the (n - 1, 2)-dominating number of UB(n) is equal to one if n ≥ 4.