基于ACO的多序列间最长公共子序列查询

王虹胜

（四川大学视觉合成图形图像技术国防重点学科实验室，成都 610065)

0 引言

多序列间的最长公共子序列（LCS）查询广泛地应用于计算生物学、模式识别、文本比较和数据压缩等。多序列间的最长公共子序列可以用来度量一组基因序列间的相似度，被广泛应用于基因测序和蛋白质功能测序等领域。本文主要针对任意数量的生物数据查找最长公共子序列。

经典的双序列间LCS查询算法是基于动态规划（Dynamic Programming）的思想，可以精确查询出双序列间的所有最长公共子序列。但是，对于长度为M的N条序列，动态规划算法的时间复杂度和空间复杂度均为O（MN），随着数据规模的增大，其复杂度将以指数形式增加，这不利于多序列（N>10）或较长序列（M=500）的查询。为了进一步提升LCS问题的解决速度，人们提出了近似方法（Approximate Algorithm）和启发式方法（Heuristic Algorithm）。这两种方法均以降低求解精度为代价，获得计算效率的大幅提升。近似方法是指在较短时间内计算出最长公共子序列的近似最优解。最早的LCS近似算法是Long Run方法，该方法在实际应用中的利用率不高。2004年Huang等人提出的 BNMAS（Beat Next for Maximal Available Symbols）算法，但其时间复杂度严重依赖于序列集合的字符种类总数。启发式方法是专为解决NP问题而提出的算法框架，常用于解决多序列间LCS查询等无法在多项式时间内获得精确解的问题。2006年Hinkemeyer和Julstrom等人提出了基于遗传算法（Genetic Algorithm）的LCS查询算法。2008年Chiang等人对已有的GALCS算法做出部分改进，进一步降低了算法复杂度，该算法查询质量结果远高于Long Run算法。

针对现有算法的不足，本文主要利用启发式算法中的蚁群优化算法（ACO）求解LCS问题，ACO-LCS在查询效率和结果近似度两方面均高于GA-LCS算法；并对其中的启发式因子计算部分做了改进，进一步提高算法的查询结果质量。

1 最长公共子序列问题模型

在计算机中，生物序列可表示为字符矩阵S={S0,S1,….,Sn-1}，矩阵每一行表示一条生物序列Si，且对于任意i(0 ≤i≤1)均有 |Si|=1。Si[j]表示序列Si中下标为j的字符。子序列为一个严格递增的下标数组对应的字符序列。例如，对于序列Si=CTATGA，下表数组p=[0 ,2,4,5]对应的子序列为CAGA。同理，N条序列间的长度为D的任意公共子序列S，可以表示为一个D×N的下标矩阵CS，即CS[i][j]表示S的第i个字符在原始序列Sj中的下标。不同的公共子序列具有不同的下标矩阵，因此，下标矩阵可以作为公共子序列的唯一标识。下标矩阵CS具有如下两个特点：

（1）对于给定的行号i，CS[i][j]和CS[i][k]对应的字符相同，其中0≤i

（2）下标矩阵每列存储的下标值严格递增。即CS[i][j]

对 于 给 定 的 序 列 集 合 S={S0：ATCACG，S1：TTCTAG，S2：TCCAGA}，其长度为 4的公共子序列s=TCAG可由一个4×3的下标矩阵表示。该矩阵存储了公共子序列s中的四个字符在所有原始序列中的下标。例如，矩阵的第0行[1 0 0]表示s的第0个字符T在原始序列S0中的下标为1，在原始序列S1和S2中的下标为0。矩阵的第0列则表示公共子序列s中的四个字符分别对应原始序列 S0中的下标为 1、2、3、5 的字符。

当下标矩阵CS的行数D达到最大值时，即为最长公共子序列的字符下标矩阵，遍历矩阵的任意一列即可计算出序列集合的最长公共子序列。因此，LCS问题可以转换为计算最大行数的字符下标矩阵的问题。在本文中，我们将利用蚁群优化算法来解决该问题。

（3）蚁群优化算法在LCS问题中的应用

对于给定的序列矩阵S={S0,S1,….,Sn-1}，其最长公共子序列是所有原始序列的子序列，因此通过遍历任意一条原始序列均可得出序列间的LCS下标矩阵。蚁群优化算法模拟了一个规模为M的人工蚁群A={A0,A1,…,AM-1}，每只蚂蚁Ai随机地分配一条序列Sj，以遍历该序列为基准来查询序列间的最长公共子序列。

蚂蚁Ai把原始序列Sj看作自然环境中的地面，把序列中每个字符s及其下标p组成的组对(s ,p)视作地面上的一个位置点。所有满足下标矩阵特点的未访问位置点为Ai的可转向位置点，即若s为所有原始序列的公共字符，且s在每条原始序列中的下标p大于该序列已被访问位置点的下标值，则(s ,p)为可转向位置点。蚂蚁Ai模拟自然界中蚁群觅食时的寻路方式，评估所有位置点的可转向性，若(s ,p)满足下标矩阵的特点，即将字符s在所有原始序列中的下标作为新的一行加入蚂蚁Ai构建的LCS下标矩阵中。蚂蚁Ai以(s ,p)作为当前位置继续向前访问，不断地将满足下标矩阵特点的位置点对应的下标添加进LCS下标矩阵中，直到遍历完序列Sj的最后一个位置点，便可得到该蚂蚁构建的近似LCS下标矩阵。图1为蚂蚁Ai的一次构建过程。

图1 LCS下标矩阵构建过程

