The simple problem holding back scientific progress — and your dinner parties

The 40-year-old Wagner-Fischer algorithm that's used to compare genetic sequences is actually the best, and scientists can't make it any better, say MIT researchers. Phys.org's Larry Hardesty writes:

In a sense, that's disappointing, since a computer running the existing algorithm would take 1,000 years to exhaustively compare two human genomes. But it also means that computer scientists can stop agonizing about whether they can do better.

You can't be all things to all people, either as a dinner party host or as a genetic sequencer, as Hardesty explains:

...say you're throwing a dinner party, and you're trying to decide whom to invite. You may face a number of constraints: Either Alice or Bob will have to stay home with the kids, so they can't both come; if you invite Cindy and Dave, you'll have to invite the rest of the book club, or they'll know they were excluded; Ellen will bring either her husband, Fred, or her lover, George, but not both; and so on.

Is there an invitation list that meets all those constraints?

Computer scientists can't satisfy every dinner party demand, but they can assure you that you're probably doing the best job you can.

Explanatory journalism is a public good

At Vox, we believe that everyone deserves access to information that helps them understand and shape the world they live in. That's why we keep our work free. Support our mission and help keep Vox free for all by making a financial contribution to Vox today.

One-Time Monthly Annual

$95/year

$120/year

$250/year

$350/year

Other

$

Yes, I'll give $120/year

Yes, I'll give $120/year

We accept credit card, Apple Pay, and Google Pay. You can also contribute via