基于A^＊算法的启发式算法求解多序列比对问题

A * -based heuristic algorithm for multiple sequence alignment problem

通过分析动态规划算法及A 算法的特点 ,针对多序列比对问题提出一种基于A 算法的启发式算法 .该算法采用了多个优化搜索机制 .通过对此算法的理论分析 ,证明了它能够在有效地减小搜索的空间、节约搜索的时间的同时 ,保证得到比较好的比对结果 .此算法不仅能够在多序列比对问题中得到应用 。

By analyzing Dynamic Programming and A * algorithms, a new heuristic algorithm was given to solve multiple sequence alignment problem. This algorithm derived from A * algorithm and several methods were applied to optimize the searching progress. It was proved that this algorithm could be effective in saving the searching space and computing time and gaining the results quite well. This algorithm can be used not only in multiple sequence alignment problem but also in shortest path problem in Directed Acylic Graph.