1 / 41
文档名称:

计算生物学.ppt

格式:ppt   大小:2,615KB   页数:41页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

计算生物学.ppt

上传人:文库新人 2022/2/17 文件大小:2.55 MB

下载得到文件列表

计算生物学.ppt

文档介绍

文档介绍:计算生物学
第1页,此课件共41页哦
六度分割
任何两个陌生人之间所间隔的人不会超过六个,也就是说,最多通过六个人就能够认识任何一个陌生人
1967年,哈佛大学的社会心理学家米尔格兰姆(Stanley Milgram)设计了一计算生物学
第1页,此课件共41页哦
六度分割
任何两个陌生人之间所间隔的人不会超过六个,也就是说,最多通过六个人就能够认识任何一个陌生人
1967年,哈佛大学的社会心理学家米尔格兰姆(Stanley Milgram)设计了一个连锁信件实验
第2页,此课件共41页哦
搜索
网络寻人
图像搜索
中文搜索大战
第3页,此课件共41页哦
算法
算法是一个明确定义的有限步骤序列,用于求解一个明确定义的问题
Algorithm:Alkhwarizmi写了一本有关代数的书<Hisab al-jabr wa’l-muqabalah>
简单、没有歧义、机械、有效、正确
第5页,此课件共41页哦
算法
确定性:无歧义
可行性:可以实现
有限性:在有限的输入下,算法能在有限的步骤内实现有限输出
第6页,此课件共41页哦
算法
一天的生活安排
电梯运行
寻找完美数
自然语言翻译
序列比对
高通量数据特征提取
第7页,此课件共41页哦
算法
算法是求解问题的步骤
算法无处不在
求于最简
速度?完美?
第8页,此课件共41页哦
算法
正确性
模块性
可维护性
健壮性
可扩展性
……
第9页,此课件共41页哦
内容
算法定义
算法分析


第10页,此课件共41页哦
伪代码
赋值语句:a<- a+1
迭代语句:for i<- 1 to n do;while<条件> do…; repeat…until<条件>
条件语句:if <条件> then … else …
中断语句:break
返回语句:return
第11页,此课件共41页哦
算法表示
Introduction to computational molecular biology
第12页,此课件共41页哦
算法分析
对一个算法所需要的资源进行预测(内存、时间、硬件资源等)
正确性分析
时空分析
算法设计
第13页,此课件共41页哦
正确性
能够终结
输入输出有限
收敛
能否得出合理的结果
找钱问题
Notice:正确性检测
第14页,此课件共41页哦
找钱问题
生物信息学算法导论
第15页,此课件共41页哦
找钱问题
生物信息学算法导论
第16页,此课件共41页哦
时空分析
时空效率:时间和空间的优化
序列分析
Fibonacci数列
时空特性
算法稳定性
理解难易度
第17页,此课件共41页哦
运行时间
运行时间是一个函数
算法运行时间指最坏情况下的运行时间
运行时间依赖于所求实例的规模
函数增长速率:渐进分析
忽略具体及其、编程和编译器的影响,只观察在输入尺寸n趋向于无穷时算法效率的表现
O标记:不考虑常数和低阶项,n2+10n+8=O(n2)
第18页,此课件共41页哦
O标记
给定两个从整数域到实数域的函数f(n)和g(n),如果存在常数c和n0,使得所有n>n0,g(n) ≤f(n),则g(n)=O[f(n)]
给定两个从整数域到实数域的函数f(n)和g(n),如果存在常数c和n0,使得所有n>n0,g(n) ≥f(n),则g(n)=Ω[f(n)]
当g(n)= O[f(n)], g(n)=Ω[f(n)],则g(n)=θ[f(n)]
第19页,此课件共41页哦
排序算法渐进分析
插入排序: O(n2)
合并排序: O(nlogn)
冒泡排序: O(n2)
第20页,此课件共41页哦
插入排序
算法导论
第21页,此课件共41页哦
合并排序
算法导论
第22页,此课件共41页哦
合并排序
算法导论
第23页,此课件共41页哦
冒泡排序
生物信息学算法导论
第24页,此课件共41页哦
迭代算法与递归算法
迭代排序算法
递归排序算法
生物信息学算法导论
第25页,此课件共41页哦
NP问题
NP问题:多项式复杂程度的非确定性问题
NP =? P
图灵机
第26页,此课件共41页哦
算法设计
必须正确
步骤尽可能少
实现尽可能简单
空间占用尽可能少
根据用户要求提供其他附加收益
第27页,此课件共41页哦
算法设计
穷举搜索法
分枝定界法
贪婪算法
动态规划
分治法
机器学习
随机化算法
第28页,此课件共41页哦
内容
算法定义
算法分析


第29页,此课件共41页哦

串:字符或者符号的有序排列
s=“ATCGGGGCTA”
串长度:leng