多重序列比对

第三章序列比较

3.3 序列多重比对

与序列两两比对不一样，序列多重比对（Multiple Alignment）的目标是发现多条序列的共性。如果说序列两两比对主要用于建立两条序列的同源关系和推测它们的结构、功能，那么，同时比对一组序列对于研究分子结构、功能及进化关系更为有用。例如，某些在生物学上有重要意义的相似性只能通过将多个序列对比排列起来才能识别。同样，只有在多序列比对之后，才能发现与结构域或功能相关的保守序列片段。对于一系列同源蛋白质，人们希望研究隐含在蛋白质序列中的系统发育的关系，以便更好地理解这些蛋白质的进化。在实际研究中，生物学家并不是仅仅分析单个蛋白质，而是更着重于研究蛋白质之间的关系，研究一个家族中的相关蛋白质，研究相关蛋白质序列中的保守区域，进而分析蛋白质的结构和功能。序列两两比对往往不能满足这样的需要，难以发现多个序列的共性，必须同时比对多条同源序列。

图3.14是从多条免疫球蛋白序列中提取的8个片段的多重比对。这8个片段的多重比对揭示了保守的残基（一个是来自于二硫桥的半胱氨酸，另一个是色氨酸）、保守区域（特别是前4个片段末端的Q-PG）和其他更复杂的模式，如1位和3位的疏水残基。实际上，多重序列比对在蛋白质结构的预测中非常有用。

多重比对也能用来推测各个序列的进化历史。从图3.14可以看出，前4条序列与后4条序列可能是从两个不同祖先演化而来，而这两个祖先又是由一个最原始的祖先演化得到。实际上，其中的4个片段是从免疫球蛋白的可变区域取出的，而另4个片段则从免疫球蛋白的恒定区域取出。当然，如果要详细研究进化关系，还必须取更长的序列进行比对分析。

对于多重序列比对的定义，实际上是两个序列的推广。设有k个序列s1, s2, ... ,s k，每个序列由同一个字母表中的字符组成，k大于2；通过插入操作，使得各序列s1, s2, ... ,s k的长度一样，从而形成这些序列的多重比对。如果将各序列在垂直方向排列起来，则可以根据每一列观察各序列中字符的对应关系，如图3.14。

通过序列的多重比对，可以得到一个序列家族的序列特征。当给定一个新序列时，根据序列特征，可以判断这个序列是否属于该家族。对于多序列比对，现有的大多数算法都基于渐进比对的思想，在序列两两比对的基础上逐步优化多序列比对的结果。进行多序列比对后，可以对比对结果进行进一步处理，例如构建序列的特征模式，将序列聚类，构建分子进化树等。

3.3.1 SP模型

SP 模型（Sum-of-Pairs，逐对加和）是一种多重序列比对的评价模型。在多重比对中，首先要对所得到的比对进行评价，以确定其优劣。例如，对图3.14中的8条序列进行比对，可以得到另外两种结果，如图3.15所示。那么，这样的三个多重比对，哪一个更好呢？这就需要有一种方法来评价一个多重比对。

评价一个多重序列比对比评价序列两两比对结果更复杂。这里，我们假设得分（代价）函数具有加和性，即多重比对的得分是各列得分总和。那么，我们首先考虑如何给比对的每一列打分，然后将各列的和加起来，成为一个总得分。

在处理每一列时，自然的处理方式是寻找一个具有k个变量的打分函数（k是参与多重比对的序列的个数），而每一个变量或者是一个来自特定字母表中的字符，或者是一个空位。我们很难得到这样一种具有k个变量的表达式函数。另一方面，这种隐式函数不具有统一的形式，随着k的变化，函数的表现形式也发生变化，不利于计算机处理。可以考虑使用显式函数，在具体实现显式函数时，用一个k维数组来表示该显式函数（类似于打分矩阵），指定对应于k个变量各种组合的函数值。这带来一个新问题，即所需的数组空间很大，而且随着k的变化，数据结构也要随之动态变化。

我们所期望的函数在形式上应该简单，具有统一的形式，不随序列的个数而发生形式变化。根据得分函数的意义，函数值应独立于各参数的顺序，即与待比较的序列先后次序无关。另外，对相同的或相似字符的比对，奖励的得分值高，而对于不相关的字符比对或空白，则进行惩罚（得分为负值）。满足上述条件的一个函数就是常用的逐对加和SP函数。SP函数定义为一列中所有字符对得分之和：

(3-34)

其中，c1,c2,…,ck是一列中的k个字符，p是关于一对字符相似性的打分函数。对于p可采用不同的定义。下面一个是SP函数计算例子。

总得分根据字符两两比较得分计算演化而来，即逐对计算p(1,2)，p (1,3)，...，p (1,8)，p (2,3)，p(2,4)，...，p (2,8)，...，p (7,8) 的所有得分，再加和得到结果。在上述计算中，我们假定：如果两个对比的字符相同，则得分为0，否则，得分为-1。所以，上述一列的得分为：（-7-6-5-4-3-2-1）+2= -26。

将一个多重比对所有列的得分全部加起来，其和即为该多重序列比对的得分。

注意：在进行多重序列比对时，可能会出现两个空位字符的比对，因此需要扩充函数p的定义域，即增加p(-，-)的定义。通常的定义是：

p(- , -) =

0 （3-35）

这似乎有点意外，因为一般只要是遇到空位字符，其得分就应该是负的，所以两个空位字符的比对应得到更多的负分。但是，这样处理是有道理的。在序列多重比对中，我们往往在得到整体比对的基础上进一步分析两条序列的对应关系。例如，根据图3.14的比对结果，取出最后两条比对的序列，见图3.16（a）。这里存在空位字符对比的列，相当于这两条序列都进行了插入操作。但是由于插入位置相同[如图3.16（a）箭头所指位置]，这两条序列本身在此位置上是完全相同的，所以，此位置上的编辑代价为零，或者得分为0。因而在分析这两条序列时，可以去掉这些空位字符对比的列，得到由多重序列比对结果推演的序列两两比对，如图3.16（b）所示。其结果又称为多重序列比对在两条特定序列上的投影（projection）。

若先处理每一个序列对，而在处理序列对时，逐个计算字符对，最后加和，则SP得分模型的计算公式如下：

(3-36)

其中，α是一个多重比对，αi,j是由α推演出来的序列s i和s j的两两比对。

具体计算SP时，我们可以先对多重序列比对a的每一列进行计算，然后将每一列的得分值相加；也可以先计算每一对推演出来的两两序列比对的得分，然后再加和。但是注意，上述两种计算过程仅在p(- , -)=0这一条件成立下才等价。

3.3.2 多重比对的动态规划算法

多重序列比对的最终目标是通过处理得到一个得分最高（或代价最小）的序列对比排列，从而分析各序列之间的相似性和差异。如同处理序列两两比对一样，依然可以用动态规划算法。

回想前一节中穿越得分矩阵的路径（见图3.9）。得分矩阵相当于二维平面，而对于三条序列，每一种可能的比对可类似地用三维晶格中的一条路径表示，而每一维对应于一条序列，如图3.17所示。路径的起点为晶格的左下角，路径的终点为晶格的右上后角。图3.17中的路径记为(0,0,0)，(1,0,0)，(2,1,0)，(3,2,0)，(3,3,1)，(4,3,2)。如果存在多条序列，则形成的空间是超晶格（Hyperlattice）。

假设在三维晶格的顶端、前面、后面各有一平行光源，这些光源将代表多重序列比对的路径投影到相对的侧面，即投影到一对序列所在的平面（图3.17仅画出了右边的光源）。将多重比对投影到两个序列所在的平面在加速优化计算中将起着重要的作用。

一个多重序列比对投影的结果可能比原来要短，例如，下面的多重序列比对

G---SNS

GN----S

GNAVSNS

如果在前两条序列方向进行投影，则投影结果为：

G-SNS

GN--S

如果路径的某一段沿投影方向进行，那么该段路径就不可能产生投影。图3.17中的第一段沿着第一条序列向前进，推进方向垂直于其他两条序列，则平行光源对这一段不产生直线投影，而仅仅产生一个投影点。

图3.17三条序列所对应的三维晶格

序列两两比对的动态规划算法经改进后可直接用于序列的多重比对。就二重序列而言，将动态规划算法的计算过程看成是在二维平面上按一定顺序访问每一个节点，访问节点的先后顺序取决于节点之间的关系，如图3.7所示。二维平面（或二维晶格）与前面所介绍的超晶格相似，上一节得分矩阵中的位置与每一个晶格节点相对应。在计算过程中，对每个节点逐一计算其得分（或代价）。每个节点的得分代表两个序列前缀的最优比对的得分，而晶格最后一个节点（右下角节点）的得分即为两条完整序列的比对得分。

