基于PAR平台的最长公共生物子序列算法族实现方法研究

摘要

在计算机科学及其相关研究领域中，序列（字符串)都是最基本的数据类型之一，普通文本、数学公式、程序源代码、基因序列（DNA、RNA）等都可以看作序列的集合。最长公共子序列是将两条或多条序列分别删去零个或多个元素后得到的最长的共有子序列，求解最长公共子序列的算法在文本识别、文件压缩、数据挖掘以及生物信息学等领域有着广泛的应用。　　在生物信息学中，常常需要判断序列之间的相似性及同源性，寻找生物序列之间的最长公共子序列是判断序列相似性及同源性的基本方法之一。最长公共子序列问题求解算法数量众多且较为复杂，不同的算法适用于不同类型的序列数据，使用者难以理解，且难以在实际应用中选择恰当的算法。现有研究主要集中于对最长公共子序列算法特定步骤的优化，这不能很好解决该类算法过于复杂、难以理解的问题。基于PAR平台，本文综合使用形式化方法、领域工程、泛型程序设计、抽象等技术和手段，从高抽象层次对最长公共生物子序列算法族实现方法进行研究，从而降低该领域算法的复杂度，提高算法的可理解性、可靠性和开发效率。主要工作包括以下三个方面：　　（1）深入分析了目前典型的最长公共子序列（LongestCommonSubsequence，LCS）算法和基于支配点的多序列最长公共子序列（MultipleLongestCommonSubsequence，MLCS）算法实现方法，基于此提出了一种综合使用PAR方法、领域工程、泛型程序设计、抽象等理论、方法和技术的LCS算法族实现方法。　　（2）将基于动态规划的最长公共子序列算法和受约束的最长公共子序列算法（ConstrainedLongestCommonSubsequence,CLCS）作为统一的研究领域进行分析，应用本文的算法族实现方法，设计了该领域的算法功能构件，生成LCS算法族构件库，进一步使用该构件库装配生成基本LCS算法，并在PAR平台Apla→C++程序生成系统的支持下，将其转换为可执行的C++程序进行实验。　　（3）在基于动态规划的LCS算法研究基础上，对基于支配点的多序列最长公共子序列算法领域进行研究。应用本文的算法族实现方法从该领域中提取五个主要功能构件，即序列合法性检查构件，序列预处理构件，支配点模式构件，有向无环图构件和结果输出构件，形成高抽象的MLCS算法构件库，进一步基于该构件库装配生成应用较为广泛的Fast_LCS算法，在Apla→C++程序生成系统支持下，将其转换为可执行的算法程序。与TOP_MLCS算法的对比实验表明，本文提出的算法族实现方法具有很高的实用性。

目录

声明

目 录

1 绪论

1.1 研究背景及意义

1.2 国内外研究现状

1.2.1 LCS问题研究现状和基本求解方法

1.2.2 MLCS问题研究现状和基本求解方法

1.2.3 软件自动化研究现状

1.3 论文主要研究内容

1.4 论文组织结构

2 LCS算法族实现方法

2.1 PAR与形式化算法开发

2.1.1 PAR

2.1.2 PAR的形式化算法开发流程

2.2 领域工程

2.3 基于PAR平台的LCS算法族实现方法

2.4 本章小结

3 基于动态规划的LCS算法族实现

3.1 基于动态规划的LCS算法领域分析

3.2 基于动态规划的LCS算法领域实现

3.2.1 构件设计

3.2.2 构件实现

3.2.3 算法装配

3.2.4 实验

3.3 本章小结

4 基于支配点的MLCS算法族实现

4.1 基于支配点的MLCS算法领域分析

4.2 基于支配点的MLCS算法领域实现

4.2.1 构件设计

4.2.2 构件实现

4.2.3 算法装配

4.2.4 实验

4.3 本章小结

5 结束语

5.1 总结

5.2 工作展望

参 考 文 献

致 谢

在读期间公开发表论文及科研情况

1 论文情况

2 课题情况