De Bruijn Graph of a Palindromic Sequence

If you find our commentaries useful, please feel free to press the donate button on the right sidebar, and your generous contribution will be acknowledged in the table at the bottom of the page.

You can follow us on twitter – @homolog_us.


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

Heroes and Heroines of New Media--2015

Our blog is deeply honored by the generous contribution of the following readers. Without their patronage, this site would go away.

Outstandingly Generous:   
Amemiya C. Schnable J. Bowman B. Osipowski P.
Shen M. Furness M. Graur D. Diesh C.
Amemiya C.      

We are also looking for subscribers to get help to finish the tutorials. Please see this post for details.

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>

Web Analytics