动态规划算法硬币收集问题论文

A. 如何准备互联网公司面试（算法相关）

书籍： 《算法导论》 这本是大部头，很多人都看不完。我本人也并没有看完，它跟了我这么多年，完全是属于常看常新的牛书。每一次看，都发现会有新的收获。比如，以前并不知道求K位数或者中位数有平均为O(n)复杂度的算法。看到了别的地方的参考资料，才知道，原来《算导》上专门有一小节讲这个内容。我基本上是本科比较集中的看了一遍，研一的时候又集中的看了一遍，才算是粗略的看完。但是其实，很多理论性的，以及图论一部分依然还是没有看完。个人推荐，先从简单的开始，挑选比较熟悉的一些偏重与数据结构方面的知识作为起点。这本书的习题非常重要，要是有时间，能够全部做完，那绝对是能够神功在手了。其实，集中把，第二部分（排序），第三部分（数据结构），第四部分（高级设计，我基本主要看动态规划和贪心），第五部分（高级数据结构，B树和二项堆，并差集），第六部分（图算法，最大流部分较难，自己可以看情况掌握）。这些部分可以先从算法本身开始，伪代码全部看懂。因为算法导论讲的很详细，而且有来龙去脉，基本不会有太大难度。数学证明，推荐大家掌握，但是，突击或者第一次，可以选择性的看看。我自己是重复看，才把证明看掉的。第一次看的时候，基本都跳过了。不过，证明和习题是精髓！希望如果有时间，一定要补回来。 《编程之美》《挑战编程》 这本书绝对是将全中国企业，或者说是一部分懒惰的企业面试题库提升了一个档次的一本神书。网络面我师兄的时候，我师兄直接把有一道题的最优解答出来了。但是，那个面试官显然是不知道最优解，一直在引导我师兄答出，这本书里面的第四个解。呵呵。书很不错。全部看一遍并不难。说个不好听的，可以背下来，而且相信我，基本上绝对有用！比如说，n!后面有多少个0。我相信，你们今年面试或者笔试，一定会碰到这道题。《挑战编程》大家可以自行考虑一下吧，这个完全是针对acm竞赛的，不过，看看题也不错。 《编程珠玑》 业界神书嘛。习题全部做完就是了。其实都是些小东西，但是，基本上一步步考察你的解决问题的能力。个人觉得，最常用的就是bit map做排序或者去重，拓展一下就是bloom filter，我当时都是在这本书里面看到的。 《算法技术手册》 这本书貌似出镜不多。书很薄，代码写的非常好，其实基本上全部都是基础算法和数据结构的实现。但是，它牛逼就在于，代码写的太好了，基本上，看一遍，绝对能背下来。面试基础很重要。基本上每个笔试或者面试，都会考一个100行以内的小程序。比如，给定一棵树，以及其中一个节点x，要求出这棵树的中序遍历序列中，x的后续节点，非递归实现。这种题非常简单，但是，真正写对的，其实并不多。《STL源码剖析》《C标准库》 都不厚。挑着看一遍非常舒服。特别是，看看STL每个数据结构迭代器类型啊，红黑书如何实现啊。C标准库，最常见的，比如strcpy()和memcpy()有什么区别啊。特别是，STL，看过之后，对泛型还是能有一定了解的。《C专家编程》《Effective c++》《深度探索C++对象模型》 第一本比较简单，可以当八卦书看。后两本其实也没啥好说的，其实都是些业界公认的牛书。我再重复一遍也没什么意义。但是，的确，考察基本上也就都是这么几本书上面的东西。基本上后两本主要侧重看c++对象方面的一些指示，特别是多态相关的。 《具体数学》《组合数学》 这两本其实可以看作修身养性的书。我当时是时间比较充裕的时候看完的。纯突击，大家就可以跳过了。但是，看完真的很有用。比如说，你们就可以跟面试官扯约瑟夫环的构造解了（这道题我觉得80%会遇到），直接推推公式，就不用写模拟代码了。《组合数学》也是，很多笔试一般会有些小智力题。不过，其实一般的题目，不看这本书也可以搞定。所以，这两本仅供参考。大家有兴趣的时候，可以翻翻。《Linux内核源码剖析》《Linux环境高级编程》…… 要是有机会，能看看最好。因为很多公司都会考察Linux相关的知识。最少要会点脚本，一些简单的Linux命令，以及正则表达式什么的。要是能聊聊内核源码或者驱动开发什么的东西，面试官肯定更加喜欢了。 知识： c & c++ 首先要知道c和c++的区别。常考的有const的用法，一些生僻关键字比如extern，static的用法。 结构体与类的差别。类里面的字对齐问题，也就是说一个类到底有多大。以及一个空的类有多大。 虚函数以及多态相关的显然是重点。比如析构函数什么时候需要写成虚函数，构造函数是否可以是虚函数。 int a[10]; a 和 &a的区别。 java java我并不熟。但是基本上肯定会考一些虚拟机相关的，以及GC等知识。然后，一般招聘的java程序员都会问到很多多线程编程的东西，以及hadoop！这个绝对是重点，淘宝绝对就是问这个的。 操作系统 这个看工作岗位的实际要求。基本的进程线程区别==肯定是会问到的。要是要求高一些，就会问很多多线程编程的问题。一些竞争死锁等基础知识，一些进程调度的算法，最近的kernel好像用的是CFS调度算法。shell编程，如何读取程序堆栈，写一些core mp的读取程序等等的。 数据结构 基本上所有的排序都要会写。与树有关的操作都要会些非递归版本。图一般考的不多。Flood-Fill算法等等。查找中位数。B树和红黑书最好要掌握，不用会写，能扯扯基本就行。KMP，这个很有可能考！而且的确真的不好懂。要是实在不行，背下来吧。哈哈。 网络 这个其实比较基础了。我个人网络方面的知识并不好。但是各种协议的基础，几次握手啊，一些操作系统的api实现到底是单工还是双工用的是TCP还是UDP。我个人网络纯粹靠拼RP。 数据库 数据库非常重要。基本的SQL肯定是要会的。最常见有一道题，inner join和out join的区别。MySQL是重点，基本上很多企业都是问这个。然后，网络扯多了会跟你扯MySQL引擎 的一些东西。这些我就不太懂了。要是能准备的话，或者说的确是做这方面的，就可以着重多准备下。 大规模数据处理这一块绝对是重点！而且本身不是一个系统的学科分支。但是，基本上几家大公司都会问这方面的。推荐先读读google那几篇论文。Page Rank那一篇，然后Map Rece好像有几篇吧。Big Table什么的。推荐一个网址。这篇貌似是转载的，我以前找到的源地址现在找不到了。处理这一类问题基本上思路都是，哈希，map rece以及bit map等等的。对了，推荐看一下外排序以及相关的败者树。这些都是大规模数据处理的一些典型问题。掌握了这些其实也就够了。这块有点屠龙之技的感觉，特别是对于学生，基本没有谁能有机会把这些代码实现出来。但是，没办法，这些公司就是喜欢考。看完那篇博客的，然后再自行查找一些资料，基本就够了。万变不离其中，而且，这些东西，没办法考那么难的。 推荐一个博客吧，作者收集了100+道面试题，并且全部给出了代码。把这个全部看完，基本上很多面试笔试，都是这些原题。 推荐Top Language里面的今天我们思考系列，好几年前的了。看大牛的思考过程，非常有帮助。希望自己能多想想再看答案。注意，google group好像有时被墙。 我把发芽网的题库版块也扫了一遍。 还有好多一时想不起来了。