在超晶格中，序列的放置与上一节有所不同，计算是从左下角进行的，而不是得分矩阵中的左上角。如图3.18所示，计算过程从超晶格的坐标点（0,0,…,0）开始，按节点之间的依赖关系向右上后方推进，直到计算完最后一个节点。实际计算时，可以采用类似二维的计算方式，即先低维后高维（对应于先行后列）。在图3.18中，当前点的得分计算取决于与它相邻的7条边，分别对应于匹配、替换或引入空位等三种编辑操作。计算各操作的得分（包括前趋节点的得分），选择一个得分最大的操作，并将得分和存放于该节点。在三维或超晶格中，计算公式与上一节相似，但计算一个节点依赖于更多的前趋节点。在三维情况下要考虑7个前趋节点，在k

维情况下要考虑2k-1个前趋节点。

假设以k维数组A存放超晶格，则计算过程如下：

①a[ 0, 0, … ,0 ] = 0

② a[ i ] = max {a[ i - b ] + SP-score[Column(s, i, b)]}

这里i是一个向量，代表当前点，b是具有k个元素的非零二进向量，代表i与前一个点的相对位置差（例如，在二维的情况下，b =（1，1）、（1，0）或（0，1）），s代表待比对的序列集合，而

其中，s j[i j]表示第j条序列在第i j位的字符，SP-score(Column(s, i, b))代表SP模型的得分值。计算过程是一个递推的过程，在计算每个晶格节点得分的时候，将其各前趋节点的值分别加上从前趋节点到当前点的SP得分，然后，取最大值作为当前节点的值。

随着待比对的序列数目增加，计算量和所要求的计算空间猛增。对于k条序列的比对，动态规划算法需要处理k维空间里的每一个节点，计算量自然与晶格中的节点数成正比，而节点数等于各序列长度的乘积。另外，计算每个节点依赖于其前趋节点的个数。在二维情况下，前趋节点个数等于3，三维等于7，四维等于15。对于k维超晶格，前趋节点的个数等于2k - 1。因此，用动态规划方法计算多重比对的时间复杂度为O(2k∏i=1,...,k∣s i∣)。这个计算量是巨大的，而动态规划算法对计算空间的要求也是很大的。

称一个问题在多项式时间内可解，当且仅当存在一个时间复杂度为O(n c)的求解算法，其中c是常数，n是问题的输入规模（如序列的长度、序列的个数）。例如前面介绍的序列两两比较动态规划算法的时间复杂度为O(n2)。假设有k个长度n的序列，则利用SP模型寻找最优多重序列比对算法的时间复杂度为O(2k n k)，这里k和n都是问题的规模。

可以证明，利用SP模型寻找最优多重序列比对是一个NP-完全问题。1971年，Cook给出NP-完全问题的定义。P类问题为多项式界的问题；而NP-完全问题是这样一类问题，如果其中的某个问题存在多项式界的算法，则NP类中的每一个问题都存在一个多项式界算法。NP-完全问题通常被认为是一些人们难以在有限的时间、空间内对问题求出最佳解的问题，几乎所有专家都认为不可能在多项式时间内准确求解NP-完全问题。到目前为止，已经证明属于NP-完全问题的达两千多个，这些问题同旅行售货员问题、有向图哈密顿回路等问题是一样难的，换句话说，要么大家都有多项式时间算法，要么都没有。目前，人们对NP-完全问题通常采用以下二种方法进行

求解：舍去寻找最优解的要求，寻找对一般问题比较接近最优解的近似解；利用非常规的求解技术求解，例如，利用神经网络、遗传算法等方法进行问题求解。

对于生物信息学的问题，有许多是NP-完全问题。在实际应用中，有一些变通的方法可以用来求解NP-完全问题。概括如下：（1）只求解规模比较小的问题；（2）利用动态规划、分支约束等技术减小搜索空间，提高求解问题的效率；（3）针对具体问题的特点，根据实际输入情况，设计实用求解算法，这样的算法虽然在最坏的情况下其时间复杂度是非多项式的，但是算法执行的平均效率和复杂度与多项式的算法相当；（4）采用近似算法或者启发式方法，如局部搜索、模拟退火、遗传算法等。

对基于SP模型寻找最优多重序列比对这样一个问题，可以用近似的方法求解，其算法的时间复杂度可用多项式表示。下面分别介绍几种实用的多重序列比对算法。

3.3.3 优化计算方法

如果待比对的序列很多，多重序列比对所形成的超晶格空间将会非常大，算法不可能访问所有的节点，而且也没有必要这样做。正如序列两两比对一样，可以想象代表最优的路径处于主对角线附近，至少不会在超晶格中的某个平面上。假设已知一个试探性的路径与最优的路径靠近，并且两条路径最多相距r个单位，则应当将动态规划算法所要计算的节点限制在以试探性路径为中心、半径为r的区域内，这样做无疑可以提高算法的效率。

我们不能盲目地搜索整个空间，应该利用人工智能空间搜索策略的剪枝技术，根据问题本身的特殊性将搜索空间限定在一个较小的区域范围内。若问题是搜索一条得分最高（或代价最小）的路径，那么，在搜索时，如果当前路径的得分低于某个下限（或累积代价已经超过某个上限），则对当前路径进行剪枝，即不再搜索当前路径的后续空间。

在序列两两比对中, Fickett和Ukkonen设计了一种称为定界约束的方法来缩小搜索空间、减少计算量，其中得分矩阵的上界和下界可以预先确定或动态变化。为了在多维空间上使用动态规划算法，Carrillo和Lipman将这种思想引入到多重序列比对，即先进行初步的序列双重比对，以便限制进一步作多重序列全面比对所需要的多维空间，从而减少计算量。这样可以克服多序列的维数、空间以及运算量之间的矛盾。

这里介绍Carrillo-Lipman的优化计算方法，该算法是基于下述关系的，即多重序列比对与向两个序列投影之间的关系，也就是通过公式（3-36）将SP得分与序列两两比对的得分联系起来。

设k条序列s1, s2, ... ,s k的长度分别为n1, n2, ... , n k，按照SP得分模型计算这些序列的最优比对。依然采用动态规划方法，但并不计算超晶格空间中所有的节点，而是仅处理“相关”的节点。但是，哪些节点是相关的呢？这需要观察节点在两条序列所在平面上的投影。

假设α是关于k条序列s1, s2, ... ,s k的最优多重比对。注意：这并不意味着α向某两条序列的投影是这两条序列的最优比对。我们可以按下述方法测试超晶格空间中的一个节点是否为相关节点：从某个节点向任何两条序列所在的平面投影，如果该投影是这两条序列两两最优比对的一部分（前面一部分），则该节点是相关节点。

在说明具体的优化计算方法之前，先介绍一种计算两条序列经过特定断点的最优比对算法。设有两条序列s、t，已知它们的两个断点分别是i、j（即s和t分别在i和j处一分为二），则s、t对于经过特定断点（i、j）的最优比对可分为两个部分，一是对应于两条序列前缀0:s:i 与0:t:j的最优比对，另一个是对应于两条序列后缀i:s:m与j:t:n的最优比对, m、n分别为两条序列的长度。实际上，经过特定断点的最优比对是两个比对。为了得到特定断点的最优比对，用两个矩阵A和B，其值为：

a i,j = sim(0:s:i , 0:t:j)

b i,j = sim(i:s:m , j:t:n)

对于矩阵A的计算与标准算法一样，而对于矩阵B的计算则是反方向的，即先对B的最后一行和最后一列进行初始化，然后反向推进到（0，0）。这样，矩阵A与B的和（A+B=C）包含了经过任意特定断点（i、j）的最优比对得分。我们称C矩阵为总得分矩阵，而A、B分别是前缀和后缀的得分矩阵。

根据矩阵C，我们可以迅速求出两个序列的最优比对，而不需要像上一节那样用反向跟踪的方法求出最优比对所对应的路径。图3.19列出了根据某个打分模型计算得到的矩阵A和C。可

以看出，根据C的最大值，可非常容易地找出最优比对所对应的路径。最优路径通过一系列断点，经过这一系列断点的所有最优比对得分值相同，实际上这个得分值就是两条序列比对的得分。换句话说，这些断点都处于最优路径上。

虽然最优多重比对的投影不一定是两两最优比对，但是我们可以为投影的得分设立一个下限。设α是关于s1, s2, ... ,s k的最优比对，如果SP-score(α) ≥ L，则可以证明

(3-39)

其中score(αi,j)是α在s i,和s j所在平面投影的得分，

(3-40)

这里，L实际上是最优多重比对的一个下限，而L i,j是序列s i和序列s j比对得分的一个下限。现在，需要判断超晶格中的一个节点i = (i1, i2, …, i k )是否在L的限制下与最优比对相关。

简单地说，如果一个节点满足(3-39)式的条件，则该节点是相关的；若条件不满足，即score(αi,j)小，则不可能是相关的，因此，i肯定不会处于最优路径上。当然，上述条件只是一个必要条件，但不是充分条件。满足条件只是说明i可能处于最优路径，但不一定处于最优路径。条件的作用是限制搜索空间，提高算法的实施效率。

