clock menu more-arrow no yes mobile

Filed under:

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.'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.