B. 算法分析与设计的作品目录

第一部分基础工具
第1章算法分析
1.1算法的分析方法学
1.1.1伪代码
1.1.2随机存取机(RAM)模型
1.1.3统计基本操作的数量
1.1.4递归算法分析
1.2渐近符号
1.2.1大O符号
1.2.2与大“O”相关的渐近符号
1.2.3渐近表示的重要性
1.3数学概览
1.3.1求和
1.3.2对数和指数
1.3.3简单证明技术
1.3.4概率基础
1.4算法分析案例研究
1.4.1二次时间前缀平均值算法
1.4.2线性时间前缀平均值算法
1.5平摊方法
1.5.1平摊技术
1.5.2扩展数组实现分析
1.6实验
1.6.1实验组织
1.6.2数据分析和可视化
1.7习题
基础题
创新题
程序设计
1.8本章注记
第2章基本数据结构
2.1栈和队列
2.1.1栈
2.1.2队列
2.2向量、表和序列
2.2.1向量
2.2.2表
2.2.3序列
2.3树
2.3.1树抽象数据类型
2.3.2树的遍历
2.3.3二叉树
2.3.4表示树的数据结构
2.4优先队列和堆
2.4.1优先队列抽象数据类型
2.4.2PQ排序、选择排序和插入排序
2.4.3堆数据结构
2.4.4堆排序
2.5字典与散列表
2.5.1无序字典ADT
2.5.2散列表
2.5.3散列函数
2.5.4压缩映射
2.5.5冲突处理模式
2.5.6通用散列
2.6Java示例：堆
2.7习题
基础题
创新题
程序设计
2.8本章注记
第3章查找树和跳跃表
3.1有序字典和二叉查找树
3.1.1有序表
3.1.2二叉查找树
3.1.3二叉查找树中的查找
3.1.4二叉查找树中的插入
3.1.5二叉查找树中的删除
3.1.6二叉查找树的性能
3.2AVL树
3.2.1更新操作
3.2.2性能
3.3深度有界查找树
3.3.1多路查找树
3.3.2(2,4)树
3.3.3红黑树
3.4伸展树
3.4.1伸展
3.4.2伸展过程的平摊分析
3.5跳跃表
3.5.1查找
3.5.2更新操作
3.5.3跳跃表的概率分析
3.6Java示例：AVL树和红黑树
3.6.1AVL树的Java实现
3.6.2红黑树的Java实现
3.7习题
基础题
创新题
程序设计
3.8本章注记
第4章排序、集合和选择
4.1归并排序
4.1.1分治法
4.1.2归并排序和递归方程
4.2集合抽象数据类型
4.2.1简单的集合实现
4.2.2具有union-find操作的划分
4.2.3基于树的划分实现
4.3快速排序
4.4基于比较的排序下界
4.5桶排序和基数排序
4.5.1桶排序
4.5.2基数排序
4.6比较排序算法
4.7选择
4.7.1剪枝-查找法
4.7.2随机化快速选择
4.7.3随机化快速选择分析
4.8Java示例：原位快速排序
4.9习题
基础题
创新题
程序设计
4.10本章注记
第5章基本技术
5.1贪心法
5.1.1背包问题
5.1.2任务调度
5.2分治法
5.2.1分治递归方程
5.2.2整数相乘
5.2.3矩阵相乘
5.3动态规划
5.3.1矩阵链乘
5.3.2一般技术
5.3.30-1背包问题
5.4习题
基础题
创新题
程序设计
5.5本章注记
第二部分图算法
第6章图
6.1图抽象数据类型
6.2图的数据结构
6.2.1边表结构
6.2.2邻接表结构
6.2.3邻接矩阵结构
6.3图的遍历
6.3.1深度优先查找
6.3.2双连通分量
6.3.3广度优先查找
6.4有向图
6.4.1遍历有向图
6.4.2传递闭包
6.4.3DFS和垃圾收集
6.4.4有向无环图
6.5Java示例：深度优先查找
6.5.1修饰模式
6.5.2DFS引擎
6.5.3模板方法设计模式
6.6习题
基础题
创新题
程序设计
6.7本章注记
第7章加权图
7.1单源点最短路径
7.1.1Dijkstra算法
7.1.2Bellman-Ford最短路径算法
7.1.3有向无环图中的最短路径
7.2所有顶点对之间的最短路径
7.2.1动态规划最短路径算法
7.2.2利用矩阵相乘计算最短路径
7.3最小生成树
7.3.1Kruskal算法
7.3.2Prim-Jarník算法
7.3.3Bar?vka算法
7.3.4MST算法比较
7.4Java示例：Dijkstra算法
7.5习题
基础题
创新题
程序设计
7.6本章注记
第8章网络流和匹配
8.1流和割
8.1.1流网络
8.1.2割
8.2最大流
8.2.1剩余容量和增大路径
8.2.2Ford-Fulkerson算法
8.2.3Ford-Fulkerson算法分析
8.2.4Edmonds-Karp算法
8.3最大二分匹配
8.4最小代价流
8.4.1增大回路
8.4.2连续最短路径
8.4.3修改权值
8.5Java示例：最小代价流
8.6习题
基础题
创新题
程序设计
8.7本章注记
第三部分因特网算法
第9章文本处理
9.1串和模式匹配算法
9.1.1串操作
9.1.2蛮力模式匹配
9.1.3Boyer-Moore算法
9.1.4Knuth-Morris-Pratt算法
9.2trie
9.2.1标准trie
9.2.2压缩trie
9.2.3后缀trie
9.2.4搜索引擎
9.3文本压缩
9.3.1赫夫曼编码算法
9.3.2修正贪心法
9.4文本相似性测试
9.4.1最长公共子序列问题
9.4.2应用动态规划求解LCS问题
9.5习题
基础题
创新题
程序设计
9.6本章注记
第10章数论和密码学
10.1与数有关的基本算法
10.1.1基本数论的一些事实
10.1.2欧几里得GCD算法
10.1.3模运算
10.1.4模指数运算
10.1.5模乘法逆元
10.1.6素性测试
10.2密码计算
10.2.1对称加密模式
10.2.2公钥密码系统
10.2.3RSA密码系统
10.2.4El Gamal密码系统
10.3信息安全算法和协议
10.3.1单向散列函数
10.3.2时间戳和认证字典
10.3.3硬币抛掷和比特承诺
10.3.4安全电子传输(SET)协议
10.3.5密钥分发和交换
10.4快速傅里叶变换
10.4.1本原单位根
10.4.2离散傅里叶变换
10.4.3快速傅里叶变换算法
10.4.4大整数相乘
10.5Java示例：FFT
10.6习题
基础题
创新题
程序设计
10.7本章注记
第11章网络算法
11.1复杂性测度和模型
11.1.1网络协议栈
11.1.2消息传递模型
11.1.3网络算法的复杂性测度
11.2基本分布式算法
11.2.1环网上的领导人选举
11.2.2树网上的领导人选举
11.2.3广度优先查找
11.2.4最小生成树
11.3广播路由和单播路由
11.3.1广播路由的洪泛算法
11.3.2单播路由的距离矢量算法
11.3.3单播路由的链路-状态算法
11.4多播路由
11.4.1逆向路径转发
11.4.2中心树
11.4.3Steiner树
11.5习题
基础题
创新题
程序设计
11.6本章注记
第四部分其他主题
第12章计算几何
12.1范围树
12.1.1一维范围查找
12.1.2二维范围查找
12.2优先查找树
..