将判断条件进一步具体化，则对于所有的1≤ x < y ≤ k，如果i满足

C x，y[i x, i y] ≥L x，y (3-41)

则i是相关的。这里，C x，y是序列s x和s y的总得分矩阵，C x，y[i x, i y]表示在点[i x, i y]处的值。这个具体的条件是根据前面的叙述推演出来的。假设最优比对α所对应的路径通过节点（i1,

i2,…,i x, .., i y,…,i k），则C x，y[i x, i y] ≥score(αi,j)≥L x，y。因此，如果C x，y[i x, i y]

为了得到一个合理的下限L，我们可以任选一个包含所有序列的多重比对，计算该多重比对的得分，以此作为L。若选取的L接近于最优值，算法速度将大大提高。注意：L的值不能超过最优值，否则算法出错。

在实现上述优化计算方法时，必须非常仔细。不可能对超晶格中的每一个节点都进行上述判断，否则，算法的计算时间不会有多大的减少。因此，我们需要一种剪枝方法，它一次能够将许多不相关节点删除。

从超晶格的零点0= (0, 0, … , 0) 出发，此节点总是相关的。逐步扩展节点，直到终点(n1, …, n k)。在扩展过程中，仅分析相关节点。以数组a[]保存各节点的计算结果。称一个节点i影响另一个节点j，如果在计算a[j]时用到i。这又称为j依赖于i，每一个节点依赖于其它2 k-1个节点。为了便于处理，设置一个缓冲区，该缓冲区内仅存放相关节点的后续节点。首先将0放入其中。当一个节点i进入缓冲区时，其对应的值a[i]被初始化，然后a[i]的值在随后的阶段中被更新。当该节点离开缓冲区时，其值即为该点真正的值，并用于其他节点（依赖于此节点）的计算。当然，其后续节点是否要计算，还取决于i是否为相关节点，若不是，则不再计算其后续的其他节点。

具体的过程如下：设j是一个依赖于i的相关节点，如果j不在缓冲区内，则将其放入缓冲区，并计算

a[j] ← a[i] + SP-score(Column(s,i,b))

如果早已在缓冲区中，则按下式更新

a[j] ← max(a[j], a[i] + SP-score(Column(s,i,b)))

Carrilo-Lipman算法要求待比较的多个序列具有较大的相似性，并且序列数不能太多。幸运的是，在实际工作中，许多生物分子序列的比较满足这两个条件。

3.3.4 星形比对

如果采用标准的动态规划算法计算最优的多重序列比对，会需要很长的时间，即使采用前面所介绍的方法，也一样需要大量的时间。所以，必须考虑其他的方法，首选的就是所谓启发式方法。启发式方法不一定保证最终能得到最优解，但在大多数情况下，其计算结果接近于最优结果；并且，重要的一点是，这类方法能够大大减少所需的计算时间，加快计算速度。目前所用的算法大部分将序列多重比对转化为序列两两比对，逐渐将两两比对组合起来，最终形成完整的多序列比对。这种方式又称为渐进法。可以按照星形结构或者树形结构组合两两序列比对。

星形比对是一种启发式方法，首先由Gusfield 提出。星形比对的基本思想是：在给定的若干条序列中，选择一个核心序列，通过该序列与其他序列的两两比对，形成所有序列的多重比对α，从而使得α在核心序列和任何一个其他序列方向的投影是最优的两两比对。

设s1, s2, ... ,s k是k条待比对的序列（暂时不考虑如何选择核心序列）。假设已知核心序列是s c，c介于1到k之间，则可以利用标准的动态规划算法求出所有s i和s c的最优两两比对。这个工作需要时间为O（kn2）（假设所有序列的长度为n）。将这些序列的两两比对聚集起来，并采用“只要是空位，则永远是空位”的原则。聚集过程从某一个两两比对开始，如s1和s c，然后逐步加上其他的两两比对。在这个过程中，逐步增加s c中的空位字符，以适应其他的比对，但决不删除s c中已存在的空位字符。假设在上述过程中的某一时刻，有一个由s c指导的、已经建立好的部分序列的多重比对，接下来就是加入一个新的、与s c两两比对的序列，如果需要，

则插入新的空位字符。这个过程一直进行到所有的两两比对都加入以后结束，所需的计算量为O(k2n)。因此，算法总的时间复杂度为O(kn2+k2n)。

那么，如何选择核心序列呢？一种方法就是尝试将每一个序列分别作为核心序列，按上述过程进行，取结果最好的一个。另一种方法是计算所有的两两比对，取下式值最大的一个：

(3-42)

例如，有5个序列，

s1 = ATTGCCATT

s2 = ATGGCCATT

s3 = ATCCAATTTT

s4 = ATCTTCTT

s5 = ACTGACC

根据它们之间的相似性度量建立如图3.20所示的表格，得分函数见公式（3-2）。从表格中可以看出，选s c=s1时，式（3-42）取最大值。接下来，计算s1与其他序列的最优两两比对。假设得到下述各两两比对：

ATTGCCATT ATTGCCATT-- ATTGCCATT ATTGCCATT

ATGGCCATT ATC-CAATTTT ATCTTC-TT ACTGACC--

图3.20 两两比对的得分

在这个例子中，核心序列s1中的空位字符是由于s3序列在末端引入的两个空位字符。最后多重序列比对的结果如下：

ATTGCCATT--

ATGGCCATT--

ATC-CAATTTT

ATCTTC-TT--

ACTGACC----

星形比对是一种多重序列比对近似的方法，然而是一种比较好的近似方法。如果用代价来评判来多重序列的比对结果，则可以证明，用该方法所得到的多重序列比对的代价不会大于最优多重序列比对代价的两倍。

3.3.5 树形比对

假设有k条待比对的序列，同时有一棵具有k个叶节点的树，其中每个叶节点对应一条序列。如果将序列也赋予树的内部节点，则可以计算树中每个分支的权值。权值代表对应分支连接的两条序列之间的相似度。所有权值的和就是这棵树（对应于将序列赋予内部节点的特定方式）的得分。树形比对的问题就是寻找一种树的内部节点序列赋予方式，使得树的得分最大。星形比对可以认为是树形比对的一种特例。

例如，图3.21中有4条简单序列，将CT、CG、CT分别赋予节点x、y、z，则树的得分为8。这里，假设a=b时，p(a,b)=1，否则p(a,b)=0，p(a,-)= p(-，b)= -1。

树形比对问题实际上是组合问题，是一个NP完全问题，算法的复杂度是指数函数。在进行树形比对时一般采用启发式方法，以距离代替权值，而不是用相似度。

在将多重序列比对分解为两两序列比对的过程中，需要有一个算法合并两个比对, 即比对的比对算法（Alignment of alignments, AA）。

假设有两个多重序列比对α1和α2，α1代表序列s1,s2,…,s i的多重比对，α2代表序列

t1,t2,…,t j的多重比对，并且（s1，s2，…，s i）?（t1，t2，…，t j）=φ，α代表s1和t1的两两比对，则计算与α相一致的α1和α2比对的算法如下：

①标定α1的各列，如果s1在比对中对应位置的编辑操作不是插入或删除，则这些列分别标记为

s1对应位置上的字符a1,a2,…,a ls1（ls1为序列s1的长度）；

②标定α2的各列，如果t1在比对中对应的位置编辑操作不是插入或删除，则这些列分别标记为

t1对应位置上的字符b1,b2,…,b l2（lt1为序列t1的长度）；

③对a1,a2,…,a l1和b1,b2,…,b l2进行比对；

④在所得到的比对中，对于α1、α2和α中原来有插入或删除操作的位置，恢复其原有的实际字

符或空位字符“-”。

例：

α1：s1 -H-LVV α2：t1 L-HCLV α：s1 -H-LVV s2 G-VLVC t2 VLHCL- t1 LHCLV-

s3 GN-LVV

AA算法的输出为

--H--LVV

-G--VLVG

-GN--LVV

L-HC-LV-

V-HC-L--

分别对第1、2列和4、5列进行压缩，则最后结果为

-H—LVV

G—VLVG

GN—LVV

LHCLV-

VHCL--

对于n条序列的进行树形比对的一种最直接算法的计算过程如下：

①初始化，对于每条序列，生成一个叶节点；

②利用AA算法合并两个节点，形成一个新节点，合并的结果放在新节点中，原来的两个节点作

为新节点的子节点；

③反复执行②，直到形成n个叶节点的树根为止，根节点中的序列即为最终的多重比对结果。

与两个序列的比较一样，对于多重序列比较，也需要进行显著性的检验，以判断一个多重序列的比对是否具有真正的意义。实际上，任何一个序列比较过程都应该包含两个步骤，即序列比对和显著性检查。

3.3.6 其他多重序列比对算法

