Skip to main content
Fig. 4 | Algorithms for Molecular Biology

Fig. 4

From: A safe and complete algorithm for metagenomic assembly

Fig. 4

An extremal graph G showing that the upper bound on the complexity of Algorithm 1 from Theorem 12 is attained. The vertex set of G is \(\{a_1,\dots ,a_{n/2},b_1,\dots ,b_{n/2}\}\). Any node- or edge-covering metagenomic reconstruction of G consists of circular walk(s) whose total length is \(\Omega (n^2)\)

Back to article page