C. 常见的数学模型有哪些

1、生物学数学模型

2、医学数学模型

3、地质学数学模型

4、气象学数学模型

5、经济学数学模型

6、社会学数学模型

7、物理学数学模型

8、化学数学模型

9、天文学数学模型

10、工程学数学模型

11、管理学数学模型

(3)动态规划算法硬币收集问题论文扩展阅读

数学模型的历史可以追溯到人类开始使用数字的时代。随着人类使用数字，就不断地建立各种数学模型，以解决各种各样的实际问题。

数学模型这种数学结构是借助于数学符号刻划出来的某种系统的纯关系结构。从广义理解，数学模型包括数学中的各种概念，各种公式和各种理论。

因为它们都是由现实世界的原型抽象出来的，从这意义上讲，整个数学也可以说是一门关于数学模型的科学。从狭义理解，数学模型只指那些反映了特定问题或特定的具体事物系统的数学关系结构，这个意义上也可理解为联系一个系统中各变量间内的关系的数学表达。

D. 生物信息学

一, 生物信息学发展简介

生物信息学是建立在分子生物学的基础上的,因此,要了解生物信息学,就

必须先对分子生物学的发展有一个简单的了解.研究生物细胞的生物大分子的结

构与功能很早就已经开始,1866年孟德尔从实验上提出了假设:基因是以生物

成分存在[1],1871年Miescher从死的白细胞核中分离出脱氧核糖核酸(DNA),

在Avery和McCarty于1944年证明了DNA是生命器官的遗传物质以前,人们

仍然认为染色体蛋白质携带基因,而DNA是一个次要的角色.

1944年Chargaff发现了着名的Chargaff规律,即DNA中鸟嘌呤的量与胞嘧

定的量总是相等,腺嘌呤与胸腺嘧啶的量相等.与此同时,Wilkins与Franklin

用X射线衍射技术测定了DNA纤维的结构.1953年James Watson 和Francis

Crick在Nature杂志上推测出DNA的三维结构(双螺旋).DNA以磷酸糖链形

成发双股螺旋,脱氧核糖上的碱基按Chargaff规律构成双股磷酸糖链之间的碱基

对.这个模型表明DNA具有自身互补的结构,根据碱基对原则,DNA中贮存的

遗传信息可以精确地进行复制.他们的理论奠定了分子生物学的基础.

DNA双螺旋模型已经预示出了DNA复制的规则,Kornberg于1956年从大

肠杆菌(E.coli)中分离出DNA聚合酶I(DNA polymerase I),能使4种dNTP连接

成DNA.DNA的复制需要一个DNA作为模板.Meselson与Stahl(1958)用实验

方法证明了DNA复制是一种半保留复制.Crick于1954年提出了遗传信息传递

的规律,DNA是合成RNA的模板,RNA又是合成蛋白质的模板,称之为中心

法则(Central dogma),这一中心法则对以后分子生物学和生物信息学的发展都起

到了极其重要的指导作用.

经过Nirenberg和Matthai(1963)的努力研究,编码20氨基酸的遗传密码

得到了破译.限制性内切酶的发现和重组DNA的克隆(clone)奠定了基因工程

的技术基础.

正是由于分子生物学的研究对生命科学的发展有巨大的推动作用,生物信息

学的出现也就成了一种必然.

2001年2月,人类基因组工程测序的完成,使生物信息学走向了一个高潮.

由于DNA自动测序技术的快速发展,DNA数据库中的核酸序列公共数据量以每

