It seems relevant to start talking about approximation algorithms as the next step after proving a "1000 year" runtime for exactly comparing genomes. My understanding is that comp bio folks typically use heuristics anyway.