陈润生,生物信息学,考试算法题总结

《陈润生,生物信息学,考试算法题总结》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、以下各题例子均来自老师的课件，看不明白的可以追本溯源。O(∩_∩)O1.不完全酶切问题。（10分）给定一个DNA片段经不完全酶切所得到的所有片段，求酶切位点。举例说明：已知L={2，2，3，3，4，5，6，7，8，10}，求各酶切位点X={0}。首先将L中最大的数10挪到X中，因为10肯定是原始片段长度。即L={2，2，3，3，4，5，6，7，8，10}，X={0，10}。然后取出8，在这里有两种可能情况，即处于0端或10端，我们任取一种，处于0端。那么L中2和8被取出，X中添加2.即L={2，2，3，3，4，5，6，7，8，10}，X={0，2，10}。然后再取出7，因为没有1

2、，所以这一位点不在0端，而在10端。由此出现片段3，5，7，将他们从L中取出。即L={2，2，3，3，4，5，6，7，8，10}，X={0，2，7，10}。再看片段6，有三个可能性出现6片段，即切割位点在4，6或8。由于如果在6或8，必有1片段，所以舍弃。选位点4.这样产生了片段2，3，4，6.将它们从L中取出。即L={2，2，3，3，4，5，6，7，8，10}，X={0，2，4，7，10}。这样就得到了最终结果X。2.最短superstring问题。（10分）给出一个superstring的3mer谱，分别用欧拉图和汉密尔顿图找出最短的superstring。例如，已知S={A

3、TG,TGG,TGC,GTG,GGC,GCA,GCG,CGT}。求最短路径。（1）用汉密尔顿图：比如ATG的后两位和TGC的前两位相同，则由ATG向TGC画箭头。ATGTGGTGCGTGGGCGCAGCGCGT由此得到两条路径：（1）用欧拉图：将所给每个三联体分割成两个二联体（如ATG分成AT和TG），去除冗余，得到{ATTGGCGGGTCACG}将能够形成已有三联体的两个二联体间画箭头，比如从TG始，已知有TGG和TGC，则由TG向GG和GC画箭头。最终得到：同样可分为两种结果：1.比对问题。（10分）给出两个序列，利用动态规划算法进行序列比对。先画出表格，横行和纵行配对是1，

4、不配是0.然后根据Fi,j=max(Fi-1,j-1+Si,j,Fi-1,j+d,Fi,j-1+d)。其中Fi,j表示i行j列处的最大值；如果第i行和第j列正好配对，则Si,j=1；一般d=0.相继求出每一个表格中的数值，并用箭头标出数值来源。最终得到了最佳配对考试时要求找出最佳配对，标示出红色的箭头。1.聚类问题。（10分）两种方法，层次聚类法和k-means法，每种方法5分。例如，有5个基因，它们的表达可以用坐标上的点标示（有可能横坐标代表某个时间的表达量，纵坐标代表另一个时间的表达量），将这五个基因聚类。（1）层次聚类法：算出各点之间的距离，列出距离矩阵：首先找出最短的距离

5、，即A和C之间的距离为1，先将A和C聚类：再找最短距离，D和E之间1.4的距离最短：亦即：然后是AC和B之间的距离最短：亦即：最终：（2）k-means法：在坐标上任取两个（或更多，视聚类需要而定）点作为中心点，如本例取（5，6）和（8，7）。（下面的图写错了）分别计算A-E各点离以上两点的距离，离哪个更近就归于哪个。经计算，A、C归于绿点，B、E、D归于红点：然后抛开我们所任取的两个点，分别算出A和C的、B和E和D的重心（即平均数）：再分别以两个重心为中心点，从新计算A-E五个点到两个中心点的距离，离哪个近就归于哪个。这次B与A、C归于了一类。再算重心：这就得出了最终的结果。如

6、果点多的话，以上的步骤会重复更多次。计算时点间的距离可以用根号表示，能看出长短就行。5.自己找一篇生物信息学方面的论文，考试的时候写出这篇文章的题目、杂志等（送分），然后写出其主要内容，以及其中和我们讲课时提到的相关知识。（10分）