天106bp速度增长,生物信息迅速地膨胀成数据的海洋.毫无疑问,我们正从一

个积累数据向解释数据的时代转变,数据量的巨大积累往往蕴含着潜在突破性发

现的可能,"生物信息学"正是从这一前提产生的交叉学科.粗略地说,该领域

的核心内容是研究如何通过对DNA序列的统计计算分析,更加深入地理解DNA

序列,结构,演化及其与生物功能之间的关系,其研究课题涉及到分子生物学,

分子演化及结构生物学,统计学及计算机科学等许多领域.

生物信息学是内涵非常丰富的学科,其核心是基因组信息学,包括基因组信

息的获取,处理,存储,分配和解释.基因组信息学的关键是"读懂"基因组的核

苷酸顺序,即全部基因在染色体上的确切位置以及各DNA片段的功能;同时在

发现了新基因信息之后进行蛋白质空间结构模拟和预测,然后依据特定蛋白质的

功能进行药物设计[2].了解基因表达的调控机理也是生物信息学的重要内容,根

据生物分子在基因调控中的作用,描述人类疾病的诊断,治疗内在规律.它的研

究目标是揭示"基因组信息结构的复杂性及遗传语言的根本规律",解释生命的遗

传语言.生物信息学已成为整个生命科学发展的重要组成部分,成为生命科学研

究的前沿.

二, 生物信息学的主要研究方向

生物信息学在短短十几年间,已经形成了多个研究方向,以下简要介绍一些

主要的研究重点.

1,序列比对(Sequence Alignment)

序列比对的基本问题是比较两个或两个以上符号序列的相似性或不相似

性.从生物学的初衷来看,这一问题包含了以下几个意义[3]:

从相互重叠的序列片断中重构DNA的完整序列.

在各种试验条件下从探测数据(probe data)中决定物理和基因图

存贮,遍历和比较数据库中的DNA序列

比较两个或多个序列的相似性

在数据库中搜索相关序列和子序列

寻找核苷酸(nucleotides)的连续产生模式

找出蛋白质和DNA序列中的信息成分

序列比对考虑了DNA序列的生物学特性,如序列局部发生的插入,删除(前

两种简称为indel)和替代,序列的目标函数获得序列之间突变集最小距离加权

和或最大相似性和,对齐的方法包括全局对齐,局部对齐,代沟惩罚等.两个

序列比对常采用动态规划算法,这种算法在序列长度较小时适用,然而对于海

量基因序列(如人的DNA序列高达109bp),这一方法就不太适用,甚至采用算

法复杂性为线性的也难以奏效.因此,启发式方法的引入势在必然,着名的

BALST和FASTA算法及相应的改进方法均是从此前提出发的.

2, 蛋白质结构比对和预测

基本问题是比较两个或两个以上蛋白质分子空间结构的相似性或不相似性.

蛋白质的结构与功能是密切相关的,一般认为,具有相似功能的蛋白质结构一般

相似.蛋白质是由氨基酸组成的长链,长度从50到1000~3000AA(Amino Acids),

蛋白质具有多种功能,如酶,物质的存贮和运输,信号传递,抗体等等.氨基酸

的序列内在的决定了蛋白质的3维结构.一般认为,蛋白质有四级不同的结构.

研究蛋白质结构和预测的理由是:医药上可以理解生物的功能,寻找docking

drugs的目标,农业上获得更好的农作物的基因工程,工业上有利用酶的合成.

直接对蛋白质结构进行比对的原因是由于蛋白质的3维结构比其一级结构

在进化中更稳定的保留,同时也包含了较AA序列更多的信息.

蛋白质3维结构研究的前提假设是内在的氨基酸序列与3维结构一一对应

(不一定全真),物理上可用最小能量来解释.

从观察和总结已知结构的蛋白质结构规律出发来预测未知蛋白质的结构.同

源建模(homology modeling)和指认(Threading)方法属于这一范畴.同源建模用

于寻找具有高度相似性的蛋白质结构(超过30%氨基酸相同),后者则用于比较

进化族中不同的蛋白质结构.

然而,蛋白结构预测研究现状还远远不能满足实际需要.

3, 基因识别,非编码区分析研究.

基因识别的基本问题是给定基因组序列后,正确识别基因的范围和在基因组

序列中的精确位置.非编码区由内含子组成(introns),一般在形成蛋白质后被丢

弃,但从实验中,如果去除非编码区,又不能完成基因的复制.显然,DNA序

列作为一种遗传语言,既包含在编码区,又隐含在非编码序列中.分析非编码

区DNA序列目前没有一般性的指导方法.

在人类基因组中,并非所有的序列均被编码,即是某种蛋白质的模板,已

完成编码部分仅占人类基因总序列的3~5%,显然,手工的搜索如此大的基因序

列是难以想象的.

侦测密码区的方法包括测量密码区密码子(codon)的频率,一阶和二阶马尔

可夫链,ORF(Open Reading Frames),启动子(promoter)识别,HMM(Hidden

Markov Model)和GENSCAN,Splice Alignment等等.

4, 分子进化和比较基因组学

分子进化是利用不同物种中同一基因序列的异同来研究生物的进化,构建进

化树.既可以用DNA序列也可以用其编码的氨基酸序列来做,甚至于可通过相

关蛋白质的结构比对来研究分子进化,其前提假定是相似种族在基因上具有相似

性.通过比较可以在基因组层面上发现哪些是不同种族中共同的,哪些是不同的.

早期研究方法常采用外在的因素,如大小,肤色,肢体的数量等等作为进化

的依据.近年来较多模式生物基因组测序任务的完成,人们可从整个基因组的角

度来研究分子进化.在匹配不同种族的基因时,一般须处理三种情况:

Orthologous: 不同种族,相同功能的基因

Paralogous: 相同种族,不同功能的基因

Xenologs: 有机体间采用其他方式传递的基因,如被病毒注入的基因.

这一领域常采用的方法是构造进化树,通过基于特征(即DNA序列或蛋白

质中的氨基酸的碱基的特定位置)和基于距离(对齐的分数)的方法和一些传统

的聚类方法(如UPGMA)来实现.

5, 序列重叠群(Contigs)装配