在多重序列近似比对算法方面，除渐进方法之外，还有许多其他方法，如用遗传算法、模拟退火算法、隐马尔柯夫模型等解决序列的多重比对问题。多重序列比对程序有ClustalW、MAP、MSA、PILEUP等，这些程序用于进行全局比对。可进行局部比对的程序有PIMA、Block Maker、MEME、MACAW、SAM等，另一个程序是Dialign，该程序注重于寻找多条序列中相似的区域。

目前，使用最广泛的多重序列比对程序是ClustalW。ClustalW是一种渐进的比对方法，先将多个序列进行两两比对，基于这些比较，计算得到一个距离矩阵，该矩阵反映每对序列之间的

关系。根据距离矩阵计算产生系统发生树，从最紧密的两条序列开始，逐步引入邻近的序列，并不断重新构建比对，直到所有序列都被加入为止。

ClustalW的程序可以自由使用，在任何主要的计算机平台上都可以运行。在美国国家生物技术信息中心NCBI的FTP服务器上可以找到下载的软件包，在欧洲生物信息学研究所EBI的主页还提供了基于Web的ClustalW服务，用户可以把序列和各种要求通过表单提交到服务器上，服务器把计算的结果用Email返回给用户。EBI的ClustalW网址是：

https://www.doczj.com/doc/e95192447.html,/clustalw/。ClustalW对用户输入序列的格式和输出格式的选择比较灵活，可以是FASTA格式，也可以是其他格式。

例：

3.3.7 统计特征分析

对于所得到的多重序列比对，我们往往需要进行归纳分析，总结这些序列的特征，或者给出这些序列共性的表示。一种是保守序列表示方式，表示序列每个位置上最可能出现的字符（或者所有可能出现的字符）。另一种表示方式是所谓的特征统计图谱（profile）表示方式，或特征统计矩阵（matrix）表示方式。

给定一个长度为L的多重序列比对α，令P=(P1,P2,…,P L)，P表示在α的每一列上各种字符出现的概率分布。令P j=(p j,0,p j,1,…,p j,|A|)，A代表字母表，P j,k代表字母表A中第k个字符在第j列出现的概率。需要说明的是，第0个字符是特殊的空位符号“-”。称P为多重序列比对α的特征统计图谱，或特征统计矩阵，它反映α各个列的特征。

利用特征统计矩阵可以判断一个序列是否满足一定的特征。给定一个序列s=a1a2…a m，定义字符a在第j位的代价为

Clustalx 多重序列比对图解教程(图解使用)

Clustalx 多重序列比对图解教程(By Raindy) 本帖首发于Raindy'blog,转载请保留作者信息，谢谢！欢迎有写生物学软件专长的战友，加入生信教程写作群：，接头暗号：你所擅长的生物学软件名称 软件简介: CLUSTALX－是CLUSTAL多重序列比对程序的Windows版本。Clustal X为进行多重序列和轮廓比对和分析结果提供一个整体的环境。 序列将显示屏幕的窗口中。采用多色彩的模式可以在比对中加亮保守区的特征。窗口上面的下拉菜单可让你选择传统多重比对和轮廓比对需要的所有选项。 主要功能： 你可以剪切、粘贴序列以更改比对的顺序； 你可以选择序列子集进行比对； 你可以选择比对的子排列(Sub-range)进行重新比对并可插入到原始比对中； 可执行比对质量分析，低分值片段或异常残基将以高亮显示。 当前版本:1.83 PS:如果你是新手或喜欢中文界面,推荐使用本人汉化的Clustalx 1.81版链接地址::ist&ID=7435(请完整复制) 应用:Clustalx比对结果是构建系统发育树的前提 实例：植物呼肠孤病毒属外层衣壳蛋白P8(AA序列)为例 流程：载入序列―>编辑序列―>设置参数―>完全比对―>比对结果 1.载入序列：运行ClustalX，主界面窗口如下所图（图1），依次在程序上方的菜单栏选择“File”－“Load Sequence”载入待比对的序列，如图2所示，如果当前已载入序列，此时会提示是否替换现有序列(Replace existing sequences)，根据具体情形选择操作。

图1

图2 2.编辑序列：对标尺(Ruler)上方的序列进行编辑操作，主要有Cut sequences(剪切序列)、Paste sequences(粘贴)、Select All sequences(选定所有序列)，Clear sequence Selection(清除序列选定)、Search for string(搜索字串)、Remove All gaps(移除序列空位)、Remove Gap-Only Columns(仅移除选定序列的空位)

时间序列分析方法及应用7

青海民族大学 毕业论文 论文题目：时间序列分析方法及应用—以青海省GDP 增长为例研究 学生姓名：学号： 指导教师：职称： 院系：数学与统计学院 专业班级：统计学 二○一五年月日

时间序列分析方法及应用——以青海省GDP增长为例研究 摘要: 人们的一切活动，其根本目的无不在于认识和改造世界，让自己的生活过得更理想。时间序列是指同一空间、不同时间点上某一现象的相同统计指标的不同数值，按时间先后顺序形成的一组动态序列。时间序列分析则是指通过时间序列的历史数据，揭示现象随时间变化的规律，并基于这种规律，对未来此现象做较为有效的延伸及预测。时间序列分析不仅可以从数量上揭示某一现象的发展变化规律或从动态的角度刻画某一现象与其他现象之间的内在数量关系及其变化规律性，达到认识客观世界的目的。而且运用时间序列模型还可以预测和控制现象的未来行为，由于时间序列数据之间的相关关系（即历史数据对未来的发展有一定的影响），修正或重新设计系统以达到利用和改造客观的目的。从统计学的内容来看，统计所研究和处理的是一批有“实际背景”的数据，尽管数据的背景和类型各不相同，但从数据的形成来看，无非是横截面数据和纵截面数据两类。本论文主要研究纵截面数据，它反映的是现象以及现象之间的关系发展变化规律性。在取得一组观测数据之后，首先要判断它的平稳性，通过平稳性检验，可以把时间序列分为平稳序列和非平稳序列两大类。主要采用的统计方法是时间序列分析，主要运用的数学软件为Eviews软件。大学四年在青海省上学，基于此，对青海省的GDP十分关注。本论文关于对1978年到2014年以来的中国的青海省GDP（总共37个数据）进行时间序列分析，并且对未来的三年中国的青海省GDP进行较为有效的预测。希望对青海省的发展有所贡献。 关键词: 青海省GDP 时间序列白噪声预测

人类短串联重复序列

人类短串联重复序列(STR)的研究进展 短串联重复序列( Short tandem repeat ,STR)又称微卫星DNA， STR 是一种可遗传的不稳定的并且具有高度多态性的短的核苷酸重复序列. STR 多态性具有种类多,分布广,高度多态性等特点,并按孟德尔遗传规律[ 1 ]在人群中世代相传. 通过对STR 多态性的认识,极大地推动了人类基因组的研究. 这种多态性标志已广泛用于构建人类遗传连锁图谱、基因定位、遗传病诊断、肿瘤细胞染色体分离与重组以及亲子鉴定等法医学检查. DNA遗传标记的多态性研究发展按时间顺序可分为三代[4 ]。第1代遗传标记:限制性片段长度多态性( restriction fragment length polymorphism, RFLP)是Wyman 和White 于1980年偶然发现的,人类14号染色体上存在DNA片段长度有变化的区域,这些区域的结构特点是DNA由一段序列串联重复、首尾相接而成。重复次数可在几次至数百上千次之间变化。DNA重复单位长度在数bp至数十bp之间,组成串联重复的DNA是小卫星DNA。第2代遗传标记:短串联重复序列是由Holly等发现的重复单位的长度只有2～6 bp、重复次数一般在数次至几十次之间的串联重复DNA 序列,即微卫星DNA。微卫星DNA的等位基因片段的长度一般在400 bp 以下,故又称为短串联重复序列( STR)。第3代遗传标记:单核甘酸多态性( single nucleotide polymorphism, SNP)是单个碱基的置换、插入或缺失而形成的,是美国MIT提出的新一代多态性标记系统[5],近年来成为多种研究的焦点。虽然SNP的多态性位点是最多的,能比STR提供更全面的基因信息,但是STR还是以其独特的优点保存下来,仍被广泛的研究。 1.1 STR 的构成 STR 的核心序列为2～7bp ,呈串联重复排列.重复次数10～60 次左右,其总长度常小于400 bp.常见的有一、二、三、四核苷酸重复序列,约占真核生物基因组的5 %. 人类基因组的STR 单核苷酸重复以polyA ,polyT 多见,双核苷酸重复以(CA) n ,( GT) n , (AA) n , ( GG) n 常见, ( GC/ CG) 少见,其原因是由于3′端为G的C(即CPG) 易于甲基化. 三核苷酸重复以(CXG) n 类型常见,由于三核苷酸具有高度多态性,常用作DNA 的标记物. 每个特定位点的STR 均由两部分构成:中间的核心区和外围的侧翼区. 核心区含有一个以上称为“重复”的短序列,一般该重复单位的碱基对数目不变,而串联在一起的重复单位数目是随机改变的,如果用一种不切重复单位的限制性内切酶把DNA 分子切割成限制性片段,该限制性片段中位于核心区的外围即是侧翼区. 人群中不同个体可表现为侧翼区相同而串联重复单位的数目不同;也可为相同数目的重复单位,但侧翼区大小不同,或

