收藏切换
Unified Formal Construction and Isabelle Verification of the Dynamic Programming Algorithms for Biological Sequence Alignment
收藏切换
Haihe Shi1, Sunwen Lan1, Riming Liu1, Haipeng Shi2, *, Lan Wang1, Linhui Zhong1
Journal of Computer Research and Development | 2025, 62(1) : 119 - 131
Less
收藏切换
Journal of Computer Research and Development | 2025, 62(1): 119-131
• Artificial Intelligence •
Unified Formal Construction and Isabelle Verification of the Dynamic Programming Algorithms for Biological Sequence Alignment
Full
Haihe Shi1, Sunwen Lan1, Riming Liu1, Haipeng Shi2, *, Lan Wang1, Linhui Zhong1
Affiliations
  • 1School of Computer Information Engineering, Jiangxi Normal University, Nanchang 330022
  • 2School of Software, Jiangxi Normal University, Nanchang 330022
  • born in 1979. PhD, professor, PhD supervisor. Senior member of CCF. Her main research interests include formal method, bioinformatics, and software engineering

    born in 1999. Master. Student member of CCF. His main research interest includes formal method

    born in 1998. Master. Student member of CCF. His main research interest includes formal method

    born in 1977. PhD, associate professor, master supervisor. Member of CCF. Her main research interests include algorithm design and software engineering

    born in 1974. Master, associate professor. Member of CCF. Her main research interests include algorithms and data structures, bioinformatics, and principles of compliers

    born in 1974. PhD, associate professor, master supervisor. Member of CCF. His main research interests include software architecture, component-based software development, and software evolution and maintenance

About Author:

born in 1979. PhD, professor, PhD supervisor. Senior member of CCF. Her main research interests include formal method, bioinformatics, and software engineering

born in 1999. Master. Student member of CCF. His main research interest includes formal method

born in 1998. Master. Student member of CCF. His main research interest includes formal method

born in 1977. PhD, associate professor, master supervisor. Member of CCF. Her main research interests include algorithm design and software engineering

born in 1974. Master, associate professor. Member of CCF. Her main research interests include algorithms and data structures, bioinformatics, and principles of compliers

born in 1974. PhD, associate professor, master supervisor. Member of CCF. His main research interests include software architecture, component-based software development, and software evolution and maintenance

Published: 2025-01-01 doi: 10.7544/issn1000-1239.202330698
Outline
收藏切换

Sequence alignment is a classical problem in biological sequence analysis, aiming to find out the similarity between sequences, which is of great significance for discovering functional, structural and evolutionary information in biological sequences. The problem can be divided into two categories: pairwise sequence alignment and multiple sequence alignment. The existing work is focused on specific algorithms, and no general solution is designed. In addition, there are few researches on the trustworthy of algorithms. By deeply analyzing the properties of sequence alignment problem and describing the essential characteristics of problem solving, a unified construction framework of sequence alignment dynamic programming algorithm seqAlign is designed based on the problem formal specification and formal method PAR. The process of constructing a multiple sequence alignment algorithm with three sequences by using the framework is further demonstrated, and the constructed results are formally verified by Isabelle theorem prover. Finally, the C++ executable program of the algorithm is generated by the code generation system of PAR platform. The process of mechanized construction of other sequence alignment algorithms using seqAlign framework is analyzed. Through strict specification refinement and formal verification, the reliability of the generated algorithm is effectively guaranteed. The developed seqAlign framework provides a general solution for the class of sequence alignment problems, which significantly improves the efficiency of generating sequence alignment algorithm families. The successful application of the designed seqAlign framework to sequence alignment problem in biological sequence analysis can provide a reference for the construction of highly reliable algorithms in complex bioinformatics field from the perspective of methodology and practice.

sequence alignment  /  PAR method  /  formal construction  /  Isabelle theorem prover
石海鹤, 蓝孙文, 刘日明, 石海鹏, 王岚, 钟林辉. 生物序列比对动态规划算法的统一形式化构造与Isabelle验证. 计算机研究与发展, 2025 , 62 (1) : 119 -131 . DOI: 10.7544/issn1000-1239.202330698
Haihe Shi, Sunwen Lan, Riming Liu, Haipeng Shi, Lan Wang, Linhui Zhong. Unified Formal Construction and Isabelle Verification of the Dynamic Programming Algorithms for Biological Sequence Alignment[J]. Journal of Computer Research and Development, 2025 , 62 (1) : 119 -131 . DOI: 10.7544/issn1000-1239.202330698
Year 2025 volume 62 Issue 1
126
58
Cite this Article
BibTeX
Article Info
doi: 10.7544/issn1000-1239.202330698
  • Receive Date:2023-08-23
  • Online Date:2026-11-10
  • Published:2025-01-01
Article Data
Affiliations
History
  • Received:2023-08-23
  • Revised:2024-01-22
Affiliations
    1School of Computer Information Engineering, Jiangxi Normal University, Nanchang 330022
    2School of Software, Jiangxi Normal University, Nanchang 330022
References
Share
https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/10.7544/issn1000-1239.202330698
Share to
QR

Scan QR to access full text

Cite this article
BibTeX
Citations
表12种不同金属材料的力学参数
科
Family
属数
Number of
genus
种数
Number of
species
占总种数比例
Percentage of
total species (%)
属
Genus
种数
Number of
species
占总种数比例
Percentage of total
species (%)
鹅膏菌科Amanitaceae 2 11 5.26 鹅膏菌属 Amanita 10 4.78
小菇科 Mycenaceae 2 12 5.74 丝盖伞属 Inocybe 5 2.39
多孔菌科 Polyporaceae 8 14 6.70 蜡蘑属 Laccaria 5 2.39
红菇科 Russulaceae 3 23 11.00 小皮伞属 Marasmius 6 2.87
小菇属 Mycena 11 5.26
光柄菇属 Pluteus 5 2.39
红菇属 Russula 17 8.13
栓菌属 Trametes 5 2.39
关闭全屏
  • BibTeX
  • EndNote
  • RefWorks
  • TxT