根据现行的测序技术,每次反应只能测出500 或更多一些碱基对的序列,

如人类基因的测量就采用了短枪(shortgun)方法,这就要求把大量的较短的序列

全体构成了重叠群(Contigs).逐步把它们拼接起来形成序列更长的重叠群,直

至得到完整序列的过程称为重叠群装配.从算法层次来看,序列的重叠群是一个

NP-完全问题.

6, 遗传密码的起源

通常对遗传密码的研究认为,密码子与氨基酸之间的关系是生物进化历史上

一次偶然的事件而造成的,并被固定在现代生物的共同祖先里,一直延续至今.

不同于这种"冻结"理论,有人曾分别提出过选择优化,化学和历史等三种学说

来解释遗传密码.随着各种生物基因组测序任务的完成,为研究遗传密码的起源

和检验上述理论的真伪提供了新的素材.

7, 基于结构的药物设计

人类基因工程的目的之一是要了解人体内约10万种蛋白质的结构,功能,

相互作用以及与各种人类疾病之间的关系,寻求各种治疗和预防方法,包括药物

治疗.基于生物大分子结构及小分子结构的药物设计是生物信息学中的极为重要

的研究领域.为了抑制某些酶或蛋白质的活性,在已知其蛋白质3级结构的基础

上,可以利用分子对齐算法,在计算机上设计抑制剂分子,作为候选药物.这一

领域目的是发现新的基因药物,有着巨大的经济效益.

8, 其他

如基因表达谱分析,代谢网络分析;基因芯片设计和蛋白质组学数据分析等,

逐渐成为生物信息学中新兴的重要研究领域;在学科方面,由生物信息学衍生的

学科包括结构基因组学,功能基因组学,比较基因组学,蛋白质学,药物基因组

学,中药基因组学,肿瘤基因组学,分子流行病学和环境基因组学.

从现在的发展不难看出,基因工程已经进入了后基因组时代.我们也有应对

与生物信息学密切相关的如机器学习,和数学中可能存在的误导有一个清楚的认

识.

三, 生物信息学与机器学习

生物信息的大规模给数据挖掘提出了新课题和挑战,需要新的思想的加入.

常规的计算机算法仍可以应用于生物数据分析中,但越来越不适用于序列分析问

题.究竟原因,是由于生物系统本质上的模型复杂性及缺乏在分子层上建立的完

备的生命组织理论.

西蒙曾给出学习的定义:学习是系统的变化,这种变化可使系统做相同工作

时更有效[4].机器学习的目的是期望能从数据中自动地获得相应的理论,通过采

用如推理,模型拟合及从样本中学习,尤其适用于缺乏一般性的理论,"噪声"

模式,及大规模数据集.因此,机器学习形成了与常规方法互补的可行的方法.

机器学习使得利用计算机从海量的生物信息中提取有用知识,发现知识成为可能

[5].

机器学习方法在大样本,多向量的数据分析工作中发挥着日益重要的作用,

而目前大量的基因数据库处理需要计算机能自动识别,标注,以避免即耗时又花

费巨大的人工处理方法.早期的科学方法—观测和假设----面对高数据的体积,

快速的数据获取率和客观分析的要求---已经不能仅依赖于人的感知来处理了.因

而,生物信息学与机器学习相结合也就成了必然.

机器学习中最基本的理论框架是建立在概率基础上的,从某种意义来说,是

统计模型拟合的延续,其目的均为提取有用信息.机器学习与模式识别和统计推

理密切相关.学习方法包括数据聚类,神经网络分类器和非线性回归等等.隐马

尔可夫模型也广泛用于预测DNA的基因结构.目前研究重心包括:1)观测和

探索有趣的现象.目前ML研究的焦点是如何可视化和探索高维向量数据.一般

的方法是将其约简至低维空间,如常规的主成分分析(PCA),核主成分分析

(KPCA),独立成分分析(Independent component analysis),局部线性嵌套(Locally

Linear embedding).2)生成假设和形式化模型来解释现象[6].大多数聚类方法可

看成是拟合向量数据至某种简单分布的混合.在生物信息学中聚类方法已经用于

microarray数据分析中,癌症类型分类及其他方向中.机器学习也用于从基因数

据库中获得相应的现象解释.

机器学习加速了生物信息学的进展,也带了相应的问题.机器学习方法大多

假定数据符合某种相对固定的模型,而一般数据结构通常是可变的,在生物信息

学中尤其如此,因此,有必要建立一套不依赖于假定数据结构的一般性方法来寻

找数据集的内在结构.其次,机器学习方法中常采用"黑箱"操作,如神经网络

和隐马尔可夫模型,对于获得特定解的内在机理仍不清楚.

四, 生物信息学的数学问题

生物信息学中数学占了很大的比重.统计学,包括多元统计学,是生物信息

学的数学基础之一;概率论与随机过程理论,如近年来兴起的隐马尔科夫链模型

(HMM),在生物信息学中有重要应用;其他如用于序列比对的运筹学;蛋白质

空间结构预测和分子对接研究中采用的最优化理论;研究DNA超螺旋结构的拓

扑学;研究遗传密码和DNA序列的对称性方面的群论等等.总之,各种数学理

论或多或少在生物学研究中起到了相应的作用.

但并非所有的数学方法在引入生物信息学中都能普遍成立的,以下以统计学

和度量空间为例来说明.

1, 统计学的悖论

数学的发展是伴随悖论而发展的.对于进化树研究和聚类研究中最显着的悖

论莫过于均值了,如图1:

图1 两组同心圆的数据集

图1是两组同心圆构成的数据集,显然,两组数据集的均值均在圆点,这也

就说明了要采用常规的均值方法不能将这两类分开,也表明均值并不能带来更多

的数据的几何性质.那么,如果数据呈现类似的特有分布时,常有的进化树算法

和聚类算法(如K-均值)往往会得错误的结论.统计上存在的陷阱往往是由于

对数据的结构缺乏一般性认识而产生的.

2, 度量空间的假设

在生物信息学中,进化树的确立,基因的聚类等都需要引入度量的概念.举

例来说,距离上相近或具有相似性的基因等具有相同的功能,在进化树中满足分

