Coffee!! Found: A use for junk DNA

Cosmologist Paul Davies suggested, in a recent essay ("Is Anybody Out There?" Wall Street Journal (April 10, 2010), another way of finding space aliens:

Another physical object with enormous longevity is DNA. Our bodies contain some genes that have remained little changed in 100 million years. An alien expedition to Earth might have used biotechnology to assist with mineral processing, agriculture or environmental projects. If they modified the genomes of some terrestrial organisms for this purpose, or created their own micro-organisms from scratch, the legacy of this tampering might endure to this day, hidden in the biological record.

Which leads to an even more radical proposal. Life on Earth stores genetic information in DNA. A lot of DNA seems to be junk, however. If aliens, or their robotic surrogates, long ago wanted to leave us a message, they need not have used radio waves. They could have uploaded the data into the junk DNA of terrestrial organisms. It would be the modern equivalent of a message in a bottle, with the message being encoded digitally in nucleic acid and the bottle being a living, replicating cell. (It is possible—scientists today have successfully implanted messages of as many as 100 words into the genome of bacteria.) A systematic search for gerrymandered genomes would be relatively cheap and simple. Incredibly, a handful of (unsuccessful) computer searches have already been made for the tell-tale signs of an alien greeting.

But what if, as scientists are increasingly finding out, the so-called junk is actually functional.

That would increase the aliens' difficulty because they would need to use an existing useful structure to encode "Take me to your leader?" or "We are the voice of Unity". I wonder how they would do that.