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

以下各题例子均来自老师的课件，看不明白的可以追本溯源。O( _)O 1.不完全酶切问题。 （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 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 8 页 - - - - - - - - - 由此得到两条路径：（2）用欧拉图： 将所给每个三联体分割成两个二联体（如 ATG分成 AT和 TG） ，去除冗余， 得到 AT TG GC GG GT CA CG 将能够形成已有三联体的两个二联体间画箭头，比如从TG始，已知有TGG和 TGC ，则由 TG向 GG和 GC画箭头。最终得到：同样可分为两种结果：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 8 页 - - - - - - - - - 3.比对问题。（ 10 分）给出两个序列，利用动态规划算法进行序列比对。先画出表格，横行和纵行配对是1，不配是 0. 然后根据Fi, jmax(Fi 1, j 1Si, j,Fi 1, jd,Fi, j 1d)。其中 Fi, j表示 i 行 j 列处的最大值；如果第i行和第 j 列正好配对，则Si, j=1；一般 d=0. 相继求出每一个表格中的数值，并用箭头标出数值来源。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 8 页 - - - - - - - - - 最终得到了最佳配对考试时要求找出最佳配对，标示出红色的箭头。4.聚类问题。（ 10 分）两种方法，层次聚类法和k-means 法，每种方法5 分。例如，有 5 个基因，它们的表达可以用坐标上的点标示（有可能横坐标代表某个时间的表达量，纵坐标代表另一个时间的表达量） ，将这五个基因聚类。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 8 页 - - - - - - - - - （1）层次聚类法：算出各点之间的距离，列出距离矩阵：首先找出最短的距离，即A和 C之间的距离为1，先将 A和 C聚类：再找最短距离，D和 E之间 1.4 的距离最短：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 8 页 - - - - - - - - - 亦即：然后是 AC和 B之间的距离最短：亦即：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 8 页 - - - - - - - - - 最终：（2）k-means 法：在坐标上任取两个（或更多，视聚类需要而定）点作为中心点，如本例取（5，6）和（ 8，7） 。 （下面的图写错了）分别计算 A-E 各点离以上两点的距离，离哪个更近就归于哪个。经计算，A、C归于绿点， B、E、D归于红点：然后抛开我们所任取的两个点，分别算出A和 C的、 B和 E和 D的重心（即平均数） ：再分别以两个重心为中心点，从新计算A-E 五个点到两个中心点的距离，离哪个近就归于哪个。这次B 与 A、C 归于了一类。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 8 页 - - - - - - - - - 再算重心：这就得出了最终的结果。如果点多的话，以上的步骤会重复更多次。计算时点间的距离可以用根号表示，能看出长短就行。5. 自己找一篇生物信息学方面的论文，考试的时候写出这篇文章的题目、杂志等（送分），然后写出其主要内容，以及其中和我们讲课时提到的相关知识。（10 分）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 8 页 - - - - - - - - -