Article(id=1327011868515873641, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1327011511924535414, articleNumber=null, orderNo=null, doi=10.7544/issn1000-1239.202330698, pmid=null, cstr=null, oa=null, hot=null, price=null, onlineType=0, articleFormat=0, articleType=null, articleTypeStr=research-article, receivedDate=1692720000000, receivedDateStr=2023-08-23, revisedDate=1705852800000, revisedDateStr=2024-01-22, acceptedDate=null, acceptedDateStr=null, onlineDate=1794313884142, onlineDateStr=2026-11-10, pubDate=1735660800000, pubDateStr=2025-01-01, doiRegisterDate=null, doiRegisterDateStr=null, onlineIssueDate=1794313884142, onlineIssueDateStr=2026-11-10, onlineJustAcceptDate=null, onlineJustAcceptDateStr=null, onlineFirstDate=null, onlineFirstDateStr=null, sourceXml=null, magXml=null, createTime=1794313884142, creator=13701087609, updateTime=1794313884142, updator=13701087609, issue=Issue{id=1327011511924535414, tenantId=1146029695717560320, journalId=1324759914146529478, year='2025', volume='62', issue='1', pageStart='1', pageEnd='283', issueExtLink='null', onlineDate='null', pubDate='1735660800000', pubDateStr='2025-01-01', beforeIssueId=null, nextIssueId=null, price=null, status=1, issueComplete=1, articleOrder=1, issueType=-1, specialIssue=null, createTime=1794313799123, creator='13701087609', updateTime=1794376660021, updator='13701087609', preIssue=null, nextIssue=null, articleTotal=null, ext={EN=IssueExt(id=1327275170160554491, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1327011511924535414, language=EN, specialIssueTitle=, coverIllustrator=null, specialIssueEditor=, specialIssueAbout=), CN=IssueExt(id=1327275170160554492, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1327011511924535414, language=CN, specialIssueTitle=, coverIllustrator=null, specialIssueEditor=, specialIssueAbout=)}, issueFiles=null, downloadFileDto=null}, startPage=119, endPage=131, ext={EN=ArticleExt(id=1327011870235538282, articleId=1327011868515873641, tenantId=1146029695717560320, journalId=1324759914146529478, language=EN, title=Unified Formal Construction and Isabelle Verification of the Dynamic Programming Algorithms for Biological Sequence Alignment, columnId=1325489891789910943, journalTitle=Journal of Computer Research and Development, columnName=Artificial Intelligence, runingTitle=null, highlight=null, articleAbstract=

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.

, authors=Haihe Shi1, Sunwen Lan1, Riming Liu1, Haipeng Shi2, *, Lan Wang1, Linhui Zhong1, authorsList=Haihe Shi, Sunwen Lan, Riming Liu, Haipeng Shi, Lan Wang, Linhui Zhong, authorCompany=null, correspAuthors=Haipeng Shi, authorNote=

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

, correspAuthorsNote=null, copyrightStatement=Copyright © 2025 Journal of Computer Research and Development. All rights reserved., copyrightOwner=null, extLink=null, articleAbsUrl=null, sourceXml=null, magXml=null, pdfUrl=null, pdf=null, pdfFileSize=null, pdfExtLink=null, richHtmlUrl=null, mobilePdfUrl=null, reviewReport=null, pdfFirstPage=null, abstractGraph=null, abstractGraphContent=null, abstractVideo=null, citation=null, cebUrl=null, magXmlContent=null, mapNumber=null, fund=null), CN=ArticleExt(id=1327011872911504264, articleId=1327011868515873641, tenantId=1146029695717560320, journalId=1324759914146529478, language=CN, title=生物序列比对动态规划算法的统一形式化构造与Isabelle验证, columnId=1325489892104483745, journalTitle=计算机研究与发展, columnName=人工智能, runingTitle=null, highlight=null, articleAbstract=

序列比对是生物序列分析中的一个经典问题,旨在找出序列之间的相似性,它对于发现生物序列中的功能、结构和进化信息都具有重要的意义. 该问题可分为双序列比对和多序列比对2类,现有工作多针对特定算法展开,没有设计通用的求解方法;此外,甚少涉及算法可信性的研究. 从生物序列比对问题的形式化规约出发,通过深入分析问题的性质,刻画问题求解的本质特征,借助形式化方法PAR(partition and recursion)设计了序列比对动态规划算法的统一构造框架seqAlign;展示了应用该框架构造序列数为3的多序列比对算法的过程,并使用Isabelle定理证明器对构造结果进行形式化验证;利用PAR平台生成了该算法的C++可执行程序,进一步分析了由seqAlign框架机械化构造其他类型序列比对算法的过程. 通过严密的规约精化和形式验证,有效地保证了生成算法的可信性;开发的seqAlign框架提供了序列比对问题类的通用求解方案,显著提高了序列比对算法族生成的效率. 研究结果在生物序列分析中序列比对问题上的成功应用,从方法学和实践上可为复杂生物信息学领域高可靠算法的构造提供参考.

, authors=石海鹤1, 蓝孙文1, 刘日明1, 石海鹏2, *, 王岚1, 钟林辉1, authorsList=石海鹤, 蓝孙文, 刘日明, 石海鹏, 王岚, 钟林辉, authorCompany=null, correspAuthors=石海鹏, authorNote=

1979年生. 博士,教授,博士生导师. CCF高级会员. 主要研究方向为形式化方法、生物信息学、软件工程

1999年生. 硕士. CCF学生会员. 主要研究方向为形式化方法

1998年生. 硕士. CCF学生会员. 主要研究方向为形式化方法

1977年生. 博士,副教授,硕士生导师. CCF会员. 主要研究方向为算法设计、软件工程

1974年生. 硕士,副教授. CCF会员. 主要研究方向为算法和数据结构、生物信息学、编译原理

1974年生. 博士,副教授,硕士生导师. CCF会员. 主要研究方向为软件体系结构、构件化软件开发、软件演化与维护

, correspAuthorsNote=
石海鹏()
, copyrightStatement=版权所有 © 2025 计算机研究与发展编辑部, copyrightOwner=null, extLink=null, articleAbsUrl=null, sourceXml=uv7gCqJUh0iADAgbHKltdQ==, magXml=vjj+Fd24xKbSxEjuig5dXg==, pdfUrl=null, pdf=JmVCmpEVUsXkasNsJny8OQ==, pdfFileSize=1326467, pdfExtLink=null, richHtmlUrl=null, mobilePdfUrl=null, reviewReport=null, pdfFirstPage=null, abstractGraph=QJr/VT5MxaKpqfROlcIFzw==, abstractGraphContent=null, abstractVideo=null, citation=null, cebUrl=null, magXmlContent=u3prVKYbmPfNcehDJtS36w==, mapNumber=null, fund=null)}, authors=[Author(id=1327012141636367223, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, orderNo=0, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=haiheshi@jxnu.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327012141850276729, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, authorId=1327012141636367223, language=EN, stringName=Haihe Shi, firstName=Haihe, middleName=null, lastName=Shi, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1School of Computer Information Engineering, Jiangxi Normal University, Nanchang 330022, bio={"content":"

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

"}, bioImg=null, bioContent=

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

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012141980300154, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, authorId=1327012141636367223, language=CN, stringName=石海鹤, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1江西师范大学计算机信息工程学院 南昌 330022, bio={"img":"p94Y18+l2Qldk8a3XAxRPA==","content":"

1979年生. 博士,教授,博士生导师. CCF高级会员. 主要研究方向为形式化方法、生物信息学、软件工程

"}, bioImg=p94Y18+l2Qldk8a3XAxRPA==, bioContent=

1979年生. 博士,教授,博士生导师. CCF高级会员. 主要研究方向为形式化方法、生物信息学、软件工程

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327012141258879856, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, xref=1, ext=[AuthorCompanyExt(id=1327012141267268465, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, companyId=1327012141258879856, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer Information Engineering, Jiangxi Normal University, Nanchang 330022), AuthorCompanyExt(id=1327012141296628594, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, companyId=1327012141258879856, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1江西师范大学计算机信息工程学院 南昌 330022)])]), Author(id=1327012142139683709, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, orderNo=1, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327012142332621695, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, authorId=1327012142139683709, language=EN, stringName=Sunwen Lan, firstName=Sunwen, middleName=null, lastName=Lan, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1School of Computer Information Engineering, Jiangxi Normal University, Nanchang 330022, bio={"content":"

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

"}, bioImg=null, bioContent=

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

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012142529753984, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, authorId=1327012142139683709, language=CN, stringName=蓝孙文, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1江西师范大学计算机信息工程学院 南昌 330022, bio={"img":"o0klePoS8LejcZ+LPx7+Zw==","content":"

1999年生. 硕士. CCF学生会员. 主要研究方向为形式化方法

"}, bioImg=o0klePoS8LejcZ+LPx7+Zw==, bioContent=

1999年生. 硕士. CCF学生会员. 主要研究方向为形式化方法

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327012141258879856, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, xref=1, ext=[AuthorCompanyExt(id=1327012141267268465, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, companyId=1327012141258879856, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer Information Engineering, Jiangxi Normal University, Nanchang 330022), AuthorCompanyExt(id=1327012141296628594, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, companyId=1327012141258879856, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1江西师范大学计算机信息工程学院 南昌 330022)])]), Author(id=1327012142651388802, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, orderNo=2, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327012142768829316, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, authorId=1327012142651388802, language=EN, stringName=Riming Liu, firstName=Riming, middleName=null, lastName=Liu, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1School of Computer Information Engineering, Jiangxi Normal University, Nanchang 330022, bio={"content":"

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

"}, bioImg=null, bioContent=

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

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012142907241349, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, authorId=1327012142651388802, language=CN, stringName=刘日明, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1江西师范大学计算机信息工程学院 南昌 330022, bio={"img":"TbRaajfNH4J3FHA30Ie3zw==","content":"

1998年生. 硕士. CCF学生会员. 主要研究方向为形式化方法

"}, bioImg=TbRaajfNH4J3FHA30Ie3zw==, bioContent=

1998年生. 硕士. CCF学生会员. 主要研究方向为形式化方法

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327012141258879856, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, xref=1, ext=[AuthorCompanyExt(id=1327012141267268465, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, companyId=1327012141258879856, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer Information Engineering, Jiangxi Normal University, Nanchang 330022), AuthorCompanyExt(id=1327012141296628594, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, companyId=1327012141258879856, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1江西师范大学计算机信息工程学院 南昌 330022)])]), Author(id=1327012143045653383, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, orderNo=3, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=option2001@jxnu.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=1, authorType=1, ext={EN=AuthorExt(id=1327012143234397065, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, authorId=1327012143045653383, language=EN, stringName=Haipeng Shi, firstName=Haipeng, middleName=null, lastName=Shi, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=2, *, address=2School of Software, Jiangxi Normal University, Nanchang 330022, bio={"content":"

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

"}, bioImg=null, bioContent=

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

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012143431529354, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, authorId=1327012143045653383, language=CN, stringName=石海鹏, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=2, *, address=2江西师范大学软件学院 南昌 330022, bio={"img":"t7/wEvpbYBXar0YC/6fYdA==","content":"

1977年生. 博士,副教授,硕士生导师. CCF会员. 主要研究方向为算法设计、软件工程

"}, bioImg=t7/wEvpbYBXar0YC/6fYdA==, bioContent=

1977年生. 博士,副教授,硕士生导师. CCF会员. 主要研究方向为算法设计、软件工程

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327012141506343795, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, xref=2, ext=[AuthorCompanyExt(id=1327012141539898228, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, companyId=1327012141506343795, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2School of Software, Jiangxi Normal University, Nanchang 330022), AuthorCompanyExt(id=1327012141544092533, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, companyId=1327012141506343795, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2江西师范大学软件学院 南昌 330022)])]), Author(id=1327012143532192652, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, orderNo=4, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327012143683187598, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, authorId=1327012143532192652, language=EN, stringName=Lan Wang, firstName=Lan, middleName=null, lastName=Wang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1School of Computer Information Engineering, Jiangxi Normal University, Nanchang 330022, bio={"content":"

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

"}, bioImg=null, bioContent=

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

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012143800628111, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, authorId=1327012143532192652, language=CN, stringName=王岚, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1江西师范大学计算机信息工程学院 南昌 330022, bio={"img":"E9fq8va5rJhM52iymSHxzQ==","content":"

1974年生. 硕士,副教授. CCF会员. 主要研究方向为算法和数据结构、生物信息学、编译原理

"}, bioImg=E9fq8va5rJhM52iymSHxzQ==, bioContent=

1974年生. 硕士,副教授. CCF会员. 主要研究方向为算法和数据结构、生物信息学、编译原理

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327012141258879856, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, xref=1, ext=[AuthorCompanyExt(id=1327012141267268465, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, companyId=1327012141258879856, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer Information Engineering, Jiangxi Normal University, Nanchang 330022), AuthorCompanyExt(id=1327012141296628594, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, companyId=1327012141258879856, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1江西师范大学计算机信息工程学院 南昌 330022)])]), Author(id=1327012143905485713, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, orderNo=5, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327012144018731923, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, authorId=1327012143905485713, language=EN, stringName=Linhui Zhong, firstName=Linhui, middleName=null, lastName=Zhong, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1School of Computer Information Engineering, Jiangxi Normal University, Nanchang 330022, bio={"content":"

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

"}, bioImg=null, bioContent=

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

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012144173921172, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, authorId=1327012143905485713, language=CN, stringName=钟林辉, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1江西师范大学计算机信息工程学院 南昌 330022, bio={"img":"F4HOfUbPB+fIzXwbi1Sqmw==","content":"

1974年生. 博士,副教授,硕士生导师. CCF会员. 主要研究方向为软件体系结构、构件化软件开发、软件演化与维护

"}, bioImg=F4HOfUbPB+fIzXwbi1Sqmw==, bioContent=

1974年生. 博士,副教授,硕士生导师. CCF会员. 主要研究方向为软件体系结构、构件化软件开发、软件演化与维护

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327012141258879856, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, xref=1, ext=[AuthorCompanyExt(id=1327012141267268465, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, companyId=1327012141258879856, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer Information Engineering, Jiangxi Normal University, Nanchang 330022), AuthorCompanyExt(id=1327012141296628594, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, companyId=1327012141258879856, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1江西师范大学计算机信息工程学院 南昌 330022)])])], keywords=[Keyword(id=1327012144320721813, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, language=EN, orderNo=1, keyword=sequence alignment), Keyword(id=1327012144396219286, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, language=EN, orderNo=2, keyword=PAR method), Keyword(id=1327012144488493975, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, language=EN, orderNo=3, keyword=formal construction), Keyword(id=1327012144559797144, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, language=EN, orderNo=4, keyword=Isabelle theorem prover), Keyword(id=1327012144618517401, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, language=CN, orderNo=1, keyword=序列比对), Keyword(id=1327012144702403482, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, language=CN, orderNo=2, keyword=PAR方法), Keyword(id=1327012144786289564, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, language=CN, orderNo=3, keyword=形式构造), Keyword(id=1327012144878564253, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, language=CN, orderNo=4, keyword=Isabelle定理证明器)], refs=[Reference(id=1327012146455622574, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=1, rfOrder=0, authorNames=null, journalName=null, refType=null, unstructuredReference=詹乃军,王戟. 复杂系统规约、分析与验证发展现状与展望[J]. 前瞻科技,2023,2(1):7−22, articleTitle=null, refAbstract=null), Reference(id=1327012146535314351, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=1, rfOrder=1, authorNames=null, journalName=null, refType=null, unstructuredReference=Zhan Naijun, Wang Ji. Challenges and trends for specification, analysis, and verification of complex systems[J]. Science and Technology Foresight, 2023, 2(1): 7−22 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1327012146610811824, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=2, rfOrder=2, authorNames=null, journalName=null, refType=null, unstructuredReference=Hoare T. The verifying compiler: A grand challenge for computing research[J]. Journal of the ACM, 2003, 50(1): 63−69, articleTitle=null, refAbstract=null), Reference(id=1327012146740835249, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=3, rfOrder=3, authorNames=null, journalName=null, refType=null, unstructuredReference=王勇献. 生物信息学导论:面向高性能计算的算法与应用[M]. 北京:清华大学出版社,2011, articleTitle=null, refAbstract=null), Reference(id=1327012146833109938, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=3, rfOrder=4, authorNames=null, journalName=null, refType=null, unstructuredReference=Wang Yongxian. Introduction to Bioinformatics: Algorithms and Applications for High Performance Computing [M]. Beijing: Tsinghua University Press, 2011 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1327012146929578931, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=4, rfOrder=5, authorNames=null, journalName=null, refType=null, unstructuredReference=Needleman S B, Wunsch C D. A general method applicable to the search for similarities in the amino acid sequence of two proteins[J]. Journal of Molecular Biology, 1970, 48(3): 443−453, articleTitle=null, refAbstract=null), Reference(id=1327012146996687796, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=5, rfOrder=6, authorNames=null, journalName=null, refType=null, unstructuredReference=Smith T F, Waterman M S. Identification of common molecular subsequences.[J]. Journal of Molecular Biology, 1981, 147(1): 195−197, articleTitle=null, refAbstract=null), Reference(id=1327012147055408053, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=6, rfOrder=7, authorNames=null, journalName=null, refType=null, unstructuredReference=Garai G, Chowdhury B. A cascaded pairwise biomolecular sequence alignment technique using evolutionary algorithm[J]. Information Sciences, 2015, 297(3): 118−139, articleTitle=null, refAbstract=null), Reference(id=1327012147114128311, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=7, rfOrder=8, authorNames=null, journalName=null, refType=null, unstructuredReference=Alawneh L, Shehab M A, Al-Ayyoub M, et al. A scalable multiple pairwise protein sequence alignment acceleration using hybrid CPU–GPU approach[J]. Cluster Computing, 2020, 23(7): 2677−2688, articleTitle=null, refAbstract=null), Reference(id=1327012147177042872, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=8, rfOrder=9, authorNames=null, journalName=null, refType=null, unstructuredReference=Rashed A E E D, Obaya M, El H, et al. Accelerating DNA pairwise sequence alignment using FPGA and a customized convolutional neural network[J]. Computers & Electrical Engineering, 2021, 92(6): 1−21, articleTitle=null, refAbstract=null), Reference(id=1327012147244151737, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=9, rfOrder=10, authorNames=null, journalName=null, refType=null, unstructuredReference=Song Y J, Ji D J, Seo H, et al. Pairwise heuristic sequence alignment algorithm based on deep reinforcement learning[J]. IEEE Open Journal of Engineering in Medicine and Biology, 2021, 2: 36−43, articleTitle=null, refAbstract=null), Reference(id=1327012147302871994, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=10, rfOrder=11, authorNames=null, journalName=null, refType=null, unstructuredReference=Clustal W, Thompson J D, Higgins D G, et al. Improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice[J]. Nucleic Acids Research, 1994, 22(22): 4673−4680, articleTitle=null, refAbstract=null), Reference(id=1327012147369980859, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=11, rfOrder=12, authorNames=null, journalName=null, refType=null, unstructuredReference=Katoh K, Misawa K, Kuma K, et al. MAFFT: A novel method for rapid multiple sequence alignment based on fast Fourier transform[J]. Nucleic Acids Research, 2002, 30(14): 3059−3066, articleTitle=null, refAbstract=null), Reference(id=1327012147432895420, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=12, rfOrder=13, authorNames=null, journalName=null, refType=null, unstructuredReference=Edgar R C. MUSCLE: Multiple sequence alignment with high accuracy and high throughput[J]. Nucleic Acids Research, 2004, 32(5): 1792−1797, articleTitle=null, refAbstract=null), Reference(id=1327012147491615677, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=13, rfOrder=14, authorNames=null, journalName=null, refType=null, unstructuredReference=Abuín J M, Pena T F, Pichel J C. PASTASpark: Multiple sequence alignment meets big data[J]. Bioinformatics, 2017, 33(18): 2948−2950, articleTitle=null, refAbstract=null), Reference(id=1327012147554530238, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=14, rfOrder=15, authorNames=null, journalName=null, refType=null, unstructuredReference=Wan Shixiang, Zou Quan. HAlign-II: Efficient ultra-large multiple sequence alignment and phylogenetic tree reconstruction with distributed and parallel computing[J]. Algorithms for Molecular Biology, 2017, 12(1): 1−10, articleTitle=null, refAbstract=null), Reference(id=1327012147613250495, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=15, rfOrder=16, authorNames=null, journalName=null, refType=null, unstructuredReference=Smirnov V, Warnow T. MAGUS: Multiple sequence alignment using graph clustering[J]. Bioinformatics, 2021, 37(12): 1666−1672, articleTitle=null, refAbstract=null), Reference(id=1327012147789411264, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=16, rfOrder=17, authorNames=null, journalName=null, refType=null, unstructuredReference=Mirarab S, Nguyen N, Guo Sheng, et al. PASTA: Ultra-large multiple sequence alignment for nucleotide and amino-acid sequences.[J]. Journal of Computational Biology: A Journal of Computational Molecular Cell Biology, 2015, 22(5): 377−386, articleTitle=null, refAbstract=null), Reference(id=1327012147906851777, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=17, rfOrder=18, authorNames=null, journalName=null, refType=null, unstructuredReference=王戟,詹乃军,冯新宇,等. 形式化方法概貌[J]. 软件学报,2019,30(1):33−61, articleTitle=null, refAbstract=null), Reference(id=1327012147982349250, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=17, rfOrder=19, authorNames=null, journalName=null, refType=null, unstructuredReference=Wang Ji, Zhan Naijun, Feng Xinyu, et al. Overview formalization method[J]. Journal of Software, 2019, 30(1): 33−61 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1327012148053652419, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=18, rfOrder=20, authorNames=null, journalName=null, refType=null, unstructuredReference=Xue Jinyun. A unified approach for developing efficient algorithmic programs[J]. Journal of computer Science and Technology, 1997, 12(4): 314−329, articleTitle=null, refAbstract=null), Reference(id=1327012148120761284, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=19, rfOrder=21, authorNames=null, journalName=null, refType=null, unstructuredReference=Durán J E. Transformational derivation of greedy network algorithms from descriptive specifications[C]// Proc of the 6th Int Conf on Mathematics of Program Construction. Beilin: Springer, 2002: 40−67, articleTitle=null, refAbstract=null), Reference(id=1327012148372419525, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=20, rfOrder=22, authorNames=null, journalName=null, refType=null, unstructuredReference=Abrial J R, Cansell D, Méry D. Formal derivation of spanning trees algorithms[C]// Proc of the 3rd Int Conf of B and Z Users. Berlin: Springer, 2003: 457−476, articleTitle=null, refAbstract=null), Reference(id=1327012148527608774, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=21, rfOrder=23, authorNames=null, journalName=null, refType=null, unstructuredReference=Almeida J B, Pinto J S. Deriving sorting algorithms[J]. arXiv preprint, arXiv: 0802.3881, 2008, articleTitle=null, refAbstract=null), Reference(id=1327012148628272071, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=22, rfOrder=24, authorNames=null, journalName=null, refType=null, unstructuredReference=Nedunuri S, Cook W R. Synthesis of fast programs for maximum segment sum problems[J]. ACM SIGPLAN Notices, 2009, 45(2): 117−126, articleTitle=null, refAbstract=null), Reference(id=1327012148699575240, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=23, rfOrder=25, authorNames=null, journalName=null, refType=null, unstructuredReference=Mu S C. Calculating a backtracking algorithm: An exercise in monadic program derivation[J]. arXiv preprint, arXiv: 2101.09409, 2021, articleTitle=null, refAbstract=null), Reference(id=1327012148796044233, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=24, rfOrder=26, authorNames=null, journalName=null, refType=null, unstructuredReference=Lammich P. Generating verified LLVM from Isabelle/HOL[C]// Proc of the 10th Int Conf on Interactive Theorem Proving (ITP 2019). Berlin: Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2019, 22: 1−22: 19, articleTitle=null, refAbstract=null), Reference(id=1327012148896707530, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=25, rfOrder=27, authorNames=null, journalName=null, refType=null, unstructuredReference=张健,李弋,彭鑫,等. 正反例归纳合成SQL查询程序[J]. 软件学报,2023,34(9):4132−4152, articleTitle=null, refAbstract=null), Reference(id=1327012149039313867, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=25, rfOrder=28, authorNames=null, journalName=null, refType=null, unstructuredReference=Zhang Jian, Li Yi, Peng Xin, et al. Inductive SQL synthesis with positive and negative tuples[J]. Journal of Software, 2023, 34(9): 4132−4152 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1327012149144171468, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=26, rfOrder=29, authorNames=null, journalName=null, refType=null, unstructuredReference=石海鹤,薛锦云. 基于PAR的算法形式化开发[J]. 计算机学报,2009,32(5):982−991, articleTitle=null, refAbstract=null), Reference(id=1327012149223863245, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=26, rfOrder=30, authorNames=null, journalName=null, refType=null, unstructuredReference=Shi Haihe, Xue Jinyun. PAR-based formal development of algorithms[J]. Chinese Journal of Computers, 2009, 32(5): 982−991 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1327012149349692366, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=27, rfOrder=31, authorNames=null, journalName=null, refType=null, unstructuredReference=孙凌宇,薛锦云. 最小生成树算法的PAR方法形式化推导[J]. 计算机工程,2006,32(21):85−87, articleTitle=null, refAbstract=null), Reference(id=1327012149475521487, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=27, rfOrder=32, authorNames=null, journalName=null, refType=null, unstructuredReference=Sun Lingyu, Xue Jinyun. Formal derivation of the minimum spanning tree algorithm with PAR method[J]. Computer Engineering, 2006, 32(21): 85−87 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1327012149605544912, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=28, rfOrder=33, authorNames=null, journalName=null, refType=null, unstructuredReference=游珍,薛锦云. 基于Isabelle定理证明器算法程序的形式化验证[J]. 计算机工程与科学,2009,31(10):85−89, articleTitle=null, refAbstract=null), Reference(id=1327012149676848081, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=28, rfOrder=34, authorNames=null, journalName=null, refType=null, unstructuredReference=You Zhen, Xue Jinyun. Formal verification of algorithmic programs based on the Isabelle theorem prover[J]. Computer Engineering and Science, 2009, 31(10): 85−89 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1327012149827843027, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=29, rfOrder=35, authorNames=null, journalName=null, refType=null, unstructuredReference=石海鹤,周卫星. 基于动态规划的双序列比对算法构件设计与实现[J]. 计算机研究与发展,2019,56(9):1907−1917, articleTitle=null, refAbstract=null), Reference(id=1327012149983032276, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=29, rfOrder=36, authorNames=null, journalName=null, refType=null, unstructuredReference=Shi Haihe, Zhou Weixing. Design and implementation of pairwise sequence alignment algorithm components based on dynamic programming[J]. Journal of Computer Research and Development, 2019, 56(9): 1907−1917 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1327012150259856341, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=30, rfOrder=37, authorNames=null, journalName=null, refType=null, unstructuredReference=Shi Haipeng, Chen Huan, Yang Qinghong, et al. A method for bio-sequence analysis algorithm development based on the PAR platform[J]. Big Data Mining and Analytics, 2023, 6(1): 11−20, articleTitle=null, refAbstract=null), Reference(id=1327012150385685462, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=31, rfOrder=38, authorNames=null, journalName=null, refType=null, unstructuredReference=肖存威,石海鹤,王岚,等. 基于混合策略的de novo序列拼接算法构造[J]. 江西师范大学学报:自然科学版,2022,46(3):300−307, articleTitle=null, refAbstract=null), Reference(id=1327012150566040536, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=31, rfOrder=39, authorNames=null, journalName=null, refType=null, unstructuredReference=Xiao Cunwei, Shi Haihe, Wang Lan, et al. The construction of de novo sequence assembly algorithm based on hybrid strategy[J]. Journal of Jiangxi Normal University: Natural Science, 2022, 46(3): 300−307 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1327012150721229785, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=32, rfOrder=40, authorNames=null, journalName=null, refType=null, unstructuredReference=Dijkstra E W. A Discipline of Programming[M]. Princeton, NJ: Prentice-hall, 1976, articleTitle=null, refAbstract=null), Reference(id=1327012150863836122, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=33, rfOrder=41, authorNames=null, journalName=null, refType=null, unstructuredReference=Floyd R W. Assigning meaning to programs[J]. Communications of the ACM, 1967, 10(8): 365−371, articleTitle=null, refAbstract=null), Reference(id=1327012150977082331, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=34, rfOrder=42, authorNames=null, journalName=null, refType=null, unstructuredReference=Hoare C A R. An axiomatic basis for computer programming[J]. Communications of the ACM, 1969, 12(10): 576−580, articleTitle=null, refAbstract=null), Reference(id=1327012151161631708, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=35, rfOrder=43, authorNames=null, journalName=null, refType=null, unstructuredReference=Dijkstra E W, Scholten C S. Predicate Calculus and Program Semantics[M]. Berlin: Springer, 2012, articleTitle=null, refAbstract=null), Reference(id=1327012151312626653, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=36, rfOrder=44, authorNames=null, journalName=null, refType=null, unstructuredReference=石海鹤. 支持泛型程序设计的Apla-Java自动程序转换系统[D]. 南昌:江西师范大学,2004, articleTitle=null, refAbstract=null), Reference(id=1327012151560090590, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=36, rfOrder=45, authorNames=null, journalName=null, refType=null, unstructuredReference=Shi Haihe. Apla-Java automatic program transformation system supporting generic programming [D]. Nanchang: Jiangxi Normal University, 2004 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1327012151694308319, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=37, rfOrder=46, authorNames=null, journalName=null, refType=null, unstructuredReference=赖勇. APLA到C++自动程序转换系统的研制[D]. 南昌:江西师范大学,2002, articleTitle=null, refAbstract=null), Reference(id=1327012151765611488, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=37, rfOrder=47, authorNames=null, journalName=null, refType=null, unstructuredReference=Lai Yong. Development of APLA to C++ automatic program conversion system [D]. Nanchang: Jiangxi Normal University, 2002 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1327012151924995041, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=38, rfOrder=48, authorNames=null, journalName=null, refType=null, unstructuredReference=Xue Jinyun. Two new strategies for developing loop invariants and their applications[J]. Journal of Computer Science and Technology, 1993, 8(2): 147−154, articleTitle=null, refAbstract=null)], funds=null, companyList=[AuthorCompany(id=1327012141258879856, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, xref=1, ext=[AuthorCompanyExt(id=1327012141267268465, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, companyId=1327012141258879856, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer Information Engineering, Jiangxi Normal University, Nanchang 330022), AuthorCompanyExt(id=1327012141296628594, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, companyId=1327012141258879856, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1江西师范大学计算机信息工程学院 南昌 330022)]), AuthorCompany(id=1327012141506343795, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, xref=2, ext=[AuthorCompanyExt(id=1327012141539898228, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, companyId=1327012141506343795, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2School of Software, Jiangxi Normal University, Nanchang 330022), AuthorCompanyExt(id=1327012141544092533, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, companyId=1327012141506343795, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2江西师范大学软件学院 南昌 330022)])], figs=[ArticleFig(id=1327012145096668062, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, language=EN, label=Figure 1, caption=Development flowchart of highly reliable algorithm based on PAR, figureFileSmall=uytekr0b1oBUot8aTI5xzQ==, figureFileBig=QJr/VT5MxaKpqfROlcIFzw==, tableContent=null), ArticleFig(id=1327012145159582623, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, language=CN, label=图1, caption=基于PAR的高可靠算法开发流程图, figureFileSmall=uytekr0b1oBUot8aTI5xzQ==, figureFileBig=QJr/VT5MxaKpqfROlcIFzw==, tableContent=null), ArticleFig(id=1327012145260245920, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, language=EN, label=Figure 2, caption=Sample sequence alignment procedure, figureFileSmall=nTQmGGuWVztbpgIJYEHYMQ==, figureFileBig=GCmwTdpN9AqHFHcOLxJ7Hg==, tableContent=null), ArticleFig(id=1327012145327354785, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, language=CN, label=图2, caption=序列对齐过程样例, figureFileSmall=nTQmGGuWVztbpgIJYEHYMQ==, figureFileBig=GCmwTdpN9AqHFHcOLxJ7Hg==, tableContent=null), ArticleFig(id=1327012145398657954, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, language=EN, label=Figure 3, caption=Example of rule 1, figureFileSmall=34nxiT+pWJEahwimSmpUJQ==, figureFileBig=dL1bkWrIxxr2TX4N8j5Lyw==, tableContent=null), ArticleFig(id=1327012145465766819, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, language=CN, label=图3, caption=规则1示例, figureFileSmall=34nxiT+pWJEahwimSmpUJQ==, figureFileBig=dL1bkWrIxxr2TX4N8j5Lyw==, tableContent=null), ArticleFig(id=1327012145528681380, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, language=EN, label=Figure 4, caption=BioSeq component, figureFileSmall=rKHOXPH5vlmDcB+nDzP2Xw==, figureFileBig=BF08VZT8nnZODZJh0BGgGQ==, tableContent=null), ArticleFig(id=1327012145591595941, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, language=CN, label=图4, caption=BioSeq构件, figureFileSmall=rKHOXPH5vlmDcB+nDzP2Xw==, figureFileBig=BF08VZT8nnZODZJh0BGgGQ==, tableContent=null), ArticleFig(id=1327012145654510502, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, language=EN, label=Figure 5, caption=matching function, figureFileSmall=uc5UuLwZBzhWgII/lDlI9A==, figureFileBig=JRmftn2XzzIx7mVxdIRZMw==, tableContent=null), ArticleFig(id=1327012145730007975, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, language=CN, label=图5, caption=matching函数, figureFileSmall=uc5UuLwZBzhWgII/lDlI9A==, figureFileBig=JRmftn2XzzIx7mVxdIRZMw==, tableContent=null), ArticleFig(id=1327012145822282664, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, language=EN, label=Figure 6, caption=Recursive relations and penalty rules, figureFileSmall=TFxI/ZRuAI0mlls3gBHkhQ==, figureFileBig=JMm0iMAPhfVqxWtXelTU7g==, tableContent=null), ArticleFig(id=1327012145931334569, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, language=CN, label=图6, caption=递推关系和罚分规则, figureFileSmall=TFxI/ZRuAI0mlls3gBHkhQ==, figureFileBig=JMm0iMAPhfVqxWtXelTU7g==, tableContent=null), ArticleFig(id=1327012145994249130, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, language=EN, label=Figure 7, caption=The function matching that records the source of the score, figureFileSmall=xtAE19NwZkJVzxHAhGgSqA==, figureFileBig=usNJ05C+C8xiI4/SaH/rZA==, tableContent=null), ArticleFig(id=1327012146065552299, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, language=CN, label=图7, caption=记录比分来源的函数matching, figureFileSmall=xtAE19NwZkJVzxHAhGgSqA==, figureFileBig=usNJ05C+C8xiI4/SaH/rZA==, tableContent=null), ArticleFig(id=1327012146136855468, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, language=EN, label=Figure 8, caption=C++ program’s running result of three sequence alignment algorithm, figureFileSmall=/a2MAV5nmNr5IkbZRcoE4A==, figureFileBig=9/wl+Q492DpQeqBCL+7haw==, tableContent=null), ArticleFig(id=1327012146279461805, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, language=CN, label=图8, caption=三序列比对算法的C++程序运行结果, figureFileSmall=/a2MAV5nmNr5IkbZRcoE4A==, figureFileBig=9/wl+Q492DpQeqBCL+7haw==, tableContent=null)], attaches=null, journal=Journal(id=1324759606947315908, delFlag=0, nameCn=计算机研究与发展, nameEn=Journal of Computer Research and Development, nameHistory1=null, nameHistory2=null, issn=1000-1239, eissn=null, cn=11-1777/TP, coden=null, periodic=0, language=CN, oaType=null, ccby=null, superviseOffice=null, ownerOffice=null, pubOffice=null, editorOffice=null, officeType=null, aims=null, clcCode=null, officeProv=null, officeCity=null, officeAddr=null, officeZip=null, officeEmail=null, officePhone=null, editDirector=null, officeDirector=null, officeDirectorPhone=null, officeStaffNum=null, officeEmpNum=null, coverPicUrl=k2l8zgqwstuxxevFX2qxVA==, journalPrice=null, startedYear=null, abbrevIsoEn=Journal of Computer Research and Development, journalRemark=null, publicationField=null, createdTime=1793776903141, updatedTime=1793850698612, createdBy=18614031015, updatedBy=13701087609, firstLetterCn=J, firstLetterEn=J, subjectCode=Electronic Information, subjectName=null, subjectCodeEn=Electronic Information, subjectNameEn=null, picCn=k2l8zgqwstuxxevFX2qxVA==, picEn=r6k0Ry+RD+c/VXj5QarmDw==, jcr=null, cjcr=null, exts=[JournalExt(id=1325069127710286688, language=CN, name=计算机研究与发展, nameHistory1=null, nameHistory2=null, managedBy=, sponsoredBy=, publishedBy=, editorOffice=, officeProv=null, officeCity=null, officeAddr=, officeZip=, editDirector=, officeDirector=null, officePhone=null, coverPicUrl=null, journalRemark=, submitArticleUrl=null, websiteUrl=, createdTime=1793850698640, updatedTime=1793850698640, createdBy=13701087609, updatedBy=13701087609, submissionGuidelinesUrl=, submissionAuthorUrl=https://crad.ict.ac.cn/journalx/authorLogOn.action, submissionEditorUrl=https://crad.ict.ac.cn/journalx/editorLogOn.action, submissionReviewUrl=https://crad.ict.ac.cn/journalx/expertLogOn.action, submissionCeEditorUrl=https://crad.ict.ac.cn/journalx/editorInChiefLogOn.action, submissionAeEditorUrl=, option={"copyright":""}), JournalExt(id=1325069127777395553, language=EN, name=Journal of Computer Research and Development, nameHistory1=null, nameHistory2=null, managedBy=, sponsoredBy=, publishedBy=, editorOffice=, officeProv=null, officeCity=null, officeAddr=, officeZip=, editDirector=, officeDirector=null, officePhone=null, coverPicUrl=null, journalRemark=, submitArticleUrl=null, websiteUrl=, createdTime=1793850698656, updatedTime=1793850698656, createdBy=13701087609, updatedBy=13701087609, submissionGuidelinesUrl=, submissionAuthorUrl=https://crad.ict.ac.cn/journalx/authorLogOn.action, submissionEditorUrl=https://crad.ict.ac.cn/journalx/editorLogOn.action, submissionReviewUrl=https://crad.ict.ac.cn/journalx/expertLogOn.action, submissionCeEditorUrl=https://crad.ict.ac.cn/journalx/editorInChiefLogOn.action, submissionAeEditorUrl=, option={"copyright":""})], databaseList=null, tenantJournalId=1324759914146529478, websiteList=[Website(id=1325070300139892771, webName=null, webTitle=null, webDomain=null, webCopyrigh=null, webIpcNo=null, seoTitle=null, seoKeywords=null, seoDescription=null, tenantJournalId=null, journalId=1324759914146529478, journalNameCn=null, journalNameEn=null, grayFlag=null, tenantId=1146029695717560320, platformId=null, journalGroupId=null, journalGroupNameCn=null, journalGroupNameEn=null, type=1, domain=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN, language=CN, createTime=1793850978169, createBy=18614031015, updateTime=1793851040259, updateBy=18614031015, name=计算机研究与发展-中文, tplId=1146099689490845704, title=计算机研究与发展, delFlag=0, indexPage=/home, props=[WebsiteProps(id=1325070893751349360, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=articleTextType, value=kx, createTime=1793851119697, updateTime=1793851119697, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893730377837, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=banner, value=null, createTime=1793851119692, updateTime=1793851119692, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893772320883, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=grayFlag, value=0, createTime=1793851119702, updateTime=1793851119702, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893721989228, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=logo, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/file/pic?fileId=U27tDsy717YF7XSPA+Vwdw==, createTime=1793851119690, updateTime=1793851119690, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893784903797, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=minRunFlag, value=0, createTime=1793851119705, updateTime=1793851119705, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893742960751, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=picServerUrl, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/file/pic, createTime=1793851119695, updateTime=1793851119695, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893780709492, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=silenceFlag, value=0, createTime=1793851119704, updateTime=1793851119704, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893738766446, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=staticResourcePath, value=https://castjournals.cast.org.cn/joweb/cast_kjdb_cn_619/, createTime=1793851119694, updateTime=1793851119694, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893755543665, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=themeColor, value=null, createTime=1793851119698, updateTime=1793851119698, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893763932274, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=themeStyle, value=null, createTime=1793851119700, updateTime=1793851119700, creator=18614031015, updator=18614031015)]), Website(id=1325070300580294698, webName=null, webTitle=null, webDomain=null, webCopyrigh=null, webIpcNo=null, seoTitle=null, seoKeywords=null, seoDescription=null, tenantJournalId=null, journalId=1324759914146529478, journalNameCn=null, journalNameEn=null, grayFlag=null, tenantId=1146029695717560320, platformId=null, journalGroupId=null, journalGroupNameCn=null, journalGroupNameEn=null, type=1, domain=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN, language=EN, createTime=1793850978274, createBy=18614031015, updateTime=1793851036638, updateBy=18614031015, name=计算机研究与发展-英文, tplId=1146101810881728533, title=Journal of Computer Research and Development, delFlag=0, indexPage=/home, props=[WebsiteProps(id=1325070925288321148, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=articleTextType, value=kx, createTime=1793851127216, updateTime=1793851127216, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925263155321, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=banner, value=null, createTime=1793851127210, updateTime=1793851127210, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925309292671, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=grayFlag, value=0, createTime=1793851127221, updateTime=1793851127221, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925254766712, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=logo, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/file/pic?fileId=U27tDsy717YF7XSPA+Vwdw==, createTime=1793851127208, updateTime=1793851127208, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925326069889, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=minRunFlag, value=0, createTime=1793851127225, updateTime=1793851127225, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925279932539, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=picServerUrl, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/file/pic, createTime=1793851127214, updateTime=1793851127214, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925317681280, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=silenceFlag, value=0, createTime=1793851127223, updateTime=1793851127223, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925271543930, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=staticResourcePath, value=https://castjournals.cast.org.cn/joweb/cast_kjdb_en_623/, createTime=1793851127212, updateTime=1793851127212, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925292515453, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=themeColor, value=null, createTime=1793851127217, updateTime=1793851127217, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925300904062, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=themeStyle, value=null, createTime=1793851127219, updateTime=1793851127219, creator=18614031015, updator=18614031015)])], journalTitle=计算机研究与发展, weixinUrl=null, journalUrl=https://crad.ict.ac.cn/, iacademicId=null, status=1, seqNo=null, journalTitleEn=Journal of Computer Research and Development, journalPhotoCn=k2l8zgqwstuxxevFX2qxVA==, journalPhotoEn=r6k0Ry+RD+c/VXj5QarmDw==, journalFirstLetter=J, journalRecommend=null, journalNew=null, journalCollection=null, jcrJf=null, cjcrJf=null, jcrJfStr=null, cjcrJfStr=null, submissionFirstDecision=null, sciSubjectClassification=null, casSubjectClassification=null, citeScore=null, totalCitationFrequency=null, icpCode=null, psCode=null, advertisingLicenseCode=null, copyrightInformation=null, country=null, option=, provinceCode=null, provinceName=null, collectFlag=false, interPubPlatform=, interPubPlatformUrl=null), detailUrlCn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/10.7544/issn1000-1239.202330698, detailUrlEn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/10.7544/issn1000-1239.202330698, pdfUrlCn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/PDF/10.7544/issn1000-1239.202330698, pdfUrlEn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/PDF/10.7544/issn1000-1239.202330698, aliStartDate=0, aliEndDate=0, collectionFlag=false, citedCount=null, citedUrl=null, previewStatus=0, delFlag=0, hasFullText=1, orderTime=1735660800000, fullTextJson=null, articleText=null, reference=null)
收藏切换
生物序列比对动态规划算法的统一形式化构造与Isabelle验证
石海鹤 1 , 蓝孙文 1 , 刘日明 1 , 石海鹏 2, * , 王岚 1 , 钟林辉 1
计算机研究与发展 | 人工智能 2025,62(1): 119-131
收起
收藏切换
计算机研究与发展 |人工智能 2025 , 62 (1) : 119 -131
生物序列比对动态规划算法的统一形式化构造与Isabelle验证
全屏
[Author(id=1327012141636367223, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, orderNo=0, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=haiheshi@jxnu.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327012141850276729, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, authorId=1327012141636367223, language=EN, stringName=Haihe Shi, firstName=Haihe, middleName=null, lastName=Shi, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1School of Computer Information Engineering, Jiangxi Normal University, Nanchang 330022, bio={"content":"

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

"}, bioImg=null, bioContent=

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

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012141980300154, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, authorId=1327012141636367223, language=CN, stringName=石海鹤, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1江西师范大学计算机信息工程学院 南昌 330022, bio={"img":"p94Y18+l2Qldk8a3XAxRPA==","content":"

1979年生. 博士,教授,博士生导师. CCF高级会员. 主要研究方向为形式化方法、生物信息学、软件工程

"}, bioImg=p94Y18+l2Qldk8a3XAxRPA==, bioContent=

1979年生. 博士,教授,博士生导师. CCF高级会员. 主要研究方向为形式化方法、生物信息学、软件工程

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327012141258879856, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, xref=1, ext=[AuthorCompanyExt(id=1327012141267268465, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, companyId=1327012141258879856, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer Information Engineering, Jiangxi Normal University, Nanchang 330022), AuthorCompanyExt(id=1327012141296628594, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, companyId=1327012141258879856, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1江西师范大学计算机信息工程学院 南昌 330022)])]), Author(id=1327012142139683709, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, orderNo=1, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327012142332621695, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, authorId=1327012142139683709, language=EN, stringName=Sunwen Lan, firstName=Sunwen, middleName=null, lastName=Lan, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1School of Computer Information Engineering, Jiangxi Normal University, Nanchang 330022, bio={"content":"

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

"}, bioImg=null, bioContent=

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

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012142529753984, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, authorId=1327012142139683709, language=CN, stringName=蓝孙文, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1江西师范大学计算机信息工程学院 南昌 330022, bio={"img":"o0klePoS8LejcZ+LPx7+Zw==","content":"

1999年生. 硕士. CCF学生会员. 主要研究方向为形式化方法

"}, bioImg=o0klePoS8LejcZ+LPx7+Zw==, bioContent=

1999年生. 硕士. CCF学生会员. 主要研究方向为形式化方法

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327012141258879856, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, xref=1, ext=[AuthorCompanyExt(id=1327012141267268465, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, companyId=1327012141258879856, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer Information Engineering, Jiangxi Normal University, Nanchang 330022), AuthorCompanyExt(id=1327012141296628594, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, companyId=1327012141258879856, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1江西师范大学计算机信息工程学院 南昌 330022)])]), Author(id=1327012142651388802, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, orderNo=2, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327012142768829316, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, authorId=1327012142651388802, language=EN, stringName=Riming Liu, firstName=Riming, middleName=null, lastName=Liu, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1School of Computer Information Engineering, Jiangxi Normal University, Nanchang 330022, bio={"content":"

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

"}, bioImg=null, bioContent=

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

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012142907241349, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, authorId=1327012142651388802, language=CN, stringName=刘日明, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1江西师范大学计算机信息工程学院 南昌 330022, bio={"img":"TbRaajfNH4J3FHA30Ie3zw==","content":"

1998年生. 硕士. CCF学生会员. 主要研究方向为形式化方法

"}, bioImg=TbRaajfNH4J3FHA30Ie3zw==, bioContent=

1998年生. 硕士. CCF学生会员. 主要研究方向为形式化方法

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327012141258879856, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, xref=1, ext=[AuthorCompanyExt(id=1327012141267268465, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, companyId=1327012141258879856, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer Information Engineering, Jiangxi Normal University, Nanchang 330022), AuthorCompanyExt(id=1327012141296628594, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, companyId=1327012141258879856, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1江西师范大学计算机信息工程学院 南昌 330022)])]), Author(id=1327012143045653383, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, orderNo=3, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=option2001@jxnu.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=1, authorType=1, ext={EN=AuthorExt(id=1327012143234397065, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, authorId=1327012143045653383, language=EN, stringName=Haipeng Shi, firstName=Haipeng, middleName=null, lastName=Shi, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=2, *, address=2School of Software, Jiangxi Normal University, Nanchang 330022, bio={"content":"

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

"}, bioImg=null, bioContent=

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

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012143431529354, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, authorId=1327012143045653383, language=CN, stringName=石海鹏, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=2, *, address=2江西师范大学软件学院 南昌 330022, bio={"img":"t7/wEvpbYBXar0YC/6fYdA==","content":"

1977年生. 博士,副教授,硕士生导师. CCF会员. 主要研究方向为算法设计、软件工程

"}, bioImg=t7/wEvpbYBXar0YC/6fYdA==, bioContent=

1977年生. 博士,副教授,硕士生导师. CCF会员. 主要研究方向为算法设计、软件工程

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327012141506343795, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, xref=2, ext=[AuthorCompanyExt(id=1327012141539898228, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, companyId=1327012141506343795, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2School of Software, Jiangxi Normal University, Nanchang 330022), AuthorCompanyExt(id=1327012141544092533, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, companyId=1327012141506343795, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=2江西师范大学软件学院 南昌 330022)])]), Author(id=1327012143532192652, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, orderNo=4, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327012143683187598, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, authorId=1327012143532192652, language=EN, stringName=Lan Wang, firstName=Lan, middleName=null, lastName=Wang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1School of Computer Information Engineering, Jiangxi Normal University, Nanchang 330022, bio={"content":"

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

"}, bioImg=null, bioContent=

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

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012143800628111, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, authorId=1327012143532192652, language=CN, stringName=王岚, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1江西师范大学计算机信息工程学院 南昌 330022, bio={"img":"E9fq8va5rJhM52iymSHxzQ==","content":"

1974年生. 硕士,副教授. CCF会员. 主要研究方向为算法和数据结构、生物信息学、编译原理

"}, bioImg=E9fq8va5rJhM52iymSHxzQ==, bioContent=

1974年生. 硕士,副教授. CCF会员. 主要研究方向为算法和数据结构、生物信息学、编译原理

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327012141258879856, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, xref=1, ext=[AuthorCompanyExt(id=1327012141267268465, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, companyId=1327012141258879856, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer Information Engineering, Jiangxi Normal University, Nanchang 330022), AuthorCompanyExt(id=1327012141296628594, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, companyId=1327012141258879856, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1江西师范大学计算机信息工程学院 南昌 330022)])]), Author(id=1327012143905485713, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, orderNo=5, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327012144018731923, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, authorId=1327012143905485713, language=EN, stringName=Linhui Zhong, firstName=Linhui, middleName=null, lastName=Zhong, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1School of Computer Information Engineering, Jiangxi Normal University, Nanchang 330022, bio={"content":"

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

"}, bioImg=null, bioContent=

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

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327012144173921172, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, authorId=1327012143905485713, language=CN, stringName=钟林辉, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=1, address=1江西师范大学计算机信息工程学院 南昌 330022, bio={"img":"F4HOfUbPB+fIzXwbi1Sqmw==","content":"

1974年生. 博士,副教授,硕士生导师. CCF会员. 主要研究方向为软件体系结构、构件化软件开发、软件演化与维护

"}, bioImg=F4HOfUbPB+fIzXwbi1Sqmw==, bioContent=

1974年生. 博士,副教授,硕士生导师. CCF会员. 主要研究方向为软件体系结构、构件化软件开发、软件演化与维护

, aboutCorrespAuthor=null)}, companyList=[AuthorCompany(id=1327012141258879856, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, xref=1, ext=[AuthorCompanyExt(id=1327012141267268465, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, companyId=1327012141258879856, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1School of Computer Information Engineering, Jiangxi Normal University, Nanchang 330022), AuthorCompanyExt(id=1327012141296628594, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327011868515873641, companyId=1327012141258879856, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=1江西师范大学计算机信息工程学院 南昌 330022)])])]
石海鹤1 , 蓝孙文1, 刘日明1, 石海鹏2, * , 王岚1, 钟林辉1
作者信息
  • 1江西师范大学计算机信息工程学院 南昌 330022
  • 2江西师范大学软件学院 南昌 330022
通讯作者:
作者简介:

1979年生. 博士,教授,博士生导师. CCF高级会员. 主要研究方向为形式化方法、生物信息学、软件工程

1999年生. 硕士. CCF学生会员. 主要研究方向为形式化方法

1998年生. 硕士. CCF学生会员. 主要研究方向为形式化方法

1977年生. 博士,副教授,硕士生导师. CCF会员. 主要研究方向为算法设计、软件工程

1974年生. 硕士,副教授. CCF会员. 主要研究方向为算法和数据结构、生物信息学、编译原理

1974年生. 博士,副教授,硕士生导师. CCF会员. 主要研究方向为软件体系结构、构件化软件开发、软件演化与维护

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
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

出版时间: 2025-01-01 doi: 10.7544/issn1000-1239.202330698
文章导航
收藏切换

序列比对是生物序列分析中的一个经典问题,旨在找出序列之间的相似性,它对于发现生物序列中的功能、结构和进化信息都具有重要的意义. 该问题可分为双序列比对和多序列比对2类,现有工作多针对特定算法展开,没有设计通用的求解方法;此外,甚少涉及算法可信性的研究. 从生物序列比对问题的形式化规约出发,通过深入分析问题的性质,刻画问题求解的本质特征,借助形式化方法PAR(partition and recursion)设计了序列比对动态规划算法的统一构造框架seqAlign;展示了应用该框架构造序列数为3的多序列比对算法的过程,并使用Isabelle定理证明器对构造结果进行形式化验证;利用PAR平台生成了该算法的C++可执行程序,进一步分析了由seqAlign框架机械化构造其他类型序列比对算法的过程. 通过严密的规约精化和形式验证,有效地保证了生成算法的可信性;开发的seqAlign框架提供了序列比对问题类的通用求解方案,显著提高了序列比对算法族生成的效率. 研究结果在生物序列分析中序列比对问题上的成功应用,从方法学和实践上可为复杂生物信息学领域高可靠算法的构造提供参考.

序列比对  /  PAR方法  /  形式构造  /  Isabelle定理证明器

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
软件发展的核心问题之一是如何保证软件系统安全可靠. 随着社会基础设施中的软件系统越来越重要,如何保证复杂软件正确性和可靠性的需求日益突出[1],开发可靠的软件系统已经成为一项巨大的挑战[2]. 算法作为软件系统的核心,其可靠性显得尤为重要.
序列比对是计算机在解决生物学问题应用中的一个经典问题,旨在找出序列之间的相似性关系,以此来判定序列的同源性[3]. 按照比对的序列个数,可以将序列比对问题分为双序列比对和多序列比对2类. 现有工作[4-16]主要关注序列比对特定问题的求解,没有为其提出一个统一的求解方法,算法开发效率较低. 另外,算法可信性研究较少,导致算法的正确性无法有效保证.
形式化方法以严格的数学化和机械化方法为基础来规约、设计、构建、验证、演化软件系统,可以有效地保障和提高系统的可信性. 软件形式化开发主要是构造、证明形式规约之间的等价转换和精化关系,以形式模型为指导,逐步求精,开发出满足需求的软件系统,也称为构造即正确(correctness-by-construction)的开发[17]. 许多著名的研究机构都投入了大量人力物力从事这方面的研究. 美国宇航局于2011年11月发射的“好奇号”火星探测器研制过程中,就广泛使用了形式化方法以提高控制软件的可信性. 在国内,2023年4月华为联合CCF发布的第3期胡杨林基金形式化专项中包含了5个产业课题方向以及若干开放课题,力求实现关键基础技术底座自主、领先. 此外,华为自主研发的鸿蒙操作系统HarmonyOS也使用了形式化方法.
薛锦云[18]提出的形式化方法PAR(partition and recursion)提供了Radl语言来书写规约和描述算法,设计了规约精化规则,提出了循环不变式开发新策略,支持构造即正确的开发. 使用PAR方法对算法程序进行形式化推导,不但能从逻辑上保证算法程序的正确性,而且能够揭示算法程序设计的本质特征.
本文借助PAR方法,对生物序列比对问题的特点进行深入分析,描述序列比对问题的通用性质,得到序列比对问题的通用形式化Radl规约,开发了序列比对动态规划(dynamic programming,DP)算法的统一构造框架seqAlign,并通过严格的形式化推导和形式化证明来确保生成算法的可靠性. 进一步展示了应用该框架构造序列数为3的多序列比对算法的过程,并使用Isabelle定理证明器对构造结果进行形式化验证,利用PAR平台的代码生成系统生成了该算法的C++可执行程序. 以GenBank数据库中3段关于光敏色素B的植物DNA序列作为输入,呈现了所生成序列比对算法的运行效果. 总结分析了由seqAlign框架机械化构造其他类型序列比对算法的过程. 应用seqAlign框架构造序列比对算法,不仅能有效保证生成的序列比对算法的可信性,而且可用于序列比对这一类问题的求解,避免了从问题出发逐步构造可靠算法的繁琐,只需简单地代入序列数和分析个性化性质即可快速生成特定序列比对算法,极大提高了序列比对算法生成的效率. 本文开展的工作可为领域复杂算法的形式化构造提供一个有价值的参考框架.
对于双序列比对问题,最为经典的确定性算法有基于全局比对的NW(Needleman-Wunsch)算法[4]和基于局部比对的SW(Smith-Waterman)算法[5]. 此外, Chowdhury等人[6]提出了一种基于遗传算法的新的序列比对技术,可达到全局或接近全局最优解的能力;Alawneh等人[7]提出了一种混合并行方法,结合了多核CPU的能力和当代GPU的能力,显著加快了目标算法的执行;Rashed等人[8]使用FPGA和定制卷积神经网络来加速DNA的双序列比对,可达到98.3%的精度;Song等人[9]定义了在序列比对系统中实现强化学习的环境和代理,提出一种新的双序列比对方法,使用深度强化学习来改进旧的双序列比对算法. 多序列比对算法主要包括动态规划算法和启发式比对算法. 前者是精准比对,可得到正确的结果,但是对计算机资源的消耗过高;后者是近似比对,占用资源较少,但只能得到近似解. 启发式比对算法可分为渐进式比对,如Clustal算法[10],以及迭代式比对,如MAFFT算法[11]、MUSCLE算法[12]等. 后续研究中,Abuín等人[13]和Wan等人[14]应用云计算实现MSA的并行化,分别成功地比对了3.4 GB和15 GB的序列文件,并在一定程度上保持了算法的准确性;Smirnov等人[15]提出了MAGUS,使用与PASTA[16]相似的初始步骤,随后使用图聚类合并来合并子集比对,在大型数据集上产生了更高的准确性,比PASTA更快. 以上工作都是针对两类不同的问题分别设计解决方案,并未将其视为一类统一的问题寻找通用求解算法.
在算法形式构造方面,Durán[19]提出了一种基于Möller代数的高效命令式网络算法的转换开发方法,并使用此方法推导了树的最短路径算法;Abrial等人[20]使用Event-B方法设计了最小生成树问题模型,并将其转化为相应的Prim算法;Almeida等人[21]从一个通用规范出发,由相似的转换步骤序列推导证明了3种已知的排序算法;Nedunuri等人[22]通过应用适当地保持语义一致性转换,将一个朴素的算法变成一个高效的程序,推导了3个最大子段和问题的程序;Mu [23]使用等式推理构造了n皇后问题的回溯算法;Lammich [24]提出了一个基于Isabelle/HOL生成经过验证的LLVM程序的框架,生成了经过验证的二分查找和Knuth-Morris-Pratt字符串搜索算法的LLVM实现;张健等人[25]提出了一种正反例归纳合成方法, 能够根据用户编辑的含有少量元组的示例表自动合成满足用户期望的SQL查询程序等. 已有工作使用方法众多,涉及领域很广,但未见有将形式化方法应用于同一类生物信息学领域问题的通用算法构造.
基于分划递推技术的PAR方法是一种简单实用的形式化方法,涵盖了算法开发的全阶段,可以清晰地展示算法的设计过程,快速开发同一类相似问题的求解算法,适用于构造即正确的算法开发[26]. 文献[27-28]使用PAR方法形式化开发了一系列组合数学问题的算法;文献[29-31]结合分划递推、领域工程和泛型编程,设计了高可信的可重用领域算法构件,装配了3类生物信息学的算法,说明了使用PAR方法开发相关算法的可行性. 生物序列包括DNA、RNA和生物大分子序列,可看成是组合数学中的序列结构,将PAR方法应用在生物信息学领域算法的形式化开发中具有充足的优势.
这里,我们首先简要介绍PAR方法开发算法的过程;然后通过分析生物序列比对问题的特征,进行seqAlign算法统一求解框架的形式构造.
由PAR方法设计算法的统一构造框架,并进一步生成高可靠算法的流程分为3个步骤,如图1所示.
构造特定算法的程序分为3个步骤:第1步对一类问题深入分析,得到问题的通用规约;第2步使用规约精化规则对Radl规约进行精化推导,得到问题求解序列递推关系和Radl算法,从而设计该类问题的统一构造框架;第3步根据统一构造框架和特定条件,生成相应的Apla算法程序.
本文中的量词采用一种统一的表示形式(Q i : r(i) : f(i)),它的含义是:在范围r(i)上对函数f(i)施行量词Q对应的q运算所得的值. 主要用到的量词为MAX和Σ,对应的运算为max和+,分别表示求最大值和求和. 利用量词的性质可以对规约作等价变换,以揭露问题求解的思想[26]. 下面给出了规约精化所使用的性质.
1)单一范围:(Q i : i=k : f(i)) = f(k).
2)范围分裂:(Q i : r(i) : f(i)) = (Q i : r(i)∧b(i) : f(i)) q (Q i : r(i)∧¬b(i) : f(i)),其中b(i)是布尔表达式.
3)函数结合律:(Q i : r(i) : f(i) q g(i)) = (Q i : r(i) : f(i)) q (Q i : r(i) : g(i)).
4)范围析取:若a q a=a,则称运算q是幂等的. 对于幂等的运算q,有(Q i : r(i)∨s(i) : f(i)) = (Q i : r(i) : f(i)) q (Q i : s(i) : f(i)).
构造正确的程序需要数学证明[32],因为传统的软件测试等方法只能证明系统软件中存在错误,而不能彻底消除错误. 故要确保构造的程序是完全正确的,还需对其进行形式化验证. 此外,通过程序正确性证明,还可加深对程序的理解.
由于Floyd归纳断言方法[33]和Hoare公理系统方法[34]书写恰当的中间断言十分困难,而Dijkstra最弱前置谓词法以定义的最弱前置谓词来书写中间断言[32,35],更加具有实用性. 因此,本文选取Dijkstra最弱前置谓词法来证明Apla程序的正确性. 该方法通过验证5个条件来证明循环语句的正确性:
1)$ {Q}_{\mathrm{p}\mathrm{r}\mathrm{o}}= > \rho ; $
2)$ \rho \wedge {C}_{i}= > WP\left(\mathrm{“}{S}_{i}\mathrm{”},\rho \right),\mathrm{ }1\le i\le n; $
3)$ \rho \wedge \neg Guard= > {R}_{\mathrm{p}\mathrm{r}\mathrm{o}}; $
4)$ \rho \wedge Guard= > \tau > 0; $
5)$ \rho \wedge {C}_{i}= > WP\left(\mathrm{“}{\tau }_{1}:=\tau ;{S}_{i}\mathrm{”},{\tau }_{1} < \tau \right),\mathrm{ }1\le i\le n. $
其中,Qpro为前置断言,Rpro为后置断言,ρ为循环不变式,τ为界函数,Ci和Si分别为循环条件分支语句和与其对应的循环体,Guard为所有分支Ci的析取.
Isabelle是当前被广泛使用的交互式定理证明器,相较于手工验证,自动化程度和可靠性更高. 本文使用Dijkstra最弱前置谓词法,并以Isabelle定理证明器辅助证明所得Apla程序的正确性. 将程序的验证条件输入到Isabelle中,使用其提供的自动证明策略证明.
PAR平台中包含系列程序生成系统[36-37],可以由抽象Apla程序自动生成C++/C#、Java等可执行程序. 使用程序生成系统,可将形式化验证后的Apla程序进一步转换成对应的高可靠可执行算法程序.
这里,分析序列比对问题的性质,抽象出共同规约,逐步精化得到递推关系,并开发序列比对DP算法的统一构造框架seqAlign. 由于序列比对的启发式算法只能得到近似解,故seqAlign框架仅考虑可得到精确解的DP算法.
双序列比对和多序列比对问题存在共性,都是参与比对的序列中的元素逐一连续地比对,最终结果是要得到最佳比对得分,以此来评定序列之间的相似性. 双序列比对问题中参与比对的序列数目为2,多序列比对问题中参与比对的序列数目大于2. 两者之间的区别只有参与比对的序列数目,故可将这两类问题刻画成一类问题.
给定k个参与比对的序列,其中k不小于2. 序列中的元素可以有4种匹配方式:匹配match、全空配smatch、错配nmacth和空配space,分别表示2个相同的元素匹配、2个空位匹配、2个不相同的元素匹配和其中1个序列中元素与空位匹配. 每种匹配方式对应一次罚分,最常用的罚分规则有2种:权值恒定模型和仿射罚分模型,不同的罚分规则对应不同的序列相似性评判标准. 为了更好地展示构造过程,本文使用固定罚分规则,如下所示:
从每个序列的第1个元素开始从前往后匹配,直到每个序列的元素全部匹配完,这为1次比对,比对得分为每次元素匹配对应的罚分之和. 序列比对的最终目的则是在所有可能的比对情况中得到最大的比对得分.
序列比对问题也可以描述成输入k条(k≥2)序列,往序列中插入若干以“#”表示的空位,使每条序列对齐,即长度相等,从所有对齐的方式中找出最大的分值. 这里用seqList表示输入的序列集合,用n1,n2,…,nk分别表示参与比对的k条序列的长度. 每条序列对齐可以看成是一系列的单列对齐,即每条序列要么提供序列中的元素,要么提供空位,但是不能所有的序列都提供空位. 图2展示了输入[A,C],[A,T,G,C],[A,A,C]这3条序列的其中一种对齐过程.
用1个k维向量(i1,i2,…,ik)来描述当前的对齐进度,i1,i2,…,ik分别表示k个序列已提供元素的长度. 序列的1次全局比对可以看作是从初始对齐进度(0,0,…,0)到终止对齐进度(n1,n2,…,nk)的过程,这个过程包括了一系列的单列对齐. 由于每一次匹配中序列的两两匹配只可能是匹配、全空配、错配和空配4种方式,序列在这次单列对齐中要么提供空位,要么提供第1个未比对元素,而且1次匹配中不能要求全部序列都提供空位. 将当前的对齐进度(i1,i2,…,ik)推进到下一个对齐进度(j1,j2,…,jk)需满足的规则作如下描述:
规则1. $ \forall u\in \left\{1,2,… ,k\right\},{j}_{u}={i}_{u}+{m}_{u}\left({m}_{u}=1\mathrm{或}{m}_{u}=0\right) $.
规则2. $ 1\le \underset{u=1}{\displaystyle\sum\limits^{k}}{m}_{u}\le k $.
当前对齐序列最后一列中,当$ {m}_{u}=1 $时,表示第u个序列提供第$ {i}_{u}+1 $个元素,即$ seqList\left[u\right]\left[{i}_{u}+1\right] $;当$ {m}_{u}=0 $时,表示第u个序列提供空位. 规则1的一个例子可见图3,图3(a)为序列对齐进度,图3(b)为单列对齐. 很显然,当前参与匹配的非空位元素的个数不少于1,且最多不能超过参与比对的序列个数.
为了简便记录对齐过程,这里用一个长度为k的序列[C1,C2,…,Ck]来存储从当前对齐进度到下一个对齐进度的单列对齐. 当$ {m}_{u}=1 $时,$ {C}_{u}=seqList\left[u\right]\left[{i}_{u}+1\right] $;当$ {m}_{u}=0 $时,$ {C}_{u}={\text{‘}}\#\text{’} $. 例如,图2中最后一步单列对齐,是从对齐进度(2,3,2)到(2,4,3),则这一步的单列对齐为[#,seqList[2][4],seqList[3][3]],即[#,C,G]. 可以直观地看出,序列的对齐过程是若干单列对齐的集合,计算每步单列对齐的分值之和可得序列比对得分. 以align(seqList,i1,i2,…,ik)表示从初始对齐进度(0,0,…,0)到终止对齐进度(i1,i2,…,ik)所有满足规则1和规则2的对齐过程集合,我们的目标则变成了从每个对齐过程的比对得分中找出最大值. 据此,我们可以得到序列比对问题的通用规约.
Specification: SeqAlignment
|[ in: k:integer;seqList:list(BioSeq(enum), k);len:list(integer, k) out: ms:integer ]|
AQ: given seqList, k≥2;
AR: maxScore(seqList, len) $\equiv $ (MAX cs:cs $\in $ align(seqList, len): ($\Sigma $sgl: sgl $\in $ cs:sglScore(sgl))),
sglScore(sgl)$\equiv $ ($\Sigma $i, j:0 $\le $ i < j $\le $ k:rule(sgl[i], sgl[j])),
其中BioSeq是我们自定义的类型构件,用来存储生物序列和操作生物序列. 构件中包含3个方法,函数rule和sglScore分别计算两两元素和单列对齐的匹配分值. 在算法的构造过程中,可以使用BioSeq构件中的方法,极大地增加了可重用性和简便性. 图4给出了BioSeq的定义和其中3个方法的抽象表达.
图4中sometype修饰泛型参数,表示生物序列的元素类型可以改变,size为可选参数,缺省表示序列长度没有限制,反之表示序列长度固定为size. 建立一个枚举类型dnaEnum=「A,C,G,T」,将泛型参数设置为此枚举类型,就可以得到一个DNA序列类型DNASeq. 如此可以很简便地得到3种生物序列类型:DNA序列DNASeq、RNA序列RNASeq和蛋白质序列ProSeq.
由规则1和规则2,我们可以得到单列对齐可能的情况种数$ {count}_{\mathrm{s}} $有2个性质:
性质1. $ {count}_{\mathrm{s}}=\displaystyle\sum\limits^{k}_{i=1}{\mathrm{C}}_{k}^{i} $.
证明. 单列对齐中的前后2个对齐进度(i1,i2,…,ik)和(j1,j2,…,jk),根据规则1,单列对齐中每条序列要么提供空位,要么提供序列中的元素,再联合规则2,可以得出单列对齐中非空位元素的个数范围是[1, k]. 换句话说,每一种情况确定非空位元素的位置是组合问题,将每种情况求和即可得到$ {count}_{\mathrm{s}} $. 证毕.
性质2. $ align\left(seqList,{i}_{1},{i}_{2},…,{i}_{k}\right)= $
证明. 对于某个对齐进度,它的来源即前一个对齐进度可能有$ {\displaystyle\sum\limits_{i=1}^{k}}{\mathrm{C}}_{k}^{i} $种. 根据规则1和性质1,将align(seqList,i1,i2,…,ik)的最后一步单列对齐排列组合的情况一一列举出来,[i1,…,ik−1,ik],[i1,…,ik−1,#],…,[#,…,ik−1,ik],…,[i1,#,…,#],…,[#,…,#,ik],即得上式. 证毕.
将前面得到的规约一般化,用score(cs)代替$ \left(\mathrm{\Sigma }sgl:sgl\in cs:sglScore\left(sgl\right)\right) $,进行以下推导:
$maxScore\left(seqList,{i}_{1},{i}_{2},… ,{i}_{k}\right)\equiv $
[maxScore定义展开]
[性质2]
[范围析取]
[变量替换]
[sglScore定义收缩]
[范围分裂]
[单一范围]
[函数结合律]
不难看出,原问题被划分为$ {\displaystyle\sum\limits_{i=1}^{k}}{\mathrm{C}}_{k}^{i} $个子问题. 由此,可以得到序列比对问题一般情况的通用递推关系:
$ \begin{split}&maxScore\left(seqList,{i}_{1},{i}_{2},… ,{i}_{k}\right)=\\ &{\mathrm{max}}\left\{\begin{aligned}&maxScore\left(seqList,{i}_{1}-1,… ,{i}_{k-1}-1,{i}_{k}-1\right)+\\&\quad sglScore\left(\left[{i}_{1},\mathrm{ }… ,{i}_{k-1},{i}_{k}\right]\right),\\&maxScore\left(seqList,{i}_{1}-1,… ,{i}_{k-1}-1,{i}_{k}\right)+\\&\quad sglScore\left(\left[{i}_{1},\mathrm{ }… ,{i}_{k-1},\#\right]\right),… ,\\ &maxScore\left(seqList,{i}_{1},{i}_{2}-1,… ,{i}_{k}-1\right)+\\&\quad sglScore\left(\left[\#,{i}_{2},… ,{i}_{k}\right]\right),… ,\\ &maxScore\left(seqList,{i}_{1}-1,{i}_{2},… ,{i}_{k}\right)+\\&\quad sglScore\left(\left[{i}_{1},\mathrm{ }\#,… ,\mathrm{ }\#\right]\right),… ,\\&maxScore\left(seqList,{i}_{1},… ,{i}_{k-1},{i}_{k}-1\right)+\\&\quad sglScore\left(\left[\#,\mathrm{ }… ,\mathrm{ }\#,{i}_{k}\right]\right). \end{aligned}\right.\end{split} $
原问题被分划成了若干子问题,而对齐进度中每条序列已提供元素的长度不能小于0. 所以,如果子问题的对齐进度中有序列提供的长度小于0,那么这个子问题将不存在. 本文将不存在的子问题的分值设置成integer类型的最小值,并且把实现这个功能的calculate函数集成到BioSeq构件中. 根据指定特定罚分规则的递推关系,即可构造出如下序列比对问题的统一Radl求解算法:
算法1. seqAlign.
|[var k, i1, i2, …, ik:integer;
score:array(0.. n1, array(0.. n2, …, array(0.. nk, integer)));seqList:list(BioSeq(), k);]|
{AQ$\wedge $AR}
$ \mathrm{b}\mathrm{e}\mathrm{g}\mathrm{i}\mathrm{n}:{i}_{1}=0++1\wedge {i}_{2}=0++1\wedge … \wedge {i}_{k}=0++1 $;
$ \mathrm{t}\mathrm{e}\mathrm{r}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}:{i}_{1}={n}_{1}\wedge {i}_{2}={n}_{2}\wedge … \wedge {i}_{k}={n}_{k} $;
recur: 式(1);
end
文献[38]给出了循环不变式的新定义,即反映循环体中所有循环变量的变化规律并在循环体执行前后都为真的谓词称为该循环体的循环不变式. 其中,循环变量定义为在循环体中,其值随着循环体的执行不断发生变化的变量.
由得到的Radl算法可以看出,该算法有k层循环,变量$ {i}_{u} $控制第u层循环,每层循环分别对应不同的循环不变式. 用变量ms存放maxScore(seqList,i1,i2,…,ik)的值,那么循环内的所有变量为i1,i2,…,ik和ms. 首先分析最外层循环,跟随循环体执行发生变化的变量为i1和ms,其他变量与外层循环无关,因为无论最外层循环执行到哪一步,最外层循环体执行前其他变量的值都为0. 循环变量ms的值始终为$ (\mathrm{M}\mathrm{A}\mathrm{X}\;cs: cs=align(seqList,i_{1},{i}_{2},… ,{i}_{k})\mathrm{ }:score(cs\left)\right) $,循环变量$ {i}_{1} $的变化范围为[0, $ {n}_{1} $]. 据此循环变量的变化规律,用谓词精确表示,即得出外层循环的循环不变式:
同理,可构造其他层的循环不变式.
在通用框架的基础上,以输入3条序列的多序列比对为例,构造序列比对算法的Apla程序. 通过算法程序的形式化验证,生成高可靠的C++可执行程序.
2.2节分析了序列比对问题的性质,得到了序列比对算法的统一构造框架seqAlign. 要得到序列数为3的序列比对算法的递推关系,只需将k=3代入seqAlign框架的递推关系中:
$ \begin{split}&maxScore\left(seqList,i_1,i_2,i_3\right)=\\ &{\mathrm{max}}\left\{\begin{aligned}&maxScore\left(seqList,i_1-1,i_2-1,i_3-1\right)+\\&\quad sglScore\left(\left[i_1,i_2,i_3\right]\right),i_1,i_2,i_3 > 0,\\ &maxScore\left(seqList,i_1-1,i_2-1,i_3\right)+\\&\quad sglScore\left(\left[i_1,i_2,\#\right]\right),i_1,i_2 > 0,\\ &maxScore\left(seqList,i_1-1,i_2,i_3-1\right)+\\&\quad sglScore\left(\left[i_1,\mathrm{ }\#,i_3\right]\right),i_1,i_3 > 0,\\ &maxScore\left(seqList,i_1,i_2-1,i_3-1\right)+\\&\quad sglScore\left(\left[\#,i_2,i_3\right]\right),i_2,i_3 > 0,\\&maxScore\left(seqList,i_1-1,i_2,i_3\right)+\\&\quad sglScore\left(\left[i_1,\mathrm{ }\#,\mathrm{ }\#\right]\right),i_1 > 0,\\ &maxScore\left(seqList,i_1,i_2-1,i_3\right)+\\&\quad sglScore\left(\left[\#,i_2,\mathrm{ }\#\right]\right),i_2 > 0,\\ &maxScore\left(seqList,i_1,i_2,i_3-1\right)+\\&\quad sglScore\left(\left[\#,\mathrm{ }\#,i_3\right]\right),i_3 > 0 . \end{aligned}\right.\end{split} $
考虑特殊情况,当i1,i2,i3都为0时,即当前处于序列比对的初始状态,对齐进度为(0,0,0). 此时,maxScore(seqList,i1,i2,i3) = 0. 将一般情况和特殊情况结合,可得到如下的Radl算法:
算法2. mulSeqAlign.
|[var k, i1, i2, i3:integer;score: array(0.. n1, array(0.. n2, array(0.. n3, integer)));seqList: list(BioSeq(), 3);]|
{AQ$\wedge $AR}
$ \mathrm{b}\mathrm{e}\mathrm{g}\mathrm{i}\mathrm{n}:i_1=0++1\wedge i_2=0++1\wedge i_3=0++1 $;
$ \mathrm{t}\mathrm{e}\mathrm{r}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}:i_1=n_1\wedge i_2=n_2\wedge i_3=n_3 $;
recur: 式(2);
end
循环不变式如下:
根据得到的递推关系和Radl算法以及循环不变式,经过简单的推导,可以简捷地得到基于BioSeq构件编写的Apla抽象算法程序. 通过严密的规约求精,保证了序列比对Apla算法程序的正确性. 限于篇幅,这里只给出比对算法的主体函数matching,如图5所示.
创建一个新的理论multSeqAlignment用于本文中Apla程序的形式化证明,理论名需要与文件名一致. 由于Isabelle自带的Main理论中包含了本文所用到的list类型,故这里只需要用import引入Main理论即可. 使用definition以及fun命令定义递推关系maxScore、分值计算规则rule和sglScore,如图6所示.
本文构造的序列比对算法程序的主体是3层循环,循环中的递推关系和罚分规则是经过严格推导得到的,故只需证明双层循环的正确性即可. 使用Dijkstra最弱前置谓词法证明循环语句的正确性,找到循环语句的循环不变式ρ和界函数τ是关键. 其中,Apla程序中的循环不变式已通过求解并且在上文给出. 另外,3层循环对应的界函数显然可以为$ n_1-i_1+1 $,$ n_2-i_2+1 $,$ n_3-i_3+1 $. 接下来,将验证循环程序需要的5个条件形式化表示.
1)$ i=0\wedge j=0\wedge k=0== > ms=$ $\left(maxScores_1s_2s_3ijk\right)\wedge\left(0\le i\wedge i\le n_1\right) $;
2)$ ms=\left(maxScores_1s_2s_3ijk\right)\wedge (0\le i\wedge i\le n_1)\wedge i < $ $n_1== >\left(maxScores_1s_2s_3\left(\mathrm{S}\mathrm{u}\mathrm{c}\;i\right)jk\right)=(maxScores_1s_2s_3 $$ (\mathrm{S}\mathrm{u}\mathrm{c}\;i)jk)\wedge\left(0\le \mathrm{S}\mathrm{u}\mathrm{c}\;i\wedge \mathrm{S}\mathrm{u}\mathrm{c}\;i\le n_1\right) $;
3)$ ms=\left(maxScore\;s_1s_2s_3ijk\right)\wedge \left(0\le i\wedge i\le n_1\right)\wedge \neg i < $ $n_1== > ms=\left(maxScore\;s_1s_2s_3n_1jk\right) $;
4)$ ms=\left(maxScore\;s_1s_2s_3ijk\right)\wedge \left(0\le i\wedge i\le n_1\right)\wedge i $$< n_1== > 0\le n_1-i+1 $ ;
5)$ ms=\left(maxScore\;s_1s_2s_3ijk\right)\wedge \left(0\le i\wedge i\le n_1\right)\wedge i $$< n_1== > n_1-i < n_1-i+1 $.
上述5条引理可以用自动证明工具auto自动消解证明目标,只需使用“by auto”命令即可完成证明,此时证明状态全部变为了“No subgoals!”,表示5条引理皆被证明是正确的. 由于3层循环的证明并无二致,这里不再给出其他循环层的证明过程. 经上述证明,说明循环不变式在循环执行前后以及循环执行过程中皆为真,验证了生成的Apla程序的正确性.
在使用Isabelle定理证明器验证Apla算法程序的正确性之后,通过PAR平台中的Apla->C++程序生成系统,生成了对应的C++程序.
为了方便查看最佳比对方式,我们在前述三序列比对算法的Apla程序的基础上,存储最佳比对方式的每一步匹配,并加入了输出最佳比对方式的过程. 在计算当前对齐进度(i,j,k)的最大比对得分时,得到最大比分的来源是可以确定的,也就是前一次的对齐进度. 因此,如需得到最佳比对方式,只需要在计算每一个对齐进度的最大比分时,使用一个3维数组path来保存最大比分的来源. 由性质1可知,三序列比对最大比分的来源可能有7种情况,故将path中元素取值范围设为{0,1,2,3,4,5,6}. 将最大比分来源 (i−1,j−1,k−1),(i−1,j−1,k),(i−1,j,k−1),(i,j−1,k−1),(i−1,j,k),(i,j−1,k),(i,j,k−1) 分别标记为以上7种情况的7个值,记录在path[i,j,k]中.
确定了数组path的值后,从终止对齐进度(n1,n2,n3)开始往前遍历,直到初始对齐进度,即(0,0,0),记录比分来源的函数matching见图7. 用3个栈存放三序列对齐后的结果,将每一次参与匹配的序列元素存入三序列对应的栈中,最后将栈顶元素依次出栈即可得到最佳比对方式.
确保三序列比对算法Apla程序的正确性后,加上文件输入、输出语句,以“#”表示空位,使用PAR平台中的程序生成系统,可以由抽象Apla程序生成Java,C++,Python等可执行程序. 这里仅给出C++程序的一个实例运行结果,如图8所示. 其中,输入序列来源于Genbank数据库中3段关于光敏色素B的植物DNA序列.
根据实际应用情况,这里对序列比对高可靠算法的通用构造过程总结如下:
1)分析特定输入序列数k(k≥2)的序列比对问题,根据独有特征简化通用规约和递推关系,继而将k代入到本文提出序列比对算法统一构造框架seqAlign中得到Radl算法.
2)根据Radl算法开发出特定序列比对算法的循环不变式,并基于此生成Apla抽象程序.
3)使用Isabelle语言,将验证Apla程序正确性需满足的条件描述成定理,然后使用Isabelle定理证明器加以验证.
4)在PAR平台的代码生成系统支撑下,可由形式验证后的Apla程序自动生成得到对应的高级语言程序,从而得到一个高可靠的序列比对算法程序.
比对序列条数大于等于4的情况与三序列比对问题本质上是一致的,而与双序列比对问题有略微差别. 区别在于双序列比对的序列数为2,计算单次匹配的分值不需要序列之间两两匹配的分值相加,只需要计算1次即可. 此时,不再需要sglScore,只需留下rule规则. 针对双序列比对算法的特性,将规约作如下简化:
Specification: pairSequenceAlignment
|[ in: m, n:integer;seq1, seq2:BioSeq(enum);out: ms:integer ]|
AQ: given seq1[0:m−1], seq2[0:n−1], m>1, n>1;
AR: $ maxScore(seq_1,seq_2,m,n)=(\mathrm{M}\mathrm{A}\mathrm{X}\;cs:cs=$ $align(seq_1,seq_2,m,n): (\mathrm{\Sigma }sgl:sgl\in cs:rule(sgl))) $.
其中rule的定义如下:
通过性质1和性质2,可以得出对齐进度(i, j)可能有3种来源,即(i-1,j),(i,j-1),(i-1,j-1). 据此,可以得到递推关系:
$ \begin{split}&maxScore\left(seq_1,seq_2,i,j\right)=\\&{\mathrm{max}}\left\{\begin{aligned}&maxScore\left(seq_1,seq_2,i-1,j\right)+\\ &\quad rule\left(seq_1\left[i-1\right]{,}\#\right),\\ &maxScore\left(seq_1,seq_2,i,j-1\right)+\\ &\quad rule\left(\#,seq_2\left[j-1\right]\right),\\&maxScore\left(seq_1,seq_2,i-1,j-1\right)+\\ &\quad rule\left(seq_1\left[i-1\right],seq_2\left[j-1\right]\right). \end{aligned}\right.\end{split} $
进一步得到Radl算法:
算法3. pairSeqAlign.
|[var i, j:integer; score:array(0..m,array(0..n, integer)); seq1, seq2:BioSeq();]|
{AQ$\wedge $AR}
$ \mathrm{b}\mathrm{e}\mathrm{g}\mathrm{i}\mathrm{n}:i=0++1\wedge j=0++1 $;
$ \mathrm{t}\mathrm{e}\mathrm{r}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}:i=m\wedge j=n $;
recur: 式(3);
end
以及循环不变式:
由得到的递推关系和Radl算法以及循环不变式,可推导出Apla抽象算法程序. 进一步通过Isabelle定理证明器验证,继而使用PAR平台的程序生成系统即可生成一个高可靠的双序列比对算法,与NW算法思想一致,代码细节略有不同.
本文针对生物序列比对问题,开展了形式化方法PAR制导的问题类通用求解框架研究. 从生物序列比对问题出发,抽象出通用的Radl形式化规约,逐步精化得到统一的序列比对DP算法的构造框架seqAlign. 将输入序列数代入seqAlign框架中,生成了特定的序列比对动态规划算法,极大提高了算法设计效率,经Isabelle定理证明器的验证以及PAR平台C++可执行代码的生成,有效保证了所生成算法的正确性,表明了seqAlign统一求解框架的有效性和实用性.
本文的主要贡献有3个方面:
1)形式化推导了一个统一的序列比对问题求解框架seqAlign,解决了一类生物序列比对问题. 从高抽象的问题通用规约出发,经严格的形式变换得到了一般化的求解递推关系. 对于特定的序列比对问题,只需将比对序列数代入到通用求解框架中,稍作改变即可得到具体的算法程序,在重用统一求解框架的同时,也实现了对算法设计过程的重用,显著提高了算法开发效率和可信性.
2)提供了一个形式化构建复杂生物信息学领域典型算法的成功样例. 在生物信息学序列分析领域,许多问题具有相似性,本文的研究方法可扩展到生物信息学领域其他算法的形式构造研究中.
3)基于 PAR方法的通用序列比对问题求解框架的构造,降低了一类复杂问题的验证代价,促进了形式化验证在相关领域的实施. 在展示了一类序列比对问题令人惊叹的解题思想之外,形式化推导的过程也描绘出得到这种精美思路的清晰逻辑.
本文算法构造的过程借助了PAR平台C++程序生成系统和Isabelle工具辅助验证,将尽可能多的创造性劳动转化为非创造性劳动,让原本困难的算法设计过程变为按部就班的工作. 接下来将进一步研究递推关系和循环不变式的自动生成方法,高效衔接算法形式构造与形式验证2部分工作,将更多算法形式构造中的创造性工作转化为机械性工作,以期不断提升自动化水平.
作者贡献声明:石海鹤设计研究方法、实验设计,并进行论文修改;蓝孙文完成实验部分并撰写论文;刘日明协助数据采集、处理和分析;石海鹏把握论文的总体创新性,验证理论分析和实验分析的正确性;王岚和钟林辉检验算法的性能,提出指导意见,并参与论文修改.

