A new analysis of the genomes of the most famous of ancient humans - Neanderthals and Denisovans - has revealed an as-yet-unidentified ancestor for our species – a branch of our distant family tree without any known label to put to it.

The study also finds further evidence of interbreeding between humans and Neanderthals, but places it much earlier than we previously knew - some 200,000 to 300,000 years ago. This interbreeding would therefore add new insight into the increasingly complicated history of our emergence as a species, and of our migration out of Africa.

There is the possibility that the unknown ancestor is actually Homo erectus, an archaic human ancestor thought to have died out more than 100,000 years ago – but as no H. erectus DNA has ever been found, we don't know for sure.

"What I think is exciting about this work is that it demonstrates what you can learn about deep human history by jointly reconstructing the full evolutionary history of a collection of sequences from both modern humans and archaic hominins," says computational biologist Adam Siepel, from the Cold Spring Harbor Laboratory in New York.

As we've seen in other recent studies, the team used a Bayesian algorithm to dig deep into patterns in the genomes – in this case in DNA from two ancient Neanderthals, one ancient Denisovan, and two modern-day African humans. The model can then match the intermingling of DNA with certain periods of time.

What the algorithm looked for was recombination events, where two sets of chromosomes are mixed together, which enabled the scientists to go back a long, long way in the history of the interbreeding of these species – as per the genetic markers left behind. Around 1 percent of Denisovan DNA is of unknown origin, the researchers report.

The algorithm used in the study was a new one, ARGweaver-D, developed by computational biologist Melissa Hubisz from Cornell University. It's an extension of the ARGweaver original, built to analyse these ancestral recombination graphs (or ARGs) in ways that aren't possible with standard statistical number crunching.

"This new algorithm that Melissa has developed, ARGweaver-D, is able to reach back further in time than any other computational method I've seen," says Siepel. "It seems to be especially powerful for detecting ancient introgression."

Some 15 percent of these mysterious "super archaic" regions of DNA found in the Denisovan genome are still in circulation in humans today, according to the study. What eventually happened to this missing species remains to be seen.

Another finding from the research was that between 3 and 7 percent of Neanderthal DNA is influenced by ancient H. sapiens, emphasising the amount of interbreeding that was happening across the centuries, way before the major mass migration of modern human ancestors out of Africa some 50,000 years ago.

"This timeline appears to be inconsistent with a genetic exchange involving the direct ancestors of most present-day Eurasians, who migrated out of Africa ~50,000 years ago. Instead, our timeline suggests an earlier migration, occurring at least 200,000 years ago," the team writes.

"Notably, orthogonal lines of evidence now support the possibility of one or more such early migrations out of Africa."

It's a fascinating look at how we can learn more about the events of the past just by applying better algorithms to DNA records. It's likely that there are plenty more discoveries to come about the sex lives - and therefore the genetic history - of our ancestors.

"Altogether, given the number of gene flow events now documented among ancient hominins, it may be reasonable to assume that genetic exchange was likely whenever two groups overlapped in time and space," the researchers conclude in their paper.

The research has been published in PLOS Genetics.