PAR框架下形式化构件装配的高效生物序列分析动态规划算法构造

With the growth of biosequence data, biosequence analysis (Ba) needs more efficient and reliable optimization algorithms. Dynamic programming (DP) is the basic optimization method in biosequence analysis, but it is hard to guarantee the productivity and reliability of Ba-DP algorithms due to the non-triviality of Ba problem domain. Most of the existing research works often take Ba-DP algorithm as a case study for a method or a theory, but rarely study the laws behind algorithm design, or just build a module database and require users to select modules from database and to adjust and modify them for solving a problem. The performance, productivity and reliability of algorithms are not desirable. Inspired by generative programming in software engineering, based on the PAR method, the project combines abstract mechanism, deductive inference, and generic programming techniques to explore efficiency-oriented algorithm calculus rules and strategies, and to formally develop domain-specific language of Ba-DP algorithms, abstract Ba-DP algorithm frame, Ba-DP algorithm generation model, and further expands PAR platform to support the algorithm construction via component assembly. Not only are efficient methods and tool provided for improvement of productivity and reliability of Ba-DP algorithms, but also the flexibility and configurability of component assembly provide an effective means to discover and generate new algorithms. This project is expected to explore new ideas and methods for highly-reliable Ba algorithms development.

生物序列数据日益增多，生物序列分析（Biosequence Analysis,Ba）需构造高效可靠的优化算法。动态规划（Dynamic Programming,DP）是Ba中的基本优化方法，由于Ba问题域的非平凡性，DP算法开发效率和可靠性难以保证。现有工作多将Ba-DP算法作为某方法/理论的案例研究，甚少涉及算法开发规律研究；或构建模块库由用户手工选取、调整和修改，开发结果不理想。本项目受生成式程序设计思想启发，以形式化方法PAR为基础，综合运用抽象、演绎、泛型等相关方法和机制，探索面向效率的算法演算法则/策略，形式化构建Ba-DP专用语言、抽象算法框架、算法生成模型等，并拓展PAR平台以支持构件装配的算法构造，不仅为提高Ba-DP算法质量和开发效率提供有效的方法、技术和工具支持，构件组装的灵活性与可配置性也将为发现和产生新算法提供有效手段。本研究可望为Ba域高效算法构造探索一条新途径。

由于生物序列分析（Biological sequence Analysis, Ba）问题域的非平凡性，Ba算法的运行效率、开发效率和可靠性难以得到保证。受生成式程序设计思想启发，本项目以PAR方法和课题组在生物信息学领域的研究为基础，运用抽象、演绎、构件等相关技术、方法和机制，研究高可靠Ba动态规划算法的有效构造问题。主要研究工作包括：（1）算法构造方法学研究。分析生成式程序设计方法学的“以系统族为建模核心”的思想，剖析形式化方法PAR设计和实现生物序列分析领域算法的机理，进而探索和实践将该方法学应用于Ba算法自动构造的过程。（2）Ba领域算法模型研究。寻找高效Ba-DP算法开发的特征及规律；刻画和提炼生物序列分析领域双序列比对、多序列比对、序列拼接等几类算法的共性特征，形式化构建泛型Ba抽象框架；在建立该算法领域的特征模型以及对应算法构件交互模型基础上，设计算法构件；进一步研究和分析Apla语言泛型程序设计机制，使用PAR方法和高可靠PAR平台形式化开发构件的高可靠实现；建立泛型约束下经抽象Ba算法框架和算子构件装配，构造特定Ba算法的生成模型。（3）构建序列比对算法构件装配平台，提供了在线构件装配和直接进行相关比对的功能，简化了构件组装的操作难度，便于研究人员对算法进行维护和优化，有助于生物信息学中基本算法的推广和普及。同时，既有利于资深用户快速选择适合自己数据的独特组合方法，也有利于新手从多个层面选择，以达到其对问题本质的各种层面的深度认识。. 本项目已取得预期研究成果，共发表学术论文10篇，其中SCI检索4篇，EI检索1篇；出版学术专著2部，获软件著作权6项。培养硕士研究生11名（毕业硕士4名、在读7名），协助培养博士研究生1名（在读1名）。