生物信息学算法-第1讲.ppt

生物信息学（Bioinformatics）算法（Algorithm）,山东大学软件学院主讲：姜海涛联系方式：htjian主讲内容,2.人类基因组计划,1.生物信息学概述,4.生物信息学应用,第一章绪论,多学科高度交叉,生物信息学的定义,生物信息学（Bioinformatics）是利用应用数学、信息学、统计学和计算机科学的方法去研究和解决生物学中生物信息的获取、处理、存储和分配等问题。,20世纪50年代末数学模型、统计学方法和计算机处理宏观生物学数据。数量分类学、数学生态。应用于分子生物学：分子生物学数据库、蛋白质结构分析与预测。人类基因组计划（humangenomeproject,HGP）：1990年启动，10年时间完成草图（3x109个碱基对，并对30,000多个基因进行了注释）。越来越多的微生物和其他模式生物也完成了全基因组测序工作。,生物信息学发展过程,大致经历了3个阶段：前基因组时代-生物数据库的建立、检索工具的开发、DNA和蛋白质序列分析、全局和局部的序列对位排列；基因组时代-基因寻找和识别、网络数据库系统的建立、交互界面的开发；后基因组时代-大规模基因组分析、蛋白质组分析。,生物信息学发展过程,HGP正启动,HumanGenome=threebillion(3*109)basepairs,人类基因组计划,人类基因组计划,HGP正启动,序列图谱：用逐个克隆法和全基因组鸟枪法等对整个基因组测序。,遗传图谱：以具有遗传多态性的遗传标记为“路标”，以遗传学距离为图距的基因组图。,物理图谱：将基因的遗传信息及其在每条染色体上的相对位置线性而系统地排列出来。,基因图谱：在识别基因组所包含的蛋白质编码序列的基础上绘制的结合有关基因序列、位置及表达模式等信息的图谱。,HGP主要研究内容,3*10910,000books1book100pages1page3,000charactersCCGGTCTCCCCGCCCGCGCGCGAAGTAAAGGCCCAGCGCAGCCCGCGCTCCTGCCCTGGGGCCTCGTCTTTCTCCAGGAAAACGTGGACCGCTCTCCGCCGACAGTCTCTTCCACAGACCCCTGTCGCCTTCGCCCCCCGGTCTCTTCCGGTTCTGTCTTTTCGCTGGCTCGATACGAACAAGGAAGTCGCCCCCAGCGAGCCCCGGCTCCCCCAGGCAGAGGCGGCCCCGGGGGCGGAGTCAACGGCGGAGGCACGCCCTCTGTGAAAGGGCGGGGCATGCAAATTCGAAATGAAAGCCCGGGAACGCCGAAGAAGCACGGGTGTAAGATTTCCCTTTTCAAAGGCGGGAGAATAAGAAATCAGCCCGAGAGTGTAAGGGCGTCAATAGCGCTGTGGACGAGACAGAGGGAATGGGGCAAGGAGCGAGGCTGGGGCTCTCACCGCGACTTGAATGTGGATGAGAGTGGGACGGTGACGGCGGGCGCGAAGGCGAGCGCATCGCTTCTCGGCCTTTTGGCTAAGATCAAGTGTAGTATCTGTTCTTATCAGTTTAATATCTGATACGTCCTCTATCCGAGGACAATATATTAAATGGATTGATCAATCCGCTTCAGCCTCCCGAGTAGCTGGGACTACAGACGGTGCCATCACGCCCAGCTCATTGTTGATTCCCGCCCCCTTGGTAGAGACGGGATTCCGCTATATTGCCTGGGCTGGTGTCGAACTCATAGAACAAAGGATCCTCCCTCCTGGGCCTGGGCGTGGGCTCGCAAAACGCTGGGATTCCCGGATTACAGGCGGGCGCACCACACCAGGAGCAAACACTTCCGGTTTTAAAAATTCAGTTTGTGATTGGCTGTCATTCAGTATTATGCTAATTAAGCATGCCCGGTTTTAAACCTCTTAAAACAACTTTTAAAATTACCTTTCCACCTAAAACGTTAAAATTTGTCAAGTGATAATATTCGACAAGCTGTTATTGCCAAACTATTTTCCTATTTGTTTCCTAATGGCATCGGAACTAGCGAAAGTTTCTCGCCATCAGTTAAAAGTTTGCGGCAGATGTAGACCTAGCAGAGGTGTGCGAGGAGGCCGTTAAGACTATACTTTCAGGGATCATTTCTATAGTGTGTTACTAGAGAAGTTTCTCTGAACGTGTAGAGCACCGAAAACCACGAGGAAGAGAGGTAGCGTTTTCATCGGGTTACCTAAGTGCAGTGTCCCCCCTGGCGCGCAATTGGGAACCCCACACGCGGTGTAGAAATATATTTTAAGGGCGCG(1250characters),破译人类遗传密码就要读懂由30亿符号组成的100万页的“天书”,人类基因组计划,后基因组时代,HGP的启动,HGP的完成,亿万数据,后基因组时代,1990年-2003年，人类基因组计划，历时13年，38亿美元；2010年，4天、6000美元测完一个人类基因组，每天产生25GB数据；2013年，15分钟、1000美元完成一个人类基因组测序。,个性化医疗以个人基因组信息为基础，结合蛋白质组，代谢组等相关内环境信息，为病人量身设计出最佳治疗方案，以期达到治疗效果最大化和副作用最小化的一门定制医疗模式。,后基因组时代,分析它们之间的进化关系,Visualizationhumaneyesarealwaysbetter,Mappingultra-fastprogramformappingNGSreads？,AnnotationNGSdataderivedfromwhatknowgenomicelements?,StorageHowstoragenewNGSdata,DiscoveryRNA-seq,CNV-seq,SNP,ChIP-seq,后基因组时代,生物信息学主要的研究方向,生物信息学的主要研究方向,其它,蛋白质表达分析,药物研发,比较基因组学,基因组注释,序列分析,基因表达分析,蛋白质结构预测,生物信息学系统化概图,基因序列信息,蛋白质相互作用网络,RNA/DNA螺旋结构,基因表达微阵列,人类疾病网络,蛋白质结构信息,主要的生物数据类型,海量性复杂性多样性关联性高噪声不完整性,生物信息特性,数据量大复杂度高数据类型多样数据间关系复杂假阳性高假阴性高,生物信息处理面临的挑战,海量生物数据分析的挑战,已知的序列-功能基于常规克隆的基因分类基于序列及功能的分析的基因分类单个基因致病机制-多个基因致病机制从基因组和蛋白质组的结构与功能关系来预测三级结构和功能从三级结构和功能反推可能的序列比较不同生物物种的基因组来进行分子进化研究。,生物信息学的应用-基因组分析,基因组研究的首要目标是获得人的整套遗传密码。人的遗传密码有30亿个碱基，而现在的测序仪每个反应只能读取几百到上千个碱基。这样，要得到人的全部遗传密码，首先要把人的基因组打碎，测完一个个小段的序列后再把它们重新拼接起来。而基因组大规模测序的每一个环节，都同信息分析紧密相关，每一步都紧密依赖于生物信息学的软件和数据库。,生物信息学的应用-基因组分析,蛋白质组基因组对生命体的整体控制必须通过它所表达的全部蛋白质来执行。由于基因芯片技术只能反映从基因组到的转录水平上的表达情况，而从到蛋白质还有许多中间环节的影响，这样，仅凭基因芯片技术人们还不能最终掌握生物功能的具体执行者蛋白质的整体表达状况。因此，近年在发展基因芯片的同时，人们还发展了一套研究基因组所有蛋白质产物表达情况的技术蛋白质组研究技术，包括二维凝胶电泳技术和质谱测序技术。然而，最重要的是如何运用生物信息学的方法去分析获得的海量数据，从中还原出生命运转和调控的整体系统的分子机制。,生物信息学的应用-基因组分析,2.基因芯片基因微阵列或DNA芯片(genemicroarray或DNAchips)的原理是将几万个寡核苷酸或DNA作为探针，密集排列于硅片等固相支持物上，将研究样品标记后与微点阵杂交并进行检测。根据杂交信号强弱及探针位置和序列，可以确定靶DNA的表达情况以及突变和多态性存在与否。,生物信息学的应用-基因组分析,3.药物开发基因组和蛋白质组研究的迅猛发展，使许多新蛋白序列涌现出来。要了解它们的功能，只有氨基酸序列是远远不够的。得到这些新蛋白的完整、精确和动态的三维结构，是摆在人们面前的紧迫任务。,生物信息学的应用-基因组分析,3.药物开发近年，随着结构生物学的发展，相当数量的蛋白质以及一些核酸、多糖的三维结构获得了精确的测定。根据生物大分子结构的知识，有针对性地设计药物成为热点。,生物信息学的应用-基因组分析,4.其他：疾病相关的基因信息及相关算法和软件开发建立与动、植物良种繁育相关的基因组数据库，发展分子标记辅助育种技术研究与发展药物设计软件和基于生物信息的分子生物学技术寄生虫与流行病学研究、农作物基因组分析、神经科学。,生物信息学的应用-基因组分析,发现新的基因和新的功能如人基因组含有30亿对核苷酸，其中大约有10万个决定各种性状和功能的基因。一个小耗子的肥胖基因都能卖上亿的美元。过去几十年中，科学家运用经典的遗传学分析方法如功能克隆、定位克隆等方法，总共定位了大约2000个基因。,生物信息学的应用-基因组分析,1.大规模基因组测序中的信息分析2.新基因和新SNP的发现与鉴定3.非编码区信息结构分析4.遗传密码的起源和生物进化5.完整基因组的比较研究6.大规模基因功能表达谱的分析7.生物大分子的结构模拟与药物设计8.生物信息学分析方法的研究9.建立国家生物医学数据库与服务系统10.应用与发展研究,生物信息学的应用-基因组分析,生物信息学的商业价值十分显著。国外很多大学，研究机构，软件公司甚至政府机构纷纷成立各种生物信息机构，建立自立的生物信息集成系统，研制这方面的软件缩短药物开发周期，抢注基因专利南、北方人类基因组中心的相继建成,生物信息学的应用,参考文献,生物信息学算法导论琼斯、帕夫纳著王翼飞等译化学工业出版社生物信息学概论罗静初北京大学北京大学出版社生物信息学D.R.Westhead科学出版社生物信息学基因和蛋白质分析的使用指南李衍达清华大学清华大学出版社生物信息学手册郝柏林中科院物理所上海科学技术出版社简明生物信息学钟扬复旦大学高等教育出版社,2020/5/16,什么是算法:图灵时代就有定义，看上去与程序的定义相同。说清楚难，是程序吗？是计算思想吗？两个含义：为什么要设计程序，因为要处理信息。为什么要设计算法，因为要解决问题。(1)问题；不是一般的问题，有意义的问题，凭感觉了。算法是针对问题的算法，没有问题，哪有算法？(2)算法是程序，又不是程序。.，计算机语言描述的计算机求解问题的步骤，按照规定的步骤可以得到正确的结果。,第二章算法与复杂性,例子：求1+2+3+n可以编一个程序也可以用公式计算：,Sum=0;Fori=1tonSum=Sum+i;EndforOutputSum,也可以用公式计算：一步就完成Sum=n*(n+1)/2OutputSum,算法从何入手，求解问题。计算机干什么？问题：什么是问题，怎么描述，日常生活中的问题描述，就是要让计算机干什么。输入，输出。两个要素:输入和输出，要有严格的描述。实例：描述问题的所有参量。输入数据包含哪些参量。询问：陈述问题所求的解的格式和解应满足的性质。,什么是问题,注意，计算机每次求解只是针对一个实例求解，问题的描述针对所有实例，给一个统一的描述。算法：对每个问题实例计算机都能计算出满足询问条件的正确答案，的计算方法。是一个过程，语句集合，语句有顺序，按照顺序执行语句，处理实例，得到正确答案。对每个实例都能得到正确答案。算法可以理解为一种计算方法，但这种方法一定能用计算机来计算，能用程序实现。程序：算法在计算机上的具体实现。算法与程序没有本质区别，算法一般不关心在哪台计算机上运行。,问题与实例,实例(Instance)：实数x和正整数n询问(query)：xn=?n=10，x=2012.0910,求：2012.091010每次计算x和n都不同，都是一个实例。,例子：求xn，求幂问题,1x*x*x*x*x*x*x*x*x*x2y=x*x,z=y*y,w=z*z,x10=y*w3(x*x)2*x2,方法1，2，3分别作9，4，4次乘法。考虑算法的总操作次数，*这个总操作次数称为算法的时间复杂度，或称为算法时间复杂性。什么是基本操作，就看个人怎么想(定义)了。具体情况，具体分析。,方法、算法：,算法3推广到一般如何：想一种通用的办法。n=(bm-1bm-2b1b0)2n=(10)2,n=(100)2,n=(1000)2,n=(11000)2,n=(10100)2x8=(x)2)2)2X16+4=(x)2)2x)2)2X16+8=(x)2x)2)2)2X32+16+4=(x)2x)2)2x)2)2,1begin/n的m位2进制数为n=(bm-1bm-2b1b0)22y=x3fori=m-2downto0do4begin5y=y*y6Ifbi=1theny=y*x7end8end例子：n=(45)10=(101101)2,x45=x32+8+4+1(x)2)2x)2x)2)2x,若n=1000，则T(n)=log2n=m-1，若n=1111，则T(n)=2log2n=2(m-1)所以可以给出时间复杂度的界，log2nT(n)2log2n,算法的时间复杂度随着n的增大而增大，要考虑算法时间复杂度T(n)的随着n增大的增长率。n是x的个数。n1=100000000,T(n1)=8n2=11111111,T(n2)=14真正讨论算法时间复杂度时，总关心算法时间复杂度随着实例规模增大而增大的增长率，即数量级。其实只能得到算法时间复杂度的上界或下界的增长率。上述算法的时间复杂度显然跟实例大小有关，跟n有关。满足：log2nT(n)2log2n两个界并不是都好估计，也不需要都去关心。,算法的时间复杂度,在算法分析时，十分关心算法时间复杂度的增长率，并不十分关心算法时间复杂度的具体值。时间复杂度不会比空间复杂度大。算法时间复杂度随着实例规模增大而增大。问题规模怎样表示？每个问题都用一个整数参量说明问题的规模。给出一个随着问题规模增大，算法时间复杂性也增大的趋势的描述函数。用时间复杂性的界函数来表示。通常要估计算法时间复杂度的上界，有时也需要估计算法时间复杂度的下界。,渐进估计技术及基本规则,(1)若存在n0和C，使当nn0时，T(n)Cf(n)，则称T(n)=O(f(n)如，T(n)=(1+n)2=O(n2);T(n)=2n3+4n2=O(n3)O(f(n)描述算法时间复杂度的上界，说明算法好时往往用O(f(n)。(2)存在常数C，存在无穷多个n，使T(n)Cg(n)，则记为：T(n)=(g(n)若存在n0和C，使当nn0时，T(n)Cg(n)，则称T(n)=(g(n)如：T(n)=2n+(3/2)n=(2n)，可以写成O(2n)吗？可以写成O(3n)?可以写成T(n)=(3/2)n)吗？可以写成T(n)=O(3/2)n)吗？,两个符号：O()，(),DNA复制算法,生物学算法与计算机算法,字符串复制算法,字符串复制问题输入：长度为n的字符串s=(s1,s2,sn)。输出：s的一个拷贝字符串t。,Stringcopy(s,n)Forinsi=tiReturnt,找零钱问题,找零钱问题的简单算法,正确的和错误的算法,硬币类型，25分，10分，5分，1分。将63分钱兑换成硬币问：最少兑换几枚硬币？贪心算法：25，25，10，1，1，1，先换大的后换小的。实际上以上解是最优的，与类型有关。,25,25,10,1,1,1,一个正例,11，5，1分三种硬币，兑换15分钱，贪心算法解为：11，1，1，1，1实际上，5，5，5是最优解。贪心解并不是最优解。贪心技术可以找到可行解，未必能找到最优解。如同现实生活中的局部利益与整体利益。寻求当前最好，未必全局最好。当前收益最大为目标/当前损失最小为目标。,11,1,1,1,1,一个反例,递归与迭代,递归算法,菲波那契数列问题,兔子繁殖模型,13世纪，意大利数学家菲波那契研究兔子后代数量。基于以下假设：在给定一段时间内，一对大兔可繁殖出一对小兔；一对小兔可在同样时间内长成大兔。,走楼梯模型,快与慢,Procedurebubblesort(A1-nofinteger)Begin1fori=1ton-12forj=ndowntoi+1do3ifAj-1Ajthen4temp=Aj-15Aj-1=Aj6Aj=temp7endif8endfor9endfor时间复杂度分析，考虑最坏情况。有时比较完成以后要交换，有时不要交换，比较一次，交换3次。我们只算比较次数作为算法时间复杂度，第一遍比较n-1次，第二遍比较n-2次，。时间复杂度。只算比较次数：用作时间复杂度的计数。T(n)=(n-1)+(n-2)+2+1=n(n-1)/2=O(n2),相邻的元素比较，小的向前移动,冒泡排序,Functionmergesort(L:listofinteger,n)BeginIfn=1thenreturnLElsebeginbreakLintoL1andL2,eachoflengthn/2return(merge(mergesort(L1,n/2),mergesort(L2,n/2)endend,归并排序,首先考虑两个有序表合并的算法，时间复杂度分析，两个n/2长的表合成一个表，需要O(n)次。,T(n),L1=10，15，18，20，31L2=5，13，19，23，35L=5，10，13，15，18，19，20，23，31，35,归并排序的时间复杂度,求出T(n)需要解递推方程。解递推方程的很多方法：1猜测法，2展开法，3求解法上述方程：猜测T(n)=O(nlogn)anlogn+b,a,b为常数，下面证明当n=1时，T(1)=b，猜测成立设nk时猜测成立，T(n)anlogn+b，下面考虑n=k+1的情况。可以认为n/2k，所以n/2k。这个在n2时成立，由前面的递推方程有：T(n/2)a(n/2)log(n/2)+bT(n)2a(n/2)log(n/2)+2b+C2n=anlogn-an+C2n+2b?anlogn+b若-an+C2n+b0，则猜测成立，只需取b=C1,a=C1+C2即可，这样猜测就成立。,如何解递推方程,枚举分而治之贪心分支定界回溯动态规划局部搜索机器学习随机,算法设计技术,先分开把大问题化为小问题，求解小问题，再把小问题的解合并。成为大问题的解。最朴素的方法。但是没有万能的办法。归并排序的例子：通过举例子说明方法。MergeSort,分而治之(divideandconquer),310，285，179，652，351|423，861，254，450，520310，285|179，652，351|423，861，254，450，520310|285|179，652，351|423，861，254，450，520285，310|179，652，351|423，861，254，450，520285，310|179|652，351|423，861，254，450，520285，310|179|652|351|423，861，25