值最小的具有相同的父系,这一度量空间的前提假设是度量在全局意义下成立.

那么,是否这种前提假设具有普适性呢

我们不妨给出一般的描述:假定两个向量为A,B,其中,

,则在假定且满足维数间线性无关的前提下,两个

向量的度量可定义为:

(1)

依据上式可以得到满足正交不变运动群的欧氏度量空间,这也是大多数生物信息

学中常采用的一般性描述,即假定了变量间线性无关.

然而,这种假设一般不能正确描述度量的性质,尤其在高维数据集时,不考

虑数据变量间的非线性相关性显然存在问题,由此,我们可以认为,一个正确的

度量公式可由下式给出:

(2)

上式中采用了爱因斯坦和式约定,描述了变量间的度量关系.后者在满足

(3)

时等价于(1),因而是更一般的描述,然而问题在于如何准确描述变量间的非线

性相关性,我们正在研究这个问题.

五, 几种统计学习理论在生物信息学中应用的困难

生物信息学中面对的数据量和数据库都是规模很大的,而相对的目标函数却

一般难以给出明确的定义.生物信息学面临的这种困难,可以描述成问题规模的

巨大以及问题定义的病态性之间的矛盾,一般从数学上来看,引入某个正则项来

改善性能是必然的[7].以下对基于这一思想产生的统计学习理论[8],Kolmogorov

复杂性[98]和BIC(Bayesian Information Criterion)[109]及其存在的问题给出简要介

绍.

支持向量机(SVM)是近来较热门的一种方法,其研究背景是Vapnik的统计

学习理论,是通过最大化两个数据集的最大间隔来实现分类,对于非线性问题则

采用核函数将数据集映射至高维空间而又无需显式描述数据集在高维空间的性

质,这一方法较之神经方法的好处在于将神经网络隐层的参数选择简化为对核函

数的选择,因此,受到广泛的注意.在生物信息学中也开始受到重视,然而,核

函数的选择问题本身是一个相当困难的问题,从这个层次来看,最优核函数的选

择可能只是一种理想,SVM也有可能象神经网络一样只是机器学习研究进程中

又一个大气泡.

Kolmogorov复杂性思想与统计学习理论思想分别从不同的角度描述了学习

的性质,前者从编码的角度,后者基于有限样本来获得一致收敛性.Kolmogorov

复杂性是不可计算的,因此由此衍生了MDL原则(最小描述长度),其最初只

适用于离散数据,最近已经推广至连续数据集中,试图从编码角度获得对模型参

数的最小描述.其缺陷在于建模的复杂性过高,导致在大数据集中难以运用.

BIC准则从模型复杂性角度来考虑,BIC准则对模型复杂度较高的给予大的

惩罚,反之,惩罚则小,隐式地体现了奥卡姆剃刀("Occam Razor")原理,近

年也广泛应用于生物信息学中.BIC准则的主要局限是对参数模型的假定和先验

的选择的敏感性,在数据量较大时处理较慢.因此,在这一方面仍然有许多探索

的空间.

六, 讨论与总结

人类对基因的认识,从以往的对单个基因的了解,上升到在整个基因组水平

上考察基因的组织结构和信息结构,考察基因之间在位置,结构和功能上的相互

关系.这就要求生物信息学在一些基本的思路上要做本质的观念转变,本节就这

些问题做出探讨和思索.

启发式方法:

Simond在人类的认知一书中指出,人在解决问题时,一般并不去寻找最优

的方法,而只要求找到一个满意的方法.因为即使是解决最简单的问题,要想得

到次数最少,效能最高的解决方法也是非常困难的.最优方法和满意方法之间的

困难程度相差很大,后者不依赖于问题的空间,不需要进行全部搜索,而只要能

达到解决的程度就可以了.正如前所述,面对大规模的序列和蛋白质结构数据集,

要获得全局结果,往往是即使算法复杂度为线性时也不能够得到好的结果,因此,

要通过变换解空间或不依赖于问题的解空间获得满意解,生物信息学仍需要人工

智能和认知科学对人脑的进一步认识,并从中得到更好的启发式方法.

问题规模不同的处理:

Marvin Minsky在人工智能研究中曾指出:小规模数据量的处理向大规模数

据量推广时,往往并非算法上的改进能做到的,更多的是要做本质性的变化.这

好比一个人爬树,每天都可以爬高一些,但要想爬到月球,就必须采用其他方法

一样.在分子生物学中,传统的实验方法已不适应处理飞速增长的海量数据.同

样,在采用计算机处理上,也并非依靠原有的计算机算法就能够解决现有的数据

挖掘问题.如在序列对齐(sequence Alignment)问题上,在小规模数据中可以采用

动态规划,而在大规模序列对齐时不得不引入启发式方法,如BALST,FASTA.

乐观中的隐扰

生物信息学是一门新兴学科,起步于20世纪90年代,至今已进入"后基因

组时代",目前在这一领域的研究人员均呈普遍乐观态度,那么,是否存在潜在

的隐扰呢

不妨回顾一下早期人工智能的发展史[11],在1960年左右,西蒙曾相信不出

十年,人类即可象完成登月一样完成对人的模拟,造出一个与人智能行为完全相

同的机器人.而至今为止,这一诺言仍然遥遥无期.尽管人工智能研究得到的成

果已经渗入到各个领域,但对人的思维行为的了解远未完全明了.从本质来看,

这是由于最初人工智能研究上定位错误以及没有从认识论角度看清人工智能的

本质造成的;从研究角度来看,将智能行为还原成一般的形式化语言和规则并不

能完整描述人的行为,期望物理科学的成功同样在人工智能研究中适用并不现

实.

反观生物信息学,其目的是期望从基因序列上解开一切生物的基本奥秘,从

结构上获得生命的生理机制,这从哲学上来看是期望从分子层次上解释人类的所

有行为和功能和致病原因.这类似于人工智能早期发展中表现的乐观行为,也来

自于早期分子生物学,生物物理和生物化学的成就.然而,从本质上来讲,与人

工智能研究相似,都是希望将生命的奥秘还原成孤立的基因序列或单个蛋白质的

功能,而很少强调基因序列或蛋白质组作为一个整体在生命体中的调控作用.我

