《生物信息学》学习报告

《《生物信息学》学习报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验报告题目基于最大权值路径算法的DNA多序列比对方法学习报告学院：软件学院系计算机专业班级：软件工程学生姓名：何宇凡学号：4066295150112016年6月1日摘要在对《基于最大权值路径算法的DNA多序列比对方法》的分析学习中，文中提出针对生物序列分析中的多序列比对问题，当输入数据量比较大时，人们提出了很多启发式的算法来改善计算速度和比对结果。提出了用于进行全局DNA多序列比对的一种方法：MWPAlign(maximumweightedpathalignment)。该算法把序列信息用deBruijn图的形式表示，并将输入序列的信息记录在图的边上，这样，就将求调和序列的问题转化为求图

2、的最大权值路径问题，使多序列比对问题的时间复杂度降低到几乎线性。基础知识多序列比对是生物信息学中挑战性的问题之一，并在序列装配、序列注释、基因和蛋白质的结构和功能预测以及系统发育和进化分析等方面应用广泛。它是SPS(sum-of-pairsscoring)意义下的NP完全问题。现阶段常用的比对方法分类：精确比对方法、渐进比对方法、迭代比对方法、基于图论的比对方法。具体介绍如下：精确比对方法精确比对方法完全基于动态规划算法，最为经典的是多维Needlman-Wunsch算法，但其可行的计算维数为3。渐进比对方法迭代地利用两序列动态规划算法，先由两条序列的比对开始，逐渐添加新序列，直到所有序

3、列都加入为止。但是，不同的添加顺序会产生不同的比对结果，所以，确定合适的比对顺序是渐进比对方法的一个关键问题。而两个序列越相似，人们对它们的比对就越有信心，因此，整个序列的比对应该从最相似的两个序列开始，由近至远逐步完成。迭代比对方法基于一个能产生比对的算法，并通过一系列的迭代方式改进多序列比对，直到比对结果不再改善为止。基于这种思想的方法很多，例如模拟退火、遗传算法、隐马尔可夫模型等。其中，最有影响的多序列比对软件包SAGA(sequencealignmentbygeneticalgorithm）基于遗传算法构建，共设计了22种不同的遗传算子，采用动态调度的策略控制22种遗传算子的使用

4、。基于图论的比对方法一种以有向无环图(directedacyclicgraph，简称DAG)的表示方式取代行列表示的全新多序列比对方法。。上述方法各有其不同的优点，但它们中的大多数对于大量输入序列，其时空复杂度依然是实际应用的一个瓶颈，至少都O(N2L2)其中N是序列条数，L是序列平均长度。针对这个问题，本文提出了一种基于图模型的新方法，将deBruijngraph方法应用到DNA全局多序列比对中，使多序列比对的时空复杂度降低到线性O(NL)。基于最大权值路径算法的DNA多序列比对方法本算法用deBruijngraph[19]的形式表示输入序列，将输入序列的信息记录在图的边上，定义边的权

5、值为经过该边的序列的条数，则边的权值越大，说明此边越有可能代表输入序列的保守区域。将图中最大权值的边连接起来的最大权值路径，正好对应输入序列中保守区域的归并，也就是所求调和序列对应的路径。设想所有输入序列都是从一个祖先序列进化而来，我们要找的就是这个祖先序列。此过程不需要进行多序列比对，并且使寻找调和序列问题的时间复杂度大为降低，几乎是线性的。最后，利用得到的调和序列和每条输入序列进行两两比对得到比对结果。我们已经使用模拟数据对本算法进行了测试，并且和现有方法进行了比较，结果表明：MWPAlign(maximumweightedpathalignment)是可行的DNA多序列比对方法，其

6、时间复杂度优于现有的方法，并且在序列变异率较低时，比对结果优于CLUSTALW，T-Coffee和HMMT(hiddenMarkovmodeltraining)。问题描述多序列比对的目标是使得参与比对的序列中有尽可能多的列具有相同的字符，即，使得相同残基的位点位于同一列，这样以便于发现不同的序列之间的相似部分，从而推断它们在结构和功能上的相似关系，主要用于分子进化关系，预测蛋白质[1]的二级结构和三级结构、估计蛋白质折叠类型的总数，基因组序列分析等。假设一条长度为m的生物序列是由m个字符组成的字符串，字符串中的字符取自于一个有限的字母表Σ，对于DNA序列，Σ包含A、T、C、G四个字母，分

7、别代表4种不同的核苷酸，将其统称为碱基。对于蛋白质序列，Σ包含20个不同的字母，分别代表20种不同的氨基酸，将其统称为残基。给定N条序列组成的序列组S=(s1，s2，。。。，sN)，其中：，为第i条序列的长度，则关于S的一个多序列比对可定义为一个矩阵。该矩阵有如下特性：1)2)如果删除空位“—”，则的每一行与对应序列相同；1)S′中不存在只由空位“−”组成的列。多序列比对结果的评判标准目标函数用来评判序列比对结果的优劣。在多序列比对