《Bioinfo_Algorithm 生物信息学课件》由会员分享，可在线阅读，更多相关《Bioinfo_Algorithm 生物信息学课件（67页珍藏版）》请在金锄头文库上搜索。
1、Xiaopeng Zhu 2011 FallREFERENCE BOOKSModel and DataModelDataCriterionAlgorithmAlgorithm IntroductionXiaopeng Zhu 2011 Fall定义: algorithm算法是指完成一个任务所需要的具体步骤和方法。Algorithm 来自于9世纪波斯数学家花拉子米 （比阿勒霍瓦里松，波斯语：，拉丁 转写：al-Khwarizmi），因为比阿勒霍瓦里松在数学上提出了算法这 个概念。“算法”原为“algorism“， 意思是阿拉伯数字的运算法则，在18世纪演变 为“algorithm“。欧几里得算法
2、被人们认为是史 上第一个算法。递归算法汉诺塔问题（又称河内塔问题）是根据一个传说形成的一个问 题： 有三根杆子A，B，C。A杆上有N个(N1)穿孔圆盘，盘的尺寸由 下到上依次变小。要求按下列规则将所有圆盘移至C杆：1.每次只能移动一个圆盘；2.大盘不能叠在小盘上面。 提示：可将圆盘临时置于B杆，也可将从A杆移出的圆盘重新移回 A杆，但都必须尊循上述两条规则。 问：如何移？最少要移动多少次？一般取N=64。这样，最少需移动264-1次。即如果一秒钟能移 动一块圆盘，仍将需5845.54亿年。目前按照宇宙大爆炸理论的 推测，宇宙的年龄仅为137亿年。在真实玩具中，一般N=8；这将需移动255次。如
3、果N=10，需 移动1023次。如果N=15，需移动32767次；这就是说，如果一 个人从3岁到99岁，每天移动一块圆盘，他仅能移动15块。如 果N=20，需移动1048575次，即超过了一百万次。我们先从最简单的说起如果只有一个盘子.ABC这个我会呀!ABCAC我是研究生, 不是小孩子!来点复杂的!来2个盘子怎么样?ABCABCABCABCABC这我也会呀!ABCABCABCABC这一步貌似我刚才学会的呀这一步貌似我刚才会的呀ABCABCABCABCn个盘子n-1个盘子n-1个盘子递归算法解Fibonacci序列f(1)=1 f(2)=1 f(n)=f(n-1)+f(n-2)递归算法1,1,
4、2,3,5,8,13,21,34.f(4)f(3)f(2)f(2)f(1)f(5)f(3)f(2)f(1)Fibonacci序列f(1)=1 f(2)=1 f(n)=f(n-1)+f(n-2)递归算法1,1,2,3,5,8,13,21,34.321115211Fibonacci序列f(1)=1 f(2)=1 f(n)=f(n-1)+f(n-2)动态规划算法1,1,2,3,5,8,13,21,34.1+1=21+2=32+3=5f(1)+f(2)=f(3)f(2)+f(3)=f(4)f(3)+f(4)=f(5)算法设计技巧穷举法分枝定界法动态规划算法分而治之贪婪法机器学习随机算法DNA Mapp
5、ing examine every possible variant to find a solutionEfficient in rare cases; usually impracticalAn Introduction to Bioinformatics Algorithmswww.bioalgorithms.info Partial Digest: Brute Force1. Find the restriction fragment of maximum length M. M is the length of the DNA sequence.2. For every possib
6、le set X=0, x2, ,xn-1, M compute the corresponding DX5. If DX is equal to the experimental partial digest L, then X is the correct restriction mapAn Introduction to Bioinformatics Algorithmswww.bioalgorithms.info BruteForcePDP1.BruteForcePDP(L, n): 2. M - maximum element in L 3. for every set of n 2
7、 integers 0 x2 xn-1 M 4. X - 0,x2,xn-1,M 5. Form DX from X 6. if DX = L 7. return X 8. output “no solution”An Introduction to Bioinformatics Algorithmswww.bioalgorithms.infoEfficiency of BruteForcePDP BruteForcePDP takes O(M n-2) time since it must examine all possible sets of positions. One way to
8、improve the algorithm is to limit the values of xi to only those values which occur in L.An Introduction to Bioinformatics Algorithmswww.bioalgorithms.info AnotherBruteForcePDP1.AnotherBruteForcePDP(L, n) 2. M - maximum element in L3. for every set of n 2 integers 0 x2 xn-1 M4. X - 0,x2,xn-1,M 5. Fo
9、rm DX from X 6. if DX = L 7. return X 8. output “no solution”An Introduction to Bioinformatics Algorithmswww.bioalgorithms.info AnotherBruteForcePDP1.AnotherBruteForcePDP(L, n) 2. M - maximum element in L3. for every set of n 2 integers 0 x2 xn-1 M from L4. X - 0,x2,xn-1,M 5. Form DX from X 6. if DX
10、 = L 7. return X 8. output “no solution”An Introduction to Bioinformatics Algorithmswww.bioalgorithms.infoEfficiency of AnotherBruteForcePDPIts more efficient, but still slow If L = 2, 998, 1000 (n = 3, M = 1000), BruteForcePDP will be extremely slow, but AnotherBruteForcePDP will be quite fastFewer
11、 sets are examined, but runtime is still exponential: O(n2n-4)An Introduction to Bioinformatics Algorithmswww.bioalgorithms.info Branch and Bound Algorithm for PDP1. Begin with X = 0 2. Remove the largest element in L and place it in X 3. See if the element fits on the right or left side of the rest
12、riction map 4. When it fits, find the other lengths it creates and remove those from L 5. Go back to step 1 until L is emptyAn Introduction to Bioinformatics Algorithmswww.bioalgorithms.info Branch and Bound Algorithm for PDP1. Begin with X = 0 2. Remove the largest element in L and place it in X 3.
13、 See if the element fits on the right or left side of the restriction map 4. When it fits, find the other lengths it creates and remove those from L 5. Go back to step 1 until L is emptyWRONG ALGORITHMAn Introduction to Bioinformatics Algorithmswww.bioalgorithms.infoDefining D(y, X) Before describin
14、g PartialDigest, first define D(y, X) as the multiset of all distances between point y and all other points in the set XD(y, X) = |y x1|, |y x2|, , |y xn|for X = x1, x2, , xnAn Introduction to Bioinformatics Algorithmswww.bioalgorithms.info PartialDigest AlgorithmPartialDigest(L):width - Maximum ele
15、ment in LDELETE(width, L)X - 0, widthPLACE(L, X)An Introduction to Bioinformatics Algorithmswww.bioalgorithms.info PartialDigest Algorithm (contd)1. PLACE(L, X) 2. if L is empty 3. output X 4. return 5. y - maximum element in L 6. Delete(y,L) 7. if D(y, X ) L 8. Add y to X and remove lengths D(y, X) from L 9. PLACE(L,X ) 10. Remove y from X and add lengths D(y, X) to L 11.if D(width-y, X ) L 12. Add width-y to X and remove lengths D(width-y, X) from L 13. PLACE(L,X ) 14. Remove width-y from X and a
