Skip to main content
Figure 1 | Algorithms for Molecular Biology

Figure 1

From: Space-efficient and exact de Bruijn graph representation based on a Bloom filter

Figure 1

A complete example of removing false positives in the probabilistic de Bruijn graph. (a) showsS, an example de Bruijn graph (the 7 non-dashed nodes), and, its probabilistic representation from a Bloom filter (taking the union of all nodes). Dashed rectangular nodes (in red in the electronic version) are immediate neighbors of in. These nodes are the critical false positives. Dashed circular nodes (in green) are all the other nodes of; (b) shows a sample of the hash values associates to the nodes ofS (a toy hash function is used); (c) shows the complete Bloom filter associated toS; incidentally, the nodes of are exactly those to which the Bloom filter answers positively; (d) describes the lower bound for exactly encoding the nodes ofS (self-information) and the space required to encode our structure (Bloom filter, 10 bits, and 3 critical false positives, 6 bits per 3-mer).

Back to article page