《计算机的计算能力》PPT课件

,计算机的计算能力-以生物信息学为例李绍华信息学院计算机科学与技术系,20世纪三个重大的科技工程：1.曼哈顿计划（原子弹研制）2.阿波罗登月计划3.人类基因组计划（HGP）：美英法德日中六国,HumanGeneProgram的目的：完成人基因组24条染色体上5万左右基因的作图和30亿碱基的DNA全序列的测定。得到以下数据：遗传图、物理图、全序列图。可定位与疾病有关的基因新药设计和疫苗制备。,基因中包含了人类的遗传密码；基因测序的完成，意味着密码已“偷到”，可这个密码里写的是什么呢？,生物信息学研究热点计算问题研究思路,基因序列中包含着有机体的大量信息,gcgtacgtacgtagagtgctagtctagtcgtagcgccgtagtcgatcgtgtgggtagtagctgatatgatgcgaggtaggggataggatagcaacagatgagcggatgctgagtgcagtggcatgcgatgtcgatgatagcggtaggtagacttcgcgcataaagctgcgcgagatgattgcaaagragttagatgagctgatgctagaggtcagtgactgatgatcgatgcatgcatggatgatgcagctgatcgatgtagatgcaataagtcgatgatcgatgatgatgctagatgatagctagatgtgatcgatggtaggtaggatggtaggtaaattgatagatgctagatcgtaggtagtagctagatgcagggataaacacacggaggcgagtgatcggtaccgggctgaggtgttagctaatgatgagtacgtatgaggcaggatgagtgacccgatgaggctagatgcgatggatggatcgatgatcgatgcatggtgatgcgatgctagatgatgtgtgtcagtaagtaagcgatgcggctgctgagagcgtaggcccgagaggagagatgtaggaggaaggtttgatggtagttgtagatgattgtgtagttgtagctgatagtgatgatcgtag.,通过对生物数据的分析可以获得基因序列中所包含的有机体的大量重要信息,分子生物学是一门信息科学。-LeroyHood,ISB,生物信息的海量性,近20年来，分子生物学发展的一个显著特点是生物信息的剧烈膨胀，且迅速形成了巨量的生物信息库。近年来GenBank中的DNA碱基数目呈指数增加，大约每14个月增加一倍。到1999年12月其数目已达30亿，它们来自47000种生物。2000年4月DNA碱基数目是60亿。2001年初这一数目已达110亿。预计2005年达到300亿。各种生物的EST序列已达600多万条，其中人类的EST序列已超过300万条，估计覆盖人类基因90以上；UniGene的数目约达7万个；自1999年初单核苷酸多态性(SNPs,SingleNucleotidePolymorphisms)数据库出现以来，到2000年3月20日SNP的总数是26569，现在已超过350万,计算机运算速度:18个月增长一倍;DNA序列数据:14个月增长一倍;,生物数据库的增长,遍布世界各地研究实验室的高通量大型测序仪在日夜不停地运转，每天都有成千上万的数据被源源不断地输入相应的生物信息库中。同时，由这些原始数据分析加工而来的蛋白质结构等数据信息也被世界各地的分子生物学、生物信息学等学科领域专家输入二级数据库中。,3*10910,000books1book100pages1page3,000charactersCCGGTCTCCCCGCCCGCGCGCGAAGTAAAGGCCCAGCGCAGCCCGCGCTCCTGCCCTGGGGCCTCGTCTTTCTCCAGGAAAACGTGGACCGCTCTCCGCCGACAGTCTCTTCCACAGACCCCTGTCGCCTTCGCCCCCCGGTCTCTTCCGGTTCTGTCTTTTCGCTGGCTCGATACGAACAAGGAAGTCGCCCCCAGCGAGCCCCGGCTCCCCCAGGCAGAGGCGGCCCCGGGGGCGGAGTCAACGGCGGAGGCACGCCCTCTGTGAAAGGGCGGGGCATGCAAATTCGAAATGAAAGCCCGGGAACGCCGAAGAAGCACGGGTGTAAGATTTCCCTTTTCAAAGGCGGGAGAATAAGAAATCAGCCCGAGAGTGTAAGGGCGTCAATAGCGCTGTGGACGAGACAGAGGGAATGGGGCAAGGAGCGAGGCTGGGGCTCTCACCGCGACTTGAATGTGGATGAGAGTGGGACGGTGACGGCGGGCGCGAAGGCGAGCGCATCGCTTCTCGGCCTTTTGGCTAAGATCAAGTGTAGTATCTGTTCTTATCAGTTTAATATCTGATACGTCCTCTATCCGAGGACAATATATTAAATGGATTGATCAATCCGCTTCAGCCTCCCGAGTAGCTGGGACTACAGACGGTGCCATCACGCCCAGCTCATTGTTGATTCCCGCCCCCTTGGTAGAGACGGGATTCCGCTATATTGCCTGGGCTGGTGTCGAACTCATAGAACAAAGGATCCTCCCTCCTGGGCCTGGGCGTGGGCTCGCAAAACGCTGGGATTCCCGGATTACAGGCGGGCGCACCACACCAGGAGCAAACACTTCCGGTTTTAAAAATTCAGTTTGTGATTGGCTGTCATTCAGTATTATGCTAATTAAGCATGCCCGGTTTTAAACCTCTTAAAACAACTTTTAAAATTACCTTTCCACCTAAAACGTTAAAATTTGTCAAGTGATAATATTCGACAAGCTGTTATTGCCAAACTATTTTCCTATTTGTTTCCTAATGGCATCGGAACTAGCGAAAGTTTCTCGCCATCAGTTAAAAGTTTGCGGCAGATGTAGACCTAGCAGAGGTGTGCGAGGAGGCCGTTAAGACTATACTTTCAGGGATCATTTCTATAGTGTGTTACTAGAGAAGTTTCTCTGAACGTGTAGAGCACCGAAAACCACGAGGAAGAGAGGTAGCGTTTTCATCGGGTTACCTAAGTGCAGTGTCCCCCCTGGCGCGCAATTGGGAACCCCACACGCGGTGTAGAAATATATTTTAAGGGCGCG(1250characters)关键是先要从一个个序列片段中得到这本天书,破译人类遗传密码就要读懂由30亿符号组成的100万页的“天书”,怎么办,Mygod!好多数据啊！,CCGGTCTCCCCGCCCGCGCGCGAAGTAAAGGCCCAGCGCAGCCCGCGCTCCTGCCCTGGGGCCTCGTCTTTCTCCAGGAAAACGTGGACCGCTCTCCGCCGACAGTCTCTTCCACAGACCCCTGTCGCCTTCGCCCCCCGGTCTCTTCCGGTTCTGTCTTTTCGCTGGCTCGATACGAACAAGGAAGTCGCCCCCAGCGAGCCCCGGCTCCCCCAGGCAGAGGCGGCCCCGGGGGCGGAGTCAACGGCGGAGGCACGCCCTCTGTGAAAGGGCGGGGCATGCAAATTCGAAATGAAAGCCCGGGAACGCCGAAGAAGCACGGGTGTAAGATTTCCCTTTTCAAAGGCGGGAGAATAAGAAATCAGCCCGAGAGTGTAAGGGCGTCAATAGCGCTGTGGACGAGACAGAGGGAATGGGGCAAGGAGCGAGGCTGGGGCTCTCACCGCGACTTGAATGTGGATGAGAGTGGGACGGTGACGGCGGGCGCGAAGGCGAGCGCATCGCTTCTCGGCCTTTTGGCTAAGATCAAGTGTAGTATCTGTTCTTATCAGTTTAATATCTGATACGTCCTCTATCCGAGGACAATATATTAAATGGATTGATCAATCCGCTTCAGCCTCCCGAGTAGCTGGGACTACAGACGGTGCCATCACGCCCAGCTCATTGTTGATTCCCGCCCCCTTGGTAGAGACGGGATTCCGCTATATTGCCTGGGCTGGTGTCGAACTCATAGAACAAAGGATCCTCCCTCCTGGGCCTGGGCGTGGGCTCGCAAAACGCTGGGATTCCCGGATTACAGGCGGGCGCACCACACCAGGAGCAAACACTTCCGGTTTTAAAAATTCAGTTTGTGATTGGCTGTCATTCAGTATTATGCTAATTAAGCATGCCCGGTTTTAAACCTCTTAAAACAACTTTTAAAATTACCTTTCCACCTAAAACGTTAAAATTTGTCAAGTGATAATATTCGACAAGCTGTTATTGCCAAACTATTTTCCTATTTGTTTCCTAATGGCATCGGAACTAGCGAAAGTTTCTCGCCATCAGTTAAAAGTTTGCGGCAGATGTAGACCTAGCAGAGGTGTGCGAGGAGGCCGTTAAGACTATACTTTCAGGGATCATTTCTATAGTGTGTTACTAGAGAAGTTTCTCTGAACGTGTAGAGCACCGAAAACCACGAGGAAGAGAGGTAGCGTTTTCATCGGGTTACCTAAGTGCAGTGTCCCCCCTGGCGCGCAATTGGGAACCCCACACGCGGTGTAGAAATATATTTTAAGGGCGCG,生物信息学在生物信息的急剧膨胀的压力下诞生。一般意义上，生物信息学是研究生物信息的采集、处理、存储、传播、分析和解释等各方面的一门学科，它通过综合利用生物学、计算机科学和信息技术揭示大量而复杂的生物数据所赋有的生物学奥秘。,生物信息学的定义,生物信息学的研究,以核酸蛋白质等生物大分子为主要研究对象以信息、数理、计算机科学为主要研究手段以计算机网络为主要研究环境以计算机软件为主要研究工具对序列数据进行存储、管理、注释、加工对各种数据库进行查询、搜索、比较、分析构建各种类型的专用数据库信息系统研究开发面向生物学家的新一代计算机软件,生物信息学研究方向,基因组序列装配基因识别基因功能预报基因多态性分析基因进化mRNA结构预测基因芯片设计基因芯片数据分析疾病相关基因分析,蛋白质序列分析蛋白质家族分类蛋白质结构预测蛋白质折叠研究代谢途径分析转录调控机制蛋白质芯片设计蛋白质芯片数据分析药物设计,生物信息学研究方法,利用数理统计、模式识别、动态规划、密码解读、语意解析、信令传递、神经网络、遗传算法以及隐马氏模型等各种方法对序列、结构数据进行定性和定量分析，从中获取基因编码、基因调控、序列-结构-功能关系等理性知识阐明细胞、器官和个体的发生、发育、病变、衰亡的基本规律和时空联系探索生命起源、生物进化、生命本质等重大理论问题，最终建立“生物学周期表”,生物信息学热点问题（1）,基因组时期：序列结构功能DNA测序和拼接分子生物数据库序列比对分子进化蛋白质质谱鉴定序列注释：基因预测、细胞定位结构预测：RNA结构预测、蛋白质折叠。,生物信息学热点问题（2）,后基因组时期：相互作用网络功能生物芯片（DNA芯片、蛋白质芯片）相互作用网络调控网络药物设计。,热点：DNA测序和拼接,鸟枪法(Shotgun)测序：得到DNA片断,基因组,forward-reverselinkedreads,序列拼接：将片断拼接为完整基因组,基因组,全基因组Shotgun拼接,比较片段集合中所有的片段对,获得可能存在的重叠部分(Overlap)建立所有片段的相互组合关系(Layout),以片段为顶点,重叠的片段相互连接，构成图,Phrap算法,Phrap算法最后一步是定义有向代权图,并在图中找出一条最佳路径,使得这条路径经过每个顶点恰好一次Hamiltonian路径问题,Euler算法,建立所有片段的相互关系,即构造deBrujin图.以每个片段为图中的线,重复片段则相当于用胶水胶在一块,用统一的一条线来表示叠放重复片断将重复片断看作一个,拼接成长序列,即找出一条欧拉路线,使得此路径经过每一条线恰好一次Eulerian路径问题,序列拼接问题可以转换为Hamiltonian路径问题Eulerian路径问题,转换为计算问题,热点：生物信息数据库,DNA序列：A、C、G、T组成的字符串,atggcaattaaaattggtatcaatggttttggtcgtatcggccgtatcgtattccgtgcagcacaacaccgtgatgacattgaagttgtaggtattaacgacttaatcgacgttgaatacatggcttatatgttgaaatatgattcaactcacggtcgtttcgacggcactgttgaagtgaaagatggtaacttagtggttaatggtaaaactatccgtgtaactgcagaacgtgatccagcaaacttaaactggggtgcaatcggtgttgatatcgctgttgaagcgactggtttattcttaactgatgaaactgctcgtaaacatatcactgcaggcgcaaaaaaagttgtattaactggcccatctaaagatgcaacccctatgttcgttcgtggtgtaaacttcaacgcatacgcaggtcaagatatcgtttctaacgcatcttgtacaacaaactgtttagctcctttagcacgtgttgttcatgaaactttcggtatcaaagatggtttaatgaccactgttcacgcaacgactgcaactcaaaaaactgtggatggtccatcagctaaagactggcgcggcggccgcggtgcatcacaaaacatcattccatcttcaacaggtgcagcgaaagcagtaggtaaagtattacctgcattaaacggtaaattaactggtatggctttccgtgttccaacgccaaacgtatctgttgttgatttaacagttaatcttgaaaaaccagcttcttatgatgcaatcaaacaagcaatcaaagatgcagcggaaggtaaaacgttcaatggcgaattaaaaggcgtattaggttacactgaagatgctgttgtttctactgacttcaacggttgtgctttaacttctgtatttgatgcagacgctggtatcgcattaactgattctttcgttaaattggtatc.caaaaatagggttaatatgaatctcgatctccattttgttcatcgtattcaacaacaagccaaaactcgtacaaatatgaccgcacttcgctataaagaacacggcttgtggcgagatatctcttggaaaaactttcaagagcaactcaatcaactttctcgagcattgcttgctcacaatattgacgtacaagataaaatcgccatttttgcccataatatggaacgttgggttgttcatgaaactttcggtatcaaagatggtttaatgaccactgttcacgcaacgactacaatcgttgacattgcgaccttacaaattcgagcaatcacagtgcctatttacgcaaccaatacagcccagcaagcagaatttatcctaaatcacgccgatgtaaaaattctcttcgtcggcgatcaagagcaatacgatcaaacattggaaattgctcatcattgtccaaaattacaaaaaattgtagcaatgaaatccaccattcaattacaacaagatcctctttcttgcacttgg,蛋白质序列：20种氨基酸构成的序列（A、R、N、D、C、Q、E、G、H、I、L、K、M、F、P、S、T、W、Y和V）,庞大的数据信息需要数据库保存,DNA数据库EMBLGenBankDDBJ蛋白质数据库SWISS-PROTPIRPDB,热点：序列比对,用于同源查找：从不同的生物中找到相似之处人类vs.老鼠vs.酵母(以下数据来自NCBI疾病数据库),BestSequenceSimilarityMatchestoDateBetweenPositionallyClonedHumanGenesandS.cerevisiaeProteinsHumanDiseaseMIM#HumanGenBankBLASTXYeastGenBankYeastGeneGeneAcc#forP-valueGeneAcc#forDescriptionHumancDNAYeastcDNAHereditaryNon-polyposisColonCancer120436MSH2U039119.2e-261MSH2M84170DNArepairproteinHereditaryNon-polyposisColonCancer120436MLH1U074186.3e-196MLH1U07187DNArepairproteinCysticFibrosis219700CFTRM286681.3e-167YCF1L35237MetalresistanceproteinWilsonDisease277900WNDU117005.9e-161CCC2L36317ProbablecoppertransporterGlycerolKinaseDeficiency307030GKL139431.8e-129GUT1X69049GlycerolkinaseBloomSyndrome210900BLMU398172.6e-119SGS1U22341HelicaseAdrenoleukodystrophy,X-linked300100ALDZ218763.4e-107PXA1U17065PeroxisomalABCtransporterAtaxiaTelangiectasia208900ATMU264552.8e-90TEL1U31331PI3kinaseAmyotrophicLateralSclerosis105400SOD1K000652.0e-58SOD1J03279SuperoxidedismutaseMyotonicDystrophy160900DML192685.4e-53YPK1M21307Serine/threonineproteinkinaseLoweSyndrome309000OCRLM881621.2e-47YIL002CZ47047PutativeIPP-5-phosphataseNeurofibromatosis,Type1162200NF1M899142.0e-46IRA2M33779InhibitoryregulatorproteinChoroideremia303100CHMX781212.1e-42GDI1S69371GDPdissociationinhibitorDiastrophicDysplasia222600DTDU145287.2e-38SUL1X82013SulfatepermeaseLissencephaly247200LIS1L133851.7e-34MET30L26505MethioninemetabolismThomsenDisease160800CLC1Z258847.9e-31GEF1Z23117Voltage-gatedchloridechannelWilmsTumor194070WT1X516301.1e-20FZF1X67787SulphiteresistanceproteinAchondroplasia100800FGFR3M580512.0e-18IPL1U07163Serine/threoinineproteinkinaseMenkesSyndrome309400MNKX692082.1e-17CCC2L36317Probablecoppertransporter,序列比对的意义,在生物学的研究中，将未知序列同已知序列进行比较分析已经成为一种强有力的研究手段，生物学领域中绝大部分的问题在计算机科学领域中主要体现为序列或字符串的问题。,两条序列之间的比对,计算机科学当中已经有比较成熟的串问题的算法,-AGGCTATCACCTGACCTCCAGGCCGA-TGCCC-TAG-CTATCAC-GACCGC-GGTCGATTTGCCCGAC,AGGCTATCACCTGACCTCCAGGCCGATGCCCTAGCTATCACGACCGCGGTCGATTTGCCCGAC,分子的动态模拟,代谢途径模拟,计算在生物问题中的角色,证实/新数据,合理设计,数据挖掘,.计算扮演一个十分重要的角色.,生物信息学中的几个计算问题,举例：VertexcovermotiffindingDSSP(DistinguishingStringSelectionProblems),一、Vertexcover,DNAsequencesA,G,T,C代表四个DNA的基本元素105个互不相同的DNA序列,GATTCCAGT,Given(here,n=105)DNAsequences,canyoufind60ofthemwhoseremovemakestheremainingsequencesconsistent?问题：105个基因序列中,只去掉60个,使得剩下的序列相似.,模型：作一个图，每个DNA串是图中的一个点。两个串比较，不相同的话加一条边进行连接，每条边对应两个不同的DNA。移除边上的任意一点相当于删除这条边。这个图上的信息量可以用计算机来计算，大约为10万的平方。在图中找到60个点后就没有边了，系统可用如果超过60个点还有边，系统不可用,问题等价于：Giveagraph,canyoufind60verticeswhoseremovemakesthegraphhasnoedge?Vertexcover(点覆盖):Giveagraph,canyoufindkverticessuchthateachedgehasatleastoneendinthesekvertices?另一种说法：GiveagraphGofnvertices,decideiftherearekverticeswhoseremovemakesthegraphedgeless.,Tryanysubsetof60verticesandcheckifitmakeavertexcover(点覆盖)图中每60个点拿出来试一试：若n比60大得多，n60实际中无法使用，需要对它进行改进。(notsolvablepractically)-NP-hard,(2)motiffinding,医学上的问题：已知几个串中有癌症细胞，要求从中找出这几个串它们的共性，也即是说，寻找一个子串，在每个串（或是大部分串）中都出现。子串相似性的定义：在串中间插、删、改的次数不超过6次，使得两个子串相同。表示相似的子串k20，每个串长度为2000,序列模体(Motif),（15，6）模型的问题：查找一个长度为15的子串，使得它在所有的20个串中都存在，（允许存在6个误差）。GivekDNAsequences,findapatternoflength15thatissimilartoasubsequenceineachsequence.,Giveak-partilegraph,findasetofvertices,onefromeachrow,suchthatallthesekverticesareconnected.（最大团）计算量为nk=200020-NP-hard!改进：n5Xn5=n102n10=4n5n5Xn5=n10,5行n55行,5行n55行,是不是什么问题都是单计算机可解的？,例一：求图G的最小顶点覆盖问题：问题描述：无向图G=(V,E)的顶点覆盖是它的顶点集V的一个子集VV，使得若(u,v)是G的一条边，则vV或uV。顶点覆盖V的大小是它所包含的顶点个数|V|。,算法：/给定图G=,其中|V|=n，|E|=m第一步：枚举出V中所有的子集：子集总数=(n1)+(n2)+(n3)+(nn)=2n,第二步：判断每个子集是否是图G的顶点覆盖：fori=1tomdo,算法时间复杂性：O(2n*m)可计算否？,例:,假设n=56,在一台运行速度为亿次级每秒的计算机里用枚举法求解VC问题，须花时多少？,计算：我们假设该机器每秒钟可判断一亿种的方案是否正确！则有：256种方案/1亿种每秒/60/60/24/365=22.85(年)！,结论：对于O(2n)的算法，当n足够大时，全世界现有的计算机都无法在可接受的时间内求解。,是不是什么问题都是并行计