北邮生物信息大作业

1、工疾病自动诊断问题1、题目分析根据题目要求，我们需要设计一套计算机自动筛选方案，目的是通过患者检测得到的20项指标，分别判断患者的腹泻类型为病毒型腹泻还是细菌型腹泻。目前，我们已有的训练集是经过专家筛选后的100例疑似患者的20项指标。其中，20位为病毒型腹泻，80位为细菌型腹泻，即80位为细菌型腹泻。因此，我认为该问题为一个监督下的模式分类问题，两个分类指标为腹泻类型为病毒型”、腹泻类型为细菌型”，观测向量为得到的疑似患者的20项指标：2、关键算法及分析信息获取与预处理部分，在之前的检查中已经较为详细的给出，这一步不再设计；特征选择与提取部分，我计划使用主成分分析方法，通过对20项标准进行线

2、性组合，可以得到更能够体现类间信息的新的一组观测向量；分类器设计采用Fisher线性判别分析+最小错误率贝叶斯决策的方法。主成分分析主成分分析的思想是从一组特征中计算出一组重要性按从大到小顺序排列的的新特征，它们是原有特征的线性组合，并且之间是互不相关的。设为x的协方差矩阵，求解出矩阵的各个特征值与特征向量，则特征值最大的特征向量，为数据集的最佳投影方向。由此方向投影，可获得最大的投影数据的方差。按照这个思路依次找到次大的，第三的特征值对应的特征向量，它们就是次优的，第三优的投影方向。我们可以只提取重要性占前k%个主成分：k.h.我们把原始数据集按这些方向投影，得到的就是降维后的观测向量。选择

3、较少的主成分来表示数据，不但可以用作特征的降维，还可以用来消除特征中的噪声。Fisher线性判别分析Fisher线性判别分析的基本思想是：将所有的样本投影到一个方向上，然后在这个一维空间确定一个阈值。选择最优的投影方向应该使得各个样本点的类内方差最小，类间方差最大。我们定义类内离散度矩阵，类间离散度矩阵，投影向量，准则的目标函数为：加皿切=£=；7这是一个约束条件下的极值问题，我们可以利用拉格朗日乘子法求解。拉格朗日函数：L（卬/）=wTSbw-4科治w-c）上式在极值点处，应该满足对w的偏导数等于零。可以解得：W*=仁"工一明）式中，为Fisher线性判别准则下的最优投影

4、方向。为两类的类均值向量。由于Fisher线性判别分析不对样本的分布做任何假设，当样本维数较高样本数也较多的时候，投影到一维空间后样本接近正态分布。这时可以在一维空间中使用正态分布拟合样本，再使用上面提到的最小错误率贝叶斯决策，往往会有很好的效果。最小错误率贝叶斯决策最小错误率贝叶斯决策的决策规则为:如果P（他分，则x属于w1,否则x属于w2o其中，后验概率可以使用贝叶斯公式求得:口rq/SI/冲3）如'POT一年.一网）产（州）但是，将一个疑似患者判为病毒携带者和排除其患病可能性，其代价（损失）是不一样的。对此，采用最小风险的贝叶斯决策。这种决策方法中，决策表是需要人为确定的，需要认

5、真分析研究问题的内在特点和分类目的，与疾病防控领域的专家共同决策，设计出适当的决策表。具体的决策步骤：（1） 利用贝叶斯公式计算后验概率（2） 利用决策表，计算条件风险：C=24明叫P9W）;-1（3） 决策：在各种决策中选择风险最小的决策，即病毒变异与否的判断1、 问题分析针对病毒变异与否的判断问题，我认为应该采样合适数目的诺拉病毒DNA序列(可以是关键部分的基因)，然后使用多序列比对的方案，将多条序列对齐，就可以方便的定位出序列中碱基对的差异位置，从而评估病毒是否发生了变异。由于整条序列做多序列比对，可能时间复杂度较大，最后得到的变异位点信息也和我们想要的相差较大。我们可以选择和病毒的致病

