  The paired de Bruijn graph is an extension of de Bruijn graph incorporating
mate pair information for genome assembly proposed by Mevdedev et al. However,
unlike in an ordinary de Bruijn graph, not every path or cycle in a paired de
Bruijn graph will spell a string, because there is an additional soundness
constraint on the path. In this paper we show that the problem of checking if
there is a sound cycle in a paired de Bruijn graph is NP-hard in general case.
We also explore some of its special cases, as well as a modified version where
the cycle must also pass through every edge.
