The latest genome to be completely sequenced (as of fall 2006) is that of the purple sea urchin, Strongylocentrotus purpuratus. I don't know about you, but sea urchin aren't something I've spent a lot of time thinking about. I hadn't realized, for example, that they're closer to humans (evolutionarily speaking) than are insects (like fruit flies) or worms (like C. elegans). In fact they're the closest relatives of the chordates: "Based on similarities of embryonic organization, zoologists grouped echinoderms and Hemichordata (a phylum of marine worms) with chordates in the superclade Deuterostomia ... Within the deuterostomes, the chordates (vertebrate and invertebrate) form one large assemblage, and the echinoderms and their sister group the hemichordates the other, all members of which are more closely related to one another than they are to any other animals."
A lot of interesting stuff arises out of the urchin genome, as has happened with most of the other genomes that have been completed. Some of the interesting stuff is immunological. (This is reviewed in Science 314:952-956; "Genomic Insights into the Immune System of the Sea Urchin", by Rast et al.)
Quick background: Most vertebrates have two branches of the immune system, "innate" and "adaptive" responses. Very broadly speaking, "innate" responses are rapid, recognize common aspects of pathogens, and lack memory; "adaptive" responses are slower, but amplify and have memory; they recognize variable aspects of pathogens. Vaccines target adaptive responses, because they're relying on the memory aspect; you can't vaccinate a fly.
(Though in the interest of complete disclosure, very recently flies and other non-vertebrates have been shown to have a completely different form of immune response which in some ways acts like an adaptive response.)
Evolutionarily, adaptive responses apparently appeared, full-fledged, in sharks. Lampreys and hagfish, which have common ancestors with sharks, more or less lack adaptive responses, whereas sharks and all their descendants unto us have adaptive responses.
The key molecular development that gave sharks this system is the RAG1/RAG2 gene pair. The RAG genes rearrange DNA -- given appropriate sequence cues, these genes (and their supporting cast) can grab and shuffle and splice DNA. That means you can get vastly more complexity out of your genome. (If you start with 10 upstream halves of a gene, and 10 downstream halves, you can get 100 possible genes by randomly rearranging the DNA. The adaptive immune molecules are more complicated than that, and in fact you can get something like 10^13 different antibodies, and 10^18 possible different T-cell receptors, by rearranging the DNA. It's that huge number of possible sequences that allow the adaptive response to target variable regions of pathogens; it's the fact that the DNA is permanently altered that allows persistent memory.)
Lampreys and hagfish don't have RAG1/RAG2. However, genomic sequencing of invertebrates has turned up things that look kind of RAG-ish. They're transposable elements, which makes sense, since transposable elements would like to be able to cut and re-attach DNA so that they can transpose. (Lampreys and hagfish haven't had their genomes done yet, so it's possible something has been missed in them, but it would have to be a fairly distant relative of RAG1/2.) But there's nothing that looks like sharks, and our, RAG1/RAG2. The presumption has been that, around the time sharks split off from the lamprey ancestors, the transposable element entered their genome and mutated to become RAG1/RAG2, and the rest is history.
You see where this is going, though. Sea urchins do have a RAG1/RAG2 gene cluster! "The identification of a homologous, Rag1/2-like functional gene cluster was one of the most unexpected findings from the sea urchin genome, as the transposon-like character of the vertebrate Rag genes suggests that they may have been acquired through a process of horizontal gene transfer at the time of the emergence of rearranging TCR and immunoglobulin gene systems in a jawed-vertebrate common ancestor. Although it is unclear at present whether or not these genes are active in immunity, it is improbable that they emerged independently in an echinoderm. The most parsimonious explanation for the distribution of Rag1/2-like clusters in two major deuterostome clades is that it represents a shared genetic feature present in a common ancestral deuterostome. Alternatively, the Rag1/2-like gene cluster may represent the independent cooption of an as yet unknown transposon that encoded both Rag1- and Rag2-like genes."
In other words, instead of arising in sharks, the RAG1/RAG2 pair may have arisen well before that, in the common ancestor with sea urchins. In that case, lampreys may have lost the genes, rather than sharks gaining it. The other possibility is that RAG1/RAG2 moved into sharks and urchins independently, perhaps from a common ancestor of the RAG-related transposon.
Sea urchins don't appear to have an adaptive immune response -- although, with this finding and a couple of other puzzling hints in their genome, I think that's something that should be examined very closely now. In any case, it's certainly made the genetic and evolutionary story more complicated in a sense. But I think in another sense, it may have simplified the story a bit, too. I've been a little puzzled by the shark thing. It's not *just* RAG1/2 that leads to an adaptive immune system: there are a host of other changes -- molecular signals indicating where its safe to rearrange DNA, for example -- that are essential for a functional adaptive response, and it seemed pretty remarkable that they'd all arise together, in a relatively short period. But now it seems likely that many of the changes arose over a much, much longer period, and sharks were just the first to put together a set of unrelated changes to pull an adaptive immune system out of their molecular hats.
You can examine the sea urchin genome yourself at the Sea Urchin Genome Project.