Palindromic nucleotide sequences are those matching their reverse complements. Here is an example -”ATACGTCATTCAAATATGTATATACATACATATTCGAATATGTATGTATATACATATTTGAATGACGTAT”. Another one is “CATGTGACTTTATAGCAGCATGCTGCTATAAAGTCACATG”. We did not make those sequences up. They are taken from chromosome 1 of human genome.
Here is the de Bruijn graph of one of the above sequences with 7-mers. We are using the convention of showing only the lexicographically smaller 7-mer.
The above graph is constructed in a hurry and may have one or two errors, even though the general structure is correct.
Enjoy !!
Case analysis of graph structures is always a fascinating topic. I didn’t check the graph for errors (surely there are simpler examples of palindromes in dBGs, with smaller sequences and smaller k values). In the figure, it is worth noting that the first and last nucleotides of the red sequence are not part of the palindrome.