The DNA idea is great. You'd need a long "this is a message" intro, say a long ATATATATAT repeating sequence (much too long to occur by chance). As you say, yo

The DNA idea is great. You'd need a long "this is a message" intro, say a long ATATATATAT repeating sequence (much too long to occur by chance). As you say, you can use forward error correction to preserve the data. The hard part is describing the data format to the reader. From the ATATA...intro, a reader knows they have a message. But now they need to know how to interpret it. You need a way of encoding information (english text?) in DNA and you also need a way of describing that encoding mechanism in DNA too... Basically, over 5k years you should look up all the protocols SETI people have thought up. And/or re-read Gödel, Escher Bach.