多序列比对算法族的形式化设计与生成  

Formal design and generation of a family of multiple sequences alignment algorithms

作　　者：张旭初 石海鹤[1] ZHANG Xu-chu;SHI Hai-he(School of Computer and Information Engineering,Jiangxi Normal University,Nanchang 330022,China)

机构地区：[1]江西师范大学计算机信息工程学院,江西南昌330022

出　　处：《计算机工程与科学》2020年第8期1383-1392,共10页Computer Engineering & Science

基　　金：国家自然科学基金(61662035,61762049,61862033)。

摘　　要：多序列比对问题是生物信息学研究的重要部分,是解决物种进化关系、基因组序列分析等问题的基础。多序列比对算法具有很高的专用性,不同的算法适用于不同的研究环境。目前常用的多序列比对软件是在生物信息学理论指导下利用多个子算法装配形成的,而现有的研究主要针对特定算法的特定步骤进行优化,缺乏领域层次高抽象性的算法框架研究,致使多序列比对算法较为繁杂且冗余过多。根据产生式编程以及软件复用的思想,分析了多序列比对算法族MSAA的特征,设计了相应的泛型算法构件并刻画了构件间的交互关系,进一步借助PAR平台形式化构建了MSAA构件库,提高了装配算法的可靠性和组装灵活性,便于研究人员的维护和优化。Multiple sequence alignment is an important part of bioinformatics research,which is the basis to solve the problems of species evolution relationship and genome sequence analysis.Multiple sequence alignment algorithms have high specificity and different algorithms are suitable for different research environments.At present,the commonly used multiple sequence alignment software is based on the assembly of multiple sub-algorithms under the guidance of bioinformatics theory.However,the existing research mainly focuses on the optimization of specific steps of specific algorithms,and the lack of algorithm framework research with high abstraction of domain level leads to the complexity and redundancy of multiple sequence alignment algorithms.According to the idea of generative programming and software reuse,the features of multiple sequence alignment algorithm(MSAA)are analyzed and modeled,and the corresponding generic algorithm components are designed and the interaction among these components is described.Further,PAR platform is used to formally build up the MSAA component library.The work improves the reliability and assembly flexibility of assembling algorithms and facilitates the maintenance and optimization of researchers.

关 键 词：多序列比对算法 特征模型 产生式编程 算法构件 PAR平台 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]