lec4-貪婪法-基因組重排Rearrangements

Outline

甘藍(lán)大白菜與蕪菁基因組重排反序排序煎餅翻轉(zhuǎn)問題反序排序的貪婪算法近似算法斷點(diǎn):另一種貪婪法則斷點(diǎn)圖第1頁/共68頁蕪菁vs甘藍(lán):形態(tài)味道大不同第2頁/共68頁蕪菁與甘藍(lán):

基因序列比較未發(fā)現(xiàn)演化信息第3頁/共68頁蕪菁與甘藍(lán):近乎一致的mtDNA基因序列1980年代JeffreyPalmer研究蕪菁與甘藍(lán)的演化關(guān)系基因之間的相似度高于99%基因順序卻很不一樣這一研究開創(chuàng)了分子演化中基因組重排的新領(lǐng)域第4頁/共68頁蕪菁與甘藍(lán):不同的mtDNA順序基因順序比較:第5頁/共68頁蕪菁與甘藍(lán):不同的mtDNA基因順序基因順序比較:第6頁/共68頁蕪菁與甘藍(lán):不同的mtDNA基因順序基因順序比較:第7頁/共68頁蕪菁與甘藍(lán):不同的mtDNA基因順序基因順序比較:第8頁/共68頁蕪菁與甘藍(lán):不同的mtDNA基因順序基因順序比較:BeforeAfter演化以基因順序不同的形式展現(xiàn)出來第9頁/共68頁甘藍(lán)轉(zhuǎn)換成

蕪菁第10頁/共68頁祖先的基因組順序是怎樣的?基因組順序的演化過程是怎樣的?~7500萬年前的哺乳動物祖先Mouse(Xchrom.)Human(Xchrom.)基因組重排第11頁/共68頁X染色體的演化RatConsortium,Nature,2004第12頁/共68頁反序

帶方向的塊代表保守的基因132410568971,2,3,4,5,6,7,8,9,10第13頁/共68頁反序132410568971,2,3,-8,-7,-6,-5,-4,9,10帶方向的塊代表保守的基因.演化中的某個時刻,塊1,…,10被誤讀為1,2,3,-8,-7,-6,-5,-4,9,10.第14頁/共68頁反序和斷點(diǎn)132410568971,2,3,-8,-7,-6,-5,-4,9,10反演reversion引入了兩個斷點(diǎn)breakpoints

(順序上發(fā)生了分裂).第15頁/共68頁另外幾種基因組重排反序/Reversal12345612-5-4-36Translocation1234

561264

53123456123456FusionFission第16頁/共68頁比較基因組結(jié)構(gòu):MousevsHuman人與小鼠基因組很相似,但是基因組順序相差很大~245個重排反序FusionsFissionsTranslocation第17頁/共68頁Waardenburg’s綜合征:

借小鼠之力研究人類基因組錯序癥狀：色素異常/失聰鎖定致病因子在2號染色體上但確切位置未知！第18頁/共68頁Waardenburg’s綜合征與斑點(diǎn)病小鼠斑點(diǎn)病小鼠的癥狀與Waardenburg癥狀相似科學(xué)家成功定位了小鼠斑點(diǎn)病的致病基因這為人類致病因子的尋找提供了線索第19頁/共68頁人類與小鼠基因組結(jié)構(gòu)的比較為成功定位人類基因組上的致病因子我們需要分析人類和小鼠的基因組相對結(jié)構(gòu)關(guān)系第20頁/共68頁反序:Example

p=12345678

r(3,5)

12543678

第21頁/共68頁反序:Example

p=12345678

r(3,5)

12543678r(5,6)12546378第22頁/共68頁反序與基因順序排列p表示基因順序:

p=p

1

------p

i-1p

ip

i+1------

p

j-1p

jp

j+1-----

p

n

p

1

------p

i-1

p

jp

j-1------

p

i+1p

i

p

j+1-----

pn反序操作

r(i,j)反轉(zhuǎn)了p中從

i

到

j

的片段r(i,j)第23頁/共68頁反序距離問題Goal:給定兩個排列,找到一個最短的反序操作序列

使它們能將一個排列變換為另一個排列Input:排列

p

andsOutput:將排列p

變換為

s的一系列反序操作序列r1,…rt,

并且

t

最小t-反序距離d(p,s)–表示p

和s之間的反序距離第24頁/共68頁反序排序問題Goal:給定一個排列,找到能將此排列變成恒等排列(12…n)的最短的反序序列。

Input:排列pOutput:將排列p變換為恒等排列的一系列反序操作

r1,

…rt

并使得t是最小的。

第25頁/共68頁反序排序:Examplet=d(p)–p的反序距離Example:

p

=3421567109843215671098

4321567891012345678910

