Burrows-Wheeler Transform

Loading...

From the course by University of California San Diego

Algorithms on Strings

438 ratings

University of California San Diego

Algorithms on Strings

438 ratings

Course 4 of 6 in the Specialization Data Structures and Algorithms

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.

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

Meet the Instructors

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Pavel Pevzner
Professor
Department of Computer Science and Engineering
Neil Rhodes
Adjunct Faculty
Computer Science and Engineering

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.

© 2018 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play