初 始 时 下 标 矩 阵 为 空 ，位 置 点(A ,0)，(T ,1)，(C ,2)，(A ,4)均为可转向位置点。假设Ai选择转向位置点(A ,0)，则搜索(A ,0)在所有原始序列中的下标[0 ,3,1]，并将其作为第0行加入下标矩阵中。Ai继续评估下一个位置点(T ,1)，分别以3和1为当前下标在原始序列S1和S2中搜索字符T，未搜寻到则表示(T ,1)不是当前的可转向点。Ai继续以[0 ,3,1]为当前下标评估下一个位置点(C ,2)，并将其对应的下标数组[2 ,4,2]作为新的一行加入LCS下标矩阵中。直到S0遍历结束蚂蚁便可构建出路径(A ,0)→(C ,2)对应的行数为2的下标矩阵，其对应的公共子序列为AC。然而，若要构建出行数较大的下标矩阵，还需要蚂蚁有效地选择“较好”的可转向点。

蚂蚁在遍历原始序列时，所有满足下标矩阵要求的未访问位置点均为其候选转向的位置点，蚂蚁通过评估转向每个位置点可获得更长公共子序列的可能性，来选择出“较好”的位置点。在图1中，若蚂蚁首次选择时放弃位置点(A ,0)，选择转向位置点(T ,1)，则可构建出路径(T ,1)→(C ,2)→(A ,4)对应的行数为3的下标矩阵，其对应的公共子序列TCA。因此，字符T是比A更好的候选转向。在实际LCS问题中，蚂蚁通常无法直观地判断那个字符“较好”，只能通过位置点(s ,p)的特性计算其能获取更长公共子序列的可能性来觉得是否选择。这种可能性被称作字符的转换概率。转换概率的决定因素主要是位置点(s ,p)的信息素因子和启发式因子。

位置点(s ,p)的信息素因子实现了蚁群系统的正反馈性，使每只蚂蚁有了经验学习的能力，从而有效地选择“较好”字符。蚂蚁每次选择一个位置点(s ,p)后，便会在改点及其在所有原始序列中的对应位置点上排放一定量的信息素。随着蚁群不断地选择。位置点(s ,p)上信息素的积累量，表示为τ(s,p)。τ(s,p)越大表示该字符在蚁群历史构建过程中被选择的次数越多，是“较好”字符的可能性也就越大。位置点(s ,p)的启发式因子是指局部范围内，转向位置点(s ,p)可获得更长公共子序列的可能性，表示为η(s,p)。η(s,p)值反映了每只蚂蚁的局部搜索能力。信息素因子和启发式因子共同决定了蚂蚁构建LCS过程中的每次字符选择。启发式因子具体计算公式如式（1）所示:

蚁群系统的交流和优化主要由信息素机制实现。蚂蚁通过每个位置点的信息素累积量，获取整个蚁群对于该位置点的历史选择经验，从而实现蚁群系统的学习和协作。每轮构建结束后，蚁群优化算法会在所有蚂蚁构建的LCS下标矩阵中，选出行数最大的一个作为本轮迭代的最优解。同时维护一个历史最优解，若当前轮产生的本轮最优解行数大于当前历史最优解，则更新历史最优解。在LCS问题中，信息素表示为一个与序列矩阵S同等规模的矩阵τ[N][D]，τ[N][D]存储了字符Si[j]位置的信息素累积量。蚁群在每轮构建LCS下标矩阵完成之后便会对全局信息素矩阵进行更新操作，以反馈蚁群的当前构建情况，为下一轮构建提供经验学习。信息素的更新主要包括信息素随时间挥发的减少量，以及优质的LCS下标矩阵储存位置点的排放量。信息素更新公式如（2）所示，其中ρ为每轮构建过程中信息素的挥发率。Δτ[i][j]为本轮构建过程中Si[j]位置信息素的总排放量。φ为信息素排放系数，且φ∈(0,1)，以防信息素排放量过高，使得某条路径信息素积累量明显高于其他路径，造成蚁群系统过早停滞。

2 实验结果分析

蚁群优化算法是一个群体智能算法，群体的规模对算法构建的质量和效率都有一定影响。蚁群优化算法中蚂蚁数量越多时，构建的公共子序列种类也就越多，可查询到更长的公共子序列的可能性也就越大。但是，当构建的公共子序列种类数过多时，大部分位置点的信息素便会趋于平均，这极大地抑制了蚁群系统的正反馈性，导致算法收敛速度变慢，影响最长公共子序列的查询效率。而若蚁群规模太小，算法很容易出现停止现象，不利于最优解的构建。本实验以不同规模的DNA序列集合为例，研究不同蚁群规模对算法查询效率和查询结果长度的结果。如表1所示，随着蚁群规模不断增大，算法查询的公共子序列长度随之变化，并且查询时间消耗成倍增加，但蚂蚁构建出的下标矩阵多样性增加，查询到的公共子序列长度也逐渐增加。但当蚁群规模增加到一定程度时，其查询出的公共子序列长度增加量逐渐减小，查询长度提升逐渐变得不明显。

表1 蚁群规模对LCS查询性能影响

3 结语

本文分析了蚁群优化算法查询最长公共子序列的基本思想和大致流程，采用基于蚁群优化算法实现了多序列间的最长公共子序列查询。本文通过大量的实验研究并分析了不同蚁群规模对查询算法的性能影响，确保蚁群优化算法可有效解决LCS问题。

[1]Dorigo M,Birattari M,Stutzle T.Ant colony optimization[J].IEEE Computational Intelligence Magazine,2006,1（4）:28-39.

[2]Bullnheimer B,Hartl R,Strauss C.A New Rank Based Version of the Ant System.A Computational Study[J].1997,7（1）:25-38.

[3]Stutzle T,Hoos H.MAX-MIN Ant System[J].Future Generation Computer Systems,2000,16（8）:889-914.

[4]Dorigo M,Maniezzo V,Colorni A.Positive Feedback as a Search Strategy[J].,1991.