参考文献 引证文献
排序方式:
1
詹乃军,王戟. 复杂系统规约、分析与验证发展现状与展望[J]. 前瞻科技,2023,2(1):7−22
Zhan Naijun, Wang Ji. Challenges and trends for specification, analysis, and verification of complex systems[J]. Science and Technology Foresight, 2023, 2(1): 7−22 (in Chinese)
2
Hoare T. The verifying compiler: A grand challenge for computing research[J]. Journal of the ACM, 2003, 50(1): 63−69
3
王勇献. 生物信息学导论:面向高性能计算的算法与应用[M]. 北京:清华大学出版社,2011
Wang Yongxian. Introduction to Bioinformatics: Algorithms and Applications for High Performance Computing [M]. Beijing: Tsinghua University Press, 2011 (in Chinese)
4
Needleman S B, Wunsch C D. A general method applicable to the search for similarities in the amino acid sequence of two proteins[J]. Journal of Molecular Biology, 1970, 48(3): 443−453
5
Smith T F, Waterman M S. Identification of common molecular subsequences.[J]. Journal of Molecular Biology, 1981, 147(1): 195−197
6
Garai G, Chowdhury B. A cascaded pairwise biomolecular sequence alignment technique using evolutionary algorithm[J]. Information Sciences, 2015, 297(3): 118−139
7
Alawneh L, Shehab M A, Al-Ayyoub M, et al. A scalable multiple pairwise protein sequence alignment acceleration using hybrid CPU–GPU approach[J]. Cluster Computing, 2020, 23(7): 2677−2688
8
Rashed A E E D, Obaya M, El H, et al. Accelerating DNA pairwise sequence alignment using FPGA and a customized convolutional neural network[J]. Computers & Electrical Engineering, 2021, 92(6): 1−21
9
Song Y J, Ji D J, Seo H, et al. Pairwise heuristic sequence alignment algorithm based on deep reinforcement learning[J]. IEEE Open Journal of Engineering in Medicine and Biology, 2021, 2: 36−43
10
Clustal W, Thompson J D, Higgins D G, et al. Improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice[J]. Nucleic Acids Research, 1994, 22(22): 4673−4680
11
Katoh K, Misawa K, Kuma K, et al. MAFFT: A novel method for rapid multiple sequence alignment based on fast Fourier transform[J]. Nucleic Acids Research, 2002, 30(14): 3059−3066
12
Edgar R C. MUSCLE: Multiple sequence alignment with high accuracy and high throughput[J]. Nucleic Acids Research, 2004, 32(5): 1792−1797
13
Abuín J M, Pena T F, Pichel J C. PASTASpark: Multiple sequence alignment meets big data[J]. Bioinformatics, 2017, 33(18): 2948−2950
14
Wan Shixiang, Zou Quan. HAlign-II: Efficient ultra-large multiple sequence alignment and phylogenetic tree reconstruction with distributed and parallel computing[J]. Algorithms for Molecular Biology, 2017, 12(1): 1−10
15
Smirnov V, Warnow T. MAGUS: Multiple sequence alignment using graph clustering[J]. Bioinformatics, 2021, 37(12): 1666−1672
16
Mirarab S, Nguyen N, Guo Sheng, et al. PASTA: Ultra-large multiple sequence alignment for nucleotide and amino-acid sequences.[J]. Journal of Computational Biology: A Journal of Computational Molecular Cell Biology, 2015, 22(5): 377−386
17
王戟,詹乃军,冯新宇,等. 形式化方法概貌[J]. 软件学报,2019,30(1):33−61
Wang Ji, Zhan Naijun, Feng Xinyu, et al. Overview formalization method[J]. Journal of Software, 2019, 30(1): 33−61 (in Chinese)
18
Xue Jinyun. A unified approach for developing efficient algorithmic programs[J]. Journal of computer Science and Technology, 1997, 12(4): 314−329
19
Durán J E. Transformational derivation of greedy network algorithms from descriptive specifications[C]// Proc of the 6th Int Conf on Mathematics of Program Construction. Beilin: Springer, 2002: 40−67
20
Abrial J R, Cansell D, Méry D. Formal derivation of spanning trees algorithms[C]// Proc of the 3rd Int Conf of B and Z Users. Berlin: Springer, 2003: 457−476
21
Almeida J B, Pinto J S. Deriving sorting algorithms[J]. arXiv preprint, arXiv: 0802.3881, 2008
22
Nedunuri S, Cook W R. Synthesis of fast programs for maximum segment sum problems[J]. ACM SIGPLAN Notices, 2009, 45(2): 117−126
23
Mu S C. Calculating a backtracking algorithm: An exercise in monadic program derivation[J]. arXiv preprint, arXiv: 2101.09409, 2021
24
Lammich P. Generating verified LLVM from Isabelle/HOL[C]// Proc of the 10th Int Conf on Interactive Theorem Proving (ITP 2019). Berlin: Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2019, 22: 1−22: 19
25
张健,李弋,彭鑫,等. 正反例归纳合成SQL查询程序[J]. 软件学报,2023,34(9):4132−4152
Zhang Jian, Li Yi, Peng Xin, et al. Inductive SQL synthesis with positive and negative tuples[J]. Journal of Software, 2023, 34(9): 4132−4152 (in Chinese)
26
石海鹤,薛锦云. 基于PAR的算法形式化开发[J]. 计算机学报,2009,32(5):982−991
Shi Haihe, Xue Jinyun. PAR-based formal development of algorithms[J]. Chinese Journal of Computers, 2009, 32(5): 982−991 (in Chinese)
27
孙凌宇,薛锦云. 最小生成树算法的PAR方法形式化推导[J]. 计算机工程,2006,32(21):85−87
Sun Lingyu, Xue Jinyun. Formal derivation of the minimum spanning tree algorithm with PAR method[J]. Computer Engineering, 2006, 32(21): 85−87 (in Chinese)
28
游珍,薛锦云. 基于Isabelle定理证明器算法程序的形式化验证[J]. 计算机工程与科学,2009,31(10):85−89
You Zhen, Xue Jinyun. Formal verification of algorithmic programs based on the Isabelle theorem prover[J]. Computer Engineering and Science, 2009, 31(10): 85−89 (in Chinese)
29
石海鹤,周卫星. 基于动态规划的双序列比对算法构件设计与实现[J]. 计算机研究与发展,2019,56(9):1907−1917
Shi Haihe, Zhou Weixing. Design and implementation of pairwise sequence alignment algorithm components based on dynamic programming[J]. Journal of Computer Research and Development, 2019, 56(9): 1907−1917 (in Chinese)
30
Shi Haipeng, Chen Huan, Yang Qinghong, et al. A method for bio-sequence analysis algorithm development based on the PAR platform[J]. Big Data Mining and Analytics, 2023, 6(1): 11−20
31
肖存威,石海鹤,王岚,等. 基于混合策略的de novo序列拼接算法构造[J]. 江西师范大学学报:自然科学版,2022,46(3):300−307
Xiao Cunwei, Shi Haihe, Wang Lan, et al. The construction of de novo sequence assembly algorithm based on hybrid strategy[J]. Journal of Jiangxi Normal University: Natural Science, 2022, 46(3): 300−307 (in Chinese)
32
Dijkstra E W. A Discipline of Programming[M]. Princeton, NJ: Prentice-hall, 1976
33
Floyd R W. Assigning meaning to programs[J]. Communications of the ACM, 1967, 10(8): 365−371
34
Hoare C A R. An axiomatic basis for computer programming[J]. Communications of the ACM, 1969, 12(10): 576−580
35
Dijkstra E W, Scholten C S. Predicate Calculus and Program Semantics[M]. Berlin: Springer, 2012
36
石海鹤. 支持泛型程序设计的Apla-Java自动程序转换系统[D]. 南昌:江西师范大学,2004
Shi Haihe. Apla-Java automatic program transformation system supporting generic programming [D]. Nanchang: Jiangxi Normal University, 2004 (in Chinese)
37
赖勇. APLA到C++自动程序转换系统的研制[D]. 南昌:江西师范大学,2002
Lai Yong. Development of APLA to C++ automatic program conversion system [D]. Nanchang: Jiangxi Normal University, 2002 (in Chinese)
38
Xue Jinyun. Two new strategies for developing loop invariants and their applications[J]. Journal of Computer Science and Technology, 1993, 8(2): 147−154
2025年第62卷第1期
135
62
0
引用本文
BibTeX
文章信息
doi: 10.7544/issn1000-1239.202330698
  • 接收时间:2023-08-23
  • 首发时间:2026-11-10
  • 出版时间:2025-01-01
补充材料
相关文章
文章信息
作者
出版历史
  • 收稿日期:2023-08-23
  • 修回日期:2024-01-22
基金
作者信息
    1江西师范大学计算机信息工程学院 南昌 330022
    2江西师范大学软件学院 南昌 330022

通讯作者:

参考文献
分享链接
https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/10.7544/issn1000-1239.202330698
分享至
全文二维码

扫描看全文

引用本文
BibTeX
本文的引用情况
2种不同金属材料的力学参数
科
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
关闭全屏