6、能力密切相关的几个基因，作为多序列分析的原材料。2、 求解算法即算法描述求解流程获取病毒关键基因IJ多序列比对IJ遍鳖多序列比对下面简要介绍多序列比对的实现方法。由于病毒的DNA序列较长，我们采取星形比对的方案。星形比对的基本思想是：在给定的若干序列中，选择一个核心序列，通过该序列与其它序列的两两比对，形成所有序列的多重比对，从而使得该多重比对在核心序列和任何一个其它序列方向的投影是最优的两两比对。下面给出星形比对的基本过程：1 .选择核心序列2 .计算与核心序列的两两比对3 .逐对聚合两两比对的结果，获得多重比对选定一个核心序列，把多重比对转化为k个两两比对聚集过程。从某一个两两比对开始，比

7、如sc和si,然后逐步加上其他的两两比对。在这个过程中，逐步增加sc中的空位字符，以适应其他的比对，但不删除sc中已经存在的空位字符。选择核心序列的方法为：尝试将每一个序列分别作为核心序列，进行星形多重序列比对，取比对结果最好的一个。在上面提到的星形比对中，最基本的核心是两两比对，我们使用的两两比对的方法为：全局最优序列比对的动态规划求解算法。给出求解过程：初始化DP辅助矩阵根据状态转移方程递归计算DP辅助矩阵A确定最优路径，即对应于最优比对矩阵更新策略:致力-1)+汉-闺的)MlD三内。一1，j-D+百($团渊口”人工-1J)+7串口D)寻找变异位点需要的序列经过了比对，已经对齐。我们可以定

8、义一个阈值，当碱基序列中连续出现的变异碱基个数超过了这个阈值后，我们即可认定这个序列是变异序列，与原序列的差异较大。阈值的选择要与疾病防控领域的专家一起协定，这样才能够准确的发现基因出现的变异情况。四:(1)若观测序列为CCGC,试计算该观测序列在所给定的HMM下的生成概率解：利用前向算法模型：隐状态集合S=S1,S2,S3明字符集合V=C,G隐状态转移概率A=.0.30,20.3.040.402I0.10.203明字符生成概率矩阵B=10.40.6.0.30.7)0.60.4初始状态概率向量兀=0.2,0.3,0.5若观测序列为CCGC,O=C,C,G,C:1 .初始化：根据公式：a(l,i

9、)=tt购6)求得：a(1,1)=Tt(1)*b(1,o1)=0.08a(1,2)=兀(2)*b(2,o1)=0.09a(1,3)=兀(3)*b(3,o1)=0.3根据公式:£记土.加2方伉a+i)求得：a(2,1)=a(1,1)*a(1,1)+a(1,2)*a(2,1)+a(1,3)*a(3,1)*b(1,o2)=0.0252同理可得：a(2,2)=0.0336a(2,3)=0.0792a(3,1)=0.011304a(3,2)=0.024024a(3,2)=0.015216a(4,1)=0.00293a(4,2)=0.00447a(4,3)=0.007663.终结：根据公式:尸。

10、=!>()t=i求得P(O入)=a(4,1)*p(S1,)+a(4,2)*p(S2,)+a(4,3)*p(S3,)=0.00499(2)若观测序列为CCGC,试计算生成该观测序列的最佳路径。解：利用Viterbi算法模型：1 .初始化：根据公式：储(')=穴i刎。1)(2)=兀(3)=兀(1)(2)(3)*b1(o1)=0.08*b2(o1)=0.09*b3(o1)=0.32 .递归：根据公式:瓦(j)=maxbj(0f)l<i<N求得：82(1)=max81(1)*a11,S1(2)*a21,81(3)*a31*b1(O2)=0.03*0.4=0.012同理可得：82(2)=0.01882(3)=0.05483(1)=0.00324S3(2)=0.00756S3(3)=0.0064884(1)=0.0003984(2)=0.0009184(3)=0.001173.终结：根据公式:max!<?<Ar历(训求得：P*=max84(1),84，84(3)=0.001174.回溯：根据公式:argmax1<?<N求得：q4*=3再由公式：仇