Designers search for N-nodes peer-to-peer networks that can have O （1） out-degree with O （log2 N） average distance. Peer-to-peer schemes based on de Bruijn graphs are found to meet this requirement. By defining av...Designers search for N-nodes peer-to-peer networks that can have O （1） out-degree with O （log2 N） average distance. Peer-to-peer schemes based on de Bruijn graphs are found to meet this requirement. By defining average load to evaluate the traffic load in a network, we show that in order to decrease the average load, the average distance of a network should decrease while the out-degree should increase. Especially, given out-degree k and N nodes, peer-to-peer schemes based on de Bruijn graphs have lower average load than other existing systems. The out-degree k of de Bruijn graphs should not be O（1） but should satisfy a lower bound described by an inequality κ^κ≥N^2, to ensure that the average load in peer-to-peer schemes based on de Bruijn graphs will not exceed that in Chord system.展开更多
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 ...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.展开更多
Background:De novo genome assembly relies on two kinds of graphs:de Bruijn graphs and overlap graphs.Overlap graphs are the basis for the Celera assembler,while de Bruijn graphs have become the dominant technical devi...Background:De novo genome assembly relies on two kinds of graphs:de Bruijn graphs and overlap graphs.Overlap graphs are the basis for the Celera assembler,while de Bruijn graphs have become the dominant technical device in the last decade.Those two kinds of graphs are collectively called assembly graphs.Results:In this review,we discuss the most recent advances in the problem of constructing,representing and navigating assembly graphs,focusing on very large datasets.We will also explore some computational techniques,such as the Bloom filter,to compactly store graphs while keeping all functionalities intact.Conclusions:We complete our analysis with a discussion on the algorithmic issues of assembling from long reads(eg.,PacBio and Oxford Nanopore).Finally,we present some of the most relevant open problems in this field.展开更多
The super edge-connectivity of a graph is an important parameter to measure fault-tolerance of interconnection networks.This note shows that the Kautz undirected graph is super edge-connected,and provides a short proo...The super edge-connectivity of a graph is an important parameter to measure fault-tolerance of interconnection networks.This note shows that the Kautz undirected graph is super edge-connected,and provides a short proof of Lü and Zhang's result on super edge-connectivity of the de Bruijn undirected graph.展开更多
de Bruijn定理是一种重要的组合计数方法,本文以非常自然的方式推广了这种方法.P-图是图G在其顶点上的置换群P作用下形成的轨道.文中引进了P-图,P-图的色容指标,P-图关于色置换群H的色权多项式以及色对称与全色对称图等概念,建立了色权...de Bruijn定理是一种重要的组合计数方法,本文以非常自然的方式推广了这种方法.P-图是图G在其顶点上的置换群P作用下形成的轨道.文中引进了P-图,P-图的色容指标,P-图关于色置换群H的色权多项式以及色对称与全色对称图等概念,建立了色权多项式的计算公式和一系列的组合公式及性质.展开更多
Genome sequencing is the process of determining in which order the nitrogenous bases also known as nucleotides within a DNA molecule are arranged. Every organism’s genome consists of a unique sequence of nucleotides....Genome sequencing is the process of determining in which order the nitrogenous bases also known as nucleotides within a DNA molecule are arranged. Every organism’s genome consists of a unique sequence of nucleotides. These nucleotides bases provide the phenotypes and genotypes of a cell. In mathematics, Graph theory is the study of mathematical objects known as graphs which are made of vertices (or nodes) connected by either directed edges or indirect edges. Determining the sequence in which these nucleotides are bonded can help scientists and researchers to compare DNA between organisms, which can help show how the organisms are related. In this research, we study how graph theory plays a vital part in genome sequencing and different types of graphs used during DNA sequencing. We are going to propose several ways graph theory is used to sequence the genome. We are as well, going to explore how the graphs like Hamiltonian graph, Euler graph, and de Bruijn graphs are used to sequence the genome and advantages and disadvantages associated with each graph.展开更多
文摘Designers search for N-nodes peer-to-peer networks that can have O （1） out-degree with O （log2 N） average distance. Peer-to-peer schemes based on de Bruijn graphs are found to meet this requirement. By defining average load to evaluate the traffic load in a network, we show that in order to decrease the average load, the average distance of a network should decrease while the out-degree should increase. Especially, given out-degree k and N nodes, peer-to-peer schemes based on de Bruijn graphs have lower average load than other existing systems. The out-degree k of de Bruijn graphs should not be O（1） but should satisfy a lower bound described by an inequality κ^κ≥N^2, to ensure that the average load in peer-to-peer schemes based on de Bruijn graphs will not exceed that in Chord system.
基金National Natural Science Foundation of China(No.19971086,19871040)Jiangsu Provincial Natural Science Foundation of China
文摘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.
文摘Background:De novo genome assembly relies on two kinds of graphs:de Bruijn graphs and overlap graphs.Overlap graphs are the basis for the Celera assembler,while de Bruijn graphs have become the dominant technical device in the last decade.Those two kinds of graphs are collectively called assembly graphs.Results:In this review,we discuss the most recent advances in the problem of constructing,representing and navigating assembly graphs,focusing on very large datasets.We will also explore some computational techniques,such as the Bloom filter,to compactly store graphs while keeping all functionalities intact.Conclusions:We complete our analysis with a discussion on the algorithmic issues of assembling from long reads(eg.,PacBio and Oxford Nanopore).Finally,we present some of the most relevant open problems in this field.
基金by ANSF( 0 1 0 4 61 0 2 ) and the National Natural Science Foundatim of China ( 1 0 2 71 1 1 4)
文摘The super edge-connectivity of a graph is an important parameter to measure fault-tolerance of interconnection networks.This note shows that the Kautz undirected graph is super edge-connected,and provides a short proof of Lü and Zhang's result on super edge-connectivity of the de Bruijn undirected graph.
文摘Genome sequencing is the process of determining in which order the nitrogenous bases also known as nucleotides within a DNA molecule are arranged. Every organism’s genome consists of a unique sequence of nucleotides. These nucleotides bases provide the phenotypes and genotypes of a cell. In mathematics, Graph theory is the study of mathematical objects known as graphs which are made of vertices (or nodes) connected by either directed edges or indirect edges. Determining the sequence in which these nucleotides are bonded can help scientists and researchers to compare DNA between organisms, which can help show how the organisms are related. In this research, we study how graph theory plays a vital part in genome sequencing and different types of graphs used during DNA sequencing. We are going to propose several ways graph theory is used to sequence the genome. We are as well, going to explore how the graphs like Hamiltonian graph, Euler graph, and de Bruijn graphs are used to sequence the genome and advantages and disadvantages associated with each graph.
