lec4-贪婪法-基因组重排Rearrangements

Outline

甘蓝大白菜与芜菁基因组重排反序排序煎饼翻转问题反序排序的贪婪算法近似算法断点:另一种贪婪法则断点图第1页/共68页芜菁vs甘蓝:形态味道大不同第2页/共68页芜菁与甘蓝:

基因序列比较未发现演化信息第3页/共68页芜菁与甘蓝:近乎一致的mtDNA基因序列1980年代JeffreyPalmer研究芜菁与甘蓝的演化关系基因之间的相似度高于99%基因顺序却很不一样这一研究开创了分子演化中基因组重排的新领域第4页/共68页芜菁与甘蓝:不同的mtDNA顺序基因顺序比较:第5页/共68页芜菁与甘蓝:不同的mtDNA基因顺序基因顺序比较:第6页/共68页芜菁与甘蓝:不同的mtDNA基因顺序基因顺序比较:第7页/共68页芜菁与甘蓝:不同的mtDNA基因顺序基因顺序比较:第8页/共68页芜菁与甘蓝:不同的mtDNA基因顺序基因顺序比较:BeforeAfter演化以基因顺序不同的形式展现出来第9页/共68页甘蓝转换成

芜菁第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页反序和断点132410568971,2,3,-8,-7,-6,-5,-4,9,10反演reversion引入了两个断点breakpoints

(顺序上发生了分裂).第15页/共68页另外几种基因组重排反序/Reversal12345612-5-4-36Translocation1234

561264

53123456123456FusionFission第16页/共68页比较基因组结构:MousevsHuman人与小鼠基因组很相似,但是基因组顺序相差很大~245个重排反序FusionsFissionsTranslocation第17页/共68页Waardenburg’s综合征:

借小鼠之力研究人类基因组错序症状：色素异常/失聪锁定致病因子在2号染色体上但确切位置未知！第18页/共68页Waardenburg’s综合征与斑点病小鼠斑点病小鼠的症状与Waardenburg症状相似科学家成功定位了小鼠斑点病的致病基因这为人类致病因子的寻找提供了线索第19页/共68页人类与小鼠基因组结构的比较为成功定位人类基因组上的致病因子我们需要分析人类和小鼠的基因组相对结构关系第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)反转了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步内排好序?第29页/共68页煎饼反转问题大厨很草率，煎饼乱序顾客喜欢吃从上到下从小到大排好的煎饼服务员负责重新排序只有两把铲子可帮助翻转ChristosPapadimitrouandBillGatesflippancakes第30页/共68页反转排序:贪婪算法对p=123645,进行排序前3个元素已经有序定义prefix(p)为p中已经排好序的元素的数目

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页其实只需要两步: p=612345

Step1:543216Step2:123456因此,SimpleReversalSort(p)不是最优算法对于很多问题而言，最优算法未知;常常使用近似算法分析SimpleReversalSort(续)第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)都是邻接对邻接

与断点第39页/共68页任意两个非邻接/连续元素之间存在一个断点:

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

p的断点

b(p)–排列p的断点数量

断点第40页/共68页Adjacency&Breakpoints邻接–连续的元素对断点–不连续的元素对π=562134 05621347邻接断点π需要扩展π0=0和π7=7第41页/共68页

在p的两端添加p

0

=0

和

p

n+1=n+1

例:

添加0

和

10Note:扩展之后会增加断点数扩展排列p=193478265p=0

193478265

10第42页/共68页每次反序操作最多消除2个断点p=231465 0

231465

7

b(p)=5 0

132

4657

b(p)=4 0123465

7

b(p)=2 01234567 b(p)=0反序距离和断点第43页/共68页每次反序操作最多消除2个断点可得:

反序距离≥断点数/2p=231465 0

231465

7

b(p)=5 0

132

4657

b(p)=4 0123465

7

b(p)=2 01234567 b(p)=0反序距离和断点第44页/共68页反序排序:改进的贪婪算法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如何才能确信在除去一些断点的同时不会引入其他的断点从而导致一个死循环？Problem:thisalgorithmmayworkforever第46页/共68页带StripStrip(带):两个相邻断点之间的子排列

减带(Decreasingstrip):带中元素递减(如.65以及321).增带(Increasingstrip):带中元素递增(如.789)

0

19437825610

单元素带可以是增带也可以是减带。除了0和n+1外，我们将所有单元素称为减带第47页/共68页减少断点数理论11:

如果p

含有至少一个减带,那么必存在一个反序操作

r

可以减少断点数(即.b(p•

r)<b(p))第48页/共68页需要考虑的：对

p=146578320

146578329 b(p)=5选择减带中的最小元素k(本例k=2)第49页/共68页需要考虑的(续)对p=146578320

14657832

9 b(p)=5选择减带中的最小元素k(本例k=2)第50页/共68页需要考虑的(续)对p=146578320

14657832

9 b(p)=5选择减带中的最小元素k(本例k=2)找到排列p中的元素k-1第51页/共68页需要考虑的(续)对p=146578320

14657832

9 b(p)=5选择减带中的最小元素k(本例k=2)找到排列p中的元素k-1反转k

和

k-1之间的片段（包括k但无k-1）:0

14657832

9

b(p)=50

1

2387564

9

b(p)=4第52页/共68页再次减少断点

如果没有减带,则可能找不到任何能减少断点数的反序操作r(即对任何反序操作

r

都有b(p•

r)≥b(p)).怎么办？反转一个增带，则可以获得一个减带下一步就肯定可以减少断点数(基于理论1).第53页/共68页需要考虑的(续)排列p中已无减带:

p=0

12567348b(p)=3p

•

r(6,7)=0

12567438b(p)=3

r(6,7)无法改变断点数r(6,7)创建了一个减带，保证下一步一定能减少断点数.第54页/共68页ImprovedBreakpointReversalSortImprovedBreakpointReversalSort(p)1while

b(p)>02if

p

中存在减带在所有反序中,选择反序r使得b(p

•

r)最小化4else5选择一个反序r,

翻转p中的一个增带6p

p

•

r7output

p8return第55页/共68页ImprovedBreakPointReversalSort

近似度为4的近似算法

至少每两步可以消除1个断点;至多

2b(p)步近似率:2b(p)/d(p)最优算法每一步至多减少2个断点:d(p)

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

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

性能分析第56页/共68页带符号的排列之前待排序序列都是无符号的但基因实际上是有方向的…所以我们需要考虑带符号的排列5’3’p

=1

-2

-3

4-5第57页/共68页GRIMMWebServer实际基因组结构都是由带符号的排列表示

已经提出了多种对带符号排列进行排序的算法GRIMMwebserver就是其中之一:

第58页/共68页GRIMMWebServer

/groups/bioinformatics/GRIMM第59页/共68页一个背包，可装物品重量

W>0.

一系列（n）物品S，重量weightswi>0以及价值

bi>0fori=1,…,n.

S={(item1,w1,b1

),(item2,w2,b2),

...,(itemn,wn,bn)

}

怎样的装包方案可获得最大价值？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页产生所有2n

个子集

去除所有总重量超过W的组合(无效组合)在剩下的有效组合中，选择价值最大的方案时间复杂度?

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