Explore
For Enterprise
Join for Free
Log In

Arts and Humanities
Business
Computer Science
Data Science
Information Technology
Health
Math and Logic
Personal Development
Physical Science and Engineering
Social Sciences
Language Learning
University of Illinois
Interested in earning a top-ranked MCS in Data Science degree?
Join the 1/8 webinar and learn more about how University of Illinois can help you grow your data science career.
Coursera for Business
World-class training to upskill your team or entire company
Transform your talent with content developed by top universities and companies.
Degrees
Certificates

Explore all of Coursera

Browse
Top Courses
For Enterprise
Log In
Join for Free

Burrows-Wheeler Transform

Loading...

Algorithms on Strings

University of California San Diego

4.5 (657 ratings) | 37K Students Enrolled

Course 4 of 6 in the Data Structures and Algorithms Specialization

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. Do you have technical problems? Write to us: coursera@hse.ru

Skills You'll Learn

Suffix Tree, Suffix Array, Knuth–Morris–Pratt (KMP) Algorithm, Algorithms On Strings

Reviews

4.5 (657 ratings)

5 stars
424 ratings
4 stars
156 ratings
3 stars
52 ratings
2 stars
17 ratings
1 star
8 ratings

AF

Aug 20, 2019

Takes your understanding of string algorithms to the next level and gives you new ideas of handling large amount of memory intensive tasks.

PG

Nov 19, 2017

great course, interesting concepts and very well delivered content from lecture videos. challenging and rewarding programming assignments.

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.

Burrows-Wheeler Transform4:36

Inverting Burrows-Wheeler Transform7:02

Using BWT for Pattern Matching6:29

Taught By

Alexander S. Kulikov
Visiting Professor
Michael Levin
Lecturer
Pavel Pevzner
Professor
Neil Rhodes
Adjunct Faculty

Transcript

The previous lecture ended with a rather difficult algorithmic challenge that we will try to solve using the Burrows-Wheeler Transform and suffix array. Let's start with the Burrows-Wheeler Transform. Allow me to slightly change the focus. Instead of pattern mention, we'll talk about text compression. And run-length encoding is the simplest way to compress text. Where a run of a single symbol is substituted by the number of times the symbol appeared in this run, followed by the symbol itself. You may be wondering why we want to do run-length encoding for genomes because genomes don't have many runs. But they do have many repeats. For example, more than half of human genome is formed by repetitive DNA and the lion's share of many plant genomes is formed also by various types of repeats. But here's an idea. Let's convert test into something else so that our repeats will be converted into runs. We'll start from the genome then we'll turn it into ConvertedGenome and then we will apply run-length encoding to the ConvertedGenome. Because our hope is that ConvertedGenome will have many runs. Let me show how we can accomplish this. So let's consider all cyclic rotations of our favorite string, panamabananas$. We start from this one, and this one, and this one, and continue to form all cyclic rotations of this string. And then after you generated all the cyclic rotations, let's sort them. The dollar sign is viewed as the first letter of alphabet, even before A, so we'll start with $panamabananas. Continue, continue, continue, continue, and finally we'll have a sorted list of all suffixes of the text. You might be wondering why we are doing this, but look at this strange sync. If we look at the last column of the resulting array and the last column of the resulting array is called Burrows-Wheeler transform of the text. That you will notice that also our regional string, panamabananas$ did not have many runs. The Burrows-Wheeler transform of this string actually has many runs. For example here's a run of five A in the Burrows-Wheeler Transform of our original text. How have we achieved it? Let me explain it by using an example from the famous Double Helix Paper by Watson and Crick where they first presented the structure of DNA. And these are just some consecutive strings in Burrows-Wheeler transform of this book. And you see that there are many runs of A in the Burrows-Wheeler transform of this text. Why so many runs of A? Well one of the most common words in English is and. And every time you have and in the text, it is likely to contribute to a run of A in the Burrows-Wheeler transport, as you see in this example. So our goal now is to start from the genome, apply Burrows–Wheeler transform to the genome. And we can now, hopefully, comprise Burrows–Wheeler transform of the genome. And after you apply this compression, we will greatly reduce memory for storing our genome. But it totally makes sense if we can invert this transformation. And from compression version of Burrows-Wheeler transform, we can easily go back to the original Burrows-Wheeler transform. But can we go back from the Burrows-Wheeler transform of the genome, to the genome itself, is it even possible?

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2019 Coursera Inc. All rights reserved.

Get it on Google Play

Coursera
About
Leadership
Careers
Catalog
Certificates
MasterTrack™ Certificates
Degrees
For Enterprise
For Government
For Campus

Community
Learners
Partners
Developers
Beta Testers
Translators

Connect
Blog
Facebook
LinkedIn
Twitter
Instagram
YouTube
Tech Blog

More
Terms
Privacy
Help
Accessibility
Press
Contact
Directory
Affiliates