 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
机器学习算法在生物信息学中的应用
下载积分：3000
内容提示：机器学习算法在生物信息学中的应用，学习，算法，帮助，机器学习，机器学习算法，机器学习在，应用，在生物信息学，中的应用，生物信息学，算法在，机器学习的应用，机器学习应用
文档格式：PDF|
浏览次数：8|
上传日期： 09:03:03|
文档星级：
该用户还上传了这些文档
机器学习算法在生物信息学中的应用
官方公共微信　　推荐期刊投稿
&&&免费论文
&&&收费论文
&&&浏览历史统计机器学习，生物信息学和自然语言处理
算法设计与分析
《集合论与代数结构》教学计划。以下资料纯属学术性质，作者拥有它们的版权和解释权，在声明来源的前提下可免费用于教学科研。但是，未经作者允许不得擅自将它们转载、稍做修改据为己有或用于商业行为，所造成的不良后果皆由肇事者一人承担。特此声明。
集合元素个数的描述及大小比较。非常关键的一节，其中Schroder-Bernstein定理及其证明尤为重要。
（PowerPoint讲义）
（PowerPoint讲义）
（PowerPoint讲义）
分子点群的分类
群论在分子对称性方面应用浅说
Bickel的名著《Mathematical
Statistics --- Basic Ideas and Selected Topics》（第一版）的第一章。2001年，Bickel出版了该书的第二版的上卷，有较大的更动，增添了当前数理统计的一些新方法。
不过，该书的错误实在太多，有两份勘误表（到Bickel的主页上下载），要耐着性子改半天。Bickel计划2003年出版该书的下卷，现在都7月份了，一点动静也没有。
大数定律和中心极限定理是数理统计的基石，在Bickel的书的附录里有提纲挈领的描述。另外，Gnedenko的概率论教材和Feller的书里对该内容也有精彩的介绍。
北京大学信息科学技术学院本科主干基础课程：、李霄翔、李德珠、张力。讨论问题、下载资料、查看成绩等请访问北大信息科学技术学院教学平台。概率论的主要内容如下：
《概率统计A》教学大纲
数理统计的主要内容如下：
随机变量与随机向量
一些常见的分布
Markov链与隐Markov模型
概率论期中考试
ü非参数统计学简介
概率论的主要参考书目：
1.Feller, W. (1968) An Introduction to Probability Theory and Its
Applications, Volume I, New York: John Wiley & Sons, Inc. (中译本《概率论及其应用》，胡迪鹤译)
2.Gnedenko (1954) 《概率论教程》，高等教育出版社
3.Shiryayev, A. N. (1984) Probability, Spring-Verlag
New York Inc.
4.王梓坤 (1996) 《概率论基础及其应用》，北京师范大学出版社
数理统计的主要参考书目：
1.Bickel, P. J. and Doksum, K. A.
(1977) Mathematical Statistics: Basic Ideas and Selected Topics, Holden-Day,
2.[波兰] M. 费史 (1978) 《概率论及数理统计》，上海科学技术出版社
3.Hogg, R. V. and Craig, A. T. (1978) Introduction to
Mathematical Statistics, Macmillan Publishing Co., Inc.
4.Rohatgi, V. K. (1976) An introduction to Probability Theory and
Mathematical Statistics. John Wiley & Sons Inc.
5.陈希孺 (2002) 《数理统计学简史》，湖南教育出版社
：2008年春季北京大学信息科学技术学院研究生课程。助教：王子桢。主要参考书如下：
1.Bishop, C. M. (2006) Pattern
Recognition and Machine Learning, Spring Science+Business
Media, LLC
2.Berger, J. O. (1985) Statistical
Decision Theory and Bayesian Analysis, Second Edition, Springer-Verlag New York, Inc.
A. and Carlin, J. B. and Stern, H. S. and Rubin, D. B. (2004) Bayesian Data
Analysis, Second Edition, Chapman & Hall/CRC
4.Rasmussen, C. E. and Williams, C. K.
I. (2006) Gaussian Processes for Machine Learning, MIT Press
5.Ripley, B. D. (1996) Pattern
Recognition and Neural Networks, Cambridge University
6.Fukunaga,
K. (1990) Introduction to Statistical Pattern Recognition, Second Edition,
Academic Press
7.Mitchell, T. M. (1997) Machine
Learning, The McGraw-Hill Companies, Inc. (undergraduate course of machine
欢迎访问本课程的教学平台http://162.105.31.238/index.htm，可以下载课程资料和老师指定的参考文献。非数学专业的同学可能需要补充一些实变函数和泛函分析的知识，请参考Kolmogorov和Fomin的Introductory to Real Analysis。《统计机器学习》课程的主要内容如下：
l（参考Riesz和Nagy的《泛函分析讲义》第二卷，科学出版社，1980。此书重点着墨于Hilbert空间的几何学，第六章讲了Mercer定理。）三篇课外阅读的论文：
1., N. Aronszajn, 1950
the Mathematical Foundations of Learning, F. Cucker
and S. Smale, 2001
l（阅读Rasmussen和Williams的新作《Gaussian
Processes for Machine Learning》，2006）
l粒子群算法（报告人：刘坤、张军旗博士）
l期中读书报告及讨论
l，课后阅读：
l信息几何学简介
概率论与数理统计
作者: Nilsson
译者: 郑扣根 庄越挺
书号: 7-111-07885-3
定价: ￥30.00
出版社: 机械工业出版社
本书内容：
1.介绍了Artificial Neural Net和heuristic learning的基本思想。
2.描述了学习启发式搜索和动作策略的技术。
3.讨论了rule learning，inductive logic programming和explanation-based
learning。
4.在介绍了logic-based planning之后，讨论了learning plan。
Artificial Intelligence
2003年4月初至2003年6月中旬，我在新疆石河子大学给00级本科生讲授《人工智能》。感谢北大计算机系许卓群教授提供该课程在北大的电子教案；感谢石河子大学信息工程技术学院给予我教学上、生活上的帮助（特别感谢梁院长、杨书记、荣江、郭理等老师）；感谢石河子大学对口支援办公室的闫卫华副主任、左兵老师给予我的帮助，尤其是当非典时期我不合时宜地发烧拉肚子的时候，他们冒着生命的危险来医院探望我们。
助教（温珍珊）
北大计算机系2002级硕士研究生。作业可以是电子版本，直接发给温珍珊同学即可。另外，他还负责答疑（通过邮件）。
内容选自MIT的教材Introduction to Algorithms（第二版，算法理论的经典名著 ），作者包括：T. H. Cormen，C. E. Leiserson，R. L. Reviest和C.
Stein。另一本教学参考书是R. Sedgewick的Algorithms in C++, Parts 1-4
(Fundamentals, Data Structures, Sortings, and
Searching)和Algorithms in C++, Parts 5
(Graph Algorithms)。Sedgewick的书内容更丰富些。数学家Abel说过，“Read the masters', not their pupils'”。在你决定选这门课之前，请仔细阅读《算法设计与分析》的教学大纲。
Wilf教授的书（网络版），一本可爱的小册子。Introduction to Algorithms的前言中提到了这本书。
为什么我们要研究算法和复杂性理论？本节课介绍了Insertion-Sort和Merge-Sort两个算法，并比较了它们时间复杂度的优劣。
刻划时间复杂度的常用函数以及它们增长速度的比较，用到一些数学分析（或高等数学）的知识。最后，我们分析了Merge-Sort算法的时间复杂度。
介绍了求解递归式的三种方法，证明了Master Theorem。证明技巧就是递归树方法：先考虑n恰好是b的次幂的情形；再考虑一般情形。Master Theorem在以后的学习中经常用到，务必掌握。
矩阵是科学计算不可缺少的工具，矩阵计算理论可参考Golub和von Loan的名著Matrix Computation。本节介绍了矩阵乘法的Strassen算法（用的是分治法），求解线性方程组的LU算法和LUP算法，矩阵求逆的算法。介绍了对称正定阵的许多有趣的性质。最后，证明了Winograd定理和Aho-Hopcroft-Ullman定理，该定理说矩阵乘法和矩阵求逆的时间复杂度相等。这是非常有趣的一节，充满了技巧。
除了以最坏情况的时间消耗作为衡量一个算法优劣的标准，我们也可以用平均时间消耗作为一个标准。如果一个算法在最坏的情况下时间复杂度很高并且其发生的概率很小，我们就可以通过将输入随机化降低风险——这样做也可能导致好的输入变坏，但是为了在统计意义上达到最优，这样做是值得的。
Heapsort是一种比Insertion-Sort和Merge-Sort都有效的算法。Heap有许多有趣的性质，是一个重要的数据结构。
分析了Quicksort，Radixsort和Bucketsort的算法复杂度。
首先，以Assembly Line Problem和Matrix-chain Multiplication为例，给出动态规划算法。主要目的是直观地启发何时、如何使用动态规划算法。在介绍了动态规划算法的一般策略后，我们分析了求解最长公共子序列和最优二分搜索树的动态规划算法。建议大家看Hidden
Markov Model (HMM)的Viterbi算法，它在语音识别和切分/词性标注（自然语言处理）等有较好的应用。
介绍了线性规划及其单纯形算法。线性规划是最优化理论中很重要的一部分，有着广泛的应用背景。单纯形法已经相当成熟，在线性规划的算法中实用性最强。
（以背包问题为例）介绍了贪心法与动态规划的关系以及使用贪心法必须满足的两个性质。介绍了Huffman编码的贪心算法。贪心法什么时候能取到最优界并无一般理论，但对于求最大weighted matroid（拟阵理论是H. Whitney于1935年提出的）我们有一个完美的结果——贪心法可取到最优解。本节最后介绍了用贪心matroid方法解决unit-time task scheduling问题，很有趣。
介绍了广度优先和深度优先的图搜索算法及其性质。接着介绍了深度优先搜索的两个应用：拓扑排序和如何找出一个有向图的所有强连通分支。
介绍了最小生成树的性质和Kruskal算法和Prim算法。
两个n次多项式相乘，用FFT可将时间复杂度从Theta(n^2)降至Theta(nlog
n)。需要一些代数学的知识，蛮有趣的。
首先，概要性地介绍了初等数论的一些结果（譬如，Euler定理和中国剩余定理）和它们在求解最大公约数（及其线性表示）、不定方程、不定方程组等方面的应用，给出了相应的算法。第二部分介绍了公钥密码系统加密和数字签名的基本想法和RSA算法。作为补充材料，最后介绍了素性检验和整数分解。
如果存在异常样本点，中位数要比样本均值更有效。在统计学中，顺序统计量非常重要（例如，基于秩的统计推断）。我们要解决的问题是：给定n个不等的实数，找出第i小的那个。首先介绍一个随机算法，它的时间复杂度的期望是线性的。接着，我们给出一个确定性的算法，它在最坏的情形可达到线性。寻找顺序统计量的算法所需的比较次数介于2n和3n之间，但精确的系数至今未知。
介绍了Naive串匹配、Rabin-Karp串匹配、基于有限自动机的串匹配和Knuth-Morris-Pratt串匹配算法并分析了它们的算法复杂度。要点：如果pattern
string与text string部分匹配，则pattern string向右最大滑动的步数与pattern string自身结构有关。正是因为这个特点，KMP算法分作两步：前处理和匹配。KMP算法前处理的时间是pattern
string长度的线性函数，匹配的时间是text string长度的线性函数。
an amortized analysis, the time required to perform a sequence of
data-structure operations is averaged over all the operations performed.
Amortized analysis can be used to show that the average cost of an operation
is small, if one averages over a sequence of operations, even though a single
operation which the sequence might be expensive.
---from Introduction to Algorithms, pp405
问题：给定一个加权有向图G和一个源点s，对于G中任意一点v，求从s到v的最短路径。我们介绍三个算法：Bellman-Ford算法，有向非循环图的单源点最短路径算法和Dijkstra算法。最后，介绍如何利用Bellman-Ford算法判定差分约束方程组（线性规划中一类特殊的约束条件）是否有解。
问题：给定一个加权有向图G，求任意点对u,v间的最短路径。首先，类比两个n阶方阵的乘法，我们介绍一个动态规划算法。第二个算法是Floyd-Warshall算法，也可用于计算有向图的传递闭包。第三个算法（Johnson算法）利用“单源点的最短路径”问题的Bellman-Ford算法和Dijkstra算法，处理稀疏图时要好于前两个算法。
问题：给定一个有向图，每条边都赋予一个非负整数（表示承载能力），规定一个源点和一个终点，求解从源点到终点的最大流。我们介绍了Ford-Fulkerson方法，该方法也可用来求解最大二部图匹配问题。
排序网络是一个并行算法，用于快速排序（时间复杂度为O(log^2 n)）。
介绍三个平面几何问题的算法。第一个问题是：给定一个线段的集合，判定其中任何两条线段是否相交。第二个问题是：给定平面上n个点，求解覆盖它们的最小凸集（Graham算法和Jarvis算法）。第三个问题是：给定平面上n个点，求所有可能两点间的最小距离（1985年，Shamos用分治法解决，时间复杂度为O(nlog n)）。
定义了NP-completeness，介绍了如何证明一个决策问题（decision problem）是NP-hard的。最后介绍了几个经典的NP-complete问题。