Well, this is a bit different than what your original post talks about...

Okay, even then- sure, you can 'goedel up' a parsimonious representation of data with a certain level of complxity. Sure, you can encode that string/integer/whatever (as long as it is finite) as a DNA sequence. BUT even if

1) You can find or engineer microbes that can survive or reproduce in these dust clouds
2) That they can do 1 for the millions and millions of years it will take them to travel long distances
3) That during those millions and millions of years they will be genetically stable in the environment of space.
4) That when they drift into another system, they will be locatable even for those organisms that know to look for them (think needle in a COSMIC haystack)

Then you are still left with all the mathematical limitations I wrote about- the data is fully encrypted, and without a key there is no way of de-coding the information.

IMHO, the notions where transmissions are made where intervals and signals rely on basic mathematical truths- these are more likely to meaningful. Probably broadcasting sequences of pulses corresponding to the first 3,141 primes, or something along those lines.

The 'corresponding' civilizations would have to 'back and forth' over thousands of years, exchanging basics and expanding vocabulary at the slow speed of light.

Yes, its an epic timeframs- but so are dustclouds with Genetic sequences.

DL