计算机的计算能力.ppt

计算机的计算能力-以生物信息学为例 李绍华 信息学院计算机科学与技术系信息学院计算机科学与技术系 20世纪三个重大的科技工程：世纪三个重大的科技工程：1.曼哈顿计划（原子弹研制）2.阿波罗登月计划3.人类基因组计划（HGP）：美英法德日中六国Human Gene Program的目的：完成人基因组24条染色体上5万左右基因的作图和30亿碱基的DNA全序列的测定。得到以下数据：遗传图、物理图、全序列图。可定位与疾病有关的基因新药设计和疫苗制备。基因中包含了人类的遗传密码；基因测序的完成，基因中包含了人类的遗传密码；基因测序的完成，意味着密码已意味着密码已“偷到偷到”，可这个密码里写的是什么，可这个密码里写的是什么呢？呢？l 生物信息学l 研究热点l 计算问题l 研究思路ccgtacgtacgtagagtgctagtctagtcgtagcgccgtagtcgatcgtgtgggtagtagctgatatgatgcgaggtaggggataggatagcaacagatgagcggatgctgagtgcagtggcatgcgatgtcgatgatagcggtaggtagacttcgcgcataaagctgcgcgagatgattgcaaagragttagatgagctgatgctagaggtcagtgactgatgatcgatgcatgcatggatgatgcagctgatcgatgtagatgcaataagtcgatgatcgatgatgatgctagatgatagctagatgtgatcgatggtaggtaggatggtaggtaaattgatagatgctagatcgtaggtagtagctagatgcagggataaacacacggaggcgagtgatcggtaccgggctgaggtgttagctaatgatgagtacgtatgaggcaggatgagtgacccgatgaggctagatgcgatggatggatcgatgatcgatgcatggtgatgcgatgctagatgatgtgtgtcagtaagtaagcgatgcggctgctgagagcgtaggcccgagaggagagatgtaggaggaaggtttgatggtagttgtagatgattgtgtagttgtagctgatagtgatgatcgtag基因序列中包含着有机体的大量信息gcgtacgtacgtagagtgctagtctagtcgtagcgccgtagtcgatcgtgtgggtagtagctgatatgatgcgaggtaggggataggatagcaacagatgagcggatgctgagtgcagtggcatgcgatgtcgatgatagcggtaggtagacttcgcgcataaagctgcgcgagatgattgcaaagragttagatgagctgatgctagaggtcagtgactgatgatcgatgcatgcatggatgatgcagctgatcgatgtagatgcaataagtcgatgatcgatgatgatgctagatgatagctagatgtgatcgatggtaggtaggatggtaggtaaattgatagatgctagatcgtaggtagtagctagatgcagggataaacacacggaggcgagtgatcggtaccgggctgaggtgttagctaatgatgagtacgtatgaggcaggatgagtgacccgatgaggctagatgcgatggatggatcgatgatcgatgcatggtgatgcgatgctagatgatgtgtgtcagtaagtaagcgatgcggctgctgagagcgtaggcccgagaggagagatgtaggaggaaggtttgatggtagttgtagatgattgtgtagttgtagctgatagtgatgatcgtag.通过对生物数据的分析可以获得基因序列中所包含的有机体的大量重要信息分子生物学是一门信息科学分子生物学是一门信息科学分子生物学是一门信息科学分子生物学是一门信息科学 。-Leroy Hood,ISBLeroy 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年初单核苷酸多态性(SNPsSNPs,Single Nucleotide Polymorphisms)数据库出现以来，到2000年3月20日SNP的总数是26569，现在已超过350万计算机运算速度计算机运算速度计算机运算速度计算机运算速度:18:18个月增长一倍个月增长一倍个月增长一倍个月增长一倍;DNADNA序列数据序列数据序列数据序列数据:14:14个月增长一倍个月增长一倍个月增长一倍个月增长一倍;生物数据库的增长l遍布世界各地研究实验室的高通量大型测序仪在日夜不停地运转，每天都有成千上万的数据被源源不断地输入相应的生物信息库中。同时，由这些原始数据分析加工而来的蛋白质结构等数据信息也被世界各地的分子生物学、生物信息学等学科领域专家输入二级数据库中。3*10910,000books1book100pages1page3,000charactersCCGGTCTCCCCGCCCGCGCGCGAAGTAAAGGCCCAGCGCAGCCCGCGCTCCTGCCCTGGGGCCTCGTCTTTCTCCAGGAAAACGTGGACCGCTCTCCGCCGACAGTCTCTTCCACAGACCCCTGTCGCCTTCGCCCCCCGGTCTCTTCCGGTTCTGTCTTTTCGCTGGCTCGATACGAACAAGGAAGTCGCCCCCAGCGAGCCCCGGCTCCCCCAGGCAGAGGCGGCCCCGGGGGCGGAGTCAACGGCGGAGGCACGCCCTCTGTGAAAGGGCGGGGCATGCAAATTCGAAATGAAAGCCCGGGAACGCCGAAGAAGCACGGGTGTAAGATTTCCCTTTTCAAAGGCGGGAGAATAAGAAATCAGCCCGAGAGTGTAAGGGCGTCAATAGCGCTGTGGACGAGACAGAGGGAATGGGGCAAGGAGCGAGGCTGGGGCTCTCACCGCGACTTGAATGTGGATGAGAGTGGGACGGTGACGGCGGGCGCGAAGGCGAGCGCATCGCTTCTCGGCCTTTTGGCTAAGATCAAGTGTAGTATCTGTTCTTATCAGTTTAATATCTGATACGTCCTCTATCCGAGGACAATATATTAAATGGATTGATCAATCCGCTTCAGCCTCCCGAGTAGCTGGGACTACAGACGGTGCCATCACGCCCAGCTCATTGTTGATTCCCGCCCCCTTGGTAGAGACGGGATTCCGCTATATTGCCTGGGCTGGTGTCGAACTCATAGAACAAAGGATCCTCCCTCCTGGGCCTGGGCGTGGGCTCGCAAAACGCTGGGATTCCCGGATTACAGGCGGGCGCACCACACCAGGAGCAAACACTTCCGGTTTTAAAAATTCAGTTTGTGATTGGCTGTCATTCAGTATTATGCTAATTAAGCATGCCCGGTTTTAAACCTCTTAAAACAACTTTTAAAATTACCTTTCCACCTAAAACGTTAAAATTTGTCAAGTGATAATATTCGACAAGCTGTTATTGCCAAACTATTTTCCTATTTGTTTCCTAATGGCATCGGAACTAGCGAAAGTTTCTCGCCATCAGTTAAAAGTTTGCGGCAGATGTAGACCTAGCAGAGGTGTGCGAGGAGGCCGTTAAGACTATACTTTCAGGGATCATTTCTATAGTGTGTTACTAGAGAAGTTTCTCTGAACGTGTAGAGCACCGAAAACCACGAGGAAGAGAGGTAGCGTTTTCATCGGGTTACCTAAGTGCAGTGTCCCCCCTGGCGCGCAATTGGGAACCCCACACGCGGTGTAGAAATATATTTTAAGGGCGCG(1250characters)关键是先要从一个个序列片段中得到这本天书破译人类遗传密码就要读懂由30亿符号组成的100万页的“天书”怎么怎么办办My god!好好多数据啊！多数据啊！CCGGTCTCCCCGCCCGCGCGCGAAGTAAAGGCCCAGCGCAGCCCGCGCTCCTGCCCTGGGGCCTCGTCTTTCTCCAGGAAAACGTGGACCGCTCTCCGCCGACAGTCTCTTCCACAGACCCCTGTCGCCTTCGCCCCCCGGTCTCTTCCGGTTCTGTCTTTTCGCTGGCTCGATACGAACAAGGAAGTCGCCCCCAGCGAGCCCCGGCTCCCCCAGGCAGAGGCGGCCCCGGGGGCGGAGTCAACGGCGGAGGCACGCCCTCTGTGAAAGGGCGGGGCATGCAAATTCGAAATGAAAGCCCGGGAACGCCGAAGAAGCACGGGTGTAAGATTTCCCTTTTCAAAGGCGGGAGAATAAGAAATCAGCCCGAGAGTGTAAGGGCGTCAATAGCGCTGTGGACGAGACAGAGGGAATGGGGCAAGGAGCGAGGCTGGGGCTCTCACCGCGACTTGAATGTGGATGAGAGTGGGACGGTGACGGCGGGCGCGAAGGCGAGCGCATCGCTTCTCGGCCTTTTGGCTAAGATCAAGTGTAGTATCTGTTCTTATCAGTTTAATATCTGATACGTCCTCTATCCGAGGACAATATATTAAATGGATTGATCAATCCGCTTCAGCCTCCCGAGTAGCTGGGACTACAGACGGTGCCATCACGCCCAGCTCATTGTTGATTCCCGCCCCCTTGGTAGAGACGGGATTCCGCTATATTGCCTGGGCTGGTGTCGAACTCATAGAACAAAGGATCCTCCCTCCTGGGCCTGGGCGTGGGCTCGCAAAACGCTGGGATTCCCGGATTACAGGCGGGCGCACCACACCAGGAGCAAACACTTCCGGTTTTAAAAATTCAGTTTGTGATTGGCTGTCATTCAGTATTATGCTAATTAAGCATGCCCGGTTTTAAACCTCTTAAAACAACTTTTAAAATTACCTTTCCACCTAAAACGTTAAAATTTGTCAAGTGATAATATTCGACAAGCTGTTATTGCCAAACTATTTTCCTATTTGTTTCCTAATGGCATCGGAACTAGCGAAAGTTTCTCGCCATCAGTTAAAAGTTTGCGGCAGATGTAGACCTAGCAGAGGTGTGCGAGGAGGCCGTTAAGACTATACTTTCAGGGATCATTTCTATAGTGTGTTACTAGAGAAGTTTCTCTGAACGTGTAGAGCACCGAAAACCACGAGGAAGAGAGGTAGCGTTTTCATCGGGTTACCTAAGTGCAGTGTCCCCCCTGGCGCGCAATTGGGAACCCCACACGCGGTGTAGAAATATATTTTAAGGGCGCG生物信息学生物信息学在生物信息的急剧膨胀的压力下诞生。一般意义上，生物信息学是研究生物信息的采集、处理、存储、传播、分析和解释等各方面的一门学科，它通过综合利用生物学、计算机科学和信息技术揭示大量而复杂的生物数据所赋有的生物学奥秘。生物信息学的定义生物信息学的研究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 dist500 bp500 bp序列拼接：将片断拼接为完整基因组DNA片断（Reads）基因组全基因组Shotgun拼接1.找重叠找重叠 reads4.最后推导出一致的序列最后推导出一致的序列.ACGATTACAATAGGTT.2.把重叠把重叠reads合并成合并成 contigs3.把把contigs 连接起来形成连接起来形成 supercontigsl比较片段集合比较片段集合中所有的片段中所有的片段对对,获得可能存获得可能存在的重叠部分在的重叠部分(Overlap)(Overlap)l建立所有片段建立所有片段的相互组合关的相互组合关系系(Layout),(Layout),以以片段为顶点片段为顶点,重重叠的片段相互叠的片段相互连接，构成图连接，构成图Phrap算法Phrap 算法最后一步是定义有向代权图,并在图中找出一条最佳路径,使得这条路径经过每个顶点恰好一次Hamiltonian 路径问题Euler 算法算法l建立所有片段的相互关系,即构造deBrujin 图.以每个片段为图中的线,重复片段则相当于用胶水胶在一块,用统一的一条线来表示 叠放重复片断 将重复片断看作一个拼接成长序列,即找出一条欧拉路线,使得此路径经过每一条线恰好一次Eulerian路径问题l序列拼接问题可以转换为Hamiltonian 路径问题Eulerian 路径问题转换为计算问题热点：生物信息数据库lDNA序列：A、C、G、T组成的字符串atggcaattaaaattggtatcaatggttttggtcgtatcggccgtatcgtattccgtgcagcacaacaccgtgatgacattgaagttgtaggtattaacgacttaatcgacgttgaatacatggcttatatgttgaaatatgattcaactcacggtcgtttcgacggcactgttgaagtgaaagatggtaacttagtggttaatggtaaaactatccgtgtaactgcagaacgtgatccagcaaacttaaactggggtgcaatcggtgttgatatcgctgttgaagcgactggtttattcttaactgatgaaactgctcgtaaacatatcactgcaggcgcaaaaaaagttgtattaactggcccatctaaagatgcaacccctatgttcgttcgtggtgtaaacttcaacgcatacgcaggtcaagatatcgtttctaacgcatcttgtacaacaaactgtttagctcctttagcacgtgttgttcatgaaactttcggtatcaaagatggtttaatgaccactgttcacgcaacgactgcaactcaaaaaactgtggatggtccatcagctaaagactggcgcggcggccgcggtgcatcacaaaacatcattccatcttcaacaggtgcagcgaaagcagtaggtaaagtattacctgcattaaacggtaaattaactggtatggctttccgtgttccaacgccaaacgtatctgttgttgatttaacagttaatcttgaaaaaccagcttcttatgatgcaatcaaacaagcaatcaaagatgcagcggaaggtaaaacgttcaatggcgaattaaaaggcgtattaggttacactgaagatgctgttgtttctactgacttcaacggttgtgctttaacttctgtatttgatgcagacgctggtatcgcattaactgattctttcgttaaattggtatc.caaaaatagggttaatatgaatctcgatctccattttgttcatcgtattcaacaacaagccaaaactcgtacaaatatgaccgcacttcgctataaagaacacggcttgtggcgagatatctcttggaaaaactttcaagagcaactcaatcaactttctcgagcattgcttgctcacaatattgacgtacaagataaaatcgccatttttgcccataatatggaacgttgggttgttcatgaaactttcggtatcaaagatggtttaatgaccactgttcacgcaacgactacaatcgttgacattgcgaccttacaaattcgagcaatcacagtgcctatttacgcaaccaatacagcccagcaagcagaatttatcctaaatcacgccgatgtaaaaattctcttcgtcggcgatcaagagcaatacgatcaaacattggaaattgctcatcattgtccaaaattacaaaaaattgtagcaatgaaatccaccattcaattacaacaagatcctctttcttgcacttggl蛋白质序列：20种氨基酸构成的序列（A、R、N、D、C、Q、E、G、H、I、L、K、M、F、P、S、T、W、Y和V）庞大的数据信息需要数据库保存lDNA数据库EMBLGenBankDDBJl蛋白质数据库SWISS-PROTPIRPDB热点：序列比对l用于同源查找：从不同的生物中找到相似之处l人类 vs.老鼠 vs.酵母(以下数据来自NCBI 疾病数据库)Best Sequence Similarity Matches to Date Between Positionally ClonedHuman Genes and S.cerevisiae ProteinsHuman 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 proteinHereditary Non-polyposis Colon Cancer 120436 MLH1 U07418 6.3e-196 MLH1 U07187 DNA repair proteinCystic Fibrosis 219700 CFTR M28668 1.3e-167 YCF1 L35237 Metal resistance proteinWilson Disease 277900 WND U11700 5.9e-161 CCC2 L36317 Probable copper transporterGlycerol Kinase Deficiency 307030 GK L13943 1.8e-129 GUT1 X69049 Glycerol kinaseBloom Syndrome 210900 BLM U39817 2.6e-119 SGS1 U22341 HelicaseAdrenoleukodystrophy,X-linked 300100 ALD Z21876 3.4e-107 PXA1 U17065 Peroxisomal ABC transporterAtaxia Telangiectasia 208900 ATM U26455 2.8e-90 TEL1 U31331 PI3 kinaseAmyotrophic Lateral Sclerosis 105400 SOD1 K00065 2.0e-58 SOD1 J03279 Superoxide dismutaseMyotonic Dystrophy 160900 DM L19268 5.4e-53 YPK1 M21307 Serine/threonine protein kinaseLowe Syndrome 309000 OCRL M88162 1.2e-47 YIL002C Z47047 Putative IPP-5-phosphataseNeurofibromatosis,Type 1 162200 NF1 M89914 2.0e-46 IRA2 M33779 Inhibitory regulator proteinChoroideremia 303100 CHM X78121 2.1e-42 GDI1 S69371 GDP dissociation inhibitorDiastrophic Dysplasia 222600 DTD U14528 7.2e-38 SUL1 X82013 Sulfate permeaseLissencephaly 247200 LIS1 L13385 1.7e-34 MET30 L26505 Methionine metabolismThomsen Disease 160800 CLC1 Z25884 7.9e-31 GEF1 Z23117 Voltage-gated chloride channelWilms Tumor 194070 WT1 X51630 1.1e-20 FZF1 X67787 Sulphite resistance proteinAchondroplasia 100800 FGFR3 M58051 2.0e-18 IPL1 U07163 Serine/threoinine protein kinaseMenkes Syndrome 309400 MNK X69208 2.1e-17 CCC2 L36317 Probable copper transporter序列比对的意义l在生物学的研究中，将未知序列同已知序列进行比较分析已经成为一种强有力的研究手段，生物学领域中绝大部分的问题在计算机科学领域中主要体现为序列或字符串的问题。如果两个序列具有足够的相似性，如果两个序列具有足够的相似性，则认为两者具有同源性。则认为两者具有同源性。两条序列之间的比对计算机科学当中已经有比较成熟的串问题的算法-AGGCTATCACCTGACCTCCAGGCCGA-TGCCC-TAG-CTATCAC-GACCGC-GGTCGATTTGCCCGACAGGCTATCACCTGACCTCCAGGCCGATGCCCTAGCTATCACGACCGCGGTCGATTTGCCCGAC分子的动态模拟分子的动态模拟代谢途径模拟代谢途径模拟计算在生物问题中的角色实验产生的庞大生物数据计算实验专业领域知识理论模型或假说证实/新数据合理设计数据挖掘.计算扮演一个十分重要的角色.生物信息学中的几个计算问题l举例：VertexcovermotiffindingDSSP(DistinguishingStringSelectionProblems)一、一、Vertex coverlDNAsequencesA,G,T,C代表四个DNA的基本元素105个互不相同的DNA序列G A T T C C A G TlGiven(here,n=105)DNAsequences,canyoufind60ofthemwhoseremovemakestheremainingsequencesconsistent?l问题：105个基因序列中,只去掉60个,使得剩下的序列相似.l模型：作一个图，每个DNA串是图中的一个点。两个串比较，不相同的话加一条边进行连接，每条边对应两个不同的DNA。移除边上的任意一点相当于删除这条边。这个图上的信息量可以用计算机来计算，大约为10万的平方。在图中找到60个点后就没有边了，系统可用如果超过60个点还有边，系统不可用l问题等价于：Giveagraph,canyoufind60verticeswhoseremovemakesthegraphhasnoedge?lVertexcover(点覆盖):Giveagraph,canyoufindkverticessuchthateachedgehasatleastoneendinthesekvertices?l另一种说法：lGiveagraphGofnvertices,decideiftherearekverticeswhoseremovemakesthegraphedgeless.lTryanysubsetof60verticesandcheckifitmakeavertexcover(点覆盖)l图中每60个点拿出来试一试：若n比60大得多，n60实际中无法使用，需要对它进行改进。(notsolvablepractically)-NP-hard(2)motif finding医学上的问题：已知几个串中有癌症细胞，要求从中找出这几个串它们的共性，也即是说，寻找一个子串，在每个串（或是大部分串）中都出现。l子串相似性的定义：在串中间插、删、改的次数不超过6次，使得两个子串相同。表示相似的子串 k20，每个串长度为2000 序列模体(Motif)TGTGAAAGACTGTTTTTTTGATCGTTTTGACAAAAATGGAAGTCCACAAAGTCCACATTGATTATTTGCACGGCGTCACACTTTGCTATCCCATAGTGATGTACTGCATGTATGCAAAGGACGTCAGATTACCGTGCAGTACAGTAAACGATTCCACTAATTTATTCCATGTCACTCTTTTCGCATCTTTGTACATTACCGCCAATTCTGTAACAGAGATCACACAAAGCGACGGTGGGGACTTTTTTTTCATATGCCTGACGGAGTTGACACTTGTAAGTTTTCAACPevzner-Sze,ISMB2000 l（15，6）模型的问题：查找一个长度为15的子串，使得它在所有的20个串中都存在，（允许存在6个误差）。lGivekDNAsequences,findapatternoflength15thatissimilartoasubsequenceineachsequence.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(年)！结论：对于O(2n)的算法，当n足够大时，全世界现有的计算机都无法在可接受的时间内求解。是不是什么问题都是并行计算机可解的？是不是什么问题都是并行计算机可解的？并行计算阿姆达尔定律：Acc_Speed=1/(f+(1-f)/p)其中，f为求解某个问题的计算存在的必须串行执行的操作占整个计算的百分比；p为处理器的数目；Acc_Speed为并行计算机系统最大的加速能力。设f=1%,p=，则Acc_Speed=100结论：一个问题的求解若有1%的串行度，则无论有多少台计算机并行计算，其计算速度至多是单台计算机计算同一个问题的100倍！易难易难/难解难解/不可解问题不可解问题从时间复杂性分析来说，许多问题的算法时间复杂性是O(nc)的，其中n是问题的规模，c是常量。易解的问题！有些问题至今只设计出算法时间复杂性为O(2n)的算法，其中n是问题的规模。难解的问题！比如：SAT,VC,CLIQUE,IS,TSP,不可解的问题！即：任何计算机不论耗费多少时间也不能解的问题。如：图灵停机问题P P类与类与NPNP类问题类问题P类问题：已找到在O(nc)时间求解的确定性算法的问题，c为常数；NP类问题：若告诉我答案，便可在O(nc)时间内验证答案是否正确的问题。P=？NP1P类问题 is in NP类问题：P NP 即:P类问题一定也是NP类问题；2.NP类问题 is in P类问题？NP P1.不知道！计算机理论假设：NP类问题 is not in P类问题！即PNP关键科学问题：关键科学问题：大量重要的生物组合计算问题是NP-难解问题l生物数据的海量性（人类基因生物数据的海量性（人类基因组包含超过三十亿个碱基对）组包含超过三十亿个碱基对）和生物结构的复杂性和生物结构的复杂性l生物结构的多态性和生物数生物结构的多态性和生物数据的非精确性据的非精确性l生物计算问题的高计算复杂性生物计算问题的高计算复杂性（大量重要的生物计算问题是（大量重要的生物计算问题是NP-NP-难解问题）难解问题）传统计算技术在生物计算中的局限性l如何解决生物计算中的如何解决生物计算中的NP-NP-难解问题已成为难解问题已成为生物信息学中最重要的课题之一生物信息学中最重要的课题之一l常规算法：无法克服高复杂计算常规算法：无法克服高复杂计算l近似算法：不能达到所要求的精度近似算法：不能达到所要求的精度l启发式算法：无法保证计算问题的完成启发式算法：无法保证计算问题的完成l概率算法：无法确定生物数据的分布概率算法：无法确定生物数据的分布研究思路参数计算理论生物基础问题参数化模型参数化算法设计与分析方法生物软件的开发与应用生物计算基础问题生物计算问题结果 生物计算问题参数化求解及应用过程生物计算问题参数化求解及应用过程生物基础问题求解技术应用计算智能、数据挖掘 生物计算热点问题参数计算理论与技术许多许多NP-NP-难解问题在实际应用中存在一个在小难解问题在实际应用中存在一个在小范围中变化的参数范围中变化的参数 k，对这类问题，我们寻求，对这类问题，我们寻求时间复杂度为时间复杂度为 f(k)nc 的算法的算法 l这种算法不违反这种算法不违反 P P NP NP 的假设的假设l有这种算法的问题称为有这种算法的问题称为小参数可解小参数可解的的l当当 k k 值较小时，值较小时，小参数可解小参数可解算法是实算法是实际可行的际可行的l没有这种算法的问题称为没有这种算法的问题称为小参数难解小参数难解的的（为计算难解性研究提供了新技术）（为计算难解性研究提供了新技术）nkncf(k)inputcomputation timeoutput参数计算理论与算法技术在生物计算中的应用l生物问题数学建模中引入参数生物问题数学建模中引入参数l许多生物计算问题中所含参数的值只在小范许多生物计算问题中所含参数的值只在小范围中变化围中变化l避开避开NP-NP-难解问题的困境难解问题的困境 例：当例：当 n=106,k=60 时时,常规算法时间复杂度：常规算法时间复杂度：nk =10360 参数算法时间复杂度：参数算法时间复杂度：1.285k+n 4.5M l实际有效的精确算法解决生物计算问题实际有效的精确算法解决生物计算问题