文档介绍：计算生物学
第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