计算机的计算能力.ppt

计算机的计算能力计算机的计算能力- 以生物信息学为例以生物信息学为例 李绍华李绍华 信息学院计算机科学与技术系信息学院计算机科学与技术系 20世纪三个重大的科技工程： 1.曼哈顿计划（原子弹研制） 2.阿波罗登月计划 3.人类基因组计划（HGP）：美英法德日中六国 Human Gene Program的目的： 完成人基因组24条染色体上5万左右基因的作图和30亿碱 基的DNA全序列的测定。 得到以下数据：遗传图、物理图、全序列图。 可定位与疾病有关的基因新药设计和疫苗制备。 基因中包含了人类的遗传密码；基因测序的完成 ，意味着密码已“偷到”，可这个密码里写的是什 么呢？ l 生物信息学 l 研究热点 l 计算问题 l 研究思路 ccgtacgtacgtagagtgctagtctagtc gtagcgccgtagtcgatcgtgtgggtagt agctgatatgatgcgaggtaggggatag gatagcaacagatgagcggatgctgag tgcagtggcatgcgatgtcgatgatagcg gtaggtagacttcgcgcataaagctgcg cgagatgattgcaaagragttagatgag ctgatgctagaggtcagtgactgatgatc gatgcatgcatggatgatgcagctgatcg atgtagatgcaataagtcgatgatcgatg atgatgctagatgatagctagatgtgatc gatggtaggtaggatggtaggtaaattga tagatgctagatcgtaggtagtagctaga tgcagggataaacacacggaggcgagt gatcggtaccgggctgaggtgttagctaa tgatgagtacgtatgaggcaggatgagt gacccgatgaggctagatgcgatggatg gatcgatgatcgatgcatggtgatgcgat gctagatgatgtgtgtcagtaagtaagcg atgcggctgctgagagcgtaggcccga gaggagagatgtaggaggaaggtttgat ggtagttgtagatgattgtgtagttgtagct gatagtgatgatcgtag 基因序列中包含着有机体的大量信息 gcgtacgtacgtagagtgctagtctagtcgtagcgccgtagtcgatcgtgtgg gtagtagctgatatgatgcgaggtaggggataggatagcaacagatgagc ggatgctgagtgcagtggcatgcgatgtcgatgatagcggtaggtagacttc gcgcataaagctgcgcgagatgattgcaaagragttagatgagctgatgcta gaggtcagtgactgatgatcgatgcatgcatggatgatgcagctgatcgatgt agatgcaataagtcgatgatcgatgatgatgctagatgatagctagatgtgat cgatggtaggtaggatggtaggtaaattgatagatgctagatcgtaggtagta gctagatgcagggataaacacacggaggcgagtgatcggtaccgggctg aggtgttagctaatgatgagtacgtatgaggcaggatgagtgacccgatga ggctagatgcgatggatggatcgatgatcgatgcatggtgatgcgatgctag atgatgtgtgtcagtaagtaagcgatgcggctgctgagagcgtaggcccga gaggagagatgtaggaggaaggtttgatggtagttgtagatgattgtgtagtt gtagctgatagtgatgatcgtag . 通过对生物数据的分析可以获得基因序列中所 包含的有机体的大量重要信息 分子生物学是一门信息科学 。 - Leroy Hood, ISB 生物信息的海量性 近20 年来，分子生物学发展的一个显著特点是 生物信息的剧烈膨胀，且迅速形成了巨量的生 物信息库。 v近年来GenBank中的DNA碱基数目呈指数增加，大 约每14个月增加一倍。到1999年12月其数目已达30 亿，它们来自47000种生物。2000年4月DNA碱基数目 是60亿。2001年初这一数目已达110亿。预计2005年 达到300亿。 v各种生物的EST序列已达600多万条，其中人类的 EST序列已超过300 万条，估计覆盖人类基因90以 上； vUniGene的数目约达7万个；自1999年初单核苷酸 多态性( SNPs,Single Nucleotide Polymorphisms )数据库出现以来，到2000年3月20日SNP的总数是 26569，现在已超过350万 计算机运算速度: 18个月增长一倍; DNA序列数据: 14个月增长一倍; 生物数据库的增长 l遍布世界各地研究实验室的高通量大 型测序仪在日夜不停地运转，每天都 有成千上万的数据被源源不断地输入 相应的生物信息库中。同时，由这些 原始数据分析加工而来的蛋白质结构 等数据信息也被世界各地的分子生物 学、生物信息学等学科领域专家输入 二级数据库中。 3*10 9 10,000 books 1 book 100 pages 1 page 3,000 characters CCGGTCTCCCCGCCCGCGCGCGAAGTAAAGGCCCAGCGCAGCCCGCGCTCCTGCCCTGGGGCCTCGT CTTTCTCCAGGAAAACGTGGACCGCTCTCCGCCGACAGTCTCTTCCACAGACCCCTGTCGCCTTCG CCCCCCGGTCTCTTCCGGTTCTGTCTTTTCGCTGGCTCGATACGAACAAGGAAGTCGCCCCCAGCG AGCCCCGGCTCCCCCAGGCAGAGGCGGCCCCGGGGGCGGAGTCAACGGCGGAGGCACGCCCTCT GTGAAAGGGCGGGGCATGCAAATTCGAAATGAAAGCCCGGGAACGCCGAAGAAGCACGGGTGTAA GATTTCCCTTTTCAAAGGCGGGAGAATAAGAAATCAGCCCGAGAGTGTAAGGGCGTCAATAGCGCT GTGGACGAGACAGAGGGAATGGGGCAAGGAGCGAGGCTGGGGCTCTCACCGCGACTTGAATGTG GATGAGAGTGGGACGGTGACGGCGGGCGCGAAGGCGAGCGCATCGCTTCTCGGCCTTTTGGCTAA GATCAAGTGTAGTATCTGTTCTTATCAGTTTAATATCTGATACGTCCTCTATCCGAGGACAATATATTA AATGGATTGATCAATCCGCTTCAGCCTCCCGAGTAGCTGGGACTACAGACGGTGCCATCACGCCCA GCTCATTGTTGATTCCCGCCCCCTTGGTAGAGACGGGATTCCGCTATATTGCCTGGGCTGGTGTCG AACTCATAGAACAAAGGATCCTCCCTCCTGGGCCTGGGCGTGGGCTCGCAAAACGCTGGGATTCCC GGATTACAGGCGGGCGCACCACACCAGGAGCAAACACTTCCGGTTTTAAAAATTCAGTTTGTGATTG GCTGTCATTCAGTATTATGCTAATTAAGCATGCCCGGTTTTAAACCTCTTAAAACAACTTTTAAAATTA CCTTTCCACCTAAAACGTTAAAATTTGTCAAGTGATAATATTCGACAAGCTGTTATTGCCAAACTATTT TCCTATTTGTTTCCTAATGGCATCGGAACTAGCGAAAGTTTCTCGCCATCAGTTAAAAGTTTGCGGCA GATGTAGACCTAGCAGAGGTGTGCGAGGAGGCCGTTAAGACTATACTTTCAGGGATCATTTCTATAG TGTGTTACTAGAGAAGTTTCTCTGAACGTGTAGAGCACCGAAAACCACGAGGAAGAGAGGTAGCGTT TTCATCGGGTTACCTAAGTGCAGTGTCCCCCCTGGCGCGCAATTGGGAACCCCACACGCGGTGTAG AAATATATTTTAAGGGCGCG (1250 characters) 关键是先要从一个个序列片段中得到这本天书 破译人类遗传密码就要读懂由30 亿符号组成的100万页的“天书” 怎么办办 My god!好 多数据啊！ ！ CCGGTCTCCCCGCCCGCGCGCGAAGTAAAGGCCCAGCGCAGC CCGCGCTCCTGCCCTGGGGCCTCGTCTTTCTCCAGGAAAAC GTGGACCGCTCTCCGCCGACAGTCTCTTCCACAGACCCCTG TCGCCTTCGCCCCCCGGTCTCTTCCGGTTCTGTCTTTTCGCT GGCTCGATACGAACAAGGAAGTCGCCCCCAGCGAGCCCCG GCTCCCCCAGGCAGAGGCGGCCCCGGGGGCGGAGTCAAC GGCGGAGGCACGCCCTCTGTGAAAGGGCGGGGCATGCAAA TTCGAAATGAAAGCCCGGGAACGCCGAAGAAGCACGGGTGT AAGATTTCCCTTTTCAAAGGCGGGAGAATAAGAAATCAGCCC GAGAGTGTAAGGGCGTCAATAGCGCTGTGGACGAGACAGAG GGAATGGGGCAAGGAGCGAGGCTGGGGCTCTCACCGCGAC TTGAATGTGGATGAGAGTGGGACGGTGACGGCGGGCGCGA AGGCGAGCGCATCGCTTCTCGGCCTTTTGGCTAAGATCAAG TGTAGTATCTGTTCTTATCAGTTTAATATCTGATACGTCCTCT ATCCGAGGACAATATATTAAATGGATTGATCAATCCGCTTCA GCCTCCCGAGTAGCTGGGACTACAGACGGTGCCATCACGCC CAGCTCATTGTTGATTCCCGCCCCCTTGGTAGAGACGGGATT CCGCTATATTGCCTGGGCTGGTGTCGAACTCATAGAACAAAG GATCCTCCCTCCTGGGCCTGGGCGTGGGCTCGCAAAACGCT GGGATTCCCGGATTACAGGCGGGCGCACCACACCAGGAGC AAACACTTCCGGTTTTAAAAATTCAGTTTGTGATTGGCTGTCA TTCAGTATTATGCTAATTAAGCATGCCCGGTTTTAAACCTCTT AAAACAACTTTTAAAATTACCTTTCCACCTAAAACGTTAAAATT TGTCAAGTGATAATATTCGACAAGCTGTTATTGCCAAACTATT TTCCTATTTGTTTCCTAATGGCATCGGAACTAGCGAAAGTTTC TCGCCATCAGTTAAAAGTTTGCGGCAGATGTAGACCTAGCAG AGGTGTGCGAGGAGGCCGTTAAGACTATACTTTCAGGGATC ATTTCTATAGTGTGTTACTAGAGAAGTTTCTCTGAACGTGTAG AGCACCGAAAACCACGAGGAAGAGAGGTAGCGTTTTCATCG GGTTACCTAAGTGCAGTGTCCCCCCTGGCGCGCAATTGGGA ACCCCACACGCGGTGTAGAAATATATTTTAAGGGCGCG 生物信息学在生物信息的急剧膨胀的 压力下诞生。 一般意义上，生物信息学是研究生 物信息的采集、处理、存储、传播、分 析和解释等各方面的一门学科，它通过 综合利用生物学、计算机科学和信息技 术揭示大量而复杂的生物数据所赋有的 生物学奥秘。 生物信息学的定义 生物信息学的研究 l以核酸蛋白质等生物大分子为主要研究对象 l以信息、数理、计算机科学为主要研究手段 l以计算机网络为主要研究环境 l以计算机软件为主要研究工具 l对序列数据进行存储、管理、注释、加工 l对各种数据库进行查询、搜索、比较、分析 l构建各种类型的专用数据库信息系统 l研究开发面向生物学家的新一代计算机软件 生物信息学 研究方向 l基因组序列装配 l基因识别 l基因功能预报 l基因多态性分析 l基因进化 lmRNA结构预测 l基因芯片设计 l基因芯片数据分析 l疾病相关基因分析 l蛋白质序列分析 l蛋白质家族分类 l蛋白质结构预测 l蛋白质折叠研究 l代谢途径分析 l转录调控机制 l蛋白质芯片设计 l蛋白质芯片数据分析 l药物设计 生物信息学 研究方法 l利用数理统计、模式识别、动态规划、密码 解读、语意解析、信令传递、神经网络、遗 传算法以及隐马氏模型等各种方法 l对序列、结构数据进行定性和定量分析，从 中获取基因编码、基因调控、序列-结构-功 能关系等理性知识 l阐明细胞、器官和个体的发生、发育、病变 、衰亡的基本规律和时空联系 l探索生命起源、生物进化、生命本质等重大 理论问题，最终建立“生物学周期表” 生物信息学热点问题（1） l基因组时期：序列结构功能 DNA测序和拼接 分子生物数据库 序列比对 分子进化 蛋白质质谱鉴定 序列注释：基因预测、细胞定位 结构预测：RNA结构预测、蛋白质折叠 。 生物信息学热点问题（2） l后基因组时期：相互作用网络功能 生物芯片（DNA芯片、蛋白质芯片） 相互作用网络 调控网络 药物设计 。 热点：DNA测序和拼接 l鸟枪法(Shotgun)测序：得到DNA片 断 随机地切很多次 基因组 forward-reverse linked reads plasmids (2 10 Kbp) cosmid (40 Kbp) known dist 500 bp500 bp 序列拼接：将片断拼接为完整基因组 DNA片断（Reads） 基因组 全基因组 Shotgun 拼接 1. 找重叠 reads 4. 最后推导出一致的序列 ACGATTACAATAGGTT 2. 把重叠reads合并成 contigs 3. 把contigs 连接起来形成 supercontigs l比较片段集 合中所有的 片段对,获得 可能存在的 重叠部分 (Overlap) l建立所有片 段的相互组 合关系 (Layout) ,以 片段为顶点, 重叠的片段 相互连接， 构成图 Phrap算法 Phrap 算法最后一步是定义有向代权图,并在图中找 出一条最佳路径,使得这条路径经过每个顶点恰好一次 Hamiltonian 路径问题 Euler 算法 l建立所有片段的相互关系, 即构造deBrujin 图. 以每个片段为图中的线,重复片段则相当于用 胶水胶在一块,用统一的一条线来表示 叠放重复片断 将重复片断看作一个 拼接成长序列,即找出一条欧拉路线, 使得此路径经过每一条线恰好一次 Eulerian路径问题 l序列拼接问题可以转换为 Hamiltonian 路径问题 Eulerian 路径问题 转换为计算问题 热点：生物信息数据库 lDNA序列：A、C、G、T组成的字符串 atggcaattaaaattggtatcaatggttttggtcgtatcggccgtatcgtattccgtgca gcacaacaccgtgatgacattgaagttgtaggtattaacgacttaatcgacgttgaatac atggcttatatgttgaaatatgattcaactcacggtcgtttcgacggcactgttgaagtg aaagatggtaacttagtggttaatggtaaaactatccgtgtaactgcagaacgtgatcca gcaaacttaaactggggtgcaatcggtgttgatatcgctgttgaagcgactggtttattc ttaactgatgaaactgctcgtaaacatatcactgcaggcgcaaaaaaagttgtattaact ggcccatctaaagatgcaacccctatgttcgttcgtggtgtaaacttcaacgcatacgca ggtcaagatatcgtttctaacgcatcttgtacaacaaactgtttagctcctttagcacgt gttgttcatgaaactttcggtatcaaagatggtttaatgaccactgttcacgcaacgact gcaactcaaaaaactgtggatggtccatcagctaaagactggcgcggcggccgcggtgca tcacaaaacatcattccatcttcaacaggtgcagcgaaagcagtaggtaaagtattacct gcattaaacggtaaattaactggtatggctttccgtgttccaacgccaaacgtatctgtt gttgatttaacagttaatcttgaaaaaccagcttcttatgatgcaatcaaacaagcaatc aaagatgcagcggaaggtaaaacgttcaatggcgaattaaaaggcgtattaggttacact gaagatgctgttgtttctactgacttcaacggttgtgctttaacttctgtatttgatgca gacgctggtatcgcattaactgattctttcgttaaattggtatc . . . . . . caaaaatagggttaatatgaatctcgatctccattttgttcatcgtattcaa caacaagccaaaactcgtacaaatatgaccgcacttcgctataaagaacacggcttgtgg cgagatatctcttggaaaaactttcaagagcaactcaatcaactttctcgagcattgctt gctcacaatattgacgtacaagataaaatcgccatttttgcccataatatggaacgttgg gttgttcatgaaactttcggtatcaaagatggtttaatgaccactgttcacgcaacgact acaatcgttgacattgcgaccttacaaattcgagcaatcacagtgcctatttacgcaacc aatacagcccagcaagcagaatttatcctaaatcacgccgatgtaaaaattctcttcgtc ggcgatcaagagcaatacgatcaaacattggaaattgctcatcattgtccaaaattacaa aaaattgtagcaatgaaatccaccattcaattacaacaagatcctctttcttgcacttgg l蛋白质序列：20种氨基酸构成的序列 （A、R、N、D、C、Q、E、G、H 、I、L、K、M、F、P、S、T、W、 Y和V） 庞大的数据信息需要数据库保存 lDNA数据库 EMBL GenBank DDBJ l蛋白质数据库 SWISS-PROT PIR PDB 热点 ：序列比对 l用于同源查找：从不同的生物中找到相似之处 l人类 vs. 老鼠 vs. 酵母 (以下数据来自NCBI 疾病数据库) Best Sequence Similarity Matches to Date Between Positionally Cloned Human Genes and S. cerevisiae Proteins Human Disease MIM # Human GenBank BLASTX Yeast GenBank Yeast Gene Gene Acc# for P-value Gene Acc# for Description Human cDNA Yeast cDNA Hereditary Non-polyposis Colon Cancer 120436 MSH2 U03911 9.2e-261 MSH2 M84170 DNA repair protein Hereditary Non-polyposis Colon Cancer 120436 MLH1 U07418 6.3e-196 MLH1 U07187 DNA repair protein Cystic Fibrosis 219700 CFTR M28668 1.3e-167 YCF1 L35237 Metal resistance protein Wilson Disease 277900 WND U11700 5.9e-161 CCC2 L36317 Probable copper transporter Glycerol Kinase Deficiency 307030 GK L13943 1.8e-129 GUT1 X69049 Glycerol kinase Bloom Syndrome 210900 BLM U39817 2.6e-119 SGS1 U22341 Helicase Adrenoleukodystrophy, X-linked 300100 ALD Z21876 3.4e-107 PXA1 U17065 Peroxisomal ABC transporter Ataxia Telangiectasia 208900 ATM U26455 2.8e-90 TEL1 U31331 PI3 kinase Amyotrophic Lateral Sclerosis 105400 SOD1 K00065 2.0e-58 SOD1 J03279 Superoxide dismutase Myotonic Dystrophy 160900 DM L19268 5.4e-53 YPK1 M21307 Serine/ threonine protein kinase Lowe Syndrome 309000 OCRL M88162 1.2e-47 YIL002C Z47047 Putative IPP-5-phosphatase Neurofibromatosis, Type 1 162200 NF1 M89914 2.0e-46 IRA2 M33779 Inhibitory regulator protein Choroideremia 303100 CHM X78121 2.1e-42 GDI1 S69371 GDP dissociation inhibitor Diastrophic Dysplasia 222600 DTD U14528 7.2e-38 SUL1 X82013 Sulfate permease Lissencephaly 247200 LIS1 L13385 1.7e-34 MET30 L26505 Methionine metabolism Thomsen Disease 160800 CLC1 Z25884 7.9e-31 GEF1 Z23117 Voltage-gated chloride channel Wilms Tumor 194070 WT1 X51630 1.1e-20 FZF1 X67787 Sulphite resistance protein Achondroplasia 100800 FGFR3 M58051 2.0e-18 IPL1 U07163 Serine/ threoinine protein kinase Menkes Syndrome 309400 MNK X69208 2.1e-17 CCC2 L36317 Probable copper transporter 序列比对的意义 l在生物学的研究中，将未知序列同已知 序列进行比较分析已经成为一种强有力 的研究手段 ，生物学领域中绝大部分 的问题在计算机科学领域中主要体现为 序列或字符串的问题 。 如果两个序列具有足够的相似性， 则认为两者具有同源性。 两条序列之间的比对 计算机科学当中已经有比较成熟的串问题的算法 -AGGCTATCACCTGACCTCCAGGCCGA-TGCCC- TAG-CTATCAC-GACCGC-GGTCGATTTGCCCGAC AGGCTATCACCTGACCTCCAGGCCGATGCCC TAGCTATCACGACCGCGGTCGATTTGCCCGAC 分子的动态模拟 代谢途径模拟 计算在生物问题中的角色 实验产生的庞大 生物数据 计算 实验 专业领域知识 理论模型 或假说 证实/新数据 合理 设计 数据挖掘 .计算扮演一个十分重要的角色 生物信息学中的几个计算问题 l举例： Vertex cover motif finding DSSP (Distinguishing String Selection Problems) 一、Vertex cover lDNA sequences A,G,T,C代表四个DNA的基本元素 105个互不相同的DNA序列 G A T T C C A G T lGive n(here,n= 105) DNA sequences, can you find 60 of them whose remove makes the remaining sequences consistent? l问题：105个基因序列中,只去掉60个 ,使得剩下的序列相似. l模型： 作一个图，每个DNA串是图中的一个点。 两个串比较，不相同的话加一条边进行连 接，每条边对应两个不同的DNA。移除边上 的任意一点相当于删除这条边。 这个图上的信息量可以用计算机来计算， 大约为10万的平方。 在图中找到60个点后就没有边了，系统可 用 如果超过60个点还有边，系统不可用 l问题等价于：Give a graph ,can you find 60 vertices whose remove makes the graph has no edge? lVertex cover(点覆盖):Give a graph, can you find k vertices such that each edge has at least one end in these k vertices? l另一种说法： lGive a graph G of n vertices , decide if there are k vertices whose remove makes the graph edgeless. lTry any subset of 60 vertices and check if it make a vertex cover(点覆盖) l图中每60个点拿出来试一试： 若n比60 大得多，n60 实际中无法使用，需要对它进行改进。 (not solvable practically)-NP-hard (2) motif finding 医学上的问题：已知几个串中有癌症细胞，要求从中找出 这几个串它们的共性，也即是说，寻找一个子串，在每 个串（或是大部分串）中都出现。 l子串相似性的定义：在串中间插、删、改的次数不超过6 次，使得两个子串相同。 表示相似的子串 k20，每个串长度为 2000 序列模体 (Motif) TGTGAAAGACTGTTTTTTTGATCGTTTTGACAAAAATGGAAGTCCACA AAGTCCACATTGATTATTTGCACGGCGTCACACTTTGCTATCCCATAG TGATGTACTGCATGTATGCAAAGGACGTCAGATTACCGTGCAGTACAG TAAACGATTCCACTAATTTATTCCATGTCACTCTTTTCGCATCTTTGT ACATTACCGCCAATTCTGTAACAGAGATCACACAAAGCGACGGTGGGG ACTTTTTTTTCATATGCCTGACGGAGTTGACACTTGTAAGTTTTCAAC Pevzner-Sze, ISMB2000 l（15，6）模型的问题：查找一个长度 为15的子串，使得它在所有的20个串 中都存在，（允许存在6个误差）。 lGive k DNA sequences,find a pattern of length 15 that is similar to a subsequence in each sequence. lGive a k-partile graph,find a set of vertices,one from each row,such that all these k vertices are connected. （最大团） l计算量为nk=200020-NP-hard! l改进： n5Xn5=n10 2n10 =4n5 n5Xn5=n10 5行 n5 5行 5行 n5 5行 是不是什么问题都是单计算机可解的？ 例一：求图G的最小顶点覆盖问题： 问题描述：无向图G=(V,E)的顶点覆盖是它的顶点集V的一个子 集 V V，使得若(u,v)是G的一条边，则vV或uV。顶点覆 盖V的大小是它所包含的顶点个数|V|。 算法：/给定图G =,其中|V| =n，|E| =m 第一步：枚举出V中所有的子集： 子集总数= (n1) + (n2) +(n3) + (nn) =2n 第二步：判断每个子集是否是图G的顶点覆 盖：for i =1 to m do 算法时间复杂性：O(2n*m) 可计算否？ 例: l假设 n=56, 在一台运行速度为 亿次级每秒的 计算机里用枚举法求解VC问题，须花时多少 ？ l计算：我们假设该机器每秒钟可判断一亿种 的方案是否正确！则有： l256种方案/1亿种每秒/60/60/24/365 =22.85(年)！ 结论