下载文档原格式
生物信息学中的序列比对算法及其性能分析序列比对是生物信息学中一项重要的任务，用于比较两个或多个生物序列之间的相似性和差异性。
序列比对算法是根据一定的准则和规则，找出序列之间相同的部分，从而揭示它们的结构和功能关联。
在生物信息学研究中，序列比对算法的准确性和效率对于生物学研究具有重要意义。
在生物信息学中，序列比对算法的应用非常广泛，涵盖了DNA、RNA和蛋白质序列的比对。
序列比对算法主要分为全局比对和局部比对两种类型。
全局比对算法会比较整个序列的完全匹配，局部比对则只比较序列片段的部分匹配。
常见的全局比对算法有Smith-Waterman算法，而局部比对算法中最著名的是BLAST算法。
Smith-Waterman算法是一种经典的全局比对算法，通过动态规划方法来寻找两个序列之间的最佳匹配。
该算法将序列比对问题转化为一个图论问题，通过构建匹配得分矩阵和回溯路径，找到最佳的序列比对结果。
Smith-Waterman算法的核心思想是通过逐个比较序列的每个字符来计算得分矩阵，并根据得分矩阵来确定最佳的序列比对结果。
尽管Smith-Waterman算法非常准确，但由于计算复杂度较高，在处理大规模序列时效率较低。
局部比对算法中，BLAST算法是最常用的一种。
BLAST算法使用快速比对技术，通过构建预处理的索引库和查询序列进行快速匹配。
该算法首先构建查询序列和数据库序列的索引，然后利用快速匹配方法，在索引库中寻找匹配候选序列，最后通过精细比对来确定最佳的序列匹配结果。
BLAST算法的高效性得益于其索引库的构建和匹配算法的优化，使得它在处理大规模生物序列时具有较高的速度和准确性。
序列比对算法的性能分析是评估算法优劣的重要手段。
性能分析包括比对准确性、比对速度和存储空间消耗等指标的评估。
比对准确性是判断算法结果是否与实际序列相符的关键指标，一般通过比对得分来评估。
比对速度则是评估算法处理速度的指标，通常以每秒比对的序列数来衡量。
生物信息学中的序列比对算法分析与优化序列比对是生物信息学中一项重要的技术与方法，用于研究生物序列之间的相似性和差异性。
比对的准确性和效率直接影响到后续的功能注释、进化分析和结构预测等生物学研究。
本文将对生物信息学中的序列比对算法进行分析与优化，探讨不同算法的原理、优缺点以及改进方法。
一、序列比对算法的原理序列比对算法的基本原理是通过寻找序列之间的共同特征来衡量它们之间的相似性。
常用的序列比对算法包括全局比对、局部比对和多序列比对，采用的算法包括动态规划、贪心算法和快速搜索算法等。
1. 全局比对全局比对算法用于比较两个序列的整个长度，并给出最佳的匹配结果。
最常用的算法是Needleman-Wunsch算法，其基本思想是通过动态规划的方法，计算出一个最优的比对方案。
全局比对适用于两个序列相似度较高的情况，但计算复杂度较高，对大规模序列比对不太适用。
2. 局部比对局部比对算法用于比较两个序列的一部分，并给出最佳的局部匹配结果。
最常用的算法是Smith-Waterman算法，其基本思想是通过动态规划的方法，计算出所有可能的局部比对方案，并选择得分最高的方案作为最佳匹配结果。
局部比对适用于两个序列相似度较低的情况，可以发现较短的共同片段。
3. 多序列比对多序列比对算法用于比较多个序列之间的相似性，常用于进化分析和亲缘关系推断等研究。
最常用的算法是CLUSTALW算法，其基本思想是通过多次的全局比对和局部比对，逐步构建多个序列的比对结果。
二、序列比对算法的优缺点不同的序列比对算法在准确性、效率和适用范围等方面有不同的优缺点。
1. 全局比对的优缺点全局比对算法可以找到两个序列的所有匹配段，准确度高；但计算复杂度高，对于大规模序列比对的时间和空间开销较大。
2. 局部比对的优缺点局部比对算法可以找到两个序列的相似片段，准确度高；但由于需要计算所有可能的局部比对，计算复杂度较高，对于大规模序列比对的时间和空间开销较大。
生物信息学中的多序列比对算法与分析生物信息学是一门交叉学科，将计算机科学和生物学相结合，通过计算机技术和方法研究生物学问题。
生物信息学包括生物序列比对、蛋白质结构预测、基因组分析等领域。
其中，生物序列比对算法是生物信息学中的重要组成部分。
随着技术的发展和数据量的不断增长，生物序列比对变得越来越重要，多序列比对算法及分析应运而生。
1. 多序列比对算法的概念多序列比对是将多个序列进行比对和对齐，找出它们之间的相同、不同和共同进化点。
多序列比对可以为生物学家提供大量的信息，例如基因识别、蛋白质功能预测、基因家族分类等。
多序列比对算法的基础是对于序列之间相似性的度量和序列的对齐。
多序列比对算法可以分为两大类：进化驱动的方法和多序列比对的区域被动方法。
2. 进化驱动的方法进化驱动的多序列比对方法基于序列的进化关系设计，主要包括进化修复和迭代模型。
进化修复方法基于序列的生物进化关系，构建出带权多层次基因族生成模型或者MCMC，利用多个序列的生物进化关系来比对序列。
该方法能够快速准确地对齐序列，并且在宏基因组学中得到广泛应用。
生命病理学家利用这种方法，找出了人类微核症和某些动物DNA片段的进化传播过程。
迭代模型是进化驱动的方法的另一类。
该方法基于多序列比对的思想，先生成初始的序列对齐，然后迭代循环地提高序列的可比性及对齐质量。
迭代模型可以应用于大规模的数据处理和基因家族的比较分析。
3. 多序列比对的区域被动方法多序列比对的区域被动方法是不考虑序列的进化关系，根据区域的相似性来生成序列的对齐。
这种方法主要有二分策略、滑动窗口和局部多序列比对等。
二分策略将序列分成长度相等或相近的子序列，用一棵二叉树将子序列进行比对，然后将比对结果合并成最终序列对齐结果。
二分策略速度快，但是对于高变异的序列处理得不太好。
滑动窗口法则是采用滑动窗口的方式，将一个序列拆分成长度相近的几个子序列进行比对。
该方法可以处理单个序列中不同区域的变异，但是算法耗时较长。
生物信息学中的序列比对算法使用方法解析序列比对在生物信息学中是一项重要的技术，用于寻找DNA、RNA或蛋白质序列之间的相似性和差异性。
它是理解生物学结构和功能的基石之一。
在本文中，我们将解析生物信息学中常用的序列比对算法的使用方法。
序列比对算法主要分为全局比对和局部比对。
全局比对用于比较完整的序列，而局部比对则更适用于在序列中查找相似区域。
在这两个主要类别中，有几种经典的序列比对算法，包括Pairwise Sequence Alignment、BLAST、Smith-Waterman算法和Needleman-Wunsch算法等。
首先，我们来看Pairwise Sequence Alignment（两两序列比对）算法。
这个算法是基本的序列比对方法，通过比较两个序列中的每一个碱基、氨基酸或核苷酸，并根据其相似性和差异性对它们进行排列。
Pairwise Sequence Alignment算法使用动态规划的思想，通过计算匹配、替代和插入/删除的分数，来确定两个序列的最佳匹配方案。
在生物信息学中，常用的实现包括Needleman-Wunsch算法和Smith-Waterman算法。
Needleman-Wunsch算法是一种全局比对算法，用于比较两个序列的整个长度。
它是通过填充一个二维矩阵来计算最佳匹配路径的。
算法的核心思想是，通过评估每个格子的分数，根据路径选择的最佳分数进行全局比对。
这个算法不仅可以计算序列的相似性，还可以计算每个位置的分数，从而获得两个序列的对应二面的对应关系。
Smith-Waterman算法是一种局部比对算法，用于寻找两个序列中的最佳匹配片段（子序列）。
它与Needleman-Wunsch算法的计算思路相同，但不同之处在于允许负分数，这使得算法能够确定具有高分数的局部匹配片段。
通过动态规划计算，Smith-Waterman算法可以寻找到两个序列中的相似片段，并生成比对的结果。
另一种常用的序列比对算法是基本本地搜索工具（BLAST）。
生物信息学中的序列比对算法及评估指标比较序列比对是生物信息学中非常重要的工具之一，用于分析和比较生物序列的相似性和差异。
序列比对是理解生物进化和功能注释的关键步骤，在基因组学、蛋白质学和遗传学等领域都有广泛应用。
本文将介绍序列比对的算法原理和常用的评估指标，并对几种常见的序列比对算法进行比较。
一、序列比对算法1.全局比对算法全局比对算法用于比较整个序列的相似性，常见的算法有Needleman-Wunsch 算法和Smith-Waterman算法。
这两种算法都是动态规划算法，其中Needleman-Wunsch算法用于比较两个序列的相似性，而Smith-Waterman算法用于寻找局部相似的片段。
这些算法考虑了序列的整体结构，但在处理大规模序列时计算量较大。
2.局部比对算法局部比对算法用于找出两个序列中最相似的片段，常见的算法有BLAST （Basic Local Alignment Search Tool）算法和FASTA（Fast All）算法。
这些算法以快速速度和高敏感性著称，它们将序列切割成小的段落进行比对，并使用统计模型和启发式搜索来快速找到最佳匹配。
3.多序列比对算法多序列比对算法用于比较多个序列的相似性，常见的算法有ClustalW和MAFFT（Multiple Alignment using Fast Fourier Transform）算法。
这些算法通过多次序列比对来找到共有的特征和区域，并生成多序列的一致性描述。
二、评估指标1.一致性分数（Consistency Score）一致性分数是衡量序列比对结果一致性的指标，它反映了序列比对的精确性和准确性。
一致性分数越高，表示比对结果越可靠。
常用的一致性分数有百分比一致性（Percentage Identity）和序列相似度（Sequence Similarity）。
2.延伸性（Extension）延伸性是衡量序列比对结果的长度的指标。
生物信息学中的DNA序列比对算法研究DNA序列比对是生物信息学领域的重要研究内容之一。
利用DNA序列比对算法，我们可以比较两个DNA序列的相似性以及其之间的差异。
这对于研究基因组的结构和功能具有重要意义，同时也为疾病诊断和治疗等领域提供了基础。
DNA序列比对算法的研究主要包括全局比对和局部比对两类。
全局比对算法是指将两个DNA序列的整个长度进行比较，寻找两个序列之间的最佳匹配。
全局比对主要应用于已知比较相似的序列之间的比较，如物种的亲缘关系研究和基因组结构比较等。
最经典的全局比对算法是Needleman-Wunsch算法。
该算法采用动态规划的思想，将两个序列的比对问题划分为子问题，通过计算每个子问题的得分，最终得到两个序列之间的最佳匹配结果。
局部比对算法是指将两个DNA序列的一部分进行比较，寻找局部相似性区域。
局部比对主要用于未知比较相似的序列之间的比较，如寻找两个基因组中的同源序列和进行基因家族分析等。
其中最常用的局部比对算法是Smith-Waterman算法，也是基于动态规划的思想，但相对于全局比对，它允许出现负分数，进一步提高了比对的准确性。
此外，还有一类常用的DNA序列比对算法是快速比对算法，它的目标是在保证一定的准确性的同时，尽可能降低比对的时间复杂度。
BLAST（Basic Local Alignment Search Tool）是其中应用最广泛的快速比对算法之一。
BLAST算法利用了序列的局部相似性特征，通过预先构建数据库，将待比对序列与数据库中的序列进行比较，从而快速找到相似性较高的序列片段。
除了以上所提到的算法，还有一些较新的DNA序列比对算法也在不断被提出和探索。
例如，近年来，深度学习技术的发展为DNA序列比对带来了新的思路。
通过将神经网络用于DNA序列比对，可以在不同层次上学习序列之间的特征，并进行相似性比较。
此外，还有一些基于哈希技术的比对算法，如BLAT（BLAST-Like Alignment Tool），它通过对序列进行预先哈希处理，从而实现快速的比对。
生物信息学中的序列比对算法综述序列比对是生物信息学领域中的一个重要问题，指的是比较两个生物序列（DNA，RNA或蛋白质序列）之间的相似性和差异性。
序列比对是许多研究任务中的第一步，如基因识别、物种分类、进化关系的推断等等。
在本文中，我们将介绍序列比对算法的基本概念、方法和软件，包括全局比对、局部比对、多序列比对等方面。
一、序列比对的基本概念序列比对的目的是找出两个序列之间的相似性和差异性，根据相似性分析序列的结构、功能以及进化关系。
相似性可以被表示成一个比对得分，即正数表示相似性，负数表示差异性。
比对得分的计算取决于匹配分、替换分和缺失分。
匹配分是指在比对中找到相同的位置并且相等的分数。
替换分是指找到不同的位置并且不相等的分数。
缺失分是指在任意序列中找不到匹配的分数。
计算得分的方法有很多种，其中最流行的方法是 Needleman-Wunsch 算法和 Smith-Waterman 算法。
二、全局比对算法全局比对算法是一种比较两个序列的整个长度的算法，使得它们之间的相似性或差异性能够被准确地测量。
全局比对算法通常用于比较高度相似的序列或同一物种中相似的序列。
Needleman-Wunsch 算法与 Smith-Waterman 算法是全局比对中最为经典的算法。
Needleman-Wunsch 算法： Needleman-Wunsch 算法是最经典的全局比对算法之一。
该算法通过构建一个二维矩阵，其中每个元素代表在比对过程中两个序列的一个指定位置。
该算法通过分配一个比对得分并使用动态规划来计算所有可能的比对方式。
通过比对得分的计算，算法确定序列之间的最佳比对方式，使比对得分最大化。
该算法常用于比较高度相似的序列，或者已知序列的情况下以寻找相同物种中潜在基因组之间的相似性信息。
Smith-Waterman 算法： Smith-Waterman 算法是一种类似Needleman-Wunsch 算法的全局比对算法。
生物信息学中的序列比对和分析序列比对和分析是生物信息学中非常基础和重要的一项研究内容。
通过比对和分析序列，可以发现序列之间的相似性和差异性，进而研究生物进化、遗传、表达等方面的问题。
本文将从序列比对和分析的意义、比对方法、分析工具和应用实例等几个方面进行讨论。
一、序列比对的意义和方法序列比对是一种比较两个或多个序列相似度的方法，通过比较序列的相同和不同部分，可以获得有关序列功能、结构和进化的信息。
序列比对的主要目的是确定两个序列之间的相似性程度，从而推断它们的共同祖先、结构和功能。
因此，序列比对是研究生物学、医学和生物工程等领域的必要手段。
序列比对的方法主要包括全局比对和局部比对两种。
全局比对是将一整个序列与另一个序列比对，得到两序列的整体相似性程度。
一般要求两序列中的相似部分要尽可能多，而不注重不同部分的对齐。
常用的全局比对算法有Needleman-Wunsch算法和Smith-Waterman算法。
局部比对是寻找两个序列中任意长度的子序列之间的相似性。
与全局比对不同，局部比对更注重相同的局部片段，忽略不同的片段。
局部比对算法有BLAST和FASTA等。
二、序列分析的工具和方法序列分析是通过对比对后的序列进行进一步分析，获得生物信息的过程。
序列分析的主要内容包括序列注释、序列搜索、序列聚类和序列比较等。
序列分析的方法和工具主要包括多序列比对、单序列比对、序列搜索、聚类分析、进化树分析和功能预测等。
多序列比对是将多个序列进行比对，得到这些序列之间的共同特征和差异。
常用的多序列比对工具有Clustal X和MUSCLE等。
单序列比对是将一个序列和已知的库中所有序列进行比对，以查找相似性和相关性。
常用的单序列比对工具有BLAST和PSI-BLAST等。
序列搜索是在一个已知的序列库中搜索相似的序列。
常用的工具有HMMER、PhyloGenie等。
聚类分析是将相似的序列放在一起形成聚类，便于分析相关性。
生物信息学中的序列比对与序列分析研究序列比对与序列分析是生物信息学领域中非常重要的研究内容之一。
在基因组学和蛋白质组学的快速发展下，对生物序列的比对和分析需求不断增长。
本文将介绍序列比对和序列分析的概念、方法和应用，并探讨其在生物学研究中的重要性。
一、序列比对的概念与方法：1. 序列比对的概念：序列比对是将两个或多个生物序列进行对比，确定它们之间的相似性和差异性的过程。
在生物信息学中，序列通常是DNA、RNA或蛋白质的一连串碱基或氨基酸。
序列比对可以用来寻找相似性，例如发现新的基因家族、识别保守的结构域或区分不同的物种。
2. 序列比对的方法：序列比对的方法可以分为两大类：全局比对和局部比对。
全局比对将整个序列进行比对，用于高度相似的序列。
而局部比对则将两个序列的某个片段进行比对，用于相对较低的相似性。
最常用的序列比对算法是Smith-Waterman算法和Needleman-Wunsch算法。
Smith-Waterman算法是一种动态规划算法，它在考虑不同区域的匹配得分时，考虑到了负分数，适用于寻找局部相似性。
而Needleman-Wunsch算法是一种全局比对算法，通过动态规划计算最佳匹配得分和最佳比对方式。
二、序列比对在生物学研究中的应用：1. 基因组比对：序列比对在基因组学中具有广泛的应用。
它可以帮助研究人员对特定基因进行鉴定，发现重要的调控元件以及揭示物种间的基因结构和功能差异。
此外，基因组比对还可以用于揭示突变引起的遗传疾病和肿瘤等疾病的发病机制。
2. 蛋白质结构预测：序列比对在蛋白质结构预测中也起着重要的作用。
通过将待预测蛋白质序列与已知结构的蛋白质序列进行比对，可以预测其二级和三级结构以及可能的功能区域。
这些预测结果对于理解蛋白质的功能和相互作用至关重要。
3. 分子进化分析：序列比对在分子进化研究中也扮演着重要的角色。
通过将源自不同物种的基因或蛋白质序列进行比对，可以构建进化树，研究物种的亲缘关系和演化历史。
生物信息学中的序列比对算法分析在现代分子生物学中，序列比对是一项非常重要的任务。
生物学家通过比对不同物种间的DNA或蛋白质序列，能够更深入地理解生物界的进化和生物学功能。
序列比对经常被用于比较蛋白质序列，以揭示它们的相同区域和变异区域，从而推测功能、拼图蛋白质结构或阐明进化关系。
在生物信息学领域，一些高质量的序列比对算法被广泛采用，但其具体方法和适用范围是如何的呢？序列比对算法大致可分为全局比对和局部比对两种。
全局比对将整条序列进行对齐，相当于将两个序列定位到横坐标和纵坐标的原点上。
与之相对应的是局部比对，它只对序列中某一区域进行对齐。
全局比对通常用于比较两个具有高度相似性的序列，例如不同物种DNA序列的比对。
而局部比对则常用于比较代表同一蛋白质家族的蛋白质序列。
除了这两种基本的比对模式，还有一些更具特殊化应用的比对方法，比如开环比对、半开放比对等等。
全局比对的经典算法是Needleman-Wunsch算法，其基本思想是动态规划。
以两条DNA序列为例，算法可以计算处所有可能的匹配方式，并选择其中总分最高的一种。
该算法忽略了序列中的重复片段，不适用于两个序列有部分区域高度一致，而其他区域则存在较大差异的情况。
如果两条序列的长度非常不同，可能会出现计算过程时间复杂度增大并产生鲁棒性的问题。
相比之下，局部比对通常采用Smith-Waterman算法，用动态规划的方式找到两条序列中的片段匹配，其过程是在确定了一个匹配片段的前提下，向两侧扩展寻找更长的匹配片段。
Smith-Waterman算法的可变步长（gap）能力使其更新得比经典全局比对算法更好。
但由于算法计算量较大，因此无法执行大规模任务。
最发达的比对算法是BLAST（基础局部对齐搜索工具），它将参考序列和数据库中的查询序列分别分割成短段，只比对那些相似性较高的片段。
从而快速访问数据库并比对大量不同序列。
该算法大大降低了序列比对的计算时间，使比对过程能够在合理的范围内进行。
文章编号"#$$#%&’’()*$$’+$,%$*#’%$-生物序列比对算法分析与比较钟诚#.宋彬*)#/广西大学计算机与电子信息学院.广西南宁(,$$$’0*/中国科学技术大学计算机科学技术系.安徽合肥*,$$*&+摘要"序列比对是生物信息学的一个非常重要的操作/它可以预测生物序列的功能1结构和进化过程等/文中首先介绍双序列比对的基本算法0接着分析和比较多序列比对的四个常用模型和三类算法以及并行比对算法0最后.给出一些研究问题/关键词"生物信息学0双序列比对0多序列比对0精确算法0近似算法0启发式算法中图分类号"23,$#04-##文献标识码"5生物信息学是一门综合数学1计算机科学和生物学的交叉学科6#7/生物信息学内涵非常丰富.其核心是基因组信息学.包括基因组信息的获取1处理1存储1分配和解释/基因组信息学的关键是8读懂9基因组的核苷酸顺序.即全部基因在染色体上的确切位置以及各:;5片段的功能0在发现新基因信息之后模拟和预测蛋白质空间结构.然后依据特定蛋白质的功能进行药物设计/生物序列中的信息在系统进化1生态守恒1疾病控制1病毒起源甚至<=>病毒统计和传播等的研究中是一个非常重要的基本工具6*7.因此.序列比对是生物信息学的基础/序列比对分为全局比对)?@A B C @5@D E F G H F I +和局部比对)J A K C @5@D E F G H F I+/全局比对要求把一个序列中的所有符号和另一个序列中的所有符号进行匹配比较.它描述整个序列的相似性/将两个序列进行比对就是双序列比对.它是比较两个生物序列相似性的重要工具/这个分析工具已经成功地运用到预测生物序列的结构1功能和进化例程中/随着生物医学中有更多的序列合成出来.人们开始用多序列比对来更好地研究生物序列/将多个序列进行比对就是多序列比对问题.它是一个将不等长的多个序列通过插入空格变成等长的过程.这些位置上的空格代表着相比较的序列从共同的祖先通过插入L 删除操作的进化过程6,7/求解多序列比对问题的算法主要分为精确算法1近似算法和启发式算法三种/#双序列比对对于两个长度分别为M 的序列有*M N OM P )*M +Q )M Q +)M Q +R**MS T M种比对情况.这是一个指数级复杂度的计算问题/#U &$年.;H H V @H G C F 和WX F Y K Z 基于动态规划方法6’7提出了第一个双序列比对算法6(7#U -*年.?A I A Z 对其做了进一步的改进6[7/<D \Y K Z B H \E 于#U &(年提出一个线性时间复杂度的算法来计算双序列比对6&7.而]^H \Y 和]D @@H \改进了该算法6-7/基于动态规划方法._G D I Z 和WC I H \G C F 给出一个局部比对算法6U 7/#U -&年.WC I H \G C F 和‘E E H \I给出一个计算双序列中a 个局部比对的算法6#$7/#U U #年.<X C F E 和]D @@H \给出一个线性空间复杂度的算法来计算双序列中a 个局部比对6##7/*多序列比对及其比对模型*b #多序列比对问题定义#设c 为符号集合.d 代表空格.给定序列组e #.e *.f.e a.多序列比对g 表示把这些序列放第*U 卷第,期*$$’年U 月广西大学学报)自然科学版+h A X \F C @A i ?X C F E j D k F D l H \Y D I ^);C I _K D ‘V +>A @/*U .;A /,_H m I /.*$$’!收稿日期"*$$’$’*#0修订日期"*$$’$-#&基金项目"广西自然科学基金)桂科自$,,U $$-+0国家-[,计划)*$$#55###$’#+作者简介"钟诚)#U [’+.男.广西桂平人.广西大学教授.博士/万方数据到!行中"每行一个序列"这些序列可以插入#"从而得到超级序列组$%"$&"’"$!"但序列组中每列不可全为#"使得($)(*+且,的代价-+)*%./$%/)0"$&/)0"’"$!/)00最小"其中./$%/)0"$&/)0"’"$!/)00代表第)列的代价1一般地"列代价反映该列中符号不相似的程度1多序列比对是一个组合问题"随着插入空格的数量与位置的不同"可得到很多种比对情况2%31目前"依旧没有非常有效的方法来求解实际的多序列比对问题1从多序列比对的定义可以看出"随着代价函数.定义的不同"就会产生不同的比对结果1对.的不同定义可得出不同的比对模型/456789:8;<=>:502%&?&@3A B C 比对/B C456789:8;0D 中心比对/E =8F :8F G F 456789:8;"也称为B ;H I 456789:8;0D 树比对/J I ::456789:8;0和熵比对/K 8;I =L M456789:8;01&1&B C 比对模型/B G 9N =O NC H 6I 456789:8;0B C 比对模型,中第)列的代价定义为./$%/)0"$&/)0"’"$!/)00*-%PQ RS P!./$Q /)0"$S/)00"其中./$Q /)0"$S /)00表示同一列中两个相应符号$Q /)0和$S/)0的代价1这个代价函数常称为B C /B G 9N =O N H 55N C H 6I F 0代价2%31B C 比对在实际应用中是一个非常有用的模型"被大家广泛地研究2%&?%T "%U ?&%31可以看出B C 比对实际上是将序列两两进行比对"这样序列在比对中的地位是相等的1若我们不知道序列之间的关系"那么我们就可以使用这个模型"通过假设序列相互之间不关联"来得出较好的结果1人们已经证明在B C 比对模型上求解多序列比对是V C W X H I >问题2&&3"并且Y 6=86Z Z =86和[:>=\H 还证明了即使对于符号集只含两个元素的情况"在B C 比对模型上求解也是个V C N X H I >问题2&&31此外"若假设序列间地位相等"则没有充分利用自然序列间本身具有的关联性"也没有建立在统计学的基础上"并且当序列中有一个符号发生改变时"结果就会有很大的变化"这和实际情况不符1&1]中心比对模型/E =8F :8F G F 456789:8;"B ;H I 456789:8;0中心比对模型第)列的代价定义为./$%/)0"$&/)0"’"$!/)00*968^_-‘a #b -cd *%./$d/)0"^0"也就是说"为了定义,的代价"重新构造,中每一列的符号或空格"这样就得到一个和所有输入序列的代价最小的e 中心f 序列1这个e 中心f 序列就可以代表输入的诸序列2%T 31与B C 比对模型相比"中心比对模型把两两比对转化为多对一的比对"这样比对次数大大减少"问题复杂性大大降低1但是"求解中心序列的过程却相当复杂"依旧需要考虑到所有的序列"这样就把两两比对的复杂性转嫁到求解中心序列的问题上"从而本质上没有突破1因此"依旧有非常困难的结果A 当符号集只含有g 个元素"代价函数定义简单/如匹配为@"不匹配为%0时"在中心比对模型上求解也是V C N X H I >问题2&]31当代价函数定义是任意的时候"中心比对更是一个<4h N B V C N X H I >问题2&g 31&1g 树比对模型/J I ::456789:8;0为了定义树比对,的代价/J I ::N i =F ;0"假设已知一个含!个叶子的进化树/K \=5G ;6=8H I MjC X M 5=7:8:;6i J I ::0k*/l "m 0"其中l 和m 代表树k 的点集和边集"树k 的每一叶子d 代表一个输入序列^d n !o %"!o &"’"!o p 代表树k 的内部结点1为了得到比对,的第)列的树代价A ./$%/)0"$&/)0"’"$!/)00"需要重建每个内部节点d 的符号或空格$d /)0"使得-/Q "S 0_m./$Q /)0"$S/)00最小1第)列的树代价定义为./$%/)0"$&/)0"’"$!/)00*-/Q "S 0_m./$Q /)0"$S/)00"其中./q "r 0用来衡量从q 到r 的e 进化f 距离"比对,第)列的树代价实际上就是进化树k 产生符号或空格的$%/)0"$&/)0"’"$!/)0最小代价2%31这个模型由B H 8s =O O 于%t u T 年首先提出2&T 3"在计算分子生物学领域中引起了广泛的关注1与B C 比对和中心比对相比"树比对更加符合自然界本身的状态"与自然进化过程有着天然的联系1比对又是建立在进化树基础上"减少了计算量1实际上"中心比对为树比对中进化树是星形的一种特殊情况1在进化树已知的情况下"在树比对模型上求解多序列比对问题显然是最佳的选择1但是进化树的构建常常需要T%&第]期钟诚等A 生物序列比对算法分析与比较万方数据多序列比对的结果!这样就产生了一个"死循环#!很难得到满意的结果$%$&熵比对模型’()*+,-./012)34)*5熵比对模型6第7列的代价定义为8’9:’75!9%’75!;!9<’755=>?@A ?B CD 7@0,2E 7@!其中D 7@代表符号@在第7列出现的次数!即D 7@=?F G’9F ’75=@5!G ’9F ’75=@5=:!HI !若9F’75=@!其余情况$E 7@代表符号@在第7列出现的概率$直观上看!每一列的变换越大!该列的熵越大J 熵越小!即每列的变换越小!也就越相似!求出熵最小的情况就是最"相似#的比对$K L 比对M 中心比对和树比对模型都是建立在双序列比对的基础上!而双序列比对问题本身也是一个比较复杂的问题!仍然需要继续研究$熵比对模型则摆脱了这个"怪圈#!从一个新的角度来解决问题!但熵比对模型的正确性和实用性还没有得到生物学家的公认$N 多序列比对算法的分析与比较动态规划算法是求解多序列比对问题最直接的方法$它不仅可以得出精确最优解!还是后面许多近似算法M启发式算法的基础$当序列条数不太多M 序列长度不太长时!动态规划算法能够有效地解决问题$但是!在生物信息学中!需要比对的序列长度常常很长!序列条数也较多!这样动态规划算法就显得"力不从心#了$这时!可以降低"标准#!不再求精确解!而只求出近似的比对结果就行了$为此!许多近似算法应运而生$N O :精确算法设P :!P %!;!P <是<个给定的序列!每个序列的长度分别为Q :!Q %!;!Q <!P 7R F S 代表P 7序列中第F 个符号!T ’7:!7%!;!7<5代表以P :R 7:S !P %R 7%S !;!P <R 7<S 结尾前缀的最优比对代价!则动态规划算法为T ’7:!7%!;!7<5=31)T’7:>:!7%>:!;!7<>:5U V ’P :R 7:S !P %R 7%S !;!P <R 7<S 5!T ’7:!7%>:!;!7<>:5U V ’>!P %R 7%S !;!P <R 7<S 5!WT ’7:>:!7%>:!;!7<5U V ’P :R 7:S !P %R 7%S !;!>5!T ’7:!7%!;!7<>:5U V ’>!>!;!P <R 7<S 5!WT ’7:!7%>:!;!7<>:!7<5U V ’>!P %R 7%S !;!>5!X Y Z W可以看出!空格出现的组合方式有%<>:种’全为空格的情况不满足比对条件5$整个算法的初始M 终止和迭代步骤与双序列比对的动态规划算法完全相同R :&S$该算法需要建立一个Q :[Q %[;[Q <规模的矩阵$为了计算矩阵中每个元素的值!需要考虑到每列中%<>:种空格的组合方式$若最终比对序列中的每条序列的长度均为Q !则动态规划算法的空间复杂度为Q <!时间复杂度为\’%<Q <5$动态规划算法复杂的时空复杂度!给计算带来很大的不便$于是人们试图利用各种方法来改进动态规划算法$]^++100,和_1-3^)在K L 模型中!提出通过减少计算体积来改进动态规划算法的方法$其基本思想就是!通过两两比对计算比对的上界!若在<维的比对矩阵中的元素超过了上界!就不予考虑!从而简化了动态规划算法R :%S$还可以用寻找最短路径的方法来改进动态规划算法$考虑这样一个有向无环网状图!图中的顶点集为‘!边集为a !使得‘=H ’b :!b %!;!b <5c b 7=I !:!;!Q 75!a=B d A H I !:e<H ’f !f U d 5c f !f U d A ‘!d g I e $这样!从顶点P =’I !I !;!I 5到顶点h =’Q :!Q %!;!Q <5的一条路径对应于一个序列比对R %i S$K -,j 24将求解最短路径问题中的/k 算法用来改进动态规划算法以计算多序列比对R %l S$m n 4o ^和m 3^1将这种/k 算法直接运用到多序列比对中R %p S $i :%广西大学学报’自然科学版5第%q 卷万方数据实际上!"#$作为现在少有的试图求最优比对的软件之一!就是用分枝界限方法和%&’()*+,的最短路径算法相结合来改进动态规划算法的时空复杂度-./01此外!2&33&,4!5&)36和789:,+使用双动态规划算法考虑序列的三维空间结构及其比对-.;01<1.近似算法首先介绍近似算法的性能比=概念!它使得对于问题中的所有实例>有?@>A B C D E @>A F =!其中?@>A 表示实例在算法?中的代价!C D E @>A 表示在最优算法中的代价15G )H &6I 于J ;;<年提出了第一个在#K 比对模型上的近似求解中心方法@L 68*6+)*,+46*M N I A 1其基本原理是!将中心比对模型与#K 比对模型O 融合P 起来!把中心比对模型中O 中心序列P 的概念引入到#K比对模型中!从而简化计算1其基本步骤是从给定的Q 个序列中选择一个中心序列R S 使得T QU V J W @R S !R UA 最小!其中W @R S !R U A 代表R S 和R U 双序列比对的最优代价X 然后!将Y Z [R S\的序列一个接一个地加入到比对]中!使得每个新加入的序列与R S 的双比对是最优的@若需要!则在比对前的序列中插入空格A !直到所有的序列都被加入为止!这样就得到了Q 个序列的多序列比对]!Y V @R J !R .!^!R QA 1该算法的时间复杂度为C @Q.>.A 1已经证明!中心方法得出的比对代价至多是最优代价的.倍-J _!J ‘01在中心方法的基础上!a ,H 8,!b ,c 6+和K 6:d 86+提出了>Z )*,+)方法1它的基本思想是!同样选择一个中心序列R S !将Q 个已知序列分成若干组!每组都包含R S 且共有>个序列!每组比对这>个序列!通过中心序列R S 将各组序列组合起来得到最终的比对1这种方法的难点是如何分组!具体细节请参看文献-J ;01上述方法均是将比对中每种情况进行穷举来求近似解1于是!人们想到!能不能加一定的限制条件!这样就可以不去考虑很少出现最优解的情况!而只考虑常会出现最优解的情况1e S Z I &,9N 8,3比对1设Y V @R J !R .!^!R QA 是Q 个序列的集合!每个序列的长度为f !它们的比对]中每条序列的长度是>1一个S Z I &,9N 8,3比对是指!对于任意的g !U 和h !如果序列R U 中的第g个符号在比对]中的第g i 列!序列R h 中的第g 个符号在比对]中的第ji 列!则k g i Z j i k F S 1也就是说!空格被O 均匀P 地插入到各个序列中!每个序列的第U 个位置至多与别的序列的第U 个位置相距S 1然而!S Z I &,9N 8,3比对的求解同样是建立在#K 比对模型和中心比对模型上的l K Z M ,+I 问题-J _!.<01b &!a &8和b G )M 689给出了在#K 比对模型和中心比对模型上的多项式时间近似求解算法1算法的基本思想是!构造在$m n o $5nS Z 5$K 限制条件下问题的K p $#解!利用这个K p $#解来得到想要的结果1q $:6+,96S Z 9,r#K 比对1求比对]使得每个序列中平均只有S 个空格插入和删除!并使得#K 代价最小1下面看看b &给出的$:6+,96S Z 9,r#K 比对的K p $#算法-</01它的理论依据是s 设t 是序列R J!R .!^!R u 的比对]的长度!v h !u 是符号w在]中的第h 列的出现次数!#K 的代价函数表示为x D @]A V T th V J Tw yzw !z {T |[}\v h !w v h !z !其中v h !u B u 表示符号w 在第h 个位置的概率1因此!可用v h !uB u 作为元素得到大小为t~@k !k "JA 的概率矩阵1这样!算法可以如此来计算s 随机地从u 个序列中选择=个序列@如图J 所示A X 穷举所有的比对!得到这=个序列的O 正确P 比对]=X 然后!计算这个比对]=的概率矩阵!并假设这个矩阵就是比对]的概率矩阵X 按照]的概率矩阵计算原先Q 个序列的比对!得出需要的结果1图J 任取=个序列的比对#J .第<期钟诚等s 生物序列比对算法分析与比较万方数据有了!"#$%&#’(&%)*+比对的结果,就可以求’(-.%&/0%1比对2首先,动态地把序列切成小的碎片,使得每个碎片满足前面!"#$%&#’(&%)*+比对的条件,且每个碎片的*+代价大约为’345,平均每个序列的碎片有’3次插入或删除6然后,用前面!"#$%&#’(&%)*+比对的+7!*算法来处理碎片8如图596最后,将碎片的结果组合起来,得到原问题的结果2因为考虑到采用的是’(-.%&/0%1比对,所以每个碎片的错误最多为’452这里问题的难点是碎片如何划分:具体内容请参考文献;<=>,该算法的性能比是?8@A 5B 83(5(@B ’99;<=>2图5序列的分割<C <启发式算法在启发式算法中,比较重要的一类是渐进比对方法8+$/&$#D D ."#!1.&0E #0F G#F H /-D 92它将两个多序列比对的结果合并成一个多序列比对2多序列比对软件I J !K L M N 和O 1P D F %1Q 就是借助向导树8&P .-#F $##9使用该方法的2O 1P D F %1Q 首先使用动态规划算法求出每两个序列间的最优比对,并把结果存储到代表进化距离的距离矩阵并构建进化树6然后,用进化树作R 向导S ,对序列渐进比对,具体的内容可参看;<@,<5>2迭代方法也是求解多序列比对的常用方法2常见的有T #$&#$(GP 0D /0算法和*%0U /V V 算法等2@W X <年,*%0U /V V提出了用迭代方法来作树比对2其基本思想是,将树中的内部节点放上序列,选择其中一个顶点Y ,使用相邻的三个节点进行比对,依次重复做,直到结果不再改进为止2在图<所示的迭代方法中,将圆上的三个序列依次进行比对,直到树上的代价不再减少,这样就得到了需要的结果;@Z ,<<>2图<*%0U /V V 的迭代算法图[多个序列中的E /F .V块多序列比对的一个重要的应用就是寻找多个序列中R 固定S 的区域,通常把这些R 固定S 的区域称为E /F .V 块2图[的粗线表示的就是E /F .V 块,这些E /F .V 块没有必要绝对的相同,而只需要E /F .V 块比与其他的区域相似得多即可2目前,求解E /F .V 块的常用方法有隐马尔柯夫模型8\.--#0G%$U /"G/-#19和M .]]D 取样8M .]]D D %E )1.0&92它们的基本思想都是将E /F .V 块作为随机的分割,然后用自学习的技巧,得出结果2所不同的是,M .]]D 取样是假设E /F .V块中的元素相互不关联,而隐马尔柯夫模型假设相互关联;<[>2[并行比对算法最直接的方法是,人们尝试把动态规划算法并行化从而降低序列比对的时空复杂度2由于动态规划X @5广西大学学报8自然科学版9第5W卷万方数据算法中!矩阵中的元素值依赖于左边一点"上面一点和对角线上一点#因此!线$上的点在之前的点的值已知的情况下!可以并行地执行#对于双序列比对!该算法若使用%个处理器则时间复杂度由&’%()降到&’%)#当两个生物序列比较相近时!动态规划矩阵中只有部分元素是有价值的#若加入一个限制条件*!则串行比对算法只要&’*%)时间!并行比对算法可以用&’*)个处理器在&’%)时间内完成’图+)#由此可推广到多序列比对即动态规划矩阵是,维’,-()的情形#图.是/维的情况!同样若加上限制条件*!则串行比对时间复杂度为&’*(%)0若使用&’*()个处理器!则并行比对的时间复杂度为&’%)1/+2#图+双序列并行比对方法图./维的并行比对方法3444年!56787!97:;<78;和=>?8@:8;运用计算前缀的方法1/.2!使用&’%A 6@B %)处理器!设计一个时间复杂度为&’C 6@B %)的双序列比对并行算法#3443年!D >8B >8和=7E F @E 提出一个基于迭代的多序列比对算法1/G 2!它的基本思想是!第3步!把输入的,个序列随机地分成两组!将两组之间的序列进行比对!并将比对结果和空格位置记录下来0第(步!若新的比对结果比当前比对的结果好!就将标记设为H !否则为I 0第/步!若第(步中的标记设为H !则用第3步中记录的空格位置更新当前的比对!更新过的和没有更新过的比对作为下一次循环的输入0如此下去直到结果达到某个标准为止#显然!迭代算法的基本思想是以后的结果由当前的输入来决定!这种串行关系给并行化带来一定困难#J F ?K L ;M ;等人将D >8B >8N =7E F @E 迭代算法改造成并行算法1/O 2P 并行计算所有’(,Q 3Q 3)种可能的分割或’,R ,’,Q 3)A ()种限制的分割’每组序列的数目大大影响到最后的结果!若在第3组中的序列只有一个或两个则结果会很好!这样分割的情况就从’(,Q 3Q 3)种限制到了’,R ,’,Q 3)A ()种)!将得出的最好结果作为下一次循环的输入#S K >E B 等人于344+年改进了该算法1/42#另外!T ;F 7F ?K 等人在使用5U 算法思想求多序列比对的基础上!提出一个并行算法来求多序列比对!将执行时间降到了人们能够V 忍受W 的范围内1X Y 2#Z B 7[>E 等人提出一个新的基于遗传算法的多序列比对算法!且将算法改写为并行算法来降低时空复杂度1X 32#+结语多序列比对问题依旧是当今分子生物学中最具有挑战性的研究问题之一#文献132给出了关于多序列比对的公开讨论问题P ’3)如何设计一个实用的多序列比对程序来处理成千上百的序列比对\’()如何将多序列比对与进化过程统一起来\自然地!可以考虑用进化树来解决该问题!但是人们知道产生进化树是=5]^Z _N ?;8‘问题!没有_S 5^!于是!问题依旧需要探索#’/)能不能利用序列中特殊区域的信息!使多序列比对成为一个交互式的过程\该问题的结果将是解决组合复杂性的关键#如何在_(_!a 8K ‘!D ^_A D ^_U!b =c ^d !e c f f=;:8K g 等并行计算模型上设计具有良好加速比的可扩放的动态规划并行算法和序列比对并行算法!以及如何更好地考虑到序列的空间结构进行比对等都是需要探索的课题#此外!如何借鉴近似串匹配并行算法1X (2的设计思想来开发高效的多序列比对并行算法也是一个值得重视的方向#参考文献P 132S h K ;E B !T ]7!=i j ?;E B #e 788>E :S @k K l F K Ee @<k 7:;:K @E ;6=@6>l 76;8D K @6@B [1=2#e ;<m 8K ‘B >!=;F F ;l ?7F >::FP 43(第/期钟诚等P 生物序列比对算法分析与比较万方数据!"#$%&’’()**)+,)-./01’23’$(4562&/7(85%98+:&;2&<=3/>2?/&’&@3&6A &5/2B 6=&6>26?C 1/0B &6&>2A565/1’2’,7-+!0/&A 3/5%$C 1/0B &6&>2A ’569D ;0/3>206()***(E F G H I J H E K L H H *+,H -M 06N 5/0M (85%9O 8(71%P 2!+4Q .=3/>2?/&’&@3&6A &5/2B 6=&6>’,7-+!0/&A 3/5%R 1’>&=5>2A ’569D ;0/3>206J #C &0%1569$%5A >2A &()**E (E *K L E E F +,S -T &//=56:D +4165=2A $%0B %5==26B ,!-+$%26A &>06J $%26A &>06U 62;+$%&’’(E V W K +,W -Q &&9/&=56RT (836’A CO4+.B &6&%5/=&>C 095??/2A 5X /&>0>C &’&5%A CY 0%’2=2/5%2>2&’26>C &5=2605A 29’&@3&6A &’0Y ><0?%0>&26’,7-+7!0/T 20/(E V K *(S Z J S S H L S W H +,F -M 0>0C[+.62=?%0;&95/B 0%2>C =Y 0%=5>A C 26BX 20/0B 2A 5/’&@3&6A &’,7-+7!0/T 20/(E V Z )(E F )J K *W L K *Z +,K -\2%’A C X &%B 4R +./26&5%’?5A &5/B 0%2>C =Y 0%A 0=?3>26B =5]2=5/A 0==06’3X ’&@3&6A &’,7-+O 0==0Y .O !(E V K W (E Z J H S E L H S H +,Z -!1&%’D8(!2//&%8+[?>2=5/5/2B 6=&6>’26/26&5%’?5A &,7-+O 0=?3>.??/2A T 20’A 2(E V Z Z (S J E E L E K +,V -R =2>C#^(85>&%=56!R +"9&6>2Y 2A 5>2060Y A 0==06=0/&A 3/5%’3X ’&@3&6A &’,7-+7!0/T 20/(E V Z E (E S K J E V W L E V K +,E *-85>&%=56!R (D B B &>!+.6&<5/B 0%2>C =Y 0%X &’>’3X ’&@3&6A &5/2B 6=&6>’<2>C5??/2A 5>206>0>:Q .A 0=?5%2’06’,7-+7!0/T 20(E V Z K (E V K J K )H L K )Z +,E E -\356B_(!2//&%8+.>2=&L &Y Y 2A 2&6>(/26&5%L ’?5A &/0A 5/’2=2/5%2>15/B 0%2>C =,7-+.9;.??/!5>C(E V V E ()J H H K L H W K +,E )-O 5%%2//0\(‘2?=564+#C &=3/>2?/&’&@3&6A &5/2B 6=&6>?%0X /&=26X 20/0B 1,7-+R ".!703%65/06.??/2&9!5>C(E V Z Z (S Z J E*K H L E*Z )+,E H -‘2?=564(./>’A C 3/R^(a &A &A 20B /374+.>00/Y 0%=3/>2?/&’&@3&6A &5/2B 6=&6>,7-+$%0A Q 5>/.A 59R A 2(E V Z V (Z F J SS E )L SS E W +,E S -M 3’Y 2&/94+D Y Y 2A 2&6>=&>C 09’Y 0%=3/>2?/&’&@3&6A &5/2B 6=&6><2>C B 35%56>&&9&%%0%X 0369’,7-+T 3//&>260Y!5>C &=5>2A 5/T 20/0B 1(E V V H (W W J E S E L E W S +,E W -M 3’Y 2&/94+./B 0%2>C =’06R >%26B ’(#%&&’(569R &@3&6A &J O 0=?3>&%R A 2&6A &569O 0=?3>5>2065/T 20/0B 1,!-+Q &<b 0%P J O 5=X %29B &U 62;&%’2>1$%&’’(E V V K +,E F -R 56P 0Y Y4(a %3’P 5/7+#2=&85%?’(R >%26BD 92>’(569!5A %0=0/&A 3/&’J #C &#C &0%1569$%5A >2A &0YR &@3&6A &O 0=?5%2’06,!-+:&5926B!.J .992’068&’/&1(E V Z H +,E K -85>&%=56!R +"6>%093A >206>0O 0=?3>5>2065/T 20/0B 1J !5?’(R &@3&6A ’(569M &60=&’,!-+‘06906J O C 5?=56569\5//(E V V W +,E Z -T 5A 0064(.69&%’068+!3/>2?/&’&@3&6A &5/2B 6=&6>,7-+703%65/0Y !0/&A 3/5%T 20/0B 1(E V ZF (E V E J E W H L E F E +,E V -T 5Y 65c (‘5<&%D ($&;N 6&%$+.??%0]2=5>2065/B 0%2>C =’Y 0%=3/>2?/&’&@3&6A &5/2B 6=&6>,7-+#C &0%&>2A 5/O 0=?3>&%R A 2&6A &(E V V K (E Z )J )H H L )S S +,)*-M 3?>5R (a &A &A 20B /37(R A C 5Y Y &%.+!5P 26B >C &’C 0%>&’>L ?5>C ’5??%05A C >0’3=L 0Y L ?52%’=3/>2?/&’&@3&6A &5/2B 6=&6>=0%&’?5A &&Y Y 2A 2&6>26?%5A >2A &,.-+$%0A +F >CR 1=?+06O 0=X 265>0%25/$5>>&%6!5>A C 26B (‘Q O R V H K ,O -+T &%/26J R ?%26B &%(E V V W (E )Z L E S H +,)E -R A C 3/&%M 4(./>’A C 3/R ^(‘2?=5647+.<0%P X &6A CY 0%=3/>2?/&5/2B 6=&6>A 06’>%3A >206569565/1’2’,7-+$%0>&26’J R >%3A >3%&(^36A >206569M &6&>2A ’(E V V E (V J E Z *L E V *+,))-T 062N N 062$(4&//5c &90;5M +#C &A 0=?/&]2>10Y =3/>2?/&’&@3&6A &5/2B 6=&6><2>CR $L ’A 0%&>C 5>2’=&>%2A ,7-+#C &0%&>2A 5/O 0=?3>&%R A 2&6A &()**E ()W V G E L )I J F H L K V +,)H -‘2!(!5T (856B‘+^26926B ’2=2/5%%&B 206’26=561’>%26B ’,.-+$%0A H E ’>.O !R 1=?+[6#C &0%10Y O 0=?3>26B,O -+Q &<b 0%P J .O !$%&’’(E V V V (S K H L S Z )+,)S -7256B#(‘5</&%D ‘(856B‘+./2B 626B’&@3&6A &’;2556&;0/3>2065/>%&&,.-+O 0=?/&]2>15695??%0]2=5>206+$%0A +)F >C.O !R 1=?+[6#C &0%10Y O 0=?3>26B ,O -+Q &<b 0%P J .O !$%&’’(E V V S (K F *L K F V +,)W -R 56P 0Y Y 4(:03’’&53$+‘0A 5>26B>C &;&%>2A &’0Y 5R >&26&%>%&&26565%X 2>%5%1=&>%2A ’?5A &,7-+!5>C$%0B %5=(E V K W (V J )S *L )SF +,)F -a 0X 515’C 2\("=52\+"=?%0;&=&6>0Y >C &.d 5/B 0%2>C =Y 0%=3/>2?/&’&@3&6A &5/2B 6=&6>,e -+$%0A 0Y V >C<0%PL ’C 0?06M &%60=&"6Y 0%=5>2A ’(#0P 10J U 62;&%’5/.A 59&=1$%&’’(E V V Z (E )*L E H *+,)K -R ?03B &7‘+R ?&&926B3?4165=2A$%0B %5==26B./B 0%2>C =’Y 0%Y 26926B[?>2=5//5>>2A &?5>C ’,7-+R ".!7.??/!5>C(E V Z V (S V G W I J EW W )L EW F F +*))广西大学学报G 自然科学版I 第)V 卷万方数据!"#$%&’()*+%,)-./0)1234)5678-29,:78;<52-=5’>’?<’@A ’35-6@,’@2!B $/C 87A /7:D 29E 78&197=7@F ’8@7,’%@:78,)2-A 1+*7&G 7H I @-J ’81)53A )(’,GC 8’11+K L L M +L N O L L /!"L $P-55-),Q *+F -15’>+%@6J )8R /;<52-=5’=872’-@1’?<’@A ’)5-6@,’@2<1-@6(7<S 5’O (G @),-A=8768),,-@6!T$/U 7,=<2’81)@(U 9’,-128G+"N N N +"M H V WK "/!V N $X -;+;)Y +P)@6X /Z ’)87=2-,)5,<52-=5’)5-6@,’@2E -29-@)S )@(-@=75G @7,-)52-,’!B $/C 87A/V "@(3U ;>G ,=/[@*9’78G7:U 7,=<2-@6+Z ’E \78&H 3U ;C 8’11+"N N N +M "D O M V M /!V K $*97,=17@T +.-66-@1]+F -S 17@*/U 5<12)5P H %,=87J -@629’1’@1-2-J -2G 7:=8768’11-J ’,<52-=5’1’?<’@A ’)5-6@,’@22987<691’?<’@A ’E ’-692-@6+=71-2-7@O 1=’A -:-A 6)==’@)52-’1)@(E ’-692,)28-^A 97-A ’!T $/Z <A 53A -(1Q ’1+K L L M +""_""‘H Ma b V O Ma #N /!V "$0’@6]+]775-225’Q 0/C 8768’11-J ’1’?<’@A ’)5-6@,’@2)1)=8’8’?<-1-2’27A 788’A 2=9G 576’@’2-A 28’’1!T $/T ;75R J 75+K L #b +"D H V D K O V a N /!V V $>)@&7::]/;-@-,)5,<2)2-7@28’’17:1’?<’@A ’!T $/>%3;T 7<8@)57@3==5-’(;)29+K L b D +"#H "D O M "/!V M $]<8S -@Q +R ((G>+c 87693+d e f g /Y -7576-A )5>’?<’@A ’3@)5G 1-1H C 87S )S -5-12-A ;7(’517:=872’-@1)@(@<A 5’-A )A -(1!;$/Z ’E \78&H U ),S 8-(6’I @-J ’81-2GC 8’11+K L L #/!V D $I &-G ),)Z +%,)-./C )8)55’5,<52-=5’)5-6@,’@21)@(29’-8-,=5’,’@2)2-7@7@U ;D !T $/F ’@7,’%@:78,)2-A 1K L L V +M H K N V O K N #/!V a $>35<8<+Z 0<2),<8)+c ;’98728)/Y -7576-A )51’?<’@A ’A 7,=)8-17@<1-@6=8’:-^A 7,=<2)2-7@1!B $/C 87A K V 29%R R R%@2’8@)2-7@)5C )8)55’5C 87A ’11-@6>G ,=71-<,+X 7135),-271+U )5-:78@-)H %R R RU 7,=<2’8>7A -’2GC 8’11+K L L L +a D V O a D L /!V b $;C Y ’86’8+C T;<@17@/3Z 7J ’58)@(7,-h ’(5-2’8)2-J ’128)2’6G:78)5-6@-@6,<52-=5’=872’-@1’?<’@A ’1!T$+U 7,=<23==5Y -71A -+K L L K +M b L O M #M /!V #$;%19-&)E )+;.719-()+;.-871)E )+d e f g /;<52-=5’1’?<’@A ’)5-6@,’@2S G=)8)55’51-,<5)2’()@@’)5-@6!T$/U 7,=<23==5Y -71-A -+K L L "H"a b O "b V /!V L $*-’@6c \+C ’2’8T ;+[=9-80+d e f g /C )8)55’5,<52-=5’1’?<’@A ’)5-6@,’@2<1-@61=’A <5)2-J ’A 7,=<2)2-7@!B $/C 87A7:29’K L L D %@2’8@)2-7@)5U 7@:’8’@A ’7@C )8)55’5C 87A ’11-@6/Y 7A )Q )27@H U Q UC 8’11+K L L D +V Ha N O a b /!M N $\)1<19-*+\<2)&)3+c ’@2)87[+d e f g /R ,=57G -@634)5678-29,-@=)8)55’5,<52-=5’=872’-@1’?<’@A ’)5-6@,’@2!T $/%C >T >%F Z 72’1+L b O ;C >O K a O M +K L L b +K L O "M /!M K $Z 6<G ’@.]+\719-9)8)%+\),),78-c +d e f g /3=)8)55’59G S 8-(6’@’2-A)5678-29,:78,<52-=5’=872’-@1’?<’@A ’)5-6@,’@2H R J 75<2-7@)8GA 7,=<2)2-7@!B $/C 87A /7:29’"N N "U 7@68’117@U R U +X 7135),-271+U )5-:78@-)H %R R R U 7,=<2’8>7A -’2GC 8’11+"N N "+K H V N L O V K M /!M "$钟诚+陈国良/C Q 3;和X 3Q C Y >模型上的近似串匹配并行算法!T$/软件学报+"N N M +K D _"‘H K D L WK a L /i j k l m n o n k j pq r s t k u o n r jv r u w o r n x y z x j q x k l o {j s x j |k l {r u o |}s nB .[Z F U 9’@6K+>[Z F Y -@"_K /U 755’6’7:U 7,=<2’8)@(R 5’A 287@-A 1)@(%@:78,)2-7@+F <)@6^-I @-J ’81-2G +Z )@@-@6+D V N N N M +U 9-@)~"/]’=2/7:U 7,=<2’8>A -’@A ’)@(*’A 9@7576G +I @-J /7:>A -/)@(*’A 9/7:U 9-@)+.’:’-+"V N N "b +U 9-@)‘i w n |u k q |H >’?<’@A ’)5-6@,’@2-1)@-,=782)@27=’8)2-7@-@Y -7-@:78,)2-A 1/%29)1S ’’@<1’(1<A A ’11:<55G27=8’(-A 229’:<@A 2-7@+128<A 2<8’+)@(’J 75<2-7@7:S -7576-A )51’?<’@A ’1/%@29-1=)=’8+17,’:<@(),’@2)5)5678-29,1:78=)-8E -1’1’?<’@A ’)5-6@,’@2)8’-@287(<A ’(+29’,<52-=5’)5-6@,’@2,7(’51)@(,)-@&-@(17:,<52-=5’)5-6@,’@2)5678-29,1)8’)@)5G h ’()@(A 7,=)8’(+)@(29’=)8)55’5)5678-29,1:78S -71’?<’@A ’)5-6@,’@2)8’1<,,)8-h ’(/0-@)55G +17,’7=’@=87S 5’,1)8’6-J ’@/!x m "r u p n H S -7-@:78,)2-A 1~=)-8E -1’1’?<’@A ’)5-6@,’@2~,<52-=5’1’?<’@A ’)5-6@,’@2~’^)A 2)5678-29,1~)==87^-,)2-7@)5678-29,1~9’<8-12-A )==87)A 9’1_责任编辑刘海涛‘K""第V 期钟诚等H 生物序列比对算法分析与比较万方数据。
