Reconstructing an Optimal Alignment

Loading...

來自 University of California San Diego 的課程

Algorithmic Toolbox

3507 個評分

University of California San Diego

Algorithmic Toolbox

3507 個評分

課程 1（共 6 門，Specialization 数据结构与算法）

The course covers basic algorithmic techniques and ideas for computational problems arising frequently in practical applications: sorting and searching, divide and conquer, greedy algorithms, dynamic programming. We will learn a lot of theory: how to sort data and how it helps for searching; how to break a large problem into pieces and solve them recursively; when it makes sense to proceed greedily; how dynamic programming is used in genomic studies. You will practice solving computational problems, designing new algorithms, and implementing solutions efficiently (so that they run in less than a second).

從本節課中

Dynamic Programming 1

In this final module of the course you will learn about the powerful algorithmic technique for solving many optimization problems called Dynamic Programming. It turned out that dynamic programming can solve many problems that evade all attempts to solve them using greedy or divide-and-conquer strategy. There are countless applications of dynamic programming in practice: from maximizing the advertisement revenue of a TV station, to search for similar Internet pages, to gene finding (the problem where biologists need to find the minimum number of mutations to transform one gene into another). You will learn how the same idea helps to automatically make spelling corrections and to show the differences between two versions of the same text.

The Alignment Game8:39

Computing Edit Distance6:37

Reconstructing an Optimal Alignment4:55

與講師見面

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Neil Rhodes
Adjunct Faculty
Computer Science and Engineering
Pavel Pevzner
Professor
Department of Computer Science and Engineering
Daniel M Kane
Assistant Professor
Department of Computer Science and Engineering / Department of Mathematics

We now know how to compute the edit distance or to compute the optimal

alignment by filling in the entries in the dynamic programming matrix.

But it doesn't tell us yet how to construct the alignment

two rows with the first row representing the first sequence and

the second row representing the second sequence.

Here's an idea.

Let's use the backtracking pointers that we constructed while filling in

the dynamic programming matrix to reconstruct optimal alignment between strings.

We can start by noting that any path from (0, 0)

to (i, j) in the dynamic programming matrix

spell an alignment of an i prefix of A with a j prefix of B.

For example let's start the line in the sequences, which means let's start

traveling from the point 0, 0 to the point n, m in our dynamic programming matrix.

As soon as we move along diagonal left it will correspond to either mismatch or

match, then we'll continue using horizontal or

vertical edges and it will correspond to insertions or deletions.

Then we will use once again diagonal edge.

In this case it is a match, and you'll continue

by constructing the n-alignment of two strings.

Please note that the constructed path corresponds to distance A and is not

an optimal alignment because we know that an optimal alignment distance is 5.

To construct an optimal alignment we will use the backtracking pointers by starting

from the last vertex in this matrix

particularly from this vertex where the added distance is recorded as 5.

Using backtracking pointers we see that

there are two possible ways to arrive to this last vertex.

Let's arbitrarily choose one of them.

One of them corresponds to a mismatch and another corresponds to insertion.

So let's arbitrarily choose a mismatch edge that will correspond to

mismatch between j and i, then from the previous point there is only

one way to move into this point and it will correspond to an indel

that will continue further, match, further, further, further,

further, and we will finally arrive to the initial point at

the same time constructing the optimal alignment between two strings.

The output alignment pseudoode implement's this idea.

We simply look at the backtracking pointers that enters in the node (i, j).

If they arrive to node (i, j) by using a vertical edge

that we will simply output one column of the alignment with

a of i in the first row.

If on the other hand it corresponds to horizontal edge we output

column with b of j in the second row, and

if it corresponds to a diagonal edge we output a column

of alignment with a of i in the first row and v of j in the second row.

It appears that we actually need to store all backtracking pointers

to output alignment, but this slightly modified

pseudocode tells you that you can compute backtracking pointers by analyzing

entries in the dynamic programming matrix and thus saving a little space.

Edit distance is just one

many applications of string comparisons in various disciplines that range

from analyzing internet pages to finding similar genes.

We started this lecture from the example of gene hunt for

cystic fibrosis: one of the first successes of the human genome project.

If you want to learn more about comparing genes, protein, and

genomes you may enroll in the Coursera specialization called Bioinformatics or

you can read the book Bioinformatics Algorithms: the Active Learning Approach.

探索我們的目錄

免費加入並獲得個性化推薦、更新和優惠。

Coursera 致力於普及全世界最好的教育，它與全球一流大學和機構合作提供在線課程。

© 2018 Coursera Inc. 保留所有權利。

通過 App Store 下載

通過 Google Play 獲取