What ancient hominins did they admix with and acquire these genes from?
A new paper that Maju has called attention to as his anthropology oriented blog makes the case for what I have long believed to be the most plausible scenario, that "Denisovian admixture" really represents admixture with Asian Homo Erectus individuals, encountered by the first significant wave of modern humans to reach Asia via a coastal route, who promptly went extinct as a separate species (as opposed to a minor contributor to the resulting population's genetic diversity) following this contact with modern humans and before the next wave of modern humans arrived. Hence, the Denisovians (whose remains date to something on the order of forty thousand years or more after the last traces of archaic hominins in archaeology or from genetic traces anywhere else in the historic Asian Homo Erectus range), to the extent that they have the genes found in modern Melanesians and Australian aborigines, were either a relict Asian Homo Erectus population, or a population that was admixed with Asian Homo Erectus individuals.
Here are some excerpts from the paper linked at his post:
Findings include some evidence of a male biased gene flow from the Denisova lineage to Papuan ancestors and possibly even more archaic gene flow. It is unclear if there is evidence for more than one Neanderthal interbreeding . . . . Papuan could have a unique split with the Denisovan (as Reich et al. 2010 suggest the Papuan lineage received ~5% of its genes from that lineage). As we will see later, the apparent reason for this would seem to be that the distance from Denisova to Chimp is more strongly underestimated than that from Denisova to Papuan. The underestimation of the Denisova to Chimp distance could be due to Denisova harboring some very archaic alleles. . . The decrease in frequency of the DP pattern on X, particularly when compared to the NP pattern (which is near autosomal average frequency on X) suggests the possibility of asymmetric gene flow in this introgression event. If so, it would seem that this might be most readily explained by greater survival and reproduction of the offspring of Denisova males impregnating the modern human female ancestors of Papuans rather than the other way around.... Note the high frequency of the DNP pattern, which may be due to the Denisovan relatives that mixed not being closely related to the Denisovan sampled. . . . a hierarchical structured coalescent model with at least two introgression events between archaic humans and out of Africa Moderns leads to a substantial increase in fit. Overall fit however, is still far far worse than could be expected. It seems that to improve the fit a number of factors may come into play. Firstly, there are too many private NH, NF and NP [Neanderthal-Han, -French and -Papuan] patterns. Secondly, the latter of these, NP, seems markedly less than the former two. . . . One model that may do a better job of describing the data with fewer parameters is independent mixing of Neanderthal genes with Han and French, but to a nearly identical total degree. Also, lesser mixing of Neanderthal genes into Papuan, made up for by a larger proportion of archaic alleles in Papuans coming from the mixing with an archaic that is only slightly closer to Denisova than to Neanderthal. This would in turn suggest that the mixing with Neanderthals was not purely right out of Africa and it was not a single event. Instead, there may have been opportunity for European ancestors to pick up Neanderthal alleles, in the unknown part of Eurasia they existed in prior to moving into Europe, ditto and independently for the ancestors of the East Asians, while Papuan ancestors moved fairly rapidly through the zone of classical Neanderthals and picked up most of their archaic genes in the Indonesian region. The form of this ancestral population may have been about equally related to Neanderthals and Denisovans, but may also have had an appreciable proportion of even earlier (e.g., Homo erectus genes) in its genome.
Maju questions the independent but identical Neanderthal admixture scenario for East Eurasians and West Eurasians based on the absence of Neanderthals in East Asia. However, the Neanderthal admixtures could take place anywhere between the Levant and South Asia and Europe (the Neanderthal range, more or less) so long as it took after the proto-West Eurasian and proto-East Eurasian populations had split and begun their migrations.
I'd started to think something along the same lines after looking at data from John Hawks at his blog on the distribution of private v. shared Neanderthal allelles in West Eurasian v. East Eurasian populations, which is very had to obtain if the admixture happens and reaches anything approaching fixation before the two branches of Eurasians split into separate populations as the migrate out of Southwest Asia and into the rest of Eurasia. There are good reasons to think that very similar population dynamics would produce very similar overall admixture percentages for out of Africa modern humans in this scenario, but this would explain the differences in the particular archaic genes found in each population which don't overlap as much as they should for other scenarios to be more likely.
Of couse, from a genetic perpsective, a highly structured population in which different clans admix with different Neanderthals in the same geographic area is effectively a split of the populations in place, even though it could happen pre-migration.
The male to female dominance in the source of archaic admixture that this paper describes based on technical ancient DNA in X chromosomes is also something that I have advocated strong for on other grounds (the lack of Neanderthal mtDNA and Y-DNA lineages in modern humans) in prior posts.