Regarding your particular point about identifying "neanderthal DNA", consider that most genes are made up of thousands of base pairs. Even though there might be individual variation, it is trivial to distinguish between, say, chimpanzee and human versions of certain genes based on what we know about the populations. We also know the rate of evolution of genes and how they diverge, which means we can be pretty sure that a given version was acquired through interbreeding versus spontaneous mutation.