们因此也不得不思考,这种研究的最终结果是否能够支撑我们对生物信息学的乐

观呢 现在说肯定的话也许为时尚早.

综上所述,不难看出,生物信息学并不是一个足以乐观的领域,究竟原因,

是由于其是基于分子生物学与多种学科交叉而成的新学科,现有的形势仍表现为

各种学科的简单堆砌,相互之间的联系并不是特别的紧密.在处理大规模数据方

面,没有行之有效的一般性方法;而对于大规模数据内在的生成机制也没有完全

明了,这使得生物信息学的研究短期内很难有突破性的结果.那么,要得到真正

的解决,最终不能从计算机科学得到,真正地解决可能还是得从生物学自身,从

数学上的新思路来获得本质性的动力.

毫无疑问,正如Dulbecco1986年所说:"人类的DNA序列是人类的真谛,

这个世界上发生的一切事情,都与这一序列息息相关".但要完全破译这一序列

以及相关的内容,我们还有相当长的路要走.

（来源 ------[InfoBio.org | 生物信息学研讨组]）http://www.infobio.org
生物信息学（Bioinformatics）是在生命科学的研究中，以计算机为工具对生物信息进行储存、检索和分析的科学。它是当今生命科学和自然科学的重大前沿领域之一，同时也将是21世纪自然科学的核心领域之一。其研究重点主要体现在基因组学(Genomics)和蛋白学(Proteomics)两方面，具体说就是从核酸和蛋白质序列出发，分析序列中表达的结构功能的生物信息。

生物信息学是一门利用计算机技术研究生物系统之规律的学科。

目前的生物信息学基本上只是分子生物学与信息技术（尤其是因特网技术）的结合体。生物信息学的研究材料和结果就是各种各样的生物学数据，其研究工具是计算机，研究方法包括对生物学数据的搜索（收集和筛选）、处理（编辑、整理、管理和显示）及利用（计算、模拟）。

1990年代以来，伴随着各种基因组测序计划的展开和分子结构测定技术的突破和Internet的普及，数以百计的生物学数据库如雨后春笋般迅速出现和成长。对生物信息学工作者提出了严峻的挑战：数以亿计的ACGT序列中包涵着什么信息？基因组中的这些信息怎样控制有机体的发育？基因组本身又是怎样进化的？

生物信息学的另一个挑战是从蛋白质的氨基酸序列预测蛋白质结构。这个难题已困扰理论生物学家达半个多世纪，如今找到问题答案要求正变得日益迫切。诺贝尔奖获得者W. Gilbert在1991年曾经指出：“传统生物学解决问题的方式是实验的。现在，基于全部基因都将知晓，并以电子可操作的方式驻留在数据库中，新的生物学研究模式的出发点应是理论的。一个科学家将从理论推测出发，然后再回到实验中去，追踪或验证这些理论假设”。

生物信息学的主要研究方向： 基因组学 - 蛋白质组学 - 系统生物学 - 比较基因组学

姑且不去引用生物信息学冗长的定义，以通俗的语言阐述其核心应用即是：随着包括人类基因组计划在内的生物基因组测序工程的里程碑式的进展，由此产生的包括生物体生老病死的生物数据以前所未有的速度递增，目前已达到每14个月翻一番的速度。同时随着互联网的普及，数以百计的生物学数据库如雨后春笋般迅速出现和成长。然而这些仅仅是原始生物信息的获取，是生物信息学产业发展的初组阶段，这一阶段的生物信息学企业大都以出售生物数据库为生。以人类基因组测序而闻名的塞莱拉公司即是这一阶段的成功代表。
原始的生物信息资源挖掘出来后，生命科学工作者面临着严峻的挑战：数以亿计的ACGT序列中包涵着什么信息？基因组中的这些信息怎样控制有机体的发育？基因组本身又是怎样进化的？生物信息学产业的高级阶段体现于此，人类从此进入了以生物信息学为中心的后基因组时代。结合生物信息学的新药创新工程即是这一阶段的典型应用。

E. 程序员算法基础——贪心算法

贪心是人类自带的能力，贪心算法是在贪心决策上进行统筹规划的统称。

比如一道常见的算法笔试题---- 跳一跳 ：

我们自然而然能产生一种解法：尽可能的往右跳，看最后是否能到达。
本文即是对这种贪心决策的介绍。

狭义的贪心算法指的是解最优化问题的一种特殊方法，解决过程中总是做出当下最好的选择，因为具有最优子结构的特点，局部最优解可以得到全局最优解；这种贪心算法是动态规划的一种特例。 能用贪心解决的问题，也可以用动态规划解决。

而广义的贪心指的是一种通用的贪心策略，基于当前局面而进行贪心决策。以 跳一跳 的题目为例：
我们发现的题目的核心在于 向右能到达的最远距离 ，我们用maxRight来表示；
此时有一种贪心的策略：从第1个盒子开始向右遍历，对于每个经过的盒子，不断更新maxRight的值。

贪心的思考过程类似动态规划，依旧是两步： 大事化小 ， 小事化了 。
大事化小：
一个较大的问题，通过找到与子问题的重叠，把复杂的问题划分为多个小问题；
小事化了：
从小问题找到决策的核心，确定一种得到最优解的策略，比如跳一跳中的 向右能到达的最远距离 ；

在证明局部的最优解是否可以推出全局最优解的时候，常会用到数学的证明方式。

如果是动态规划：
要凑出m元，必须先凑出m-1、m-2、m-5、m-10元，我们用dp[i]表示凑出i元的最少纸币数；
有 dp[i]=min(dp[i-1], dp[i-2], dp[i-5], dp[i-10]) + 1 ;
容易知道 dp[1]=dp[2]=dp[5]=dp[10]=1 ；
根据以上递推方程和初始化信息，可以容易推出dp[1~m]的所有值。

似乎有些不对？ 平时我们找零钱有这么复杂吗？
从贪心算法角度出发，当m>10且我们有10元纸币，我们优先使用10元纸币，然后再是5元、2元、1元纸币。
从日常生活的经验知道，这么做是正确的，但是为什么？

假如我们把题目变成这样，原来的策略还能生效吗？

