Here's a link to a much better story that indicates that the Denisovans are cousins to neanderthals, though frustratingly, none that I can find give figures for the % difference between the two genomes.
http://www.physorg.co...ne-yields-genome.html
The reason why relationships are made between any two living things and why we're so sure there is a common ancestor is down to nested hierarchies; related organisms share similar characteristics and the number of shared traits increases with relatedness.
The nested heirarchy was developed by Linnaeus, who was actually a creationist (creationists hate this being mentioned. Linneaus was also the person who classified man along with the apes, hence the designation 'primate' for apes, as he - wrongly - thought man was the apex of God's creation (humans are no more evolved or privilleged than say a bacterium), and was based on morphological features; i.e. all creatures with wings are more closely related than those without. It was (broadly) successful as a means of classification, but with the advent of genetics, we find the same genetic patterns be observed in more closely related species.
This even relates to things such as Endogenous Retroviruses, which is genetic code inserted by viruses, but which has become part of our genome. It can conclusively be shown that ERVs can be detected in the same part of the genome of closely related species.
The best thing is that ERVs are randomly inserted into the genome by the virus. The chances of a virus just happening to insert itself in an indentical position in two different species are spectacularly low, and we have many more than one of these randomly inserted bits of code in our genome, yet all of them confirm the same nested heirarchy. This is one