多序列比对软件Clustalw使用方法

多序列比对软件Clustalw使用方法2011年06月23日星期四 16:44 Clustal的基本思想是基于相似序列通常具有进化相关性这一假设。比对过程中，先对所有的序列进行两两比对并计算它们的相似性分数值，然后根据相似性分数值将它们分成若干组，并在每组之间进行比对，计算相似性分数值。根据相似性分数值继续分组比对，直到得到最终比对结果。比对过程中，相似性程度较高的序列先进行比对，而距离较远的序列添加在后面。作为程序的一部分，Clusal可以输出用于构建进化树的数据。 Clustal程序有许多版本，ClustalW(Thompson等，1994)，根据对亲缘关系较近的序列间空位情况，确定如何在亲缘关系较远的序列之间插入空位。同样，相似性较高的序列比对结果中的残基突变信息，可用于改变某个特殊位置空位罚分值的大小，推测该位点的序列变异性。ClustalW是一种渐进的多序列比对方法，先将多个序列两两比对构建距离矩阵，反应序列之间两两关系;然后根据距离矩阵计算产生系统进化指导树，对关系密切的序列进行加权;然后从最紧密的两条序列开始，逐步引入临近的序列并不断重新构建比对，直到所有序列都被加入为止。 ClustalX是CLUSTAL多重序列比对程序的Windows版本。Clustal X为进行多重序列和轮廓比对和分析结果提供一个整体的环境。 软件下载地址: 使用步骤如下: Step 1: 软件初始化界面

Step 2:选择1 进入如下界面 Step 3:输入序列名1Seq_650_300.txt.txt 进入如下界面

Step 4:选择2 进入如下界面 Step 5:选择9 进入如下界面 Step 6:选择1 进入如下界面

实验2 序列比对

实验二：两条序列比对与多序列比对 实验目的： 学会使用MegAlign，ClustalX和MUSCLE进行两条序列和多条序列比对分析。 实验内容： 双序列比对是使两条序列产生最高相似性得分的序列排列方式和空格插入方式。两条序列比对是生物信息学最基础的研究手段。 多序列比对是将多条序列同时比对，使尽可能多的相同（或相似）字符出现在同一列中。多序列比对的目标是发现多条序列的共性。如果说序列两两比对主要用于建立两条序列的同源关系，从而推测它们的结构和功能，那么，同时比对多条序列对于研究分子结构、功能及进化关系更为有用。多序列比对对于系统发育分析、蛋白质家族成员鉴定、蛋白质结构预测、保守模块的搜寻等具有非常重要的作用。我们这节课主要学习多条序列比对的软件-ClustalX, MUSCLE。 一、MegAlign 用dotplot方法能够直观地认识两条序列比对，但是dotplot仅仅是展示了两条序列中所有可能的配对，并不是真正意义上的序列比对。这里介绍由DNASTAR公司开发的一个比较全面的生物信息学软件包--Lasergene，它包含了7个模块，其中MegAlign可进行两条或多条序列比对分析。 1. 两条序列比对 1.1 安装程序 解压DNASTAR Lasergene软件压缩包，双击Lasergene710WinInstall.exe文件，按照默认路径安装软件到自己电脑上。 1.2 载入序列 a.点击开始－程序－Lasergene－MegAlign，打开软件。 我们首先用演示序列（demo sequence）学习软件的使用。演示序列所在位置：C:\Program files\ DNASTAR\ Lasergene\ Demo Megalign\ Histone Sequences\。 b. 点击主菜单File—Enter sequence－选择序列所在文件夹，选择序列tethis21.seq和tethis22.seq，点击Add，这两条序列将出现在右侧selected sequences框中（Figure 2.3），选择完毕点击Done回到程序页面。 Figure 2.3 载入序列

功能基因的序列比对方法

功能基因的序列比对 <1>.切除载体和(或)引物 a.打开所有的原始引物序列于一个EditSeq的窗口中 b. export all as one c.保存 d.打开这个保存的文件，开始切除载体和引物 e.选择载体插入点两侧的序列(10-15个的样子)搜索注意：不存在正反向的问题，都是一个

方向，因为测序的时候是选择两个载体上的引物其中的一条来往后测序的！ 切完之后另存为 f. 重新打开这个文件，开始切除引物 方法同切载体，但是要注意正反向的问题。比如mcrA基因，其引物为Forward: 5'-GGTGGTGTMGGATTCACACARTAYGCWACAGC-3' Reverse: 5'-TTCATTGCRTAGTTWGGRTAGTT-3'

先找Forward 5’端，此时只找到的部分序列。切去5’端。 然后再切这些切掉5’端序列的3’端的序列，此时其3’端序列应该是Reverse 的反向互补序列。 切去这个反向互补序列，这样一来这个些序列就已经被切去两端的引物了。 但此时还剩下另一部分未切除任何引物的序列，此时记下这些序列的编号，先切去Reverse 5’

端。 再用Forward 的反向互补序列切去3’端，这样剩下的序列也都被切除两端的引物了。 <2>将所有序列调整为同向序列： a. 选择前面记录编号的序列，将这些序列一个个都转换为其反向互补序列。这样一来所有的序列都成为同向序列了，即在DNA两条反向互补链的其中一条上的比较了。

b. 保存该文件 <3> 生成OTUs Google 搜索”Fastgroup II” 或https://www.doczj.com/doc/e95192447.html,/fg_tools.htm

重复序列分析文档

1 重复序列分析 重复序列广泛存在于真核生物基因组中，这些重复序列或集中成簇，或分散在基因之间，根据分布把重复序列分为分散重复序列和串联重复序列。 分散重复序列分为四种：LTR、LINE、SINE、和DNA转座子、 LTR，长末端重复转座子（long terminal repeat），是由RNA反转录而成的元件，它在两端有长大数百碱基对的LTR。Length： 1.5-10kbp Encode reverse transcriptase Flanked by 300-1000bps terminal repeats LINE，长散在重复序列（long interspersed nuclear elements），意为散在分布的长细胞核因子，是散在分布在哺乳动物基因组中的一类重复，这种重复序列比较长，平均长度大于1000bp，平均间隔3500-5000bp，如：rRNA，tRNA基因，形成基因家族。 SINE 为短散在重复序列（short interspersed nuclear elements）。SINE是非自主转座的反转录转座子，来源于RNA聚合酶III的转录物，它的平均长度约为300bp，平均间隔1000bp，如：Alu家族，Hinf家族序列。 DNA 转座子: single intron-less open reading frame Encode transposase Two short inverted repeat sequences flanking the reading frame。 串联重复序列根据重复序列的重复单位的长度可分为卫星DNA、小卫星DNA 和微卫星DNA。微卫星DNA又称为串联重复序列（short Tandem Repeat. STR） ●Simple Sequence Repeats (SSR)+Satellites GGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG (G) ATATATATATATATATATATATATATATATATATATAT (AT)n

序列比对及建树步骤

序列比对及建树步骤 1.以细菌、病毒或寄生虫为例，参考分类生物学资料，从GenBank中查询相关序列，详述Blast寻找、CLUSTAL比对、建树及种系发育过程 以隐孢子虫actin基因为例做一叙述： 1.1 Blast: 登录NCBI主页，打开Blast搜索引擎，将测得的一个已知的actin序列输入，下 载了12条隐孢子虫序列，另外下载一条恶性疟原虫actin序列作为外群。所获得的14条序列改为FAST格式，用TXT文件保存。 1.2 cluxtal 比对 用软件clustalx1.83比对软件进行比对。

1.3 比对的精制 对比对结果可以进行一些简单的调整，删去目的序列比对效果最差的开头和结尾部分。可以用word文档打开比对所生成的aln.文件，在word文档下进行剪切。然后将剪切的文档再用ClustalX软件进行比对，并生成Phylip格式文件。

1.4 使用Phylip软件建树 以neighbour-jioning方法为例做一叙述。 1.4.1 先导树 将生成的PHY文件（*.phy）拷贝到Phylip软件包目录下，最好修改成比较简单的文件名，比如修改成1或a等（比较方便下边的输入运行）。运行DNADIST.EXE子软件，输入文件(比如1)，打回车后弹出软件界面，打D可以选择不同的模型，在此选用Kimura 2-parameter模型。生成的outfile文件可以再修改成简单的文件名，比如修改成2。打开neighbor.exe子程序，输入文件2，打回车后运行完毕会生成两个文件，将文件outtree另存为.tre文件格式，即为所生成的先导树。