接下来我们来分析这种策略：
已知对于m元纸币，1，2，5元纸币使用了a，b，c张，我们有a+2b+5c=m；
假设存在一种情况，1、2、5元纸币使用数是x，y，z张，使用了更少的5元纸币（z<c），且纸币张数更少（x+y+z<a+b+c），即是用更少5元纸币得到最优解。
我们令k=5*(c-z)，k元纸币需要floor(k/2)张2元纸币，k%2张1元纸币；（因为如果有2张1元纸币，可以使用1张2元纸币来替代，故而1元纸币只能是0张或者1张）
容易知道，减少(c-z)张5元纸币，需要增加floor(5*(c-z)/2)张2元纸币和(5*(c-z))%2张纸币，而这使得x+y+z必然大于a+b+c。
由此我们知道不可能存在使用更少5元纸币的更优解。
所以优先使用大额纸币是一种正确的贪心选择。

对于1、5、7元纸币，比如说要凑出10元，如果优先使用7元纸币，则张数是4；（1+1+1+7）
但如果只使用5元纸币，则张数是2；（5+5）
在这种情况下，优先使用大额纸币是不正确的贪心选择。（但用动态规划仍能得到最优解）

如果是动态规划：
前i秒的完成的任务数，可以由前面1~i-1秒的任务完成数推过来。
我们用 dp[i]表示前i秒能完成的任务数 ；
在计算前i秒能完成的任务数时，对于第j个任务，我们有两种决策：
1、不执行这个任务，那么dp[i]没有变化；
2、执行这个任务，那么必须腾出来(Sj, Tj)这段时间，那么 dp[i] = max(dp[i], dp[ S[j] ] ) + 1 ；
比如说对于任务j如果是第5秒开始第10秒结束，如果i>=10，那么有 dp[i]=max(dp[i], dp[5] + 1)； （相当于把第5秒到第i秒的时间分配给任务j）

再考虑贪心的策略，现实生活中人们是如何安排这种多任务的事情？我换一种描述方式：

我们自然而然会想到一个策略： 先把结束时间早的兼职给做了！
为什么？
因为先做完这个结束时间早的，能留出更多的时间做其他兼职。
我们天生具备了这种优化决策的能力。

这是一道 LeetCode题目 。
这个题目不能直接用动态规划去解，比如用dp[i]表示前i个人需要的最少糖果数。
因为（前i个人的最少糖果数）这种状态表示会收到第i+1个人的影响，如果a[i]>a[i+1]，那么第i个人应该比第i+1个人多。
即是 这种状态表示不具备无后效性。

如果是我们分配糖果，我们应该怎么分配？
答案是： 从分数最低的开始。
按照分数排序，从最低开始分，每次判断是否比左右的分数高。
假设每个人分c[i]个糖果，那么对于第i个人有 c[i]=max(c[i-1],c[c+1])+1 ; （c[i]默认为0，如果在计算i的时候,c[i-1]为0，表示i-1的分数比i高）
但是，这样解决的时间复杂度为 O(NLogN) ，主要瓶颈是在排序。
如果提交，会得到 Time Limit Exceeded 的提示。

我们需要对贪心的策略进行优化：
我们把左右两种情况分开看。
如果只考虑比左边的人分数高时，容易得到策略：
从左到右遍历，如果a[i]>a[i-1]，则有c[i]=c[i-1]+1；否则c[i]=1。

再考虑比右边的人分数高时，此时我们要从数组的最右边，向左开始遍历：
如果a[i]>a[i+1], 则有c[i]=c[i+1]+1；否则c[i]不变；

这样讲过两次遍历，我们可以得到一个分配方案，并且时间复杂度是 O(N) 。

题目给出关键信息：1、两个人过河，耗时为较长的时间；
还有隐藏的信息：2、两个人过河后，需要有一个人把船开回去；
要保证总时间尽可能小，这里有两个关键原则： 应该使得两个人时间差尽可能小（减少浪费），同时船回去的时间也尽可能小（减少等待）。

先不考虑空船回来的情况，如果有无限多的船，那么应该怎么分配？
答案： 每次从剩下的人选择耗时最长的人，再选择与他耗时最接近的人。

再考虑只有一条船的情况，假设有A/B/C三个人，并且耗时A<B<C。
那么最快的方案是：A+B去, A回；A+C去；总耗时是A+B+C。（因为A是最快的，让其他人来回时间只会更长， 减少等待的原则 ）

如果有A/B/C/D四个人，且耗时A<B<C<D，这时有两种方案：
1、最快的来回送人方式，A+B去；A回；A+C去，A回；A+D去； 总耗时是B+C+D+2A （减少等待原则）
2、最快和次快一起送人方式，A+B先去，A回；C+D去，B回；A+B去；总耗时是 3B+D+A （减少浪费原则）
对比方案1、2的选择，我们发现差别仅在A+C和2B；
为何方案1、2差别里没有D？
因为D最终一定要过河，且耗时一定为D。

如果有A/B/C/D/E 5个人，且耗时A<B<C<D<E，这时如何抉择？
仍是从最慢的E看。（参考我们无限多船的情况）
方案1，减少等待；先送E过去，然后接着考虑四个人的情况；
方案2，减少浪费；先送E/D过去，然后接着考虑A/B/C三个人的情况；（4人的时候的方案2）

到5个人的时候，我们已经明显发了一个特点：问题是重复，且可以由子问题去解决。
根据5个人的情况，我们可以推出状态转移方程 dp[i] = min(dp[i - 1] + a[i] + a[1], dp[i - 2] + a[2] + a[1] + a[i] + a[2]);
再根据我们考虑的1、2、3、4个人的情况，我们分别可以算出dp[i]的初始化值：
dp[1] = a[1];
dp[2] = a[2];
dp[3] = a[2]+a[1]+a[3];
dp[4] = min(dp[3] + a[4] + a[1], dp[2]+a[2]+a[1]+a[4]+a[2]);

由上述的状态转移方程和初始化值，我们可以推出dp[n]的值。

贪心的学习过程，就是对自己的思考进行优化。
是把握已有信息，进行最优化决策。
这里还有一些收集的 贪心练习题 ，可以实践练习。
这里 还有在线分享，欢迎报名。