下载文档原格式
利用动态规划算法进行两条序列比对实 验 目 的学会使用EMBOSS 软件包的NEEDLE 和WATER 进行两条序列比对。
实 验 内 容1. Get the mRNA and protein sequence of Chlorocebus sabaeus and Colobus angolensispalliates from NCBI.2. Use Needle to do the sequence alignment in default parameters.*****Protein Sequence alignment result*****Program: needle# Rundate: Sat 28 Sep 2019 16:43:43 # Commandline: needle # -auto # -stdout# -datafile EBLOSUM62# -gapopen 10.0 # -gapextend 0.5 # -endopen 10.0 # -endextend 0.5# -aformat3 pair # -sprotein1 # -sprotein2 # Align_format: pair # Report_file: stdout # Aligned_sequences: 2# 1: XP_008000870.1 # 2: XP_011811726.1 # Matrix: EBLOSUM62 # Gap_penalty: 10.0 # Extend_penalty: 0.5 # Length: 586# Identity: 561/586 (95.7%) # Similarity: 572/586 (97.6%) # Gaps: 4/586 ( 0.7%) # Score: 2906.0***** mRNA Sequence alignment result *****# Program: needle# Rundate: Sat 28 Sep 2019 16:47:19 # Commandline: needle # -auto # -stdout# -datafile EDNAFULL# -gapopen 10.0 # -gapextend 0.5 # -endopen 10.0 # -endextend 0.5 # -aformat3 pair # -snucleotide1# -snucleotide2# Align_format: pair # Report_file: stdout # Aligned_sequences: 2# 1: XM_008002679.1 # 2: XM_011956336.1 # Matrix: EDNAFULL# Gap_penalty: 10.0 # Extend_penalty: 0.5 # Length: 2594# Identity: 2505/2594 (96.6%) # Similarity: 2505/2594 (96.6%) # Gaps: 27/2594 ( 1.0%) # Score: 12207.5a. After alignment, we have found that the identity and the gaps between two mRNAs were higher than protein, but the similarity of mRNA was lower than protein.b. The two sequences are closely related.3. Use Water to do the sequence alignment in default parameters.*****Protein Sequence alignment result*****# Program: water# Rundate: Sat 28 Sep 2019 16:52:02 # Commandline: water # -auto # -stdout# -datafile EBLOSUM62# -gapopen 10.0 # -gapextend 0.5 # -aformat3 pair# -sprotein1 # -sprotein2 # Align_format: pair # Report_file: stdout# Aligned_sequences: 2 # Matrix: EBLOSUM62# Gap_penalty: 10.0 # Extend_penalty: 0.5 ## Length: 582# Identity: 561/582 (96.4%) # Similarity: 572/582 (98.3%) # Gaps: 0/582 ( 0.0%) # Score: 2906.0*****mRNA Sequence alignment result*****# Program: water# Rundate: Sat 28 Sep 2019 16:53:55 # Commandline: water # -auto # -stdout# -datafile EDNAFULL# -gapopen 10.0 # -gapextend 0.5 # -aformat3 pair# -snucleotide1 # -snucleotide2 # Align_format: pair # Report_file: stdout## Aligned_sequences: 2 # Matrix: EDNAFULL# Gap_penalty: 10.0 # Extend_penalty: 0.5 ## Length: 2592# Identity: 2505/2592 (96.6%) # Similarity: 2505/2592 (96.6%) # Gaps: 25/2592 ( 1.0%) # Score: 12207.5a. After alignment, we have found that the identity and the gaps between two mRNAs were higher than protein, but the similarity of mRNA was lower than protein. ( THE SAME TO Needle )b. The two sequences are closely related.c. Higher identity and similarity than Needle.4. Do the protein sequence alignment and change the original parameters.Eg: We used the needle to do the protein sequence alignment and changed the GAP_OPEN from 10 to 1.# Program: needle# Rundate: Sat 28 Sep 2019 16:58:37 # Commandline: needle # -auto # -stdout# -datafile EBLOSUM62# -gapopen 1.0 # -gapextend 0.5 # -endopen 10.0 # -endextend 0.5# -aformat3 pair# -sprotein1 # -sprotein2 # Align_format: pair # Report_file: stdout ## Aligned_sequences: 2 # Matrix: EBLOSUM62# Gap_penalty: 1.0 # Extend_penalty: 0.5 ## Length: 588 # Identity: 561/588 (95.4%) # Similarity: 572/588 (97.3%) # Gaps: 8/588 ( 1.4%)# Score: 2908.0a. We can get a consequence that the identity, gaps and similarity between the protein sequences become lower, but the score become higher. ( Were more distinct but got higher score )b. Moreover, we have changed other 4 parameters, but not got any distinct result.5. Global and local pairwise sequence alignment between human myoglobin and hemoglobin protein sequences.***Global pairwise sequence alignment***Protein Sequence Alignment between hemoglobin subunit alpha(beta) and myoglobin(Homo sapiens)***Local pairwise sequence alignment***Protein Sequence Alignment between hemoglobin subunit alpha(beta) and myoglobin(Homo sapiens)实验总结1.此次实验，我们基本掌握了如何对两条序列进行全局&局部比对，以及根据不同情况对具体参数进行调整的能力。
双序列比对算法综述作者：王沛来源：《学习与科普》2019年第12期摘要：在生物信息学中，基因序列比对是最基本、最重要的操作。
本文首先介绍了序列比对的划分方式，提出了双序列比对算法的研究意义；接着对典型的双序列比对算法的研究现状进行了较为详细的阐述，包括算法的原理、对比等；然后通过收集双序列比对算法的优化方案，总结出当前算法的发展趋势，得出结论。
关键词：生物信息，序列比对，双序列比对，动态规划，点阵图1 引言序列比对问题是指将基因序列进行比对，将其中相似性的部分标示出来，通过标示出的序列相似度来确定序列间的同源性关系。
在生物信息学中，基因序列的比对是最基本、最重要的操作，是进行基因识别、信息分析、结构预测等问题的前提。
本文将介绍一种最基础的比对方式——双序列比对。
2 背景与意义序列比对有多种划分方式。
根据比对数量的不同，可分为双序列比对和多序列比对。
双序列比对即通过两个基因序列的比对，找到相似的基因片段，从而推测目标基因可能具有的功能以及可能的分子进化关系。
而多序列比对通过多个基因序列的比对，寻找到它们相同的位点、区域，推测具有共同功能的序列模式。
就序列本身而言，对序列进行整体比对的方式称为全局比对，对序列进行部分比对的方式称为局部比对。
全局比对适用于总体相似度高的同源序列；局部比对适用于长度差别大、亲缘关系远的序列，可找出两条序列中相似度最高的片段。
由于双序列比对是基因序列比对最早采取的方式，也是生物信息学最基本的研究方法，所以我决定先从这种最基本的方式入手，了解双序列比对算法的研究现状及发展趋势，为进一步的学习做好铺垫。
3 双序列比对算法研究现状3.1 典型双序列比对算法介绍3.1.1 基于动态规划的双序列比对算法Needleman-Wunsch算法1970年，Needleman和Wunsch最早提出了一种基于动态规划思想的序列全局比对算法：使用迭代的方式求出两个基因序列之间的对比得分，并把结果存放在二维得分矩阵里面，然后运用动态规划方法在二维得分矩阵中进行回溯从而找到序列最佳比对路径，即序列比对的最优结果。
两序列比对算法摘要：序列比对是生物信息学研究的一个基本方法，对于发现生物序列中的功能、结构和进化信息具有重要的意义。
两序列比对中，典型的全局比对算法是Needleman—Wunsch算法；局部比对算法的基础是Smitll—Waterm an 算法，本文对典型的双序列比对算法进行描述。
关键词：生物信息学；两序列比对；算法引言：为了满足基因组中获得更多更有价值的信息，生物信息学迅速发展起来，生物信息学是一门多门科学交叉的学科，将数学、计算机科学应用于生物大分子信息的获取、加工、存储、分类、检索和分析等，以达到阐明和理解大量数据所蕴含的生物学意义的目的。
通过对DNA和蛋白质序列进行相似性比较，指明序列间的保守区域和不同之处，为进一步研究它们在结构、功能以及进化上的联系提供了重要的参考依据。
而序列比对就是运用某种特定的数学模型或算法，找出两个或多个序列之间的最大匹配碱基或残基数，比对的结果反映了算法在多大程度上反映了序列之间的相似性关系以及它们的生物学特征。
双序列比对算法双序列比对分为全局比对和局部比对，全局比对是考察两个序列之间的全局相似性，局部比对则比较序列片段之间的相似性。
Needleman—Wunsch算法是典型的全局比对算法，适用于全局水平上相似性程度较高的两个序列；Smitll—Waterman 算法适用于寻找局部相似序列对，该算法是目前被使用最广泛的序列相似性比较算法之一，由所熟悉的Needleman—Wunsch算法演变而来。
Needleman-Wunsch 算法使用迭代方法计算出两个序列的相似分值，存于一个得分矩阵中，然后根据这个得分矩阵，通过动态规划的方法回溯寻找最优的比对序列。
具有很高的灵敏度使用二维表格，一个序列沿顶部展开，一个序列沿左侧展开。
而且也能通过以下三个途径到达每个单元格：1.来自上面的单元格，代表将左侧的字符与空格比对。
2.来自左侧的单元格，代表将上面的字符与空格比对。
双序列比对算法
/// 双序列比对用于研究两个序列定义的DNA有多少相似之处，或者蛋白质序列有多少相似之处。
/// 这种比较在DNA鉴定和遗传暗示步骤中是非常重要的，在生物信息学应用中，两个序列之间比较也特别重要，特别是在研究顺序的进化关系和鉴定功能。
///
/// 双序列比对算法主要用于非完全比对，因为完全比对可以利用穷举法，把序列中的元素两两比对，以期发现所需的最近分数最高的所需的比对对。
/// 双序列比对算法可以利用动态规划算法，其中首先定义一个矩阵，表示序列i和序列j的最佳比对，在这个矩阵中，每个条目用于表示以矩阵中元素为末尾的两个序列段的相似度/距离，元素i和元素j越来越相似，这个度量值越大，距离越小。
///
/// 动态规划法大概有两个步骤：第一个步骤是填充一个矩阵，第二个步骤是从矩阵中搜索出最有可能产生最高得分的比对对。
DNA双序列比对问题的算法曹莉;许玉龙;邓崇彬【摘要】With the surge in sequence data of biological sequence database, developing a algorithm which has the high biology sensitivity and efficiency is very urgent. Based on the deep analysis on the Needleman-Wunsch and Smith-Waterman Algorithm of bio-sequence alignment, the author enhances the Smith-Waterman algorithm as well as proves its accuracy through a series of experiments in this paper. Comparing between the Smith-Waterman algorithm and the improved one, the author analyzes the performance of the two algorithms. Experimental results show that the newly improved algorithm can optimize the number of local optimal solutions for pairwise sequence, reduce the complexity in time and space of bio-sequence alignment algorithms, and increase the scores and accuracy of sequence alignments.%随着生物序列数据库中序列数据的激增，开发兼有高度生物敏感性和高效率的算法显得极为迫切。
