Explore
For Enterprise
Join for Free
Log In

艺术与人文
商务
计算机科学
数据科学
信息技术
健康
数学和逻辑
个人发展
物理科学与工程
社会科学
语言学习
學位和證書

瀏覽 Coursera 的全部課程

瀏覽
搜索
企業版
登錄
免費加入

Reconstructing an Optimal Alignment

Loading...

Algorithmic Toolbox

加州大学圣地亚哥分校

4.7（4,615 個評分） | 150K 名學生已註冊

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

查看授課大綱

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, Debugging, Software Testing, Algorithms, Computer Programming

審閱

4.7（4,615 個評分）

5 stars
3,442 ratings
4 stars
934 ratings
3 stars
165 ratings
2 stars
34 ratings
1 star
40 ratings

PR

Feb 10, 2019

The course is perfectly designed. The perfect start for those who start with data structures and algorithms. The Dynamic programming was a little bit tough but overall course is perfectly designed

RS

Dec 23, 2018

This course is just awesome and outstanding in every term. Teachers are very good at explaining even the toughest of problems and really helped throughout the course, i enjoyed and leaned a lot.

從本節課中

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
Michael Levin
Lecturer
Neil Rhodes
Adjunct Faculty
Pavel Pevzner
Professor
Daniel M Kane
Assistant Professor

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 致力於普及全世界最好的教育，它與全球一流大學和機構合作提供在線課程。

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

通過 App Store 下載

通過 Google Play 獲取

Coursera
關於
管理團隊
工作機會
目錄
證書
MasterTrack™ 證書
學位
企業版
政府版

社區
Learners
Partners
Developers
Beta Testers
Translators

連接
博客
Facebook
領英
Twitter
Instagram
YouTube
技術博客

更多
條款
隱私
幫助
內容訪問
媒體
聯繫我們
目錄
附屬公司