北邮生物信息基础期末作业

《生物信息基础》期末作业1目录一、疾病自动诊断问题........................................................................21、设计思路.....................................................................................22、基于K-L变换的主成分分析法.................................................23、近邻法判别分析.........................................................................3二、病毒变异与否的判断....................................................................41、设计思路.....................................................................................42、基本步骤.....................................................................................43、星型比对算法.............................................................................44、两两比对算法.............................................................................55、寻找变异位点.............................................................................5三、基因编码区域识别........................................................................51、设计思路.....................................................................................52、问题建模.....................................................................................53、参数估计与计算过程.................................................................64、实验结果.....................................................................................7四、隐马尔科夫模型的求解................................................................71、设计思路.....................................................................................82、问题建模.....................................................................................83、参数估计与计算过程.................................................................94、计算结果.....................................................................................9五、课堂内容回顾..............................................................................10《生物信息基础》期末作业2《生物信息基础》期末作业一、疾病自动诊断问题1、设计思路根据题目，我们获得80份腹泻类型为细菌型的常规化验结果数据，以及20份腹泻类型为病毒型的化验结果数据，基于以上100份数据中的20项数值型结果，我们将其作为分类器训练集，设计出合理的算法将某常规化验结果分类，判断其腹泻类型。该计算机自动诊断方案包括以下部分：信息获取与预处理特征选择与提取分类器设计、训练分类决策（识别）结果输出其中，信息获取与预处理，即为通过常规化验，采集化验所得的20项数据结果𝐱=(x1,x2,x3,x4,…,x17,x18,x19,x20)T，并将其作为观测向量。特征选择与提取采用通过K-L变换实现主成分分析法，分类器设计及决策采用近邻法，基于以上流程，将输出的结果作为判别结果。2、基于K-L变换的主成分分析法主成分分析的基本思想是进行特征降维的变换，虽然不能完全地表示原有的对象，能量总会有损失，但是希望找到一种能量最为集中的变换方法使得能量损失最小，即根据已知向量，将其做变换得到一组互不相关新的特征，对新特征向量进行排序，舍掉最小的特征，从而使得损失的能量最小。1)K-L变换的基本算法原始输入为𝐱=(x1,x2,x3,x4,…,x17,x18,x19,x20)T，变换后特征为y，变换矩阵（线性变换）为A，则y=𝐴𝑇𝑥，变换后的相关矩阵则R𝑦=𝐴𝑇𝑅𝑥𝐴。若不同的y特征互不相关，则对R𝑦进行分析，以R𝑥的特征向量作为A的列，则满足：R𝑦=𝐴𝑇𝑅𝑥𝐴=[𝑎1,𝑎2,…,𝑎𝑛]𝑇𝑅𝑥[𝑎1,𝑎2,…,𝑎𝑛]=[𝑎1,𝑎2,…,𝑎𝑛]𝑇[𝜆1𝑎1,𝜆2𝑎2,…,𝜆𝑛𝑎𝑛]=Λ，其中Λ为对角矩阵，对角线元素为𝜆1,𝜆2,…,𝜆𝑛，以此来达到变换后特征不相关的目的。2)主成分分析的基本算法通过K-L变换时特征降维，原有N维，只保留m维，去掉𝑦𝑚+1…𝑦𝑁，若希望和原来的表示方法差别最小，即E[||𝑥′−𝑥||2]最小，𝑥′表示[𝑦1…𝑦𝑚]在原空间中对应的表示方法。通过计算不难得出如下公式：E[||𝑥′−𝑥||2]=∑𝜆𝑖𝑁𝑖=𝑀+1将𝜆𝑖从大到小排序，则保留m维后的结果即为损失的能量最小。《生物信息基础》期末作业33)简要分析通过主成分分析可以实现将所得特征降维的目的，同时还可以消除特征中误差的干扰，使得特征提取的结果更为准确，有利于之后分类器的设计及决策。3、近邻法判别分析1)基本算法近邻法的基本思想为：将于测试样本最近邻样本的类别作为决策的方法。对于一个C类别的问题，每类有𝑁𝑖个样本，i=1,2,…,C，则第𝜔𝑖类的判别函数为：𝑔𝑖(𝑥)=min𝑘||𝑥−𝑥𝑖𝑘||，k=1,…,𝑁𝑖其中𝑥𝑖𝑘为第𝜔𝑖类的第k个样本。决策函数为：𝑔𝑗(𝑥)=min𝑔𝑖(𝑥)𝑖，i=1,…,𝐶，则决策x∈𝜔𝑗。由题目得，该诊断方案需要判断的类别有两类，即细菌型腹泻和病毒型腹泻。已知细菌型腹泻有80个样本作为训练集，病毒型腹泻有20个样本作为训练集，以此为分类基础设计出一个基于近邻法的分类器。2)错误率分析已知待分类样本x，其最近邻样本为𝑥′，已经有N个已知类别的训练样本，而𝑥′是其中之一，则特征空间中x点的错分概率：如果样本x的两类别后验概率分别为P(𝜔1|x)与P(𝜔2|x)，那么对x值，在N⟶∞条件下，发生错误决策的概率为：而在这条件下的平均错误率为：设贝叶斯错误率为𝑃∗，比较两者错误率，得出如下关系：3)改进：K-近邻法最近邻法可以扩展成找测试样本的k个最近样本作为决策依据。基本规则为：《生物信息基础》期末作业4在所有N个样本中找到与测试样本的k个最近邻者，其中各类别所占个数为𝑘𝑖，i=1,…,C，则决策规划为：𝑘𝑗(𝑋)=min𝑖𝑘𝑖(𝑋)，i=1,..,C，则做出决策：x∈𝜔𝑗。二、病毒变异与否的判断1、设计思路判断病毒是否发生变异涉及序列比对的问题。已知15条病毒型腹泻患者的病毒核酸序列，将待测序列与样本集进行多序列比对，判断病毒是否发生了变异。当待判断序列与样本序列特征差异超过一定阈值时，判断该病毒发生了变异，同时定义另一阈值，当碱基对连续错误超过该阈值时，判断起始位点处发生了变异。因为基因突变等现象的存在，特征差异及碱基对的阈值设定需要专家进行专业评估后给出。方案中多序列比对采用星型比对的方法，通过星型比对获得15条对齐的序列，从而总结出该样本集的序列特征，之后将待判断序列与该特征进行对比，将对比的结果与设定的阈值进行比较，从而判断是否变异，如果该病毒发生了变异，重新遍历对齐序列，记录碱基对连续出现变异的数目，也与设定的阈值进行比较，从而找出变异位点。2、基本步骤3、星型比对算法目前所用的大部分序列多重比对算法需要交多重序列比对转换为两两序列比对，再将两两序列比对组合起来，最终形成完整的多序列比对，这种方法称为渐进法，星型比对是其中的一种。星形比对的基本思路是：在给定的若干序列中，选择一个核心序列，通过该序列与其它序列的两两比对，形成所有序列的多重比对，从而使得该多重比对在核心序列和任何一个其它序列方向的投影是最优的两两比对。星型比对的基本过程为：1)选定一个核心序列；2)计算与核心序列的两两比对；3)逐对聚合比对结果，获得多重比对。聚集过程从某一个两两比对开始，比如𝑆𝐶和𝑆1，然后逐步加上其他的两两比对。在这个过程中，逐步增加𝑆𝐶中的空位字符，以适应其他的比对，但不删除𝑆𝐶中已经存在的空位字符。星型比对获取序列特征判断是否变异寻找变异位点《生物信息基础》期末作业5选择核心序列的方法为：尝试将每一个序列分别作为核心序列，进行星形多重序列比对，取比对结果最好的一个。4、两两比对算法在上面提到的星形比对中，最基本的核心是两两比对，我们使用的两两比对的方法为：全局最优序列比对的动态规划求解算法。给出求解过程：1)初始化DP辅助矩阵；2)根据状态转移方程递归计算DP辅助矩阵A；3)确定最优路径，即对应于最优比对。矩阵更新策略：A(i,j)={𝐴(𝑖,𝑗−1)+𝑝(−,𝑡[𝑗])𝐴(𝑖−1,𝑗−1)+𝑝(𝑠[𝑖],𝑡[𝑗])𝐴(𝑖−1,𝑗)+𝑝(𝑠[i],−)}5、寻找变异位点待测序列在经过比对之后，已实现对齐。在此基础之上，我们只需再重新进行一次遍历，记录碱基序列中连续出现变异的碱基个数，并与专家给出的阈值进行比较，从而找出变异的起始位点。三、基因编码区域识别1、设计思路根据已经给出的编码区域与非编码区域的碱基序列样本，结合题目中提及的该病毒RNA序列中基因编码区域的碱基排列顺序具有特定规律，考虑利用马尔科夫链分别来计算所给出的序列片段出现在编码区和非编码区的概率，通过比较概率的大小来判断其是否为编码区域。利用马尔科夫模型计算概率时，需要统计出各碱基的起始概率及概率转移矩阵，因为题目中所给的序列长度较短，考虑一阶马氏链的情况，各概率矩阵在参数估计中给出。2、问题建模利用马尔科夫链模型求解时，需要考虑一个具有多个状态的系统S，令𝑂1,…,𝑂𝑛为一系列在各个时刻系统状态的变量，即状态链。《生物信息基础》期末作业6对于一阶马氏链，系统在时间步t处于哪个状态，仅与时间t-1时系统所处的状态有关，P(𝑂1,…,𝑂𝑛)=𝑃(𝑂1)𝑃(𝑂2|𝑂1)𝑃(𝑂3|𝑂2)…𝑃(𝑂𝑛|𝑂𝑛−1)，即系统未来的状态仅依赖于当前状态，马尔科夫链完全决定于初始分布和状态转换概率。计算𝐴