《生物信息学单体型组装与推断》由会员分享，可在线阅读，更多相关《生物信息学单体型组装与推断（77页珍藏版）》请在金锄头文库上搜索。
1、http:/zhangroup.aporc.org生物信息学单体型组装与推断吴凌云 中国科学院数学与系统科学研究院SNP和单体型和单体型多态性 人类在DNA水平上有99.9%的相似程度 不同个体或种群之间DNA序列的差异称为基因多态性 基因多态性决定着一些外部特征如绿眼睛和褐眼睛，或直 发与弯法等 基因变异(Mutation)是主要的一种多态性 单体型是研究基因变异与疾病联系的重要工具单核苷酸多态性(SNP) 在单个核苷酸上的差异称为单核苷酸多态性(Single Nucleotide Polymorphism) SNP是人类基因组DNA序列变异的主要形式 SNP是决定人类疾病（尤其是多基因疾病
2、）易感性和药物 反应性差异的核心信息 90%的多态性都是由单个核苷酸的变异引起的 人的SNP密度：平均1000个碱基中含有1个SNP位点 在整个人类基因组中大约有300万个单核苷酸多态性存在SNP的类型 大部分SNP都是以双等位基因的形式出现： major (wild type) / minor (mutant type) 非同义(Non-Synonymous) SNP是指那些导致编码的氨基酸 发生变化的SNP 编码序列中的SNP有一半是非同义SNP 普通(Common) SNP是指那些minor等位基因出现频率大于 5%的SNP单体型和基因型 双倍体生物的染色体总是成对出现的 在双倍体生物的
3、每一条染色体的每一个SNP位点上，都会 出现两个可能的等位基因中的一个 每一条染色体上的所有等位基因按一定顺序排列构成一条 单体型单体型 两条染色体上的对应等位基因组合在一起构成一条基因型基因型例子来自父方的染色体来自父方的染色体: ATAGCCTATTTCCAGGAGTCGAAGAC 来自母方的染色体来自母方的染色体: ATAGCGTATTTCCAGGAGTCGTAGAC单体型单体型 1C C A 单体型单体型 2G C T基因型基因型C,G C,C A,T单体型和基因型的表达两条单体型两条单体型一条基因型一条基因型0 1 1 1 0 0 1 1 01 1 0 1 0 0 1 0 02 1
4、2 1 0 0 1 2 0复 合Linkage DisequilibriumABabABabHigh LD - No Recombination (r2= 1) SNP1 “tags” SNP2A BA BA Ba ba ba bLow LD - Recombination Many possibilitiesA bA ba Ba bA BA Ba BA betcA BA BXORParent 1Parent 2SNP1SNP2 alleles:A/aB/b C1 C2POP allele freqs:A (80%)B (60%) a (20%)b (40%)genotypes:Person
5、1Person 2Person 3 AAAAAa BBBbBbphased haplotypes (C1/C2): ABABAB ABAbab OR Ab aB标签SNP单体型图(HapMap)计划 检测染色体上所有的SNPs的费用极其昂贵 一些相互邻近的多态位点趋向于在一起共同遗传，这些变 异连锁的区域就是单体型 在一个特定人群中，55的人可能拥有同一种单体型，30 的人可能拥有另一种单体型，8的人可能拥有第三种 单体型，而其余的人可能拥有若干种稀有的单体型 通过标签SNPs来鉴定一个人的单体型集合 定位与重要医学特征相关的基因单体型检测 目前检测单体型的方法主要有两种 单体型组装单体型组装
6、(Haplotype Assembly) 从较小的SNP片断来组装单体型 优点：比较精确 缺点：技术实现较难、费用昂贵、速度慢 单体型推断单体型推断(Haplotype Inference) 从群体的基因型来推断单体型 优点：技术实现容易、基因型容易获取 缺点：不精确单体型组装问题单体型组装问题单体型组装问题 Haplotype Assembly Haplotyping for individual 从Shotgun测序实验得到的序列片断来组装 出一对单体型困难 序列片断可能来自任何一条染色体 片断较短：每个片断可能包含23个SNP 测序错误 杂质污染SNP矩阵f1f2f3f4f5G CATG
7、G G ATG AG CATG CATGATG AATG CATGATCAATGACs1s2s3DNA fragmentsSNP matrixf1f2f3f4f5s1s2s3010010011冲突图f1f2f3f4f5s1s2s3010010011s4s5s60101001001SNP matrixf4f1f3f2f5Fragment conflict graph GF二分图f3f5f2H1H2f1f4图的二分化 可以用Mathematica 5.1中的子程序 BipartiteQ 来计算判断 一个图是否是一个二分图 一个图是否是二分图当且仅当它没有奇圈 (a cycle with odd n
8、umber of edges) (S.Skiena,1990) 如何从带有误差的数据中恢复出一对单体型 如何将一个图合理地变成一个二分图去除顶点 去掉一些顶点来得到二分图 (相当于去除一 些受污染的片段)f4f1f3f2f5去除边 去掉一些边来得到二分图 (相当于去除一些 SNP位点或改变某些片段上某些SNP位点的 值)f4f1f3f2f5单体型组装模型Conflict GraphMFR Minimum Fragment RemovalLHR Longest Haplotype ReconstructionMSR Minimum SNP RemovalMEC Minimum Error Cor
9、rectionOmit VerticesOmit Edges去除一组片断使得矩阵可分且导出 的单体型长度最长去除一组最少的片断使得矩阵可分 （使冲突图为二分图）去除尽可能少的SNP点(矩阵的列)， 使得矩阵可分改变尽可能少的SNP位点上的值， 使矩阵可分计算复杂性Conflict GraphMFR Minimum Fragment RemovalLHR Longest Haplotype ReconstructionMSR Minimum SNP RemovalMEC Minimum Error CorrectionOmit VerticesOmit EdgesAPX-HardNP-HardA
10、PX-HardAPX-HardMEC的整数规划模型线性约束算法思想 将MEC问题转化为分类问题 将SNP片断分为两类：C1和C2 对每一个分类Ci，用最大似然原则迅速求出对应的最优单体型Hi （即Ci中的SNP片断只需最少的修正次数即可与单体型Hi一致） 搜索比较所有可能的分类 MEC的最优解为满足下式的分类P*MEC模型算法 精确算法 分支定界算法 近似算法 动态聚类算法 神经网络算法 遗传算法MEC模型的扩展 MEC/GI MEC with Genotype Information 要求组装出的单体型和基因型数据一致MEC模型的扩展 WMEC Weighted MEC DNA测序时每个碱基
11、都有一个置信度 被纠正的SNP的权重之和最小 当所有SNP的权重设为1时，即原始的MEC模型MEC模型的扩展 CWMEC Complete Weighted MEC 给定删除比例RF和RS，允许去掉不超过RF比例 的片断和RS比例的SNP位点 WMEC和MFR、MSR的结合 RF =1,RS =0,即MFR模型 RF =0,RS =1,即MSR模型 RF =0,RS =0,即WMEC模型图的二分化算法Reed B, Smith K, Vetta A. Finding odd cycle transversals. Oper Res Letters 2004; 32(4): 299301. H
12、ffner F. Algorithm engineering for optimal graph bipartization. In Proceedings of the 4th International Workshop of Efficient and Experimental Algorithms (WEA). Springer-Verlag 2005; 240-252. Guo J, Gramm J, H ffner F, Niedermeier R, Wernicke S. Improved fixed parameter algorithms for two feedback s
13、et problems. In Proceedings of the 9th Workshop on Algorithms and Data Structures (WADS). Springer- Verlag 2005; 158-168.评论 我们注意到，在 Reed et al. 的工作之前，在 图论研究中极少有对图的最优二分化的研 究，原因是大家知道这是一个NP-难问题。 正是由于生物信息学研究的需要，推动图 论学家回来研究这一问题并得到好的研究 结果。单体型推断问题单体型推断问题单体型推断问题 Haplotype Inference Haplotype Phasing Haploty
14、ping in population 从一个人群的基因型来推断单体型 给定一个人群的基因型数据 为该人群中的每个人找到最可能的单体型配对 估计在该人群中的单体型出现频率基因型 Genotype (基因型) 是指每个标签位置（Marker）的无序等 位基因对（unordered pair of alleles for each marker）组成 的一个序列 Homozygous (纯合子): 在一个位置上的一对等位基因是相 同的 Heterozygous (杂合子):在一个位置上的一对等位基因是相 异的例子来自父方的染色体来自父方的染色体: ATAGCCTATTTCCAGGAGTCGAAGAC
15、 来自母方的染色体来自母方的染色体: ATAGCGTATTTCCAGGAGTCGTAGAC单体型单体型 1C C A 单体型单体型 2G C T基因型基因型C,G C,C A,T基因型的解析 与基因型一致的一对单体型称为这个基因 型的解析（resolution) 一个基因型的杂合子个数为k，则对应的不 同的解析有2k-1个 2k-1个解析中哪种才是正确的、合理的？例子基因重组(Recombination)Pedigree Data Assumption Pedigree graph (genetic relationship) Mendelian law (no mutation) Difficulty Additional genotyping costs Potential recruiting proble
