The 40-Year-Old Algorithm
Talk about job security. . . after 40 years, mathematicians have concluded that they cannot improve on the industry-standard algorithm used to compute the “edit distance” in analyzing long sets of digits or data.
Decades of testing and analysis showed this to be a math problem with no solution, according to MIT researchers.
The algorithm is used to compare two sequences with many common digits to identify differences – and for decades it has been the best available tool for the job. And the conclusion that no better option can be produced has implications for Big Data and computational analytics. At Seven Bridges Genomics, algorithms are the building blocks for understanding cancer genomics and biostatistics.
The Wagner-Fischer Algorithm is used to effectively compute the quadratic of substituting one data point for another in comparing long strings. Turning ABC into CBA requires two changes, for instance, and always will. Imagine the challenge of analyzing 30 billion genetic pairs and knowing that you have no better method than Wagner-Fischer — from the era when pocket calculators were exotic.
This is as good as it gets, according to two MIT scientists and despite tremendous advances in computational power, the physical transfer of “reads” requires the same amount of effort it did when Jimmy Carter was US president, the laser printer was introduced by IBM and Brotherhood of Man won the Eurovision song contest.
For non-polymaths and fledgling bioinformaticians, this Boston Globe article, from Kevin Hartnett, nicely explains the importance of this algorithm in today’s genomics and Big Data world. It also details just how long and how thoroughly mathematicians have been searching for a potential successor.
What items from your workplace are still “best-in breed” after a generation?
In my case, a stapler and pencil are the only tool that remain largely unchanged since the early days of supersonic flight on the Concorde. The desk chair is more comfortable, the copy paper is now recycled. Even the coffee has been upgraded thanks to overnight shipping of beans on jets and remote-control coffee-making technology.