时间序列分析——最经典的

【时间简“识”】 说明：本文摘自于经管之家(原人大经济论坛) 作者：胖胖小龟宝。原版请到经管之家(原人大经济论坛) 查看。 1.带你看看时间序列的简史 现在前面的话—— 时间序列作为一门统计学，经济学相结合的学科，在我们论坛，特别是五区计量经济学中是热门讨论话题。本月楼主推出新的系列专题——时间简“识”，旨在对时间序列方面进行知识扫盲（扫盲，仅仅扫盲而已……），同时也想借此吸引一些专业人士能够协助讨论和帮助大家解疑答惑。 在统计学的必修课里，时间序列估计是遭吐槽的重点科目了，其理论性强，虽然应用领域十分广泛，但往往在实际操作中会遇到很多“令人发指”的问题。所以本帖就从基础开始，为大家絮叨絮叨那些关于“时间”的故事！ Long long ago，有多long估计大概7000年前吧，古埃及人把尼罗河涨落的情况逐天记录下来，这一记录也就被我们称作所谓的时间序列。记录这个河流涨落有什么意义当时的人们并不是随手一记，而是对这个时间序列进行了长期的观察。结果，他们发现尼罗河的涨落非常有规律。掌握了尼罗河泛滥的规律，这帮助了古埃及对农耕和居所有了规划，使农业迅速发展，从而创建了埃及灿烂的史前文明。

好~~从上面那个故事我们看到了 1、时间序列的定义——按照时间的顺序把随机事件变化发展的过程记录下来就构成了一个时间序列。 2、时间序列分析的定义——对时间序列进行观察、研究，找寻它变化发展的规律，预测它将来的走势就是时间序列分析。 既然有了序列，那怎么拿来分析呢 时间序列分析方法分为描述性时序分析和统计时序分析。 1、描述性时序分析——通过直观的数据比较或绘图观测，寻找序列中蕴含的发展规律，这种分析方法就称为描述性时序分析 描述性时序分析方法具有操作简单、直观有效的特点，它通常是人们进行统计时序分析的第一步。 2、统计时序分析 （1）频域分析方法 原理：假设任何一种无趋势的时间序列都可以分解成若干不同频率的周期波动 发展过程： 1）早期的频域分析方法借助富里埃分析从频率的角度揭示时间序列的规律 2）后来借助了傅里叶变换，用正弦、余弦项之和来逼近某个函数 3）20世纪60年代，引入最大熵谱估计理论，进入现代谱分析阶段 特点：非常有用的动态数据分析方法，但是由于分析方法复杂，结果抽象，有一定的使用局限性 （2）时域分析方法

季节性时间序列分析方法

季节性时间序列分析方 法 LG GROUP system office room 【LGA16H-LGYY-LGUA8Q8-LGA162】

第七章季节性时间序列分析方法 由于季节性时间序列在经济生活中大量存在，故将季节时间序列从非平稳序列中抽出来，单独作为一章加以研究，具有较强的现实意义。本章共分四节：简单随机时间序列模型、乘积季节模型、季节型时间序列模型的建立、季节调整方法X-11程序。 本章的学习重点是季节模型的一般形式和建模。 §1 简单随机时序模型 在许多实际问题中，经济时间序列的变化包含很多明显的周期性规律。比如：建筑施工在冬季的月份当中将减少，旅游人数将在夏季达到高峰，等等，这种规律是由于季节性（seasonality）变化或周期性变化所引起的。对于这各时间数列我们可以说，变量同它上一年同一月（季度，周等）的值的关系可能比它同前一月的值的相关更密切。 一、季节性时间序列 1．含义：在一个序列中，若经过S个时间间隔后呈现出相似性，我们说该序列具有以S为周期的周期性特性。具有周期特性的序列就称为季节性时间序列，这里S为周期长度。 注：①在经济领域中，季节性的数据几乎无处不在，在许多场合，我们往往可以从直观的背景及物理变化规律得知季节性的周期，如季度数据（周期为4）、月度数据（周期为12）、周数据（周期为7）；②有的时间序列也可能包含长度不同的若干种周期，如客运量数据（S=12，S=7） 2．处理办法： （1）建立组合模型； （1）将原序列分解成S个子序列（Buys-Ballot 1847）

