There has been an interesting story in Science Express earlier this month about being able to get sequence from a cave bear fossil (Nature subscription link; SciAm free link is here despite massive contamination with more recent DNAs. Cave bear fossils (and hobbit, and Neanderthal, by the way) are commonly found in cave floors, at more-or-less cave temperature, which is pretty rough on ancient DNA. Worse, the really interesting cavebeds have mixtures of different fossils overlaid by whatever microbes and more modern DNA contaminations happened by. To date, methods of recovering ancient DNA have relied on PCR amplification, which unfortunately prefers to amplify modern contaminating DNA. Thus recoveries have been limited to a few favorable instances, and usually targeted mitochondrial DNA.
In this work, they got around these twin problems by basically sequencing everything without PCR amplification, and then sorting out what came from bear by computational comparison with the recently completed dog genome (they still needed to be very stringent about excluding modern dog DNA from the analysis lab, still a much easier job than keeping microbes out. Some matching stretches were 90% identical to dog genomic entries.) They were able to use some computational tricks to identify additional, divergent stretches as very likely coming from bear. In all, they think that about 6% of their sequence is the genuine article.
Although Nature and SciAm are hyping the computer tools used, I think the real hero here is the improvement in cloning, the step in which foreign DNA fragments are molecularly joined to other stretches for preservation by bacteria. That they recovered 1000 little pieces to sequence from a single tooth just blows me away. They think they could get 10x coverage of the cave bear genome if the sequenced everything from this one tooth! It also doesn't hurt that sequencing is dirt-cheap these days either.
The point for these workers is the proof-in-principle that Neanderthal remains could be sequenced. There remains the problem of keeping modern human DNA out of the mix.