5 ms·

Atrocious that David Reich and Nick Patterson were not recognized, although this is typical of the Nobel committee.

nodding_smiling 4y ago
I hadn't considered that Reich and Patterson might have deserved recognition. I think a case could possibly be made for that, especially if the prize-winning work had been defined more broadly as ancient DNA research in general rather than sequencing archaic hominins and identifying introgression into modern humans more specifically. Reich and Patterson were after all heavily involved in the analysis identifying gene flow from Neanderthals into modern non-Africans. But Reich's and Patterson's (very successful and important) careers have focused on more recent, within-sapiens population history, and I think their role in archaic hominin work was less "irreplaceable" than Paabo's. There are plenty of very important archaic hominin papers from Paabo and collaborators which did not involve Reich and Patterson at all: the earliest Neanderthal mtDNA and autosomal sequences, Denisovan mtDNA (which came out before the autosomal paper), much of the biochemically focused work on gene expression differences between species and so on, Sima de los Huesos... Reich and Patterson also came into the picture quite a bit after Paabo initiated the whole ancient DNA field - I think about 10 years later. So, even though I would have for personal reasons preferred that Reich and Patterson be recognised too, I think Paabo's contributions in the more narrowly defined field of archaic hominin research are very clearly much more comprehensive and vital than theirs.
bhickey 4y ago
My greatest contribution to scientific progress came in 2010 when I was having lunch with Nick. He described an admixture problem to me, summarizing: "I've got observed populations and I want to build a tree where I pick points for unobserved populations such that it minimizes the edge length of the tree. I can't seem to come up with a good algorithm for it." "Nick, that's the Steiner Tree problem! It's NP-complete!" He probably would've wasted a few more days going down that rabbit hole. Edit: Nick has some great Cold War spy games stories that I've only heard him tell in broad strokes.
- qclibre22 4y ago
  Any hope of solving it using quantum computing?
  - jjtheblunt 4y ago
    NP-complete isn't necessarily bad, depending on the size of inputs, right?
    - dekhn 4y ago
      Most problems in this space have reasonable-time approximations that get you close to the right answer for far less computational complexity. Even without ever having looked at Steiner trees before, I guess that there were reasonable approximations, and confirmed that was true without looking too hard. Letting Patterson know about the problem mapping ("your problem is an instance of <X>") is typically enough for a person of his calibre to research approximate solutions good enough for him to run some experiments. (many people say the protein folding problem is NP-complete, but the community generally believes you can predict the folding pathways of all proteins without explicitly running such calculations).
      - bhickey 4y ago
        > typically enough for a person of his calibre to research approximate solutions good enough for him to run some experiments And it's hard to overstate his caliber. For those of you who are unfamiliar with the name, Nick mentored Clifford Cocks at GCHQ and pushed him in the direction of inventing public key cryptography.
  - bhickey 4y ago
    Looks like there's a quantum speedup: https://arxiv.org/abs/1904.03581 https://arxiv.org/abs/1904.03581 IIRC there's no epsilon approximation.
  - dave18 4y ago
    No. Theory offers you a quadratic speed-up of the exponential worst-case running time. And this is the theory. In practice, it looks worse. ....and: exponential worst-case running time is almost never observed in any kind of practical NP-hard optimization problem when using state-of-the-art algorithms on digital computers... and talking about the Steiner tree problem: It is basically solved for all practical matters. Same for the famous travelling salesman problem. Look at this solver: https://www.math.uwaterloo.ca/tsp/concorde.html https://www.math.uwaterloo.ca/tsp/concorde.html Or look at these amazing results: https://www.math.uwaterloo.ca/tsp/star/index.html https://www.math.uwaterloo.ca/tsp/star/index.html
dekhn 4y ago
I thought the latter name sounded familiar and then I realized I met with him at the Broad Insitute and he told an off color joke about getting DNA from mosquito's testicles. Interesting guy who worked on UK crypto before genomics.

I hadn't considered that Reich and Patterson might have deserved recognition. I think a case could possibly be made for that, especially if the prize-winning work had been defined more broadly as ancient DNA research in general rather than sequencing archaic hominins and identifying introgression into modern humans more specifically. Reich and Patterson were after all heavily involved in the analysis identifying gene flow from Neanderthals into modern non-Africans. But Reich's and Patterson's (very successful and important) careers have focused on more recent, within-sapiens population history, and I think their role in archaic hominin work was less "irreplaceable" than Paabo's. There are plenty of very important archaic hominin papers from Paabo and collaborators which did not involve Reich and Patterson at all: the earliest Neanderthal mtDNA and autosomal sequences, Denisovan mtDNA (which came out before the autosomal paper), much of the biochemically focused work on gene expression differences between species and so on, Sima de los Huesos... Reich and Patterson also came into the picture quite a bit after Paabo initiated the whole ancient DNA field - I think about 10 years later. So, even though I would have for personal reasons preferred that Reich and Patterson be recognised too, I think Paabo's contributions in the more narrowly defined field of archaic hominin research are very clearly much more comprehensive and vital than theirs.

bhickey 4y ago

My greatest contribution to scientific progress came in 2010 when I was having lunch with Nick. He described an admixture problem to me, summarizing: "I've got observed populations and I want to build a tree where I pick points for unobserved populations such that it minimizes the edge length of the tree. I can't seem to come up with a good algorithm for it." "Nick, that's the Steiner Tree problem! It's NP-complete!" He probably would've wasted a few more days going down that rabbit hole. Edit: Nick has some great Cold War spy games stories that I've only heard him tell in broad strokes.

qclibre22 4y ago
Any hope of solving it using quantum computing?
- jjtheblunt 4y ago
  NP-complete isn't necessarily bad, depending on the size of inputs, right?
  - dekhn 4y ago
    Most problems in this space have reasonable-time approximations that get you close to the right answer for far less computational complexity. Even without ever having looked at Steiner trees before, I guess that there were reasonable approximations, and confirmed that was true without looking too hard. Letting Patterson know about the problem mapping ("your problem is an instance of <X>") is typically enough for a person of his calibre to research approximate solutions good enough for him to run some experiments. (many people say the protein folding problem is NP-complete, but the community generally believes you can predict the folding pathways of all proteins without explicitly running such calculations).
    - bhickey 4y ago
      > typically enough for a person of his calibre to research approximate solutions good enough for him to run some experiments And it's hard to overstate his caliber. For those of you who are unfamiliar with the name, Nick mentored Clifford Cocks at GCHQ and pushed him in the direction of inventing public key cryptography.
- bhickey 4y ago
  Looks like there's a quantum speedup: https://arxiv.org/abs/1904.03581 https://arxiv.org/abs/1904.03581 IIRC there's no epsilon approximation.
- dave18 4y ago
  No. Theory offers you a quadratic speed-up of the exponential worst-case running time. And this is the theory. In practice, it looks worse. ....and: exponential worst-case running time is almost never observed in any kind of practical NP-hard optimization problem when using state-of-the-art algorithms on digital computers... and talking about the Steiner tree problem: It is basically solved for all practical matters. Same for the famous travelling salesman problem. Look at this solver: https://www.math.uwaterloo.ca/tsp/concorde.html https://www.math.uwaterloo.ca/tsp/concorde.html Or look at these amazing results: https://www.math.uwaterloo.ca/tsp/star/index.html https://www.math.uwaterloo.ca/tsp/star/index.html

dekhn 4y ago

I thought the latter name sounded familiar and then I realized I met with him at the Broad Insitute and he told an off color joke about getting DNA from mosquito's testicles. Interesting guy who worked on UK crypto before genomics.