World and internet is full of textual information. We search for information using textual queries, we read websites, books, e-mails. All those are strings from the point of view of computer science. To make sense of all that information and make search efficient, search engines use many string algorithms. Moreover, the emerging field of personalized medicine uses many search algorithms to find disease-causing mutations in the human genome.
Burrows-Wheeler Transform
Loading...
Skills You'll Learn
Suffix Tree, Suffix Array, Knuth–Morris–Pratt (KMP) Algorithm, Algorithms On Strings
Reviews
NR
Oct 19, 2019
Very well put together course. Challenging but understandable. I highly recommend you stick out. If you get stuck check the forums there's lots of helpful things there. Time well spent!
HC
May 07, 2018
Excelentes algoritmos, nunca había pensado lo complicado que era hacer pattern matching eficientemente en términos de tiempo de procesamiento y memoria.
From the lesson
Burrows-Wheeler Transform and Suffix Arrays
Although EXACT pattern matching with suffix trees is fast, it is not clear how to use suffix trees for APPROXIMATE pattern matching. In 1994, Michael Burrows and David Wheeler invented an ingenious algorithm for text compression that is now known as Burrows-Wheeler Transform. They knew nothing about genomics, and they could not have imagined that 15 years later their algorithm will become the workhorse of biologists searching for genomic mutations. But what text compression has to do with pattern matching??? In this lesson you will learn that the fate of an algorithm is often hard to predict – its applications may appear in a field that has nothing to do with the original plan of its inventors.
Taught By
Alexander S. Kulikov
Visiting Professor
Michael Levin
Lecturer
Pavel Pevzner
Professor
Neil Rhodes
Adjunct Faculty
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
© 2020 Coursera Inc. All rights reserved.
