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

Outline

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

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

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

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

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

561264

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

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

p=12345678

r(3,5)

12543678

第21頁(yè)/共68頁(yè)反序:Example

p=12345678

r(3,5)

12543678r(5,6)12546378第22頁(yè)/共68頁(yè)反序與基因順序排列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頁(yè)/共68頁(yè)反序距離問(wèn)題Goal:給定兩個(gè)排列,找到一個(gè)最短的反序操作序列

使它們能將一個(gè)排列變換為另一個(gè)排列Input:排列

p

andsOutput:將排列p

變換為

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

并且

t

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

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

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

r1,

…rt

并使得t是最小的。

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

p

=3421567109843215671098

4321567891012345678910

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

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

p

的排序過(guò)程

123

645

1234

65

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

i

1ton–12j

元素i

在

p中的位置

(即,pj=i)3if

j≠i4p

p*r(i,j)5output

p6if

p

為恒等排列

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

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

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

p=p1p2p3…pn-1pn

如果pi+1=pi

+1則元素對(duì)（p

i

，

p

i+1

）稱(chēng)為

鄰接例如:

p

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

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

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

p的斷點(diǎn)

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

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

在p的兩端添加p

0

=0

和

p

n+1=n+1

例:

添加0

和

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

193478265

10第42頁(yè)/共68頁(yè)每次反序操作最多消除2個(gè)斷點(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頁(yè)/共68頁(yè)每次反序操作最多消除2個(gè)斷點(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頁(yè)/共68頁(yè)反序排序:改進(jìn)的貪婪算法BreakPointReversalSort(p)1

while

b(p)>02

所有反序中,選擇反序

r，使得b(p

?

r)最小化3

p

p?r(i,j)4

output

p5

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

while

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

r，使得b(p

?

r)最小化3

p

p?r(i,j)4

output

p5

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

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

0

19437825610

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

如果p

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

r

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

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

p=146578320

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

14657832

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

14657832

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

14657832

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

和

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

14657832

9

b(p)=50

1

2387564

9

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

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

r

都有b(p?

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

p=0

12567348b(p)=3p

?

r(6,7)=0

12567438b(p)=3

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

b(p)>02if

p

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

?

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

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

p

?

r7output

p8return第55頁(yè)/共68頁(yè)ImprovedBreakPointReversalSort

近似度為4的近似算法

至少每?jī)刹娇梢韵?個(gè)斷點(diǎn);至多

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

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

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

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

=1

-2

-3

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

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

第58頁(yè)/共68頁(yè)GRIMMWebServer

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

W>0.

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

bi>0fori=1,…,n.

S={(item1,w1,b1

),(item2,w2,b2),

...,(itemn,wn,bn)

}

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

，滿(mǎn)足以下條件:0/1背包問(wèn)題，每種物品只有一個(gè)，要么選要么不選不能多選不能拆分

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

個(gè)子集

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

O(n2n),Omega(2n)窮舉法!GreedyvsDynamic63第63頁(yè)/共68頁(yè)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頁(yè)/共68頁(yè)S={(i