现实世界中的大量信息都可以表示为字符序列的形式,而求解多个字符序列最长公共子序列（MLCS）问题作为数据挖掘的一种具体技术,可以对大量的字符序列进行分析和处理,以便找到和发现有用的知识以及它们之间的内在联系,并将其应用于生物信息学、模式识别、文件比较和信息检索等领域。然而现有一些算法还普遍存在效率不高的问题,只能用来处理较为简单的MLCS问题。随着MLCS问题规模的增大,这些算法对运算时间和内存空间的消耗将会成倍甚至呈指数级增加,导致无法在有限的时间（空间）内求出最终结果。影响算法效率的根本原因在于,1)算法的搜索空间大,在求解过程中需要对大量重复、无用信息进行存储和计算,这消耗了大量的计算和存储资源;2)用于求解最长路径（对应于MLCS）的非支配排序技术十分耗费运算时间,而拓扑排序技术十分耗费内存空间;3)在基于图模型的求解算法中,存在大量的无用匹配点（即对最长路径的求解没有贡献）以及经过这些匹配点的非最长路径,而现有的技术无法及时地识别出它们并进行相应的剪枝操作。本文研究和分析了影响算法低效的根本原因,设计了多个高效算法以期能够处理更大规模的MLCS问题。现将本文的主要工作和创新点总结如下:（1）针对现有算法在构建DAG时存在图中节点重复出现及非最长路径不能动态删除等问题,提出了一个路径记录器有向无环图（PRDAG）模型和基于该模型的路径记录器算法（PRA）。在构建PRDAG时,设计了一个重复节点检查机制,可以利用哈希技术快速检测出某一节点是否已经存在于DAG中,若节点已经存在,则直接使用图中的节点进行操作,而不必再次将该节点放入图中,以保证DAG中不出现重复或冗余的节点。另外,图中所有节点只记录关键前驱节点,节点的层级值一旦更新之后,PRA算法会及时删除掉节点先前的前驱节点（现在已成为非关键前驱节点）,相当于删除了非最长路径信息,这样DAG的大小（规模）就变得更小,从而节省大量内存空间和运算时间。（2）为解决内存消耗过多,以及基于非支配排序技术的算法耗费运算时间过多的问题,开发了层次递推有向无环图（HP-DAG）模型,并基于该模型提出了一种求解MLCS问题的高效算法EAHPM。该算法将从序列中寻找MLCS的问题转化为搜索DAG中最长路径的问题。设计的匹配点动态删除技术可以及时删除过时匹配点（这些匹配点在后续DAG构建中不再使用）,同时,结合最长距离估计技术,检查匹配点是否为不可达匹配点,以减少DAG中匹配点的总数,从而达到降低算法时空开销的目的。（3）针对DAG的规模过大,图中的无用匹配点无法及时识别等问题,提出了一种基于分支消除的,在空间和时间上都十分高效的算法BEST-MLCS。BEST-MLCS算法设计了一种全新的基于上下界估计的无用匹配点判定技术和分支消除策略,即首先在算法的预处理阶段,通过一种启发式方法快速估计出MLCS长度的一个下界Lmlcs,然后设计了一个可以快速计算出经过某一匹配点的所有路径长度上界(记为U（O,p,∞）)的方法,如果该上界U（O,p,∞）小于下界Lmlcs,则可以判断出该匹配点必定为一无用匹配点,经过该匹配点的所有路径都是非最长路径。在构建DAG的过程中,可以及时地把这些无用匹配点和经过这些匹配点的分支路径删除掉（即分支消除策略）,所构建出来的DAG的规模非常小,极大节省运算时间和内存空间。（4）针对算法搜索空间大和图中节点数量过多等问题,提出了一种新的最小化图模型的Mema-MLCS算法。算法设计了一种计算匹配点跨度值的技术方案,通过比较匹配点的跨度值与MLCS长度下界值的方式,实现无用匹配点和非最长路径的及时删除。另外,Mema-MLCS只使用最有希望（即跨度值最大）的匹配点来构造DAG,而忽略其他的匹配点和不在最长路径上的分支,使生成的DAG的规模更小,因此,Mema-MLCS消耗的空间和所需运行时间相比其他算法要小得多,可以用来处理更大规模的MLCS问题。