对于这样每一个子序列都可以给它拟合ARIMA 模型，同时认为各个序列之间是相互独立的。但是这种做法不可取，原因有二：（1）S 个子序列事实上并不相互独立，硬性划分这样的子序列不能反映序列{}t x 的总体特征；（2）子序列的划分要求原序列的样本足够大。 启发意义：如果把每一时刻的观察值与上年同期相应的观察值相减，是否能将原序列的周期性变化消除（ 或实现平稳化），在经济上，就是考查与前期相比的净增值，用数学语言来描述就是定义季节差分算子。 定义：季节差分可以表示为S t t t S t S t X X X B X W --=-=?=)1(。 二、 随机季节模型 1．含义：随机季节模型，是对季节性随机序列中不同周期的同一周期点之间的相关关系的一种拟合。 AR （1）：t t S t S t t e W B e W W =-?+=-)1(11??，可以还原为：t t S S e X B =?-)1(1?。 MA （1）：t S t S t t t e B W e e W )1(11θθ-=?-=-，可以还原为：t S t S e B X )1(1θ-=?。 2．形式：广而言之，季节型模型的ARMA 表达形式为 t S t S e B V W B U )()(= （1） 这里，?? ? ??----=----=?=qS q S S S pS P S S S t d S t B V B V B V B V B U B U B U B U X W 2212211)(1)()(平稳。 注：（1）残差t e 的内容；（2）残差t e 的性质。 §2 乘积季节模型 一、 乘积季节模型的一般形式 由于t e 不独立，不妨设),,(~m d n ARIMA e t ，则有

多重序列比对的数学模型与算法

多重序列比对的数学模型与算法 自美国提出组织的人类基因组计划（Human Genome Proreet）简称为HGP 以来，美国每年拔出相当大的经费支持，日本、法国、英国、德国等纷纷响应，它们的工作使新的交叉学科生物信息论得以诞生和发展，生物信息论是用数理和信息科学的观点、理论和方法去研究生命现象，组织和分析呈指数增长的生物学数据。生物信息学是一门综合学科，是计算机科学、数学、物理、生物学的结合。生物信息学的基础是各种数据库的建立和分析工具的发展。目前，生物学数据库已达500个以上，共有四大类：基因组数据库，核酸和蛋白质一级结构数据库、生物大分子三维空间结构数据库及其以她们为基础构建的二级数据库。生物信息学主要研究基因组测序及其信息分析、生物大分子的结构与功能预测及其模拟和药物设计、大规模基因表达数据的分析与基因芯片设计，以及基因与蛋白质相互作用网络等四方面的问题。 多重序列比对是计算分子生物学中最重要的运算。多重序列比对的基本问题就是找出适当安排删减与插入尽量少的空格，使得两个序列达到最大程度的一致的方案。比如给出下列三个序列： AC_G AGTCC (1) ACT 我们适当安排删减与插入空格得到： ACG___ A_GTCC (2) AC_T__ （2）就是多重序列的一个比对。 局部分段比对是其中更为常见的运算。上世纪80年代，Smith-Waterman提出了两个序列的局部比对的明确的模型。1998—1999年，相继出现利用k-tuple 的快速容错分段比对搜索法。2002年开始出现对完整基因组及其异常基因的比

较研究以及多重序列比对问题的研究，2003年刘军Mayetri Gupta和刘军得到Motif的搜索算法。 人类基因组计划后，目前已经进入后基因时代，主要就是对人类基因组计划实施得到的基本数据库进行信息分析、加工和利用，提取有用信息，用来研究生命现象中的重大问题。多重序列比对问题是生物信息学的基本问题，多重序列比对技术也是生物信息学的基本工具，有着十分广泛的应用，比如基因是否为同一个家族，癌症患者的基因与正常时的基因比对分析等等。因此，请您们就基因的多重序列比对，设计合理的衡量比对好坏的定量描述模型，建立多重序列比对的基本问题的数学模型，并设计一种求解的算法。最后就附录一中的12个序列，请您们利用你们得到的模型与算法，给出使序列有最大相似程度的比对。 附录一： CATTTCTTTTTAGGGATTTTAAAAGTTGTCTTTTCTT CATTTCTTTTTAAGGTTTTAAAAATTGTCTTTTTT CATTTCTTTTTAAGGGTTTTAAAAATTGTCTTTTCTT CATTTTTTCTTAAGTGTTTTGGTATTTATCTTTTTCTT CATTTTTGCTTATGTATTTATAGTGGGTTGTCTTTTTGACTT CATTTCTTTTGAAGTGATTTGAGATTTATCTTTTTCTT CATTTCTTTTTAAGGGTTTTAAAAATTGTCTTTTCTT CATTTCTTTTTATGTTGAGATATTTGTCTGTTTTCTT CATTTTTACTATGTGTTGATTGTGGATTGTCTTTTCTT CATTTCTTTTATTGAGTGAAGAAGAGATTTTGTCTTGTTTTGAT CATTTTTCTTAGTGTTTTGGTATTTATCTTTTTCTT CATTTCTTTTAAGGGTTTTAAAAATTGTCTTTTCTT

什么是简单重复序列(SSR)

生物的基因组中，特别是高等生物的基因组中含有大量的重复序列，根据重复序列在基因组中的分布形式可将其分为串联重复序列（Tandem Repeats Sequence，TRS）和散布重复序列（Dispersed Repeats Sequence，DRS）。其中，串联重复序列是由相关的重复单位首位相连、成串排列而成的。目前发现的串联重复序列主要有两类：一类是由功能基因组成的（如rRNA和组蛋白基因）；另一类是由无功能的序列组成的。根据重复序列的重复单位的长度，可将串联重复序列分为卫星DNA、微卫星DNA、小卫星DNA等。 微卫星DNA又叫简单重复序列（Simple Sequence Repeat，SSR），指的是基因组中由1-6个核苷酸组成的基本单位重复多次构成的一段DNA，广泛分布于基因组的不同位置，长度一般在200 bp以下。研究表明，微卫星在真核生物的基因组中的含量非常丰富，而且常常是随机分布于核DNA中。在植物中通过对拟南芥、玉米、水稻、小麦等的研究表明微卫星在植物中也很丰富，均匀分布于整个植物基因组中，但不同植物中微卫星出现的频率变化是非常大的，如在主要的农作物中两种最普遍的二核苷酸重复单位（AC）n和（GA）n在水稻、小麦、玉米、烟草中的数量分布频率是不同的。在小麦中估计有3000个（AC）n序列重复和约6000个（G A）n序列重复，两个重复之间的距离平均分别为704 kb、440 kb，而在水稻中，（AC）n 序列重复约有1000个左右，（GA）n 重复约有2000个，重复之间的平均距离分别为450 kb、225 kb。另外在植物中也发现一些三核苷酸和四核苷酸的重复，其中最常见的是（AAG）n、（AAT）n。在单子叶和双子叶植物中SSR数量和分布也有差异，平均分别为64.6 kb和21.2 kb中有一个SSR。研究还发现，单核苷酸及二核苷酸重复类型的SSR主要位于非编码区，而有部分三核苷酸类型位于编码区。另外在叶绿体基因组中，目前也报道了一些微卫星，以A/T序列重复为主。 研究发现，微卫星中重复单位的数目存在高度变异，这些变异表现为微卫星数目的整倍性变异或重复单位序列中的序列有可能不完全相同，因而造成多个位点的多态性。如果能够将这些变异揭示出来，就能发现不同的SSR在不同的种甚至不同个体间的多态性，基于这一想法，人们发展了SSR标记。SSR标记又称为序列标签微卫星位点（sequence tagged mic rosatell ite site），简写为STMS，是目前最常用的微卫星标记之一。由于基因组中某一特定的微卫星的侧翼序列通常都是保守性较强的单一序列，因而可以将微卫星侧翼的DNA片段克隆、测序，然后根据微卫星的侧翼序列就可以人工合成引物进行PCR扩增，从而将单个微卫星位点扩增出来。由于单个微卫星位点重复单元在数量上的变异，个体的扩增产物在长度上的变化就产生长度的多态性，这一多态性称为简单序列重复长度多态性（Simple Sequence length polymorp

实验3 两条序列比对与多序列比对

实验三：两条序列比对与多序列比对 实验目的： 学会使用MegAlign，ClustalX和MUSCLE进行两条序列和多条序列比对分析 实验内容： 双序列比对是使两条序列产生最高相似性得分的序列排列方式和空格插入方式。两条序列比对是生物信息学最基础的研究手段。第一次实验我们用dotplot方法直观地认识了两条序列比对。但是dotplot仅仅是展示了两条序列中所有可能的配对，并不是真正意义上的序列比对。这里介绍进行两条序列比对的软件-MegAlign。 多序列比对是将多条序列同时比对，使尽可能多的相同（或相似）字符出现在同一列中。多序列比对的目标是发现多条序列的共性。如果说序列两两比对主要用于建立两条序列的同源关系，从而推测它们的结构和功能，那么，同时比对多条序列对于研究分子结构、功能及进化关系更为有用。多序列比对对于系统发育分析、蛋白质家族成员鉴定、蛋白质结构预测、保守模块的搜寻等具有非常重要的作用。我们这节课主要学习多条序列比对的软件-ClustalX, MUSCLE。 一、MegAlign DNASTAR公司的Lasergene软件包是一个比较全面的生物信息学软件，它包含了7个模块。其中MegAlign可进行两条或多条序列比对分析。 1. 两条序列比对 1.1 安装程序 解压DNASTAR Lasergene软件压缩包，双击Lasergene710WinInstall.exe文件，按照默认路径安装软件到自己电脑上。 1.2 载入序列 a.点击开始－程序－Lasergene－MegAlign，打开软件。 我们首先用演示序列（demo sequence）学习软件的使用。演示序列所在位置：C:\Program files\ DNASTAR\ Lasergene\ Demo Megalign\ Histone Sequences\。 b. 点击主菜单File—Enter sequence－选择序列所在文件夹，选择序列tethis21.seq和tethis22.seq，点击Add，这两条序列将出现在右侧selected sequences框中（Figure 3.1），选择完毕点击Done回到程序页面。 Figure 3.1 载入序列

多重序列比对及系统发生树的构建

多重序列比对及系统发生树的构建 【实验目的】 1、熟悉构建分子系统发生树的基本过程，获得使用不同建树方法、建树材料和建树参数对建树结果影响的正确认识； 2、掌握使用Clustalx进行序列多重比对的操作方法； 3、掌握使用Phylip软件构建系统发生树的操作方法。 【实验原理】 在现代分子进化研究中，根据现有生物基因或物种多样性来重建生物的进化史是一个非常重要的问题。一个可靠的系统发生的推断，将揭示出有关生物进化过程的顺序，有助于我们了解生物进化的历史和进化机制。 对于一个完整的进化树分析需要以下几个步骤：⑴ 要对所分析的多序列目标进行比对（alignment）。 ⑵ 要构建一个进化树（phyligenetic tree）。构建进化树的算法主要分为两类：独立元素法（discrete character methods）和距离依靠法（distance methods）。所谓独立元素法是指进化树的拓扑形状是由序列上的每个碱基/氨基酸的状态决定的（例如：一个序列上可能包含很多的酶切位点，而每个酶切位点的存在与否是由几个碱基的状态决定的，也就是说一个序列碱基的状态决定着它的酶切位点状态，当多个序列进行进化树分析时，进化树的拓扑形状也就由这些碱基的状态决定了）。而距离依靠法是指进化树的拓扑形状由两两序列的进化距离决定的。进化树枝条的长度代表着进化距离。独立元素法包括最大简约性法（M aximum Parsimony methods）和最大可能性法（Maximum Likelihood methods）；距离依靠法包括除权配对法（UPGMAM）和邻位相连法（Neighbor-joining）。⑶ 对进化树进行评估，主要采用Bootstraping法。进化树的构建是一个统计学问题，我们所构建出来的进化树只是对真实的进化关系的评估或者模拟。如果我们采用了一个适当的方法，那么所构建的进化树就会接近真实的"进化树"。模拟的进化树需要一种数学方法来对其进行评估。不同的算法有不同的适用目标。一般来说，最大简约性法适用于符合以下条件的多序列：i 所要比较的序列的碱基差别小，ii 对于序列上的每一个碱基有近似相等的变异率，iii 没有过多的颠换/转换的倾向，iv 所检验的序列的碱基数目较多（大于几千个碱基）；用最大可能性法分析序列则不需以上的诸多条件，但是此种方法计算极其耗时。如果分析的序列较多，有可能要花上几天的时间才能计算完毕。UPGMAM（Unweighted pair group method with arithmetic mean）假设在进化过程中所有核苷酸/氨基酸都有相同的变异率，也就是存在着一个分子钟。这种算法得到的进化树相对来说不是很准确，现在已经很少使用。邻位相连法是一个经常被使用的算法，它构建的进化树相对准确，而且计算快捷。其缺点是序列上的所有位点都被同等对待，而且，所分析的序列的进化距离不能太大。另外，需要特别指出的是对于一些特定多序列对象来说可能没有任何一个现存算法非常适合它。 CLUSTALX和PHYLIP软件能够实现上述的建树步骤。CLUSTALX是Windows界面下的多重序列比对软件。PH YLIP是多个软件的压缩包，功能极其强大，主要包括五个方面的功能软件：i，DNA和蛋白质序列数据的分析软件。ii，序列数据转变成距离数据后，对距离数据分析的软件。 iii，对基因频率和连续的元素分析的软件。iv，把序列的每个碱基/氨基酸独立看待（碱基/氨基酸只有0和1的状态）时，对序列进行分析的软件。v，按照DOLLO简约性算法对序列进行分析的软件。vi，绘制和修改进化树的软件。

序列比对方法

序列对齐（sequence alignment）的目的是通过两个或多个核酸序列或蛋白质序列进行对齐，并将其中相似的结构区域突出显示。通过比较未知序列与已知序列（尤其是功能和结构已知的序列）之间的同源性，往往可以很容易地预测未知序列的功能。 1、两两对齐分析 国际互联网上序列两两对齐资源有： ①ALIGN（http://genome.eerie.fr/fasta/align-query.html），对用户所提交的两条序列进行优化对齐，允许选择不同的记分矩阵，但是不允许空位罚分。 ②Align（http://www.mips.biochem.mpg.de/mips/programs/aligh.html； http://www.mips.biochem.mpg.de/）只允许对数据库的已有记录进行两两比对，不接受用户所提交的序列。 ③Bl2Seq（https://www.doczj.com/doc/e95192447.html,/gorf/bl2.htm）可对任意两条序列进行两两对齐，具有Blast软件的所有功能。 2、多重序列对齐分析 国际互联网上多重序列对齐程序有： ①ClustalW/X。最为著名的序列多重对齐软件包。用户可自行下载进行数据分析。接受多种输入格式，包括FASTA、EMBL、SWISS-PROT、PIR、GCG/MSF等，但所有输入序列必须在同一文件中。如果输入序列中的非空格号85%以上为A、C、G、T、U、N，判定为核酸序列，否则作为蛋白质序列计算。但核酸和蛋白质序列不能在同一文件中。 网址：https://www.doczj.com/doc/e95192447.html,/cgi-bin/newclustalw.pl； https://www.doczj.com/doc/e95192447.html,/multi-align/multi-align.html； ftp://https://www.doczj.com/doc/e95192447.html,/pub/software； ②Match-Box。同时考虑序列数据和氨基酸性质进行序列多重对齐分析。 网址：http://www.fundp.ac.be/sciences/biologie/bms/matchbox_submit.html ③BCM服务器。Baylor College of Medicine，BCM launcher。 网址：https://www.doczj.com/doc/e95192447.html,/multi-align/multi-align.html

vector nti 11 使用教程 第十章_多重序列比对

第十章多重序列比对 Vector NTI的多重序列比对程序和其他的比对软件比较起来非常的方便实用，操作接口也很简单，比对的结果可以存取和输出。NTI有两种序列比对程序，一种为AlignX，可以用在核酸序列和蛋白质序列比对；另一种为AlignX Blocks，只能用在蛋白质序列比对。 如何开始进行序列比对？用户可以从程序集开启档案(图10.1)： 图10.1 由程序集开启AlignX 或者是从主程序中开启(图10.2)： 图10.2 由主程序开启AlignX 用户也可以在主程序(图10.3)具有操作序列的情况下开启AlignX-Align Selected Molecules，使用者的序列会直接加载到AlignX中： 图10.3 在操作序列的情况下开启AlignX的方法

开启AlignX之后，使用者会见到图10.4的画面： 图10.4在操作序列的情况下开启AlignX 首先用户要把序列加载Vector NTI程序中，可以点选或者从左上方的Project →Add Files把序列档案加载，请注意文件名不可以过长，檔名过长会造成程序进行比对时无法完全显示文件名(图10.5)： 图10.5 输入的档名注意不可过长 选取档案后按下开启就可以加载程序中，若比对的序列很多时可以用鼠标圈选欲分析的序列后选择开启。序列档案加载的时候程序会询问该序列为核酸序列或是蛋白质序列，点选好以后再点选Import就可以了(图10.6)：

图10.6 载入时，会询问序列的性质，核酸序列或蛋白质序列 接下来程序的左上方会出现使用者加载的序列(图10.7)，序列加载完成以后就可以开始进行比对的操作： 图10.7 成功载入序列的画面 进行比对前，先把欲比对的序列用鼠标进行圈选(图10.8)： 图10.8 选取欲比对之序列 只要按下或是从上方Align→Align Selected Sequence(图10.9)就会进行比对运算：

时间序列分析法原理及步骤

时间序列分析法原理及步骤 ----目标变量随决策变量随时间序列变化系统 一、认识时间序列变动特征 认识时间序列所具有的变动特征, 以便在系统预测时选择采用不同的方法 1》随机性:均匀分布、无规则分布,可能符合某统计分布(用因变量的散点图和直方图及其包含的正态分布检验随机性, 大多服从正态分布 2》平稳性:样本序列的自相关函数在某一固定水平线附近摆动, 即方差和数学期望稳定为常数 识别序列特征可利用函数 ACF :其中是的 k 阶自 协方差,且 平稳过程的自相关系数和偏自相关系数都会以某种方式衰减趋于 0, 前者测度当前序列与先前序列之间简单和常规的相关程度, 后者是在控制其它先前序列的影响后,测度当前序列与某一先前序列之间的相关程度。实际上, 预测模型大都难以满足这些条件, 现实的经济、金融、商业等序列都是非稳定的,但通过数据处理可以变换为平稳的。 二、选择模型形式和参数检验 1》自回归 AR(p模型

模型意义仅通过时间序列变量的自身历史观测值来反映有关因素对预测目标的影响和作用,不受模型变量互相独立的假设条件约束,所构成的模型可以消除普通回归预测方法中由于自变量选择、多重共线性的比你更造成的困难用 PACF 函数判别 (从 p 阶开始的所有偏自相关系数均为 0 2》移动平均 MA(q模型 识别条件

平稳时间序列的偏相关系数和自相关系数均不截尾,但较快收敛到 0, 则该时间序列可能是 ARMA(p,q模型。实际问题中,多数要用此模型。因此建模解模的主要工作时求解 p,q 和φ、θ的值,检验和的值。 模型阶数 实际应用中 p,q 一般不超过 2. 3》自回归综合移动平均 ARIMA(p,d,q模型 模型含义 模型形式类似 ARMA(p,q模型, 但数据必须经过特殊处理。特别当线性时间序列非平稳时,不能直接利用 ARMA(p,q模型,但可以利用有限阶差分使非平稳时间序列平稳化,实际应用中 d (差分次数一般不超过 2. 模型识别 平稳时间序列的偏相关系数和自相关系数均不截尾,且缓慢衰减收敛,则该时间序列可能是 ARIMA(p,d,q模型。若时间序列存在周期性波动, 则可按时间周期进

多重序列比对及系统发生树的构建

多重序列比对及系统发生树的构建 作者：佚名来源：生物秀时间：2007-12-31 【实验目的】 1、熟悉构建分子系统发生树的基本过程，获得使用不同建树方法、建树材料和建树参数对建树结果影响的正确认识； 2、掌握使用Clustalx进行序列多重比对的操作方法； 3、掌握使用Phylip软件构建系统发生树的操作方法。 【实验原理】 在现代分子进化研究中，根据现有生物基因或物种多样性来重建生物的进化史是一个非常重要的问题。一个可靠的系统发生的推断，将揭示出有关生物进化过程的顺序，有助于我们了解生物进化的历史和进化机制。 对于一个完整的进化树分析需要以下几个步骤：⑴要对所分析的多序列目标进行比对（alignment）。⑵要构建一个进化树（phyligenetic tree）。构建进化树的算法主要分为两类：独立元素法（discrete character methods）和距离依靠法（distance methods）。所谓独立元素法是指进化树的拓扑形状是由序列上的每个碱基/氨基酸的状态决定的（例如：一个序列上可能包含很多的酶切位点，而每个酶切位点的存在与否是由几个碱基的状态决定的，也就是说一个序列碱基的状态决定着它的酶切位点状态，当多个序列进行进化树分析时，进化树的拓扑形状也就由这些碱基的状态决定了）。而距离依靠法是指进化树的拓扑形状由两两序列的进化距离决定的。进化树枝条的长度代表着进化距离。独立元素法包括最大简约性法（Maximum Parsimony methods）和最大可能性法（Maximum Likelihood methods）；距离依靠法包括除权配对法（UPGMAM）和邻位相连法（Neighbor-joining）。⑶对进化树进行评估，主要采用Bootstraping法。进化树的构建是一个统计学问题，我们所构建出来的进化树只是对真实的进化关系的评估或者模拟。如果我们采用了一个适当的方法，那么所构建的进化树就会接近真实的“进化树”。模拟的进化树需要一种数学方法来对其进行评估。不同的算法有不同的适用目标。一般来说，最大简约性法适用于符合以下条件的多序列：i 所要比较的序列的碱基差别小，ii 对于序列上的每一个碱基有近似相等的变异率，iii 没有过多的颠换/转换的倾向，iv 所检验的序列的碱基数目较多（大于几千个碱基）；