因此d(p)=3第26頁/共68頁反序排序:5步第27頁/共68頁反序排序:4步第28頁/共68頁反序排序:4步該排列的反序距離是多少?能不能在3步內(nèi)排好序?第29頁/共68頁煎餅反轉(zhuǎn)問題大廚很草率，煎餅亂序顧客喜歡吃從上到下從小到大排好的煎餅服務(wù)員負(fù)責(zé)重新排序只有兩把鏟子可幫助翻轉(zhuǎn)ChristosPapadimitrouandBillGatesflippancakes第30頁/共68頁反轉(zhuǎn)排序:貪婪算法對p=123645,進(jìn)行排序前3個元素已經(jīng)有序定義prefix(p)為p中已經(jīng)排好序的元素的數(shù)目

prefix(p)=3貪婪法則:每一步都增加prefix(p)How？第31頁/共68頁

p

的排序過程

123

645

1234

65

123456長度為n的排列，最多需要(n–1)步貪婪算法:示例第32頁/共68頁貪婪算法:偽代碼SimpleReversalSort(p)1for

i

1ton–12j

元素i

在

p中的位置

(即,pj=i)3if

j≠i4p

p*r(i,j)5output

p6if

p

為恒等排列

7return第33頁/共68頁分析SimpleReversalSort算法SimpleReversalSort不能保證找到最小距離

p=612345用了5步：Step1:162345Step2:126345Step3:123645Step4:123465Step5:123456第34頁/共68頁其實(shí)只需要兩步: p=612345

Step1:543216Step2:123456因此,SimpleReversalSort(p)不是最優(yōu)算法對于很多問題而言，最優(yōu)算法未知;常常使用近似算法分析SimpleReversalSort(續(xù))第35頁/共68頁ApproximationAlgorithmsThesealgorithmsfindapproximatesolutionsratherthanoptimalsolutionsTheapproximationratioofanalgorithmAoninputpis:A(p)/OPT(p)whereA(p)-solutionproducedbyalgorithmAOPT(p)-optimalsolutionoftheproblem第36頁/共68頁ApproximationRatio/PerformanceGuaranteeApproximationratio(performanceguarantee)ofalgorithmA:maxapproximationratioofallinputsofsizenForalgorithmAthatminimizesobjectivefunction(minimizationalgorithm):max|p|=nA(p)/OPT(p)第37頁/共68頁ApproximationRatio/PerformanceGuaranteeApproximationratio(performanceguarantee)ofalgorithmA:maxapproximationratioofallinputsofsizen（意即最壞情況）ForalgorithmAthatminimizesobjectivefunction(minimizationalgorithm):max|p|=nA(p)/OPT(p)Formaximizationalgorithm:min|p|=nA(p)/OPT(p)第38頁/共68頁

p=p1p2p3…pn-1pn

如果pi+1=pi

+1則元素對（p

i

，

p

i+1

）稱為

鄰接例如:

p

=193478265(3,4)，(7,8)和(6,5)都是鄰接對鄰接

與斷點(diǎn)第39頁/共68頁任意兩個非鄰接/連續(xù)元素之間存在一個斷點(diǎn):

p=193478265元素對(1,9),(9,3),(4,7),(8,2),(2,5)形成排列

p的斷點(diǎn)

b(p)–排列p的斷點(diǎn)數(shù)量

斷點(diǎn)第40頁/共68頁Adjacency&Breakpoints鄰接–連續(xù)的元素對斷點(diǎn)–不連續(xù)的元素對π=562134 05621347鄰接斷點(diǎn)π需要擴(kuò)展π0=0和π7=7第41頁/共68頁

在p的兩端添加p

0

=0

和

p

n+1=n+1

例:

添加0

和

10Note:擴(kuò)展之后會增加斷點(diǎn)數(shù)擴(kuò)展排列p=193478265p=0

193478265

10第42頁/共68頁每次反序操作最多消除2個斷點(diǎn)p=231465 0

231465

7

b(p)=5 0

132

4657

b(p)=4 0123465

7

b(p)=2 01234567 b(p)=0反序距離和斷點(diǎn)第43頁/共68頁每次反序操作最多消除2個斷點(diǎn)可得:

反序距離≥斷點(diǎn)數(shù)/2p=231465 0

231465

7

b(p)=5 0

132

4657

b(p)=4 0123465

7

b(p)=2 01234567 b(p)=0反序距離和斷點(diǎn)第44頁/共68頁反序排序:改進(jìn)的貪婪算法BreakPointReversalSort(p)1

while

b(p)>02

所有反序中,選擇反序

r，使得b(p

?

r)最小化3

p

p?r(i,j)4

output

p5

return第45頁/共68頁SortingByReversals:ABetterGreedyAlgorithmBreakPointReversalSort(p)1

while

b(p)>02所有反序中,選擇反序

r，使得b(p

?

r)最小化3

p

p?r(i,j)4

output

p5

return如何才能確信在除去一些斷點(diǎn)的同時不會引入其他的斷點(diǎn)從而導(dǎo)致一個死循環(huán)？Problem:thisalgorithmmayworkforever第46頁/共68頁帶StripStrip(帶):兩個相鄰斷點(diǎn)之間的子排列

減帶(Decreasingstrip):帶中元素遞減(如.65以及321).增帶(Increasingstrip):帶中元素遞增(如.789)

0

19437825610

