De Bruijn Sequences (2011) [video]

A popular mnemonic for remembering the formulae of the basic units of Sanskrit metre is probably the first ever recorded example of De Bruijn Sequence. The phrase "Ya-Maa-Taa-Raa-Ja-Bhaa-Na-Sa-La-Gam" encodes all 8 possible combinations of syllables of length 3.

The basic unit of Sanskrit metre is called Gana and is composed of 3 syllables. Since a syllable can be either short (I) or long (U), we have 2^3 = 8 Ganas in total corresponding to UUU, UUI, UIU etc. To know the composition of a specific Gana say for example Ja Gana, one has to find the index of "Ja" in the aforementioned phrase and extract the next two syllables as well so Ja Gana equals Ja-Bhaa-Na => IUI (because Ja is short, Bhaa is long and Na is short again).

Code in Python if my explanation wasn't clear

  mnemonic = "Ya-Maa-Taa-Raa-Ja-Bhaa-Na-Sa-La-Gaam"

  def symbol(syllable):
      if syllable.count("a") == 1:
        return "I"
   else:
        return "U"

  def ganaSymbol(ganaName):
      mnerray = mnemonic.split("-")
      ganaIndex = mnerray.index(ganaName)
      return "".join([symbol(syllable) for syllable in mnerray[ganaIndex : ganaIndex + 3]])

Metres are then defined in terms of Ganas and the number of lines in a stanza, for example Utpala Mala metre can be defined simply as Na-Ja-Bhaa-Ja-Ja-Ja-Raa, 4 which means a stanza in that meter should comprise of 4 lines, with each line having 21 syllables corresponding to Na-Ja-Bhaa-Ja-Ja-Ja-Raa sequence

  utpalaMala = "Na-Ja-Bhaa-Ja-Ja-Ja-Raa"

  def printMetre(metreGanas, numLines):
    print("\n".join(["".join([ganaSymbol(ganaName) for ganaName in metreGanas.split("-")])]*numLines))

Edits: Formatting

A surprising bit twiddling trick[0] uses a De Bruijn sequence to calculate log base 2.

[0] https://graphics.stanford.edu/~seander/bithacks.html#Integer...

The colored variant of a De Bruijin graph is used extensive for high throughput sequencing alignment, assembly or quantification. For example, Pufferfish [1] has worked towards an efficient and compact index of these graphs.

[1] https://github.com/COMBINE-lab/pufferfish

A colleague and I used De Bruijn sequences as test input for comparing matches on recursively generated regexes between PCRE and our own regex engine. The sequence was guaranteed to give us a search hit regardless of the pattern so it was a nice way to control for good testing results.

I've found de bruijn sequences useful for generating test inputs, where you want to make sure every state transition is checked.

First time I came across this was when I was reading a chapter on genome assembly in a bioinformatics algorithms book. It seemed like such a great solution until it got to the section about practical complications with DNA sequencing: sequencing errors, the fact that that their are 2 strings being assembled (double stranded DNA), repeats in the genome, etc..

Unfortunately, I can't find a reference at the moment, but there are two American mathematicians who perform card tricks in class and one of these tricks uses a de Bruijn sorted deck to allow to cut the deck many times and still be able to do the magic afterwards.

De Bruijn sequences are useful in neuroimaging, too. My former lab: https://cfn.upenn.edu/aguirre/wiki/public:de_bruijn

I watched the video hoping to learn how to finally pronounce "de bruijin"

Very nice video, though unbelievable that the presenter wrote out that 10,000 number solution in his notebook while he has a computer on his desk.