论文部分内容阅读
生物信息学是利用现代计算技术来处理和研究生物数据的一门新型交叉学科。其中,序列比对是生物信息学最基本的一个研究方法。如何获得比对质量更好、时间空间效率更高的序列比对算法是生物信息学研究的一个重要的课题。生物序列比对算法在生物信息学中占有重要的地位。 论文首先叙述了序列比对算法领域从70年代到现在的发展过程,讨论了Needleman和Wunsch最早提出的生物序列比对算法——全局比对动态规划算法,同时,分析了目前双序列比对算法及其启发式算法存在的问题。接着论文提出了一种新的基于高分片段对HSP的同源性搜索启发式算法Segment Pair Alignment(SPA),在加快比对速度的同时,又能发现序列之间微弱的相似关系,大大提高了序列数据库相似性搜索的敏感性,并且能返回比对的具有统计学显著性的评分。 多序列比对是一个NP-Complete问题。当序列数量增加时,对计算的挑战就令人生畏。在实际操作中,算法都会在计算速度和获得最佳比对之间寻求平衡。论文介绍了多序列比对算法的发展现状,分析了各个算法的优缺点;着重介绍了基于SGA的多序列比对算法,总结了该算法存在的问题。最后,提出了一种新型的多序列比对算法(GA—DP),在该算法中综合了片段对思想和动态规划思想,并且,能在合理的时间内找到多序列比对问题的近优解,大大改善了多序列比对的质量。