【作者】 王俊；

【导师】 石海鹤；

【作者基本信息】 江西师范大学 ， 工程硕士（专业学位）， 2021， 硕士

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

【Abstract】 In computer science and other research fields,sequences(strings)are one of the most basic and important data types.Ordinary texts,mathematical formulas,source codes of program,gene sequences(DNA,RNA)can all be regarded as a collection of sequences.The longest common subsequence is the longest common subsequence obtained by deleting zero or more elements from the two or more sequences.The algorithm for solving the longest common subsequence has a wide range of applications in text recognition,file compression,data mining,and bioinformatics.In bioinformatics,it is often necessary to judge the similarity and homology between sequences.Finding the longest common subsequence between biological sequences is one of the basic methods to judge the similarity and homology between sequences.The solving algorithms of the longest common subsequence problem are numerous and complex.Different longest common subsequence algorithms are suitable for different types of sequence data,which makes it difficult for users to understand this type of algorithms and cannot choose a suitable algorithm in practical applications.Existing research mainly focuses on the optimization of the specific steps of the longest common subsequence algorithm,and cannot solve the problem that this type of algorithm is too abstract and difficult to understand.Based on the PAR platform,this article comprehensively uses formal methods,domain engineering,generic programming,abstraction and other technologies and methods to study the realization of the longest common biological subsequence algorithm family from a high level of abstraction.Thereby reducing the complexity of the algorithm in this field,improving the intelligibility,reliability and development efficiency of the algorithm.The main work of this paper includes the following Three aspects:(1)The current typical implementation method of Longest Common Subsequence(LCS)and the multiple longest common subsequence(MLCS)algorithm based on the dominating point are investigated and analyzed in depth.Based on this,an implementation method of LCS algorithm family that comprehensively uses PAR method,domain engineering,generic programming,abstraction and other theories,methods and technologies is proposed.(2)Analyze the dynamic programming-based longest common subsequence algorithm and the constrained longest common subsequence algorithm(CLCS)as a unified domain.Designed the algorithm function components in this field,and applied the algorithm family realization method in this paper to realize it,thereby generating the LCS algorithm family component library.The component library is further used to assemble and generate the basic LCS algorithm,and with the support of the PAR platform Apla→C++ program generation system,it is converted into an executable C++ program for experimentation.(3)On the basis of the research to LCS algorithm based on dynamic programming,the domain of Multiple Longest Common Subsequence(MLCS)algorithm based on dominating point is studied.Extract five main functional components from this domain: sequence legitimacy check component,sequence preprocessing component,dominant＿mode component,directed acyclic graph component,result output component.And with the support of the PAR platform,the above components are abstractly implemented to form a highly abstract component library of MLCS algorithms.Further assembly generates the widely used Fast＿LCS algorithm based on this component library and with the support of Apla→C++program generation system,it is converted into an executable algorithm program.The comparative experiment with TOP＿MLCS algorithm shows that the implementation method of algorithm family proposed in this paper has high practicability.更多还原