• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

计算机工程与科学 ›› 2020, Vol. 42 ›› Issue (08): 1383-1392.

• 软件工程 • 上一篇    下一篇

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

张旭初,石海鹤   

  1. (江西师范大学计算机信息工程学院,江西 南昌 330022)

  • 收稿日期:2020-01-15 修回日期:2020-04-17 接受日期:2020-08-25 出版日期:2020-08-25 发布日期:2020-08-29
  • 基金资助:
    国家自然科学基金(61662035,61762049,61862033)

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

ZHANG Xu-chu,SHI Hai-he   

  1. (School of Computer and Information Engineering,Jiangxi Normal University,Nanchang 330022,China)

  • Received:2020-01-15 Revised:2020-04-17 Accepted:2020-08-25 Online:2020-08-25 Published:2020-08-29

摘要: 多序列比对问题是生物信息学研究的重要部分,是解决物种进化关系、基因组序列分析等问题的基础。多序列比对算法具有很高的专用性,不同的算法适用于不同的研究环境。目前常用的多序列比对软件是在生物信息学理论指导下利用多个子算法装配形成的,而现有的研究主要针对特定算法的特定步骤进行优化,缺乏领域层次高抽象性的算法框架研究,致使多序列比对算法较为繁杂且冗余过多。根据产生式编程以及软件复用的思想,分析了多序列比对算法族MSAA的特征,设计了相应的泛型算法构件并刻画了构件间的交互关系,进一步借助PAR平台形式化构建了MSAA构件库,提高了装配算法的可靠性和组装灵活性,便于研究人员的维护和优化。

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

Abstract: 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.






Key words: multiple sequences alignment algorithm;feature model, generative programming;algorithm component;PAR platform