动态规画技巧简介DynamicProgramming.ppt
《动态规画技巧简介DynamicProgramming.ppt》由会员分享,可在线阅读,更多相关《动态规画技巧简介DynamicProgramming.ppt(52页珍藏版)》请在三一文库上搜索。
1、動態規畫技巧簡介 (Dynamic Programming),趙坤茂 陽明大學生命科學系 Email: kmchaoym.edu.tw WWW: http:/www.ym.edu.tw/kmchao,聰明的教授,有四個人一起搭一班往花蓮的飛機, 分別是總理,教授,神父和一個小學生, 加上駕駛共五人, 很不巧的, 在飛到機場上空時飛機竟然故障要墜毀了, 但機上卻只有四套降落傘. 首先飛行員很沒道義的搶了一具就跳了下去, 接著總理說, 我是最有權力的人所以我不能死,也抱了一具跳下去, 然後教授說,我是最聰明的人,必須留著我的有用之軀,因此也搶了一套降落傘就跳, 這時只剩一套降落傘啦怎麼辦呢? 神父
2、便對小學生說:我離天堂比較近,你就逃生去吧,不用管我了! 小學生說: 不用呀,我們還有兩套降落傘喔!,聰明的教授(續),因為剛才那個最聰明的人, 背著我的書包跳下去了.,The Heaviest Non-decreasing Subsequence Problem,Let S be a sequence of integers. A heaviest non-decreasing subsequence of S is a non-decreasing subsequence with the maximum sum. (這是2000年全國大專軟體設計競賽大學甲組的試題),動態規畫技巧與序列分
3、析,費氏數(Fibonacci number) 最長共同子序列 兩個序列的分析 多重序列分析,費氏數(Fibonacci number),費氏數(Fibonacci number),How to compute,請問F10是多少?,列表式計算,如果我們從F0、F1、往F10邁進,很快我們就可以算出F10,好漢做事好漢當,上代數的時候,小明同學在後面z.z.z。 後來,老師發現了,就生氣地說: 旁邊的同學,把睡覺的叫起來! 語畢, 不知道是哪個活得不耐煩的同學答道: 是你自己把他弄睡著的,你自己去把他叫醒,最長共同子序列,動態規畫(dynamic programming),基本上,動態規畫技巧有
4、三個主要部份: 遞迴關係(recurrence relation) 列表式運算(tabular computation) 路徑迴溯(traceback),最長共同子序列(LCS, Longest Common Subsequence)問題,首先我們先解釋什麼是子序列(subsequence) ,所謂子序列就是將一個序列中的一些(可能是零個)字元去掉所得到的序列,例如:pred、sdn、predent等都是 ”president” 的子序列。 給定兩序列,最長共同子序列(LCS)問題是決定一個子序列,使得 (1) 該子序列是這兩序列的子序列;(2) 它的長度是最長的。,LCS,例如: 序列一:p
5、resident 序列二:providence 它的一個LCS為,LCS,例如: 序列一:president 序列二:providence 它的一個LCS為 priden ( PResIDENt PRovIDENce ),LCS,又例如: 序列一:algorithm 序列二:alignment 它的一個LCS為,LCS,又例如: 序列一:algorithm 序列二:alignment 它的一個LCS為 algm or algt ( ALGorithM ALiGnMent ),How to compute LCS?,給定兩序列及,令len(i, j)表示與的LCS之長度,則下列遞迴關係可用來計算
6、len(i, j):,極樂世界,老師: 小明,你的毛病就是用詞不當,現在考考你 。用一句成語來形容老師很開心,而且成語中要包含數字。 小明: ,極樂世界,老師: 小明,你的毛病就是用詞不當,現在考考你 。用一句成語來形容老師很開心,而且成語中要包含數字。 小明:含笑九泉,兩個序列的分析,兩個序列的分析,在1970年代,分子生物學家Needleman 及Wunsch 15以動態程式設計技巧(dynamic programming)分析了氨基酸序列的相似程度; 有趣的是,在同一時期,計算機科學家Wagner及Fisher 22也以極相似的方式來計算兩序列間的編輯距離(edit distance),
7、而這兩個重要創作當初是在互不知情下獨立完成的。 雖然分子生物學家看的是兩序列的相似程度,而計算機科學家看的是兩序列的差異,但這兩個問題已被證明是對偶問題(dual problem),它們的值是可藉由公式相互轉換的。,三種常用的序列分析方法,目前序列分析工具可說是五花八門 ,僅管如此,有三種構想是較受大家所青睬的: 第一種是Smith-Waterman的方法,這種方法很精細地計算兩序列間最好的k 個區域排比(local alignment),雖然這個方法很精確,但因耗時較久,所以多半應用在較短序列間的比較,然而,也有一些學者試著去改善它的一些計算複雜度,使它在長序列的比較上也有一些實際的應用。,
8、三種常用的序列分析方法(續),第二種是Pearson的FASTA方法,這種方法先以較快方式找到一些有趣的區域,然後再以Smith-Waterman的方法應用在那些區域中。如此一來,它的計算速度就比Smith-Waterman快,而且在很多情況下,它的精細程度也不差。 第三種是Altschul等人所製作的BLAST ,它的最初版本完全沒有考慮間隔(gap),所以在計算上比其他方式快了許多。雖然它不夠經細,但它的計算速度使得它在生物序列資料庫的搜尋上有很大的優勢,也因此它可說是目前最受歡迎的序列分析工具。此外,1997年剛出爐的Gapped BLAST已針對精細程度做了很大的改進,且在計算速度上仍
9、維持相當的優勢。,為什麼要用排比(alignment)?,早期的序列分析通常是以點矩陣(dot matrix)方法來進行的,這種方法是以二維平面將兩序列間相同的地方點出來,從而藉由目視的方式看看兩序列有那些相似的地方。這種方法最大的優點是一目了然且計算簡單; 然而,當序列較長的時候,藉由目視方法去分析它們是一種很沒有效率的方式 況且有些生物序列(如蛋白質序列)並不是只有相同字符才相似,這時候點矩陣方法就無法看出整體的相似程度。 於是有人建議以排比(alignment)來顯示兩序列的相似程度,排比(alignment),給定兩序列,它們的整體排比(global alignment)是在兩序列內加
10、入破折號(dash),使得兩序列變得等長且相對的位置不會同時都是破折號。 例如:假設兩序列為及,下圖列出了它們的一種排比。 圖: 及的一種可能排比。,排比的評分方式,有那麼多種不同的排比組合,到底要挑那一個排比呢?為了要挑出較理想的排比,通常我們需要一些評分方式來做篩選工作。 最簡單的評分方式是將每一個配對基底(aligned pair)都給一個分數,再看看那一種排比的總分最高。令w(a,b)代表a與b配對所得到的分數(通常w(*,-)及w(-,*)是負值;mismatch也是負值;只有match是正值,而蛋白質序列分析則採用PAM矩陣或BLOSUM矩陣來決定這些值) 在上述的簡單評分原則下,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 动态 技巧 简介 DynamicProgramming
链接地址:https://www.31doc.com/p-2572498.html