De Bruijn Graph of a Palindromic Sequence

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 !!

1 comment to De Bruijn Graph of a Palindromic Sequence

  • Rayan

    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.

Leave a Reply




You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>