單元素帶可以是增帶也可以是減帶。除了0和n+1外，我們將所有單元素稱為減帶第47頁/共68頁減少斷點(diǎn)數(shù)理論11:

如果p

含有至少一個減帶,那么必存在一個反序操作

r

可以減少斷點(diǎn)數(shù)(即.b(p?

r)<b(p))第48頁/共68頁需要考慮的：對

p=146578320

146578329 b(p)=5選擇減帶中的最小元素k(本例k=2)第49頁/共68頁需要考慮的(續(xù))對p=146578320

14657832

9 b(p)=5選擇減帶中的最小元素k(本例k=2)第50頁/共68頁需要考慮的(續(xù))對p=146578320

14657832

9 b(p)=5選擇減帶中的最小元素k(本例k=2)找到排列p中的元素k-1第51頁/共68頁需要考慮的(續(xù))對p=146578320

14657832

9 b(p)=5選擇減帶中的最小元素k(本例k=2)找到排列p中的元素k-1反轉(zhuǎn)k

和

k-1之間的片段（包括k但無k-1）:0

14657832

9

b(p)=50

1

2387564

9

b(p)=4第52頁/共68頁再次減少斷點(diǎn)

如果沒有減帶,則可能找不到任何能減少斷點(diǎn)數(shù)的反序操作r(即對任何反序操作

r

都有b(p?

r)≥b(p)).怎么辦？反轉(zhuǎn)一個增帶，則可以獲得一個減帶下一步就肯定可以減少斷點(diǎn)數(shù)(基于理論1).第53頁/共68頁需要考慮的(續(xù))排列p中已無減帶:

p=0

12567348b(p)=3p

?

r(6,7)=0

12567438b(p)=3

r(6,7)無法改變斷點(diǎn)數(shù)r(6,7)創(chuàng)建了一個減帶，保證下一步一定能減少斷點(diǎn)數(shù).第54頁/共68頁ImprovedBreakpointReversalSortImprovedBreakpointReversalSort(p)1while

b(p)>02if

p

中存在減帶在所有反序中,選擇反序r使得b(p

?

r)最小化4else5選擇一個反序r,

翻轉(zhuǎn)p中的一個增帶6p

p

?

r7output

p8return第55頁/共68頁ImprovedBreakPointReversalSort

近似度為4的近似算法

至少每兩步可以消除1個斷點(diǎn);至多

2b(p)步近似率:2b(p)/d(p)最優(yōu)算法每一步至多減少2個斷點(diǎn):d(p)

b(p)/2性能保證:(2b(p)/d(p))

[2b(p)/(b(p)/2)]=4ImprovedBreakpointReversalSort:

性能分析第56頁/共68頁帶符號的排列之前待排序序列都是無符號的但基因?qū)嶋H上是有方向的…所以我們需要考慮帶符號的排列5’3’p

=1

-2

-3

4-5第57頁/共68頁GRIMMWebServer實(shí)際基因組結(jié)構(gòu)都是由帶符號的排列表示

已經(jīng)提出了多種對帶符號排列進(jìn)行排序的算法GRIMMwebserver就是其中之一:

第58頁/共68頁GRIMMWebServer

/groups/bioinformatics/GRIMM第59頁/共68頁一個背包，可裝物品重量

W>0.

一系列（n）物品S，重量weightswi>0以及價(jià)值

bi>0fori=1,…,n.

S={(item1,w1,b1

),(item2,w2,b2),

...,(itemn,wn,bn)

}

怎樣的裝包方案可獲得最大價(jià)值？0/1背包問題GreedyvsDynamic60第60頁/共68頁確定S的子集A

，滿足以下條件:0/1背包問題，每種物品只有一個，要么選要么不選不能多選不能拆分

0/1背包問題GreedyvsDynamic61第61頁/共68頁Fractionsareallowed.Thisappliestoitemssuchas:bread,forwhichtakinghalfaloafmakessensegolddustNofractions.0/1(1brownpants,1greenshirt…)Allowsputtingmanyitemsofsametypeinknapsack5pairsofsocks10goldbricksMorethanoneknapsack,etc.First0/1knapsackproblemwillbecoveredthentheFractionalknapsackproblem.VariationsoftheKnapsackproblemGreedyvsDynamic62第62頁/共68頁產(chǎn)生所有2n

個子集

去除所有總重量超過W的組合(無效組合)在剩下的有效組合中，選擇價(jià)值最大的方案時間復(fù)雜度?

O(n2n),Omega(2n)窮舉法!GreedyvsDynamic63第63頁/共68頁S={(item1,5,$70),(item2,10,$90),(item3,25,$140)},W=25Subsets:1.{}2.{(item1,5,$70)}Profit=$703.{(item2,10,$90)}Profit=$904.{(item3,25,$140)}Profit=$1405.{(item1,5,$70),(item2,10,$90)}.Profit=$160****6.{(item2,10,$90),(item3,25,$140)}exceedsW7.{(item1,5,$70),(item3,25,$140)}exceedsW8.{(item1,5,$70),(item2,10,$90),(item3,25,$140)}exceedsW

“窮舉法”示例GreedyvsDynamic64第64頁/共68頁S={(i