启发式序列比对算法种子长度及其灵敏度研究.pdfVIP

第23卷　 第2期 计算机技术与发展 Vol.23　 No.2 2013年2月 　 　 　 　 　 　 　 　 　 　 COMPUTERTECHNOLOGYANDDEVELOPMENT　 　 　 　 　 　 　 　 　 　 Feb.　 2013 启发式序列比对算法种子长度及其灵敏度研究 丁茂华,徐永安,邵　 明,李　 谦 (扬州大学信息工程学院,江苏扬州225009) 摘　 要:序列比对是生物信息学中一个重要的研究方向,它可以确定两个或多个序列之间的相似性,进而判断其同源性并 推测出序列间的进化关系。 目前,启发式序列比对算法BLAST算法在实际问题用着重要应用。 该算法中有一个参数叫做 种子(Seeds),种子是控制比对速度和灵敏度的关键。 但是种子的长度是基于经验而取的一个固定值,这个经验值并不适 合于所有长度序列比对问题。 因此,对于两条不用长度的序列之间实现启发式比对就需要取合理长度的种子,以便实现 高效快速的比对。 文中应用概率随机的思想对不同长度序列比对的种子的长度进行了分析,在此基础上对一定长度下种 子的比对灵敏度做出了计算。 通过理论推导和实验分析一定灵敏度下种子长度的计算结果是可行且有效的。 这就给在 高灵敏度(灵敏度几乎等于动态规划算法)下实现快速启发式序列比对的优化提供了保证。 关键词:启发式比对算法;种子长度;灵敏度 中图分类号:TP391　 　 　 　 　 　 文献标识码:A　 　 　 　 　 　 　 文章编号:1673-629X(2013)02-0097-04 doi:10.3969/j.issn.1673-629X.2013.02.024 StudyonSeed’sLengthandSensitivityofHeuristic SequenceAlignmentAlgorithm DINGMao-hua,XUYong-an,SHAOMing,LIQian (CollegeofInformationEngineering,YangzhouUniversity,Yangzhou225009,China) Abstract:equencealignmentisanimportantdirectioninbioinformatics,whichistodeterminethesimilarityfortwoormoresequences andthusdeterminesthehomologyandevolutionaryrelationshipbetweenthededucedsequence.Atpresent,theheuristicsequencealign- mentalgorithmhasimportantapplicationsinthepracticalproblems.Thisalgorithmhasaparametercalledseeds,whichistocontrolthe speedandsensitivityofthealgorithm.Butthelengthoftheseedisbasedontheexperienceandtakesafixedvalue.Obviously,thisvalue isnotsuitablefortheactualproblemofalllengthsequence.Itstudiesthelengthoftheseedbytheprobabilitytheory,and,onthisbasis, studiesthesensitivityofthealgorithm.Theheuristicsequencealignmentalgorithmcanbeusednearlyasthesamesensitivityofdynamic programmingalgorithmintheoreticalanalysisandexperimentalanalysis.Inthispaper,theprobab