|
De Bruijn Graph
In graph theory, an -dimensional De Bruijn graph of symbols is a directed graph representing overlaps between sequences of symbols. It has vertices, consisting of all possible sequences of the given symbols; the same symbol may appear multiple times in a sequence. For a set of symbols the set of vertices is: :V=S^n=\. If one of the vertices can be expressed as another vertex by shifting all its symbols by one place to the left and adding a new symbol at the end of this vertex, then the latter has a directed edge to the former vertex. Thus the set of arcs (that is, directed edges) is :E=\. Although De Bruijn graphs are named after Nicolaas Govert de Bruijn, they were invented independently by both de Bruijn and I. J. Good. Much earlier, Camille Flye Sainte-Marie implicitly used their properties. Properties * If , then the condition for any two vertices forming an edge holds vacuously, and hence all the vertices are connected, forming a total of edges. * Each vertex has e ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph theory), vertices'' (also called ''nodes'' or ''points'') which are connected by ''Glossary of graph theory terms#edge, edges'' (also called ''arcs'', ''links'' or ''lines''). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics. Definitions Definitions in graph theory vary. The following are some of the more basic ways of defining graphs and related mathematical structures. Graph In one restricted but very common sense of the term, a graph is an ordered pair G=(V,E) comprising: * V, a Set (mathematics), set of vertices (also called nodes or points); * ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Radix
In a positional numeral system, the radix (radices) or base is the number of unique digits, including the digit zero, used to represent numbers. For example, for the decimal system (the most common system in use today) the radix is ten, because it uses the ten digits from 0 through 9. In any standard positional numeral system, a number is conventionally written as with ''x'' as the string of digits and ''y'' as its base. For base ten, the subscript is usually assumed and omitted (together with the enclosing parentheses), as it is the most common way to express value. For example, (the decimal system is implied in the latter) and represents the number one hundred, while (100)2 (in the binary system with base 2) represents the number four. Etymology ''Radix'' is a Latin word for "root". ''Root'' can be considered a synonym for ''base,'' in the arithmetical sense. In numeral systems Generally, in a system with radix ''b'' (), a string of digits denotes the number , ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Kautz Graph
Kautz is a surname. Notable people with the surname include: *Albert Kautz (1839–1907), American naval officer, born at Georgetown, Ohio *August Kautz (1828–1895), German-American soldier and Union Army cavalry officer during the American Civil War *Christian Kautz (1913–1948), auto racing driver from Switzerland *Jacob Kautz (1500–1532), Anabaptist who posted seven theses to the door of the Worms Cathedral in 1527 *Julius Kautz (1829–1909), Hungarian economist See also *Kautz Creek, tributary of the Nisqually River in the Mount Rainier National Park of Washington *Kautz Creek Falls, waterfall on Kautz Creek in the Mount Rainier National Park of Washington *Kautz Glacier, narrow glacier on the southern flank of Mount Rainier in Washington *Kautz Family YMCA Archives collects the historical records of its national organization, the YMCA of the USA *Kautz filter, named after William H. Kautz, is a fixed-pole traversal filter, published in 1954 *Kautz graph, directed grap ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hamming Graph
Hamming graphs are a special class of graphs named after Richard Hamming and used in several branches of mathematics (graph theory) and computer science. Let be a set of elements and a positive integer. The Hamming graph has vertex set , the set of ordered -tuples of elements of , or sequences of length from . Two vertices are adjacent if they differ in precisely one coordinate; that is, if their Hamming distance is one. The Hamming graph is, equivalently, the Cartesian product of complete graphs .. In some cases, Hamming graphs may be considered more generally as the Cartesian products of complete graphs that may be of varying sizes.. Unlike the Hamming graphs , the graphs in this more general class are not necessarily distance-regular, but they continue to be regular and vertex-transitive. Special cases *, which is the generalized quadrangle *, which is the complete graph . *, which is the lattice graph and also the rook's graph *, which is the singleton gra ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
De Bruijn Torus
In combinatorics, combinatorial mathematics, a De Bruijn torus, named after Dutch mathematician Nicolaas Govert de Bruijn, is an matrix (mathematics), array of symbols from an alphabet (often just 0 and 1) that contains every possible matrix (mathematics), matrix of given dimensions exactly once. It is a torus because the edges are considered wraparound for the purpose of finding matrices. Its name comes from the De Bruijn sequence, which can be considered a special case where (one dimension). One of the main open questions regarding De Bruijn tori is whether a De Bruijn torus for a particular alphabet size can be constructed for a given and . It is known that these always exist when , since then we simply get the De Bruijn sequences, which always exist. It is also known that "square" tori exist whenever and even (for the odd case the resulting tori cannot be square). The smallest possible binary "square" de Bruijn torus, depicted above right, denoted as de Bruijn torus (o ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Genome
A genome is all the genetic information of an organism. It consists of nucleotide sequences of DNA (or RNA in RNA viruses). The nuclear genome includes protein-coding genes and non-coding genes, other functional regions of the genome such as regulatory sequences (see non-coding DNA), and often a substantial fraction of junk DNA with no evident function. Almost all eukaryotes have mitochondrial DNA, mitochondria and a small mitochondrial genome. Algae and plants also contain chloroplast DNA, chloroplasts with a chloroplast genome. The study of the genome is called genomics. The genomes of many organisms have been Whole-genome sequencing, sequenced and various regions have been annotated. The first genome to be sequenced was that of the virus φX174 in 1977; the first genome sequence of a prokaryote (''Haemophilus influenzae'') was published in 1995; the yeast (''Saccharomyces cerevisiae'') genome was the first eukaryotic genome to be sequenced in 1996. The Human Genome Project ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
De Novo Sequence Assemblers
De novo sequence assemblers are a type of program that assembles short nucleotide sequences into longer ones without the use of a reference genome. These are most commonly used in bioinformatic studies to assemble genomes or transcriptomes. Two common types of de novo assemblers are greedy algorithm assemblers and De Bruijn graph assemblers. Types of de novo assemblers There are two types of algorithms that are commonly utilized by these assemblers: greedy, which aim for local optima, and graph method algorithms, which aim for global optima. Different assemblers are tailored for particular needs, such as the assembly of (small) bacterial genomes, (large) eukaryotic genomes, or transcriptomes. Greedy algorithm assemblers are assemblers that find local optima in alignments of smaller reads. Greedy algorithm assemblers typically feature several steps: 1) pairwise distance calculation of reads, 2) clustering of reads with greatest overlap, 3) assembly of overlapping reads into lar ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Bioinformatics
Bioinformatics () is an interdisciplinary field of science that develops methods and Bioinformatics software, software tools for understanding biological data, especially when the data sets are large and complex. Bioinformatics uses biology, chemistry, physics, computer science, data science, computer programming, information engineering, mathematics and statistics to analyze and interpret biological data. The process of analyzing and interpreting data can sometimes be referred to as computational biology, however this distinction between the two terms is often disputed. To some, the term ''computational biology'' refers to building and using models of biological systems. Computational, statistical, and computer programming techniques have been used for In silico, computer simulation analyses of biological queries. They include reused specific analysis "pipelines", particularly in the field of genomics, such as by the identification of genes and single nucleotide polymorphis ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Koorde
In peer-to-peer networks, Koorde is a distributed hash table (DHT) system based on the Chord (DHT), Chord DHT and the De Bruijn graph (De Bruijn sequence). Inheriting the simplicity of Chord, Koorde meets hops per Node (networking), node (where is the number of nodes in the DHT), and hops per lookup request with neighbors per node. The Chord concept is based on a wide range of Network address, identifiers (e.g. 2) in a structure of a Ring network, ring where an identifier can stand for both node and data. Node-successor is responsible for the whole range of IDs between itself and its predecessor. De Bruijn's graphs Koorde is based on Chord but also on the De Bruijn graph (De Bruijn sequence). In a -dimensional de Bruijn graph, there are Vertex (graph theory), nodes, each of which has a unique Network address, ID with bits. The node with ID is connected to nodes and . Thanks to this property, the routing algorithm can route to any destination in hops by successively "shi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Distributed Hash Table
A distributed hash table (DHT) is a Distributed computing, distributed system that provides a lookup service similar to a hash table. Key–value pairs are stored in a DHT, and any participating node (networking), node can efficiently retrieve the value associated with a given key. The main advantage of a DHT is that nodes can be added or removed with minimum work around re-distributing keys. ''Keys'' are unique identifiers which map to particular ''values'', which in turn can be anything from addresses, to Electronic document, documents, to arbitrary Data (computing), data. Responsibility for maintaining the mapping from keys to values is distributed among the nodes, in such a way that a change in the set of participants causes a minimal amount of disruption. This allows a DHT to scale (computing), scale to extremely large numbers of nodes and to handle continual node arrivals, departures, and failures. DHTs form an infrastructure that can be used to build more complex services, su ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Grid Network
A grid network is a computer network consisting of a number of computer systems connected in a grid topology. In a regular grid topology, each node in the network is connected with two neighbors along one or more dimensions. If the network is one-dimensional, and the chain of nodes is connected to form a circular loop, the resulting topology is known as a ring. Network systems such as FDDI use two counter-rotating token-passing rings to achieve high reliability and performance. In general, when an ''n''-dimensional grid network is connected circularly in more than one dimension, the resulting network topology is a torus, and the network is called "toroidal". When the number of nodes along each dimension of a toroidal network is 2, the resulting network is called a hypercube. A parallel computing cluster or multi-core processor is often connected in regular interconnection network such as a de Bruijn graph, [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Book Thickness
In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings in a ''book'', a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie on this boundary line, called the ''spine'', and the edges are required to stay within a single half-plane. The book thickness of a graph is the smallest possible number of half-planes for any book embedding of the graph. Book thickness is also called pagenumber, stacknumber or fixed outerthickness. Book embeddings have also been used to define several other graph invariants including the pagewidth and book crossing number. Every graph with vertices has book thickness at most \lceil n/2\rceil, and this formula gives the exact book thickness for complete graphs. The graphs with book thickness one are the outerplanar graphs. The graphs with book thickness at most two are the subhamiltonian graphs, which are always planar; more generally, e ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
