chap7-基因组重排课件

1、基因组重排2012/11/13内容基因组重排无向块重排有向块重排Waardenburgs syndrome1951，眼科及遗传学医师瓦登伯革（Petrus Johanner Waardenburg）首先在文献提出一种新的症候群病患通常会出蓝色眼珠，对视没有影响，听上可能出现极大的障碍及有先天性巨结肠症Chr2上的PAX3基因由2q35重排到13q14基因组重排染色体的片段进行交换，影响染色体一个染色体片段可以被移动或复制到另外一个位置，甚至从一条染色体到另外一条染色体染色体移动即为染色体重排把一个基因组转换为另一个基因组所需要的反转操作的数量来度量两个基因组间的进化距离示例重组事件是影响基因组

2、进化的重要方式紫花苜蓿和豌豆叶绿体基因组大头菜和卷心菜比较基因组序列，没有位点进化信息基因组比较1980年，Jeffrey Palmer通过比较大头菜和卷心菜的线粒体染色体研究植物细胞进化基因间99%都相似，但基因的排序不同这个研究促进了分子进化里基因组重组的研究基因组比较大头菜和卷心菜mtRNA比较基因组顺序变化也是进化的一种方式基因组比较卷心菜到大头菜基因组比较大鼠和人的X染色体比较大鼠X染色体人X染色体反序对块的邻接片段进行操作，反转相关块的序，并反转箭头方向假定自然界总能找到所需变化最小的途径寻找导致一个基因组变为另一个基因组的最小反转数目反序1, 2, 3, 4, 5, 6, 7,

3、8, 9, 1013241056897反序410568971, 2, 3, -8, -7, -6, -5, -4, 9, 10反序断裂反序5 ATGCCTGTACTA 33 TACGGACATGAT 55 ATGTACAGGCTA 33 TACATGTCCGAT 5无向块重排不考虑朝向，寻找可将一种块次序转换为另一种块次序的最少反转操作序列有向块重排考虑朝向无向重排标记 p = 1 2 3 4 5 6 7 8 r3,5 1 2 5 4 3 6 7 8 r5,6 1 2 5 4 6 3 7 8无向块重排给定一个排列，找到一系列反序置换使排序为自然顺序输入：打乱顺序的序列输出：一组反序置换p =

4、3 4 2 1 5 6 7 10 9 8 4 3 2 1 5 6 7 10 9 8 4 3 2 1 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10贪婪算法示例1p = 4 3 2 1 5 6 9 8 7 1 2 3 4 5 6 9 8 7 1 2 3 4 5 6 7 8 9贪婪算法 示例2: p = 6 1 2 3 4 5 贪婪算法：Step 0: 6 1 2 3 4 5Step 1: 1 6 2 3 4 5Step 2: 1 2 6 3 4 5 Step 3: 1 2 3 6 4 5Step 4: 1 2 3 4 6 5Step 5: 1 2 3 4 5 6近似算法Ste

5、p 0: 6 1 2 3 4 5Step 1: 5 4 3 2 1 6 Step 2: 1 2 3 4 5 6有向块重排=2,4假定同一标记集合上两个有向排列、，寻找把变成的最小反转数t=d()断点在的左右加上L、R即为的扩展形式关于的断点：L0的一对元素x、y，xy出现在的扩展形式中，但xy和 均不出现在的扩展形式中相对于恒等排列的断点断点一个反转最多可从一个排列中移去两个断点到反转距离的下界为关于的断点数一半现实与期望图现实线连接当前排列中相接触标记的端点期望线连接目标排列中接触标记的端点现实与期望图关于的现实-期望图式（reality and desire digram）Rd增加结点L、R和有向标记现实边按连接排列中连续标记的末端，L和R分别连接第一个和最后一个末端期望变根据连接标记所有末端结点连成一圈，L和R占据顶上位置，L在R左侧，其他节点按的逆时针排列