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

以下各题例子均来自老师的课件，看不明白的可以追本溯源。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，所以这一位点不在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=ATG,TGG,TGC,GTG,GGC,GCA,GCG,CGT。求最短路径。（1） 用汉密尔顿图：比如ATG的后两位和TGC的前两位相同，则由ATG向TGC画箭头。 ATG TGG TGC GTG GGC GCA GCG CGT由此得到两条路径：（2） 用欧拉图：将所给每个三联体分割成两个二联体（如ATG分成AT和TG），去除冗余，得到AT TG GC GG GT CA CG将能够形成已有三联体的两个二联体间画箭头，比如从TG始，已知有TGG和TGC，则由TG向GG和GC画箭头。最终得到：同样可分为两种结果：3. 比对问题。（10分）给出两个序列，利用动态规划算法进行序列比对。先画出表格，横行和纵行配对是1，不配是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.相继求出每一个表格中的数值，并用箭头标出数值来源。最终得到了最佳配对考试时要求找出最佳配对，标示出红色的箭头。4. 聚类问题。（10分）两种方法，层次聚类法和k-means法，每种方法5分。例如，有5个基因，它们的表达可以用坐标上的点标示（有可能横坐标代表某个时间的表达量，纵坐标代表另一个时间的表达量），将这五个基因聚类。（1） 层次聚类法：算出各点之间的距离，列出距离矩阵：首先找出最短的距离，即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归于了一类。再算重心：这就得出了最终的结果。如果点多的话，以上的步骤会重复更多次。 计算时点间的距